Let F be a formal system falling prey to Gödel's incompleteness theorems, implyng there is a true but unprovable statement, call it $G_1$. Of course, adding $G_1$ to the axioms of F doesn't solve the problem - there would appear another true-but-unprovable statement, call it $G_2$. Now, adding $G_2$ to F+$G_1$ again doesn't solve the problem. In other words, no matter how many times you try to patch the original formal system, you will always end up having another true-but-unprovable statement.

My question: in light of the fact that most mathematicians accept the absulute infinite, why can't we just solve the whole problem by constructing the formal system F+$\bigwedge_{1}^{\infty}G_i$?

  • 5
    $\begingroup$ See math.stackexchange.com/questions/309147/…. $\endgroup$ – Pockets Apr 17 '16 at 8:38
  • 1
    $\begingroup$ In what sense are you regarding the unprovable statement as true? Do you mean a statement that is true in some preferred model of the theory? $\endgroup$ – joriki Apr 17 '16 at 9:11
  • 1
    $\begingroup$ @Mikhail Katz: on one hand, as I pointed out, this sense of "true" can also be read by formalists as "provable in PRA". It is common even for formalists to write "true" as if they were platonists, because it is well known how to re-interpret that language in a formalist way. However, it would be silly to go around math forum such as this challenging all speakers on their platonist views, for various reasons. $\endgroup$ – Carl Mummert Apr 17 '16 at 12:10
  • 1
    $\begingroup$ @CarlMummert: Thanks for the explanation. I wasn't aware of this usage. It seems confusing to use something as meaning three different things according to people's taste :-), but I guess in some useful practical sense the differences don't matter too much in many cases. $\endgroup$ – joriki Apr 17 '16 at 12:21
  • 1
    $\begingroup$ @joriki: no problem - the word "challenge" was introduced by someone else's comment anyway. I agree that, for practical purposes, there isn't much difference. My opinion on why the terminology is so common in logic is that it makes naive sense, but also those who want to use a non-naive understanding of "truth" can easily translate sentences written that way into their own preferred viewpoint. There is an analogy with reading a proof in constructive mathematics - a naive reader can pretend it's a classical proof, while experts can interpret the proof in their preferred constructive system. $\endgroup$ – Carl Mummert Apr 17 '16 at 12:34

The challenge is that the theory has to remain effective. You are asking about adding new axioms in stages. For the first few stages things are clear. We can make $F_2 = F + G_1$, $F_3 = F_2 + G_2$, etc.

So we can make the theory $F + \{ G_i : i \in\mathbb{N}\}$. Let's call that $F_\omega$. That will be an effective theory as well. This means that, just from $F$, we can enumerate the entire sequence of formulas $\{G_i : i \in \mathbb{N}\}$.

So we can then continue, making $F_{\omega + 1} = F_{\omega} + G_{\omega}$, $F_{\omega + 2} = F_{\omega+ 1} + G_{\omega+1}$, etc.

Eventually, we can make $F_{\omega + \omega}$ in the same way. To do this, we need to enumerate the entire sequence of formulas $\{G_\alpha: \alpha < \omega + \omega\}$, but we can do that effectively by enumerating $\{G_i : i \in \mathbb{N}\}$, then $G_\omega$, then $\{G_{\omega + i} : i \in \mathbb{N}\}$. So, as long as we have a good grasp of the overall sequence of extensions we have made, we can enumerate the necessary sequence of Goedel sentences.

For the incompleteness theorem to apply, we need the theory at hand to be effective. The problem, as you can see, is that we have to have a computable way to keep track of the "stages", so that we know which sentences have been added at each stage. There are limits to how many stages can be described in a coherent, computable way. The stages are usually treated as ordinals, re-using a concept from set theory.

Essentially, in order to create the Goedel sentence $G_\alpha$ for some ordinal $\alpha$, we need to have an effective way of describing $\alpha$. Recall that the Goedel sentence for a theory refers to an effective axiomatization of the theory, and to axiomatize one of the theories in our sequence of extensions, we need to know just how much it has been extended.

The easiest limit on how long we can keep going is that the number of stages can be at most countable, especially when the theory at hand is only countable. If there are only countably many sentences overall, then we can't continue adding Goedel sentences an uncountable number of times.

It turns out, however, that if we want the description of the stages to be effective, it cannot be near uncountable. The least bound for the computable ordinal numbers, known as the "Church-Kleene ordinal", $\omega_1^{CK}$, is countable. So our sequence of extensions will eventually have to stop, not because we run out of sentences, but because we run out of effective ways to describe the overall sequence of extensions we have made.


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.