2
$\begingroup$

I have some conceptual question about the completeness of a formal theory and hence Godel's first incompleteness theorem. First, to be clear, I give the definition of completeness I mean.

Definition: A formal theory $\Gamma$ of a first-order language $\mathcal{L}$ is complete if for every sentence $\phi$ of $\mathcal{L}$, either $\Gamma\vdash\phi$ or $\Gamma\vdash\neg\phi$.

(For convience, the first-order language used in this article allow sentence symbols $P,~Q,~R,\cdots$ etc., which is usually not a way standard mathematical logic books would did, though I don't know why.)

Now my question starts.

Let $\Gamma=\{P,Q\}$, we know that neither $\{P,Q\}\not\vdash R$ nor $\{P,Q\}\not\vdash\neg R$. So here the formal theory $\Gamma$ is not complete, right? Here we don't know the valuation of $R$ under a model $\mathfrak{A}$, denoted by $V_{\mathfrak{A}}(R)$ in this article, is True or False -- in fact, it could be either True or False.

On the other hand, Godel's first incompletness theorem said that, under some assumptions of a consistent formal theory $\Gamma$, $\Gamma$ must be incomplete. Namely, there exists a sentence $\phi$ such that $\Gamma\not\vdash \phi$ and $\Gamma\not\vdash\neg\phi$. From here it arises many saying, primarily from popular science literature, blog posts or some websites, and they're all different: (some of their description is rather ambiguous and nonrigorous, I keep their original statement as possible, but rephrasing it more uniformly.)

  1. It means that there exists a sentence $\psi$ that doesn't have a truth value(i.e., neither true nor false.)
  2. It means that there exists a sentence $\psi$ having a truth value, but we don't know.
  3. It means that there exists a true sentence $\psi$, but $\Gamma\not\vdash \psi$ and $\Gamma\not\vdash\neg\psi$. (ps: this saying is so blurred, how does "true" mean by him? Under what model? Under all model?)
  4. There exists sentence $\psi$ such that $\Gamma\not\vdash \psi$ and $\Gamma\not\vdash\neg\psi$, and there exists some model $\mathfrak{A}$ such that $\mathfrak{A}\vDash\Gamma$ and $V_{\mathfrak{A}}(\psi)=T$, and at the same time there also exist some model $\mathfrak{B}$ such that $\mathfrak{B}\vDash\Gamma$ and $V_{\mathfrak{B}}(\psi)=F$.
  5. There exists sentence $\psi$ such that $\Gamma\not\vdash \psi$ and $\Gamma\not\vdash\neg\psi$, and for any model $\mathfrak{A}$ that $\mathfrak{A}\vDash\Gamma$, then $V_{\mathfrak{A}}(\psi)=T$.
  6. ... (there are more than these, but I think I may stop listing at here)

Which point of view above is correct? And what does Godel's incompleteness really said? What conclusion and observation we can make by the theorem?

$\endgroup$
  • $\begingroup$ Not a complete answer, but: "Truth" is a slippery concept in mathematics. If we could pin it down formally into a propostion TRUE(x), then we could use a construction similar to Godel's proof to create a statement P:TRUE(P) and ~TRUE(P). $\endgroup$ – Michael Hartley Aug 3 '17 at 6:39
  • $\begingroup$ This is my understanding: Given a (first-order) language $\mathcal L$ and a theory $Γ$, logicians define a sentence $ψ$ to be true in $Γ$ if all models $\mathcal A$ of $Γ$ satisfy $ψ$ (written $Γ \vDash ψ$). A sentence is provable in $Γ$ if $Γ \vdash ψ$. Gödel’s completeness theorem says $Γ \vdash Ψ \Longleftrightarrow Γ \vDash Ψ$, that is: A sentence is true in $Γ$ if and only if it is provable in $Γ$. Gödel’s incompleteness theorem says: If $Γ$ has these and those properties, then there is always some sentence $ψ$ satisfied by some models, but not by others. $\endgroup$ – k.stm Aug 3 '17 at 6:52
  • $\begingroup$ to 1). NO; the relation $\vdash$ is provability (i.e. derivability from the axioms by way of the rules of logic). Under suitable conditions regarding the language and the axioms of the theory $T$ (see Gödel's Incompleteness Theorems) G's Th "manufacture" a sentence $G$ in the language of the theory that is neither provable (i.e. $T \nvdash G$) nor refutable (i.e. $T \nvdash \lnot G$). $\endgroup$ – Mauro ALLEGRANZA Aug 3 '17 at 7:09
  • $\begingroup$ Under "standard" semantics, if the theory $T$ is consistent (and this is one of the pre-conditions of G's Th) it has a model $\mathcal M$, i.e. an interpretation of the language that satisfies the axioms. If so, one of the two sentences $G$ and $\lnot G$ must be true in it. $\endgroup$ – Mauro ALLEGRANZA Aug 3 '17 at 7:11
  • $\begingroup$ to 2). Not necessarily: the G's sentence $G$ is manufactured in a way to be "interpretable" by humans; in a certain sense, it says "I'm not provable in the theiory $T$". Thus, due to the fact that $T \nvdash G$, we know its truth value. $\endgroup$ – Mauro ALLEGRANZA Aug 3 '17 at 7:13
1
$\begingroup$

Taking the numbered statements one by one ...

  1. It means that there exists a sentence $\psi$ that doesn't have a truth value(i.e., neither true nor false.)

No. The situation is really quite different from your example where $\Gamma=\{P,Q\}$ and we want to know the truth-value of $R$. In that case, we could consider interpretations relative to $\Gamma$ that simply do not consider $R$, and you could in some sense say that $R$ does not have a truth-value (some will disagree and say that as soon as you refer to a proposition $R$ it must have a truth-value, which is why I say 'in some sense').

In the case of Godel and arithmetic, however, $\Gamma$ is a first-order logic theory of arithmetic, meaning that it contains sentences described by the language of arithmetic, which includes symbols $\mathbf{0}$, $\mathbf{s}$, $\mathbf{+}$, and $\mathbf{\cdot}$. The sentence $\phi$ (called the 'Godel sentence) is expressed in this language as well. As such, any interpretation for $\Gamma$ is an interpretation of the the language of arithmetic, and thus the Godel sentence $\phi$ will always have a truth-value.

  1. It means that there exists a sentence $\psi$ having a truth value, but we don't know.

No. The Godel sentence $\phi$ such that $\Gamma\not\vdash \phi$ and $\Gamma\not\vdash\neg\phi$ for any consistent formal arithmetical theory $\Gamma$, when interpreted by the standard interpretation $N$ (which has as domain $\mathbb{N}$, and which maps $\mathbf{0}$ to $0$, $\mathbf{s}$ to $s$ (successor function), $\mathbf{+}$ to $+$, and $\mathbf{\cdot}$ to $\cdot$)), ends up saying "I ($\phi$) cannot be derived from $\Gamma$". And since $\Gamma \not \vdash \phi$, it indeed cannot be derived from $\Gamma$, and thus it is true under the standard interpretation.

And when mathematicians talk about sentences being true, they of course use the 'standard interpretation' of their language. In other words, $\phi$ is as much 'true' as '1+1=2'. .... which in mathematics we simply consider true, period. So, $\phi$ is true, period.

  1. It means that there exists a true sentence $\psi$, but $\Gamma\not\vdash \psi$ and $\Gamma\not\vdash\neg\psi$. (ps: this saying is so blurred, how does "true" mean by him? Under what model? Under all model?)

Yes. "true" under the 'standard interpretation', i.e. 'true' by normal mathematical standards, i.e. true in as much any other mathematical theorem is considered true.

  1. There exists sentence $\psi$ such that $\Gamma\not\vdash \psi$ and $\Gamma\not\vdash\neg\psi$, and there exists some model $\mathfrak{A}$ such that $\mathfrak{A}\vDash\Gamma$ and $V_{\mathfrak{A}}(\psi)=T$, and at the same time there also exist some model $\mathfrak{B}$ such that $\mathfrak{B}\vDash\Gamma$ and $V_{\mathfrak{B}}(\psi)=F$.

Yes ... but this is a weaker statement than 3. We don't just mean 'some' model; we mean the 'standard model', i.e. we mean 'true' by normal mathematical standards. Again, it is as true as any other mathematical theorem. So yes, there does exist a model in which it is true (namely the 'standard model'), and there is also a model (a 'non-standard model' or 'non-standard interpretation') in which it is false. And we know the latter, since because:

  1. There exists sentence $\psi$ such that $\Gamma\not\vdash \psi$ and $\Gamma\not\vdash\neg\psi$, and for any model $\mathfrak{A}$ that $\mathfrak{A}\vDash\Gamma$, then $V_{\mathfrak{A}}(\psi)=T$.

Is definitely false! If $\phi$ is true under any interpretation, then $\vDash \phi$, and since first-order logic itself is complete (This is Godel Completeness Theorem (for logic), not to be confused with his Incompleteness Theorem (for arithmetic)), $\phi$ can be derived from nothing (i.e. $\vdash \phi$) and so certainly from $\Gamma$ (i.e. $\Gamma \vdash \phi$.). So this is why in 4. we know there must be at least one model that sets $\phi$ to False.

To sum up: out of these 5, only 3 and 4 are true, and 3 is the best way to think about it: "Given any consistent set of axioms about arithmetic, there is always some arithmetical truth that cannot be derived from those axioms." Or even shorter: "arithmetic is not axiomatizable", or shorter yet: "arithmetic is incomplete"

P.s. It should really be: "Any recursive and consistent set of axioms for arithmetic is incomplete". For simplicity sake you can think of 'recursive' as 'finitely expressible' ... for if you don't put in that constraint, you can simply choose all arithmetical truths as your 'axiom set', and that axioms set is of course both consistent and complete.

$\endgroup$
  • $\begingroup$ I understand all paragraph, except one sentence under 2. "And since it indeed cannot be derived, it is true under the standard interpretation." What is the logical connection and relation between these two clause? Well, I guess maybe I missed some critical/important theorem in mathematical logic... $\endgroup$ – Eric Aug 5 '17 at 14:56
  • $\begingroup$ @Eric It cannot be derived because we said $\Gamma \not \vdash \phi$: that means '$\phi$ cannot be derived from $\Gamma$. $\endgroup$ – Bram28 Aug 5 '17 at 15:03
  • $\begingroup$ Yes, I know this, and why "because of it",it is true under the standard interpretation.? (I also understand the latter, but can't see the logical inference here) $\endgroup$ – Eric Aug 5 '17 at 15:05
  • $\begingroup$ @Eric The Godel sentence $\phi$ is a cleverly constructed sentence (exploiting the fact that logical statements and logical proofs can be given a natural number, and that, as such, can be used to describe, as a statement about arithmetic, logical relationships such as 'can be derived from') that is logically equivalent to a sentence that under the standard interpretation ends up saying '$\phi$ cannot be derived from $\Gamma$'. So, under the standard interpretation, $\phi$ is the claim: "I cannot be derived from $\Gamma$". ... (continued) $\endgroup$ – Bram28 Aug 5 '17 at 15:23
  • $\begingroup$ @Eric Now, why would that make $\phi$ true? Well, if $\phi$ was false, then the claim it is making would be false, and hence $\phi$ would be derivable from $\Gamma$. However, we insist that $\Gamma$ is consistent (sound, really), meaning that everything we derive from $\Gamma$ better be an arithmetical truth (again, under the standard interpretation of course). So, if $\phi$ is false, then it is derivable from $\Gamma$, and hence it would be true. Contradiction! So, $\phi$ cannot be false. Hence, $\phi$ is true, and indeed not derivable (and neither would its negation) $\endgroup$ – Bram28 Aug 5 '17 at 15:27
3
$\begingroup$

When they say "true", they are referring to one specific model : the standard model of arithmetic, i.e. $\mathbb{N}$. Indeed they can't (rightly) be referring to all models, because what Gödel's completeness theorem states is that if a sentence $\phi$ is true in all models of $\Gamma$, then $\Gamma\vdash \phi$.

So the right way to see Gödel's incompleteness theorem is the following (for convenience I'll restrict to Peano's arithmetic PA and not the general theories to which Gödel's theorem applies) :

There exists a sentence $\phi$ such that PA does not prove $\phi$ nor $\neg \phi$ (which implies that there exist models of PA in which$\phi$ holds, and some in which $\neg \phi$ holds), but such that $\phi$ is a sentence of "true arithmetic", that is $Th(\mathbb{N})$, the theory of the standard model of arithmetic.

Replace PA by any appropriate theory (it needs to have some nice computability properties, and it needs to be able to express PA), and change a bit what you mean by "standard model", and you'll have the same result

What I often say is that saying "true" with Gödel's incompleteness theorem is a bit misleading because what Gödel's completeness theorem says is "If a sentence is always true, then it is provable"

$\endgroup$
  • $\begingroup$ Thanks. Can you explain more on true arithmetic and the standard model of arithmetic? I'm not familiar with these two concepts, and see some introductory articles on it somewhat require a pre-understanding of Godel's incompleteness theorem. $\endgroup$ – Eric Aug 3 '17 at 14:56
  • 1
    $\begingroup$ If you have a language $L$ and an $L$-structure $\mathfrak{M}$, the theory of $\mathfrak{M}$, often denoted $Th(\mathfrak{M})$ is the set of sentences $\phi$ such that $\mathfrak{M}\models \phi$, that is, the set of sentences satisfied by $\mathfrak{M}$. By definition of satisfaction, this is a complete theory. In particular when $L=\{+,\times, 0, S\}$ is the language of arithmetic, and $\mathbb{N}$ is the set of integers with the usual operations (you can say for instance it's the set of finite ordinals), then $Th(\mathbb{N})$ is called "true arithmetic", it's the theory of (cont) $\endgroup$ – Max Aug 3 '17 at 15:39
  • 1
    $\begingroup$ (cont) the so-called "standard model" of arithmetic. Now I'm not a logician and I don't know Gödel's theorem by heart, but simply you can define a notion of intepretability of a theory (which essentially means what you think it means) in another one. So if $T$ is a theory that can interpret PA, and a theory "sufficiently computable", that is if I'm not mistaken here, we want it to be recursively axiomatizable, then it has such a sentence $\phi$ as well. I have to admit I don't really know for such a general theory $T$ what the notion of standard model precisely encompasses $\endgroup$ – Max Aug 3 '17 at 15:43
  • $\begingroup$ Thank you very much. Both your and Bram28's answers help a lot! $\endgroup$ – Eric Aug 5 '17 at 16:02

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.