[FOM] Credit where credit is due (a cute trick in BBJ)
Peter Smith
ps218 at cam.ac.uk
Mon Nov 7 09:40:46 EST 2005
Boolos, Burgess and Jeffrey (p. 206) use a cute trick to show that Q can
capture all the Sigma_1 functions. They show (the cute bit) that any
Sigma_1 function can be defined as the composition of two Delta_0
functions, and then (the easy bit) that given Q can capture the Delta_0
functions it can capture compositions of Delta_0 functions too.
This might be a terrible confession of ignorance/advancing years killing
off memory but I couldn't recall having noted the cute trick before in my
not-very-systematic reading around this stuff. So should the trick be
credited to BBJ? Or is it folk lore? Or in something I've (hopefully!) read
and forgotten?? A quick trawl hasn't turned up anything ...
--
Dr Peter Smith: Faculty of Philosophy, University of Cambridge
www.logicbook.net | www.godelbook.net
--
http://www.phil.cam.ac.uk/teaching_staff/Smith/LaTeX/
(for the "LaTeX for Logicians" page)
More information about the FOM
mailing list