[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
(for the "LaTeX for Logicians" page) 

More information about the FOM mailing list