Rough sketch of Goedels Theorems
Hallo friends,
I have tried to sketch Goedels incompleteness theorems and showing their main ideas to not get lost in all the formalities. Maybe someone with deeper knowledge of Goedel can check and help or we can discuss certain aspects. Here we go:
First Incompleteness Theorem
We assume a consistent formal S(ystem) where we can formulate the following function (statement): G (G is unprovable in S). Now there are two possible cases:
a) G is provable in S, but then G says it's unprovable, contradiction,
b) ~G is provable in S, but ~G says that G is provable, which would mean both, G and ~G, are provable, contradiction.
Neither G nor ~G are provable in S. S is incomplete.
p.s. Goedel's real accomplishment was to formulate the function G in a system that just contains propositional and predicate logic and the natural numbers with addition.
Second Incompleteness Theorem
Let S be consistent (assumption). Because of the first incompleteness theorem it follows that if S is consistent, then G is unprovable. From this it follows by mp (and is thus proved) that G in S is unprovable. But this is precisely the content of G (see above, the italic style marked one), so that G in S would be proved, which is impossible according to the first incompleteness theorem (there case 1a), so that the consistency assumption must be false.
I have tried to sketch Goedels incompleteness theorems and showing their main ideas to not get lost in all the formalities. Maybe someone with deeper knowledge of Goedel can check and help or we can discuss certain aspects. Here we go:
First Incompleteness Theorem
We assume a consistent formal S(ystem) where we can formulate the following function (statement): G (G is unprovable in S). Now there are two possible cases:
a) G is provable in S, but then G says it's unprovable, contradiction,
b) ~G is provable in S, but ~G says that G is provable, which would mean both, G and ~G, are provable, contradiction.
Neither G nor ~G are provable in S. S is incomplete.
p.s. Goedel's real accomplishment was to formulate the function G in a system that just contains propositional and predicate logic and the natural numbers with addition.
Second Incompleteness Theorem
Let S be consistent (assumption). Because of the first incompleteness theorem it follows that if S is consistent, then G is unprovable. From this it follows by mp (and is thus proved) that G in S is unprovable. But this is precisely the content of G (see above, the italic style marked one), so that G in S would be proved, which is impossible according to the first incompleteness theorem (there case 1a), so that the consistency assumption must be false.
Comments (17)
The natural with addition and multiplication. The theory of the natural numbers with addition (also known as presburger arithmetic) is actually complete.
Quoting Pippen
Bold emphasis mine.
The question is: proved where? Your argument proceeds entirely in the metalanguage, so it doesn't suffice to generate the contradiction, because we known (outside S) that G is not provable. What you require is a proof inside S that the consistent statement Con(S) is equivalent to G, whence it follows that Con(S) is also not provable.
I already did it, in my last post. What part did you find troubling?
I think my beginning is fine, the 2nd theorem starts with: Let's assume S to be consistent. But then how would you continue if you had to explain the proof in simple words to someone else?
First Incompleteness Theorem
We assume a consistent formal S(ystem) where we can formulate the following function: G (G is unprovable in S). Now there are two possible cases:
a) G is provable in S, but then G says it's unprovable, contradiction,
b) ~G is provable in S, but ~G says that G is provable, which would mean both, G and ~G, are provable, contradiction.
Neither G nor ~G are provable in S. S is incomplete.
p.s. Goedel's real accomplishment was to formulate the function G in a system that just contains propositional and predicate logic and the natural numbers with addition and multiplication.
.Second Incompleteness Theorem
Because of the First Incompleteness Theorem we know that if S is consistent then G is unprovable in S. Since "G is unprovable in S" is our function G (see above) we can shortcut: If S is consistent then G. Now, we just formulate this statement in S and we know it's provable in S. Now, we assume we could also prove in S that S is consistent. Then by mp G would follow (and thus be proven) in S which is impossible due to the First Incompleteness Theorem. Because of this contradiction our assumption must have been false.
I think Godel's incompleteness theorem is:
1) If a system is complete (as in every possible truth can be proved) then it's necessarily inconsistent (contradictions arise)
2) If a system is consistent (as in there are no contradictions) then it is neccesarily incomplete (some truths can't be proved)
You've shown that, given a complete system S, a proposition such as G: G is unprovable in S, will generate contradictions. Thus, the system S is necessarily incomplete.
Now assume the system S to be consistent. Taking G:G is unprovable, by the initial assumption, we shouldn't generate contradictions. But, G is designed such that we do. So, we conclude S is inconsistent.
Am I getting this right? If you reply, please keep it simple. Thanks.
No, that's not exactly right. The first theorem states that, if T is a theory strong enough to capture all the primitive recursive functions, then, if T is consistent, then T is incomplete. The italicized condition is necessary, since we have examples of arithmetical theories which do not satisfy it and are complete (for instance, the theory of addition or the theory of multiplication in the natural numbers). Going a bit deeper, the reason for this requirement is that the first theorem works because we can construct a predicate inside the theory which captures the provability relation, i.e. the relation prf(x, y) which holds between x and y iff x is a proof of y. This relation, in turn, is primitive recursive, so we need to capture at least as much as the primitive recursive functions in order to prove the first theorem.
The second theorem says that, if T is consistent, strong enough to capture all the primitive recursive functions and some other conditions, then T cannot prove its own consistency. Roughly, the proof of the second theorem works as follows: we start by noting that an inconsistent theory (trivially) proves everything. Hence, by contraposition, if a theory cannot prove everything, then it is consistent (which is desirable: we don't want a theory which proves contradictions!). But this implies that, if the Gödel sentence is true, then the theory is consistent, since the Gödel sentence states that there is a statement which the theory does not prove. More importantly, by showing that the prf(x, y) predicate above satisfies certain conditions, we can actually prove that T proves that G -> Con(T), where Con(T) is a statement which encodes the consistency of the theory (say, it is the statement that T does not prove that 0=1). Using some other conditions (known as the derivability conditions), we can also formalize the first incompleteness theorem inside T, that is, T proves that Con(T) -> G. So we have that T proves that G <-> Con(T). Since G is unprovable, it follows that Con(T) is unprovable.
It is essential that the reasoning above is formalizable in the language of the theory and that T has the necessary resources to prove the various claims being made. That is because consistency is a syntactic property: it says that T does not prove a contradiction. Thus, in order to prove claims about a theories consistency, we have to show that it proves or does not prove something. In other words, we need to actually produce arguments as to why certain proofs are or are not possible starting from T's axioms. That's why it is not sufficient to give mere semantic arguments outside of T: consistency is a stronger property than soundness.
Notice that this does not say that complete theories are inconsistent, since there may be complete theories which do not satisfy the conditions of Gödel's theorems. In fact, that is precisely the case: again, the theory of addition in the natural numbers is complete. Also, note that "complete" does not mean that every truth is provable: it means that every true sentence in the language of the theory is provable.
Bold emphasis mine.
The bold part is the difficult (or, at least, tedious) part. As I mentioned, we need to show that T proves that Con(T) -> G, which is basically formalizing the first theorem inside T. That's not a "shortcut", since it takes pages and pages of theorems (Gödel himself declined to produce a full proof of it, in part because it was so tedious; the first complete proof was written by Bernays and published in Hilbert & Bernays's Grundlagen)!
Yes, so long as you distinguish syntax and semantics:
Quoting Wikipedia
Technically, to say "This statement is unprovable". But what is remarkable is that the fanciness consists in showing (i) isolating a class of interesting functions (the recursive functions, which would pave the way for the computers you and I are using to communicate), (ii) showing that this class is capturable using simple arithmetic operations, and (iii) showing that truth is not so capturable. That is, Gödel's theorems can be summed up quickly as: (i) the set of theorems is recursively enumerable (i.e. there is an algorithm which tells us whether a given sentence is a theorem) and (ii) by Tarski's theorem, the set of truths is not even arithmetic, let alone recursively enumerable. Thus, the set of truths is not the same as the the set of theorems.
Second Incompleteness Theorem
Because of the First Incompleteness Theorem we know that if S is consistent then G is unprovable in S. Since "G is unprovable in S" is our function G (see above) we can re-formulate that statement as: If S is consistent then G. Now, we "just" formulate this statement in S and we know it's provable in S. Now, we assume we could also prove in S that S is consistent. Then by mp G would follow (and thus be proven) in S which is impossible due to the First Incompleteness Theorem. Because of this contradiction our assumption must have been false.
It's very rough, but yes, that's the gist of it. Incidentally, this is a very good bare-bones summary of both theorems.