Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I (think) that I once heard it said that from Tarski's Theorem on the undecidability of truth, Gödel's Second Incompleteness Theorem follows. Is this right?

share|improve this question
add comment

1 Answer

Tarski's theorem is on the unDEFINability of truth, but yes, Goedel's results follow (and in some sense are the same thing): provability (in some particular system of interest) is definable, therefore truth cannot match provability, therefore (supposing the system of interest is consistent, and therefore sound for the relevant sentences) there is a sentence which is true but not provable. This is the first completeness theorem.

What would it mean for a predicate T to actually define truth? Just that T(s) and s are equivalent for each sentence s. Thus, Tarski's undefinability theorem tells us more specifically that, for any definable T, there is some sentence G such that T(G) and G are equivalent to each other's negation. The above is just what happens when we take T to define provability; we thus see more specifically that incompleteness arises from a sentence G equivalent to the negation of its provability, which is therefore (supposing the system of interest is consistent) true but not provable.

One can then argue, in the usual way, that our proof of the first incompleteness theorem, suitably internalized in the system of interest, yields the second incompleteness theorem. [Our argument shows that the consistency of the system of interest entails the non-provability of G. But this conclusion is just what it means for G to be true! Thus, if the system of interest proves its own consistency, it proves G, contra its own consistency.]

share|improve this answer
    
But all that really shows is that some of the ideas used in Tarski's result are also used in a proof of the 2nd incompleteness theorem, which is a pretty modest claim. The question, I take it, is rather whether given the truth of Tarski's theorem, the truth of the 2nd incompleteness theorem follows by some clever argument or other. –  provocateur Nov 17 '12 at 16:49
    
I've modified the word of the second paragraph to alleviate this concern. The second incompleteness theorem follows from the simultaneous "external" and "internal" truth of Tarski's theorem (by which I mean, the fact that Tarski's theorem is both true and provable (or, just as well, true inside every model)). –  Sridhar Ramesh Nov 17 '12 at 18:54
    
Well, one caveat: One needs that Tarski's result is constructive enough that we have not just "For every T, for every model, there is a G such that...", but in fact "For every T, there is a G such that for every model...". But, basically, were Tarski's result phrased as strongly as its proof actually warranted, it would give us everything. –  Sridhar Ramesh Nov 17 '12 at 19:23
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.