Logic Matters 2008-04-15

Sigma_1 functions and properties

Rob Trueman, one of our undergraduates, came up with a nice question today which left me kicking myself that I'd not footnoted the point/forestalled the question in my Gödel book.In Ch. 13, I'd proved that any function that is expressible by a Sigma_1 expression of arithmetic can be represented in e.g. PA, again by a Sigma_1 wff. (Or as I prefer to say, it can be "CAPtured", as that is memnonic for CAse-by-case Proved).In Ch. 21, I'd also proved that, while the property of Gödel-numbering a PA-theorem is expressible by a Sigma_1 expression of arithmetic, it can't be represented in PA (whether by a Sigma_1 wff or anything else).How come, asked Rob, is there that stark lack of parallelism, given that we can move to-and-fro from property talk to function talk by the characteristic function trick?The answer, of course(?!), is ...

read more   

more posts from Logic Matters