Understanding the definition of completeness of formal theorys(and Godel's famous theorem)

Question

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?

Answer 1

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.

2. 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.

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?)

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.

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$.

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:

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$.

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.

Answer 2

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"