Tuesday, April 15, 2008

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 that just because a property is Sigma_1 expressible it doesn't follow that its characteristic function is Sigma_1 expressible. But it takes a moment to see this, and I should have explained.

No comments: