2
$\begingroup$

Given a first-order language $L$ and a theory $T$ in that language (a set of formulas of $L$), if $T$ is strong enough to prove arithmetic, then Gödel's second incompleteness theorem tells us that $T$ cannot prove its own consitency, ie $T\not\vdash \text{Cons}(T)$.

Now, imagine for a second that Gödel's second incompleteness theorem is false, and that we do have a formal proof that $T\vdash \text{Cons}(T)$. What confidence does it give us in $T$ ? If $T$ is inconsistent, it proves all formulas and in particular $T\vdash \text{Cons}(T)$. That makes this imaginary proof of $T\vdash \text{Cons}(T)$ fundamentally useless.

So if I rephrase Gödel's theorem tongue-in-cheek, it reads : do not look for a useless proof of consistency, because apart from being useless, it is nonexistent.

Then what makes the incompleteness theorem so famous ? It halted Hilbert's program, but I fail to pinpoint exactly what Hilbert hoped to achieve.

$\endgroup$
  • $\begingroup$ @MauroALLEGRANZA I know Gödel's theorem is true. I said "imagine" it is false :) $\endgroup$ – V. Semeria Sep 27 '18 at 11:03
  • $\begingroup$ Hilbert hoped to achieve a "normal" mathematical proof of consistency of arithmetic (and then analysis). We have math proofs of consistency : prop calculus, first-order logic, etc. and they need mathematical "resources" of a quite elementary level. $\endgroup$ – Mauro ALLEGRANZA Sep 27 '18 at 11:58
  • $\begingroup$ Hilbert project aimed at use "reasonable" mathematical resources (basically: Primitive Recursive Arithmetic) to develop a "combinatoric" proof (in a nutshell, a formal theory is a collection of finite sequences of finite strings) of e.g. Peano's arithmetic (formalized with predicate calculus) using "elementary" mathematical resources. $\endgroup$ – Mauro ALLEGRANZA Sep 27 '18 at 12:00
3
$\begingroup$

The second incompleteness theorem is useful because it points out an unprovable statement with a more natural meaning than the unprovable statement we get from the first incompleteness theorem.

This can be used as a part of independence proofs: One way to prove that theory $T$ cannot prove some interesting statement $A$ is to show that $T$ proves $A\to\operatorname{Con}(T)$ -- so if $T$ also proved $A$, it would prove its own consistency, which we know it doesn't.

As one example, this is a quick way to know that ZFC (if it is consistent) does not prove that there are inaccessible cardinals. This gives the positive knowledge that if ZFC is consistent, it has a model with no inaccessible cardinal in it, which may be further useful.

If you don't care at all about knowing that this-or-that theory cannot possibly prove $A$, then I suppose this would not count as useful for you. However, if you've banged your head into a wall for long enough trying to prove $A$ -- because that would certainly be useful for your research if only you knew how! -- then you might not dismiss this so quickly.

$\endgroup$
  • $\begingroup$ Fair point. I actually knew how to use incompleteness to prove some independence results. But I think this is a clever indirect application of incompleteness that came afterwards, it is not what historically happened between Hilbert and Gödel. Hilbert wanted to prove that mathematics were correct and Gödel stopped him. I don't see what Hilbert wanted to do, since $T \vdash\text{Cons}(T)$ tells us nothing about the consistency of $T$. As you said, only about some other statements independent of $T$. $\endgroup$ – V. Semeria Sep 27 '18 at 11:00
  • 1
    $\begingroup$ @V.Semeria: Hilbert's program was not just to find a theory that proved itself consistent. It was to bootstrap mathematics by starting with a simple theory $T_0$ that everyone could believe in on intuitive grounds (something like PA, for example), and then prove in $T_0$ that some stronger and richer theory $T_1$ (something like set theory) is also trustworthy. This is not inherently meaningless or useless. However, the second incompleteness theorem prevents this if $T_1$ proves everything $T_0$ does. It $T_0$ proves $T_1$ consistent, then $T_1$ would prove itself consistent. $\endgroup$ – Henning Makholm Sep 27 '18 at 11:14
  • $\begingroup$ Even if what we got was only a relative consistency result ($T_0$ proves that if $T_0$ is consistent then so is $T_1$), we would still run into problems if $T_1$ is strong enough to prove $T_0$ consistent. This is the case for $T_0$ being $PA$ and $T_1$ being ZF set theory, a possibility that definitely was on the Hilbertians' minds. $\endgroup$ – Henning Makholm Sep 27 '18 at 11:17
  • $\begingroup$ So do you say that the main impact of incompleteness was that $\text{PA}\not\vdash\text{Cons}(\text{ZF})$ ? (because if it did, then $\text{PA}\vdash\text{Cons}(\text{PA})$). In that case it looks obvious, even without proving the incompleteness theorem, that the bootstrapping collapses to the question of PA proving the consistency of PA, which is ill-founded. $\endgroup$ – V. Semeria Sep 27 '18 at 11:32
  • $\begingroup$ @V.Semeria: I don't know what you mean by "which is ill-founded" there. Your argument in the question post is at best that PA proving its own consistency would be uninteresting; there's nothing there which implies that it should be expected to be impossible, except for the incompleteness theorem stating that it is. $\endgroup$ – Henning Makholm Sep 27 '18 at 12:12

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.