4
$\begingroup$

As I understand it, Godel's completeness theorem essentially says that if a sentence $\phi$ can be proven in a first order theory $\Gamma$, then $\phi$ is satisfied in all models $\mathcal{U}$ of $\Gamma$.

The first incompleteness theorem can be understood to mean that there are some sentences $\phi$ that cannot be proven in $\Gamma$ and this is because there are models of $\Gamma$ in which $\phi$ is satisfied and other models in which $\phi$ is not satisfied.

The second incompleteness theorem then states that one such sentence is $Con(\Gamma)$, the statement that "$\Gamma$ is consistent".

I've been trying to understand what this theorem means in terms of the models of the theory.

Proving $\Gamma$ is consistent is equivalent (I think!) to showing that there exists a model $\mathcal{U}$ of $\Gamma$. My question is essentially:

Is the second incompleteness theorem true because in some models $\mathcal{U}$ of the theory you cannot construct a submodel $\mathcal{V}$ obeying the axioms of $\Gamma$ and hence in those models you cannot prove consistency. Then, since in this particular model you can't prove consistency, it follows from the completeness theorem that you can't prove consistency directly from the axioms of $\Gamma$.

Even if this reasoning is completely wrong, I'm essentially just looking for a model-theoretic explanation of the second incompleteness theroem.

$\endgroup$
  • $\begingroup$ Note that even if $\Gamma$ is consistent, it could still prove $\neg \mathcal{C}on(\Gamma)$, so the situation is different from the usual undecidable sentences. Also, the second incompleteness theorem assumes as hypothesis (among others) that $\Gamma$ is indeed consistent, so while you will have at least one model where $\mathcal{C}on(\Gamma)$ does not hold, your theory is still consistent though, it's just that this particular model is not "aware" of it. $\endgroup$ – godelian Feb 10 '14 at 12:43
  • $\begingroup$ I'm not completely sure if I know what model-theoretic explanation you are looking for, but let me just say, assume $\Gamma$ is consistent, since $Con(\Gamma)$ is not provable from $\Gamma$, there is a model of $\Gamma$ such that $\neg Con(\Gamma)$ is true, namely, in this model you could even show that ``$\Gamma$ proves $\exists v (v\neq v)$'' $\endgroup$ – Jing Zhang Feb 10 '14 at 12:44
  • 7
    $\begingroup$ @DarMM your first sentence states the soundness theorem for first-order logic, not the completeness theorem. The completeness theorem is the converse of the soundness theorem. $\endgroup$ – Benedict Eastaugh Feb 10 '14 at 12:47
  • $\begingroup$ Thank you all. Godelian, that's basically the kind of idea I was looking for, i.e. the model not being "aware" of its own consistency. Similar to how you can have countable models of the reals and naturals in countable models of ZFC, but yet (due to the necessary bijections being missing from the model) the model isn't aware they are the same size. Zhang, that's very interesting. Benedict, you are right of course, thank you. $\endgroup$ – DarMM Feb 10 '14 at 13:45
  • $\begingroup$ The first incompleteness theorem imposes very important restrictions on $\Gamma$: it must be computably axiomatizable and it must interpret a sufficient fragment of arithmetic. $\endgroup$ – François G. Dorais Feb 12 '14 at 0:11
5
$\begingroup$

Your explication is essentially correct if the theory you are dealing with is strong enough so that it can manipulate (infinite) models as objects of the theory, and prove the completeness theorem. This is true for typical set theories (but not for typical arithmetical theories). You might be interested in Jech’s proof of Gödel’s theorem: http://www.math.psu.edu/jech/preprints/goedel.pdf .

$\endgroup$
  • $\begingroup$ Thank you Emil, your comments and the paper have cleared things up for me. $\endgroup$ – DarMM Feb 10 '14 at 13:52
3
$\begingroup$

No. Gödel's completeness theorem says that if a sentence ϕ is satisfied in all models of the first-order theory Γ, then it can be formally proven in Γ. The first sentence of your question merely expresses that a given formal calculus is sound.

Gödel's first incompleteness theorem should not be thought of in terms of models. It states the existence of a sentence that is not deducible (nor its negation) in any "reasonable" first-order calculus for number theory.

Completeness and incompleteness mean very different things here.

$\endgroup$
  • $\begingroup$ Perhaps I have understood things incorrectly, but I got the impression from discussing it with logicians that the reason Godel's first incompleteness theorem is true is because for those sentences which cannot be deduced (nor their negation) are undeducible because there exists models of the axioms where the sentence is true and other models where its negation is true. $\endgroup$ – DarMM Feb 12 '14 at 21:20
  • 1
    $\begingroup$ I would say that the "reason" it's true is found in the proof itself, namely in the possibility of coding the syntax of the formal system within itself. The proof is entirely syntactic. Note that the undecidable sentence is actually true provided the formal system is consistent. $\endgroup$ – Lawrence Paulson Feb 13 '14 at 21:49
  • $\begingroup$ Thank you Lawrence, I can see now that I hadn't fully understood this (to use loose language) syntactic/semantic distinction and was attempting to understand purely syntactic facts semantically. $\endgroup$ – DarMM Feb 14 '14 at 8:42
  • $\begingroup$ @Lawrence Paulson: What does it mean and why "the undecidable sentence is actually true"? $\endgroup$ – Isaac Gorelic Mar 28 '15 at 3:54
  • $\begingroup$ @IsaacGorelic, the undecidable sentence (call it G) uses a fixed point argument to refer to itself. G states that that G is not provable within the formal calculus. And as G is indeed not provable, it is true. All this rests on our assumption that the calculus is consistent. We cannot hope to prove consistency, so in a sense, the truth of G is unknowable. $\endgroup$ – Lawrence Paulson Mar 29 '15 at 16:28
3
$\begingroup$

Assume $\Gamma$ is strong enough to talk about models and prove the completeness and incompleteness theorems. In this case, $\Gamma+\neg Con(\Gamma)$ is consistent provided that $\Gamma$ itself is consistent. Then, no model of $\Gamma+\neg Con(\Gamma)$ agrees that there is a model of $\Gamma$ as it would believe $\neg Con(\Gamma)$. This is an example of what you are describing.

However, that particular model believing that there are no models of $\Gamma$ inside it does not actually imply there are no such models from outside perspective. It may just not recognize some structures as models of $\Gamma$ because its notion of natural numbers and proofs do not coincide with the real world!

For the case of ZFC, you should check this beautiful argument explained by Joel Hamkins multiple times on MO!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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