I don’t understand Gödel’s incompleteness theorem anymore

Here’s the picture I have in my head of Model Theory:

  • a theory is an axiomatic system, so it allows proving some statements that apply to all models consistent with the theory
  • a model is a particular — consistent! — function that assigns every statement to its truth value, it is to be thought of as a “concrete” object, the kind of thing we actually usually think about. It’s only when it comes to models that we have the law of the excluded middle.

My understanding of Gödel’s first incompleteness theorem is that no theory that satisfies some finiteness condition can uniquely pin down a model.

So I am not really surprised by it. The idea of theories being incomplete — of not completely pinning down a particular model — is quite normal. The fact that no theory is complete seems analogous to how no Turing machine can compute every function.

But then I read this thread and there were two claims there in the answers which made no sense to me:

  1. Self-referential statements as examples of unprovable statements — Like “there is no number whose ASCII representation proves this statement“.

A statement like this cannot be constructed in propositional logic. I’m guessing this has to do with the concept of a “language”, but why would anyone use a language that permits self-reference?

Wouldn’t that be completely defeat the purpose of using classical logic as the system for syntactic implications?

If we permit this as a valid sentence, wouldn’t we also have to permit the liar paradox (and then the system would be inconsistent)?

  1. Unprovable statements being “intuitively true/false” — According to this answer, if we found that the Goldbach conjecture was unprovable, then in particular that means we cannot produce a counter-example, so we’d “intuitively” know that the conjecture is true.

How is this only intuitive? If there exist \sf PA-compatible models M_1, M_2 where Goldbach is true in M_1 but not M_2, then \exists n, p, q such that n= p+q in M_1 but not in M_2. But whether n=p+q is decidable from \sf PA, so either “\sf{PA}+\sf{Goldbach}” or “\sf{PA}+\lnot\sf{Goldbach}” must be inconsistent, and Goldbach cannot be unprovable. Right?

In any case, I don’t know what it means for the extension to be “intuitively correct”. Do we know something about the consistency of each extension or do we not?

Further adding to my confusion, the answer claims that the irrationality of e+\pi is not such a statement, that it can truly be unprovable. I don’t see how this can be — surely the same argument applies; if e+\pi‘s rationality is unprovable, there does not exist p/q that it equals, thus it is irrational. Right?

Answer

This answer only addresses the second part of your question, but you asked many questions so hopefully it’s okay.

First, there is in the comments a statement: “If Goldbach is unprovable in PA then it is necessarily true in all models.” This is incorrect. If Goldbach were true in all models of PA then PA would prove Goldbach by Godel’s Completeness Theorem (less popular, still important).

What is true is:

Lemma 1: Any \Sigma_1 statement true in \mathbb{N} (the “standard model” of PA) is provable from PA.

These notes (see Lemma 3) have some explanation: http://journalpsyche.org/files/0xaa23.pdf

So the correct statement is:

Corollary 2: If PA does not decide Goldbach’s conjecture then it is true in \mathbb{N}.

Proof: The negation of Goldbach’s conjecture is \Sigma_1. So if PA does not prove the negation, then the negation of Goldbach is not true in \mathbb{N} by Lemma 1.

Remember that \mathbb{N} is a model so any statement is either true or false in it (in our logic). But PA is an incomplete theory (assuming it’s consistent), so we don’t get the same dichotomy for things it can prove.

Now, it could be the case that PA does prove Goldbach (so its true in all models of PA including \mathbb{N}). But if we are in the situation of Corollary 2 (PA does not prove Goldbach or its negation) then Goldbach is true in \mathbb{N} but false in some other model of PA. (This would be good enough for the number theorists I imagine.) This is also where the problem in your reasoning is. It is NOT true that if Goldbach fails in some model M of PA then there is a standard n in \mathbb{N} that is not the sum of two primes. Rather the witness to the failure of Goldbach is just some element that M believes is a natural number. In some random model, this element need not be in the successor chain of 0.

On the other hand, the rationality of \pi+e is not known to be expressible by a \Sigma_1 statement. So we can’t use Lemma 1 in the same way.

Edited later: I don’t have much to say about the question on self-referential statements beyond what others have said. But I’ll just say that one should be careful to distinguish propositional logic and predicate logic. This also goes for your “general picture of Model Theory”. Part of the interesting thing with the incompleteness theorems is that they permit self-reference without being so obvious about it. In PA there is enough expressive power to code statements and formal proofs, and so the self-referential statements about proofs and so forth are fully rigorous and uncontroversial.

Attribution
Source : Link , Question Author : Abhimanyu Pallavi Sudhir , Answer Author : halrankard

Leave a Comment