0
$\begingroup$

The proof of Godel's first incompleteness theorem is often paraphrased like this. First, find a sentence $\phi$ which is true exactly if it is not provable. If $\phi$ is false, it must be provable, meaning that it must be true. This is a contradiction. On the other hand, if it $\phi$ is provable, then it must be true, which means that is is not provable, also a contradiction.

In this version of the argument, it is assumed that any sentence that is provable is also true. This seems like some version of soundness. I know that Godel's proof assumes the consistency of the theory $T$ capable of doing arithmetic. Is soundness an additional assumption that must be made, or is it proven as a part of Godel's argument? I know that this is not soundness in the sense of a sound proof system, but maybe it's related? I am worried that the version of the proof I paraphrased also might be conflating provability in $T$, or $T\vdash \phi$ with the provability predicate holding for $\phi$, or $T\vdash \textrm{Pr}(\lceil \phi \rceil)$.

Thanks!

Edit: I learned that the kind of soundness I am referring to is called arithmetical soundness, which means that theorems proven by $T$ are true of the standard model of the natural numbers.

$\endgroup$
6
  • 2
    $\begingroup$ That's not a good reflection of how the proof works. The proof itself makes no soundness assumptions. It defines binary relation among numbers which, in the metatheory, corresponds to the fact that the first number is the number of a formal proof of the sentence whose number is the second number. Then it constructs a sentence $\phi$ that asserts that there is not number $m$ which is in the relation with the number $n$ we obtain through a series of well-defined operations. Then it verifies that the number number of $\phi$ is $n$. (cont) $\endgroup$ Mar 11 at 22:09
  • 1
    $\begingroup$ (cont). It then argues: if the theory is consistent, then a proof of $\phi$ would establish that there is no number $m$ in the relation with $n$; and the proof itself would yield a number $m$ in the relation with $n$. This implies that there can be no proof of $\phi$. On the other hand, if there were a proof of $\neg\phi$, this would mean there is a number $m$ that is the number of a proof for $n$, and so you would be able to use $m$ to construct a proof of $\phi$, a contradiction. Thus, there can be no proof of $\neg\phi$. So either the theory is inconsistent, or incomplete. $\endgroup$ Mar 11 at 22:13
  • 3
    $\begingroup$ Note that Goedel's Theorem is purely syntactic, not semantic. It is about provability, not about truth. That's why one should not introduce paraphrases that rely on "true" and "false"; the late Torkel Franzen wrote about this issue a lot, I recomment his writings. $\endgroup$ Mar 11 at 22:16
  • 3
    $\begingroup$ I'm going to disagree, to a certain extent, with the existing comments/answers: different proofs assume different things (and there are many proofs of the first incompleteness theorem). What is true is that we can prove a version of the incompleteness theorem without any soundness assumptions, namely "Any computably axiomatized consistent first-order theory interpreting $\mathsf{Q}$ is incomplete." $\endgroup$ Mar 11 at 22:31
  • 1
    $\begingroup$ I recommend changing the title from "the proof" to "this proof" to emphasize that you're focusing on a specific argument, not the optimal situation. $\endgroup$ Mar 13 at 3:13

3 Answers 3

2
$\begingroup$

It is true that the incompleteness theorem ultimately requires no extra hypotheses: Rosser improved Godel's original argument to show that (in modern phrasing) any consistent computably axiomatizable first-order theory interpreting $\mathsf{Q}$ is incomplete.

However, the specific argument you sketch in the OP

find a sentence $\phi$ which is true exactly if it is not provable. If $\phi$ is false, it must be provable, meaning that it must be true. This is a contradiction. On the other hand, if it $\phi$ is provable, then it must be true, which means that is is not provable, also a contradiction.

(which can be made fully rigorous) does require soundness. Specifically, we can show that $T\not\vdash\phi$ without any soundness hypothesis (if $T\vdash\phi$ then $T\vdash \mathsf{Prov}_T\phi$ but we also have $T\vdash\phi\leftrightarrow\neg\mathsf{Prov}_T\phi$ so that would give a contradiction), but showing that $T\not\vdash\neg\phi$ requires $\Sigma_1$-soundness: think about a theory like $\mathsf{PA+\neg Con(PA)}$.


It's worth noting that there are other natural arguments which require even more soundness. For example, consider the following (I think due to Kotlarski?) which takes us to the two-quantifier level:

Let $f(e)$ be $1+$ the value of the $e$th $T$-provably total recursive function on input $e$. Then $f$ is total recursive, but not $T$-provably total recursive. So "$f$ is total recursive" is a true sentence not provable in $T$.

$\endgroup$
1
$\begingroup$

Godel’s Incompleteness Theorem does not assume soundness or consistency, but states that there is no consistent, recursive, and complete theory of arithmetic. Or: if we have a consistent and recursive set of axioms, then they are not complete.

So why is it called just the Incompleteness Theorem? It’s because we really want consistency and recursiveness, but completeness is ‘merely nice to have’. So, in some sense you are right: once we do assume consistency and recursiveness, then incompleteness follows.

$\endgroup$
2
  • $\begingroup$ I think you misunderstand what I mean by "assumes consistency". The version of Godel's theorem I have seen is that any consistent, effectively axiomatized theory must fail completeness. This obviously fails if we subtract consistency because every inconsistent theory is automatically complete. After doing some reading, I've seen that there are actually at least two different versions of Godel's incompleteness theorem. The weaker version assumes soundness in addition to consistency, and uses soundness in the construction of a statement which is true but unprovable. $\endgroup$
    – subrosar
    Mar 12 at 4:00
  • $\begingroup$ This weaker version of Godel's theorem is slightly easier to prove, and I think that the sketch I have heard is a simplification of the standard proof of this weaker version of the theorem. Of course, the soundness assumption can be done away with. $\endgroup$
    – subrosar
    Mar 12 at 4:02
1
$\begingroup$

In order to prove that consistency alone suffices, Rosser needed to construct a different sentence than Gödel's.

There's a nice proof from just the standard minimal assumptions (consistent, recursively axiomatizable, extends Robinson arithmetic), that doesn't use Rosser's trick, but uses a bit more computability theory and doesn't give an explicit undecidable sentence:

  1. Assume for the sake of contradiction that $T$ is a complete, consistent, recursively axiomatizable theory extending Robinson arithmetic.
  2. A recursively axiomatizable, complete and consistent theory is recursively decidable, since one can enumerate all possible proofs and wait for a proof of either $\phi$ or $\lnot\phi.$ Furthermore, any recursively decidable relation is representable in Robinson arithmetic and thus in $T$. Thus there is an arithmetical predicate $F(v)$ such that $T\vdash F(\mathbf n)$ if $n$ is the number of a sentence provable in $T$ and $T\vdash \lnot F(\mathbf n)$ if $n$ is the number of a sentence not provable in $T.$
  3. Use the diagonalization lemma to find a sentence $\varphi$ such that $T\vdash \varphi\leftrightarrow \lnot F(\ulcorner \varphi \urcorner).$ If $\varphi$ is provable in $T$ then so is $F(\ulcorner \varphi \urcorner)$ (by representation) and so is $\lnot F(\ulcorner \varphi \urcorner)$ (by equivalence), which is impossible since $T$ is consistent. On the other hand if, $\varphi$ is not provable, then $\lnot F(\ulcorner \varphi \urcorner)$ is provable (by representation), so $\varphi$ is provable (by equiavalence)... an outright contradiction.
$\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.