One of the corollaries that easily follow from Gödel’s first incompleteness theorem for arithmetic is the incompleteness of second-order logic: there can be no proof system that generates all and only the validities of second-order logic. It follows from the incompleteness of arithmetic because for any sentences φ of first-order arithmetic, there is a sentence of second-order logic φ′ which is valid iff φ is true in the standard model. So if second-order logic was recursively enumerable (r.e.) then true arithmetic (the sentences true in the standard model) would be r.e. Now you may ask (and students regularly do ask): but what if Gödel’s theorem had been false? What if arithmetic were complete? Would second-order logic then be complete, too? This question is usually not answered in the usual textbooks (at least I wasn’t able to find it covered in the ones I looked). Now a conditional with a necessarily false antecedent is true, so “if arithmetic were complete, second-order logic would still be incomplete” is trivially true. But there’s of course a way to give a non-trivial answer: There is no Turing machine that churns out all the valid sentences of second-order logic, even if that machine has access to an oracle which answers “yes” or “no” according to whether any given sentence of arithmetic is true in the standard model. (The function of such an oracle, of course, cannot itself be performed by a Turing machine, since the set of Gödel numbers of true arithmetic sentences is undecidable, and not even r.e.) That this is so is most easily seen by thinking of computability in terms of definability.
A set V of numbers is Σ01-definable if there is a Σ01 formula ψ(x) of arithmetic (one existential quantifier, then only bounded quantifiers) with a free variable x so that ψ(n) is true in the standard model iff n ∈ V. V is r.e. iff it is Σ01-definable. (In one direction: ψ(x) says “there is a number k which codes a computation of a Turing machine started on input l ≤ k and with output n.”) If W is a set of numbers, we say that V is Σ01(W)-definable if there is a formula ψ(x, Y) with a second-order variable Y so that n ∈ V iff ψ(n, Y) is true in the standard model when Y is interpreted as the set W. V is enumerable by a Turing machine with access to an oracle for W iff it is Σ01(W)-definable.
If we let TA be the set of Gödel numbers of the true sentences of arithmetic and Val2 the set of Gödel numbers of valid sentences of second-order logic, our question:
Is Val2 enumerable by a Turing machine with an oracle for TA?
can be restated as:
Is Val2 Σ01(TA)-definable?
It isn’t: the class {TA} is definable in arithmetic, that is, there is an arithmetical formula σ(Y) with a free second-order variable Y so that σ(Y) is true iff Y = TA (see Theorem 23.2 in Boolos, Burgess, Jeffrey, Computability and Logic, 4th ed.). So if Val2 were Σ01(TA)-definable by some formula ψ(n, Y), it would then also be definable in second-order arithmetic by the formula ∃ Y(σ(Y) ∧ ψ(n, Y)). And if Val2 were definable in second-order arithmetic, then TA2, the set of Gödel numbers of true sentences of second-order arithmetic would be definable in second-order arithmetic, since the Gödel number of a sentence α of second-order arithmetical sentence is in TA2 iff the Gödel number of PII → α is in Val2 (where PII is the conjunction of the the second-order Peano axioms, as in Example 22.6 of BBJ). But by Tarski’s Theorem, TA2 is not definable in second-order arithmetic (see Theorem 41C of Enderton’s A Mathematical Introduction to Logic).
Leave a Reply to Richard Zach Cancel reply