1
$\begingroup$

Take a consistent formal system $F$ within which a certain amount of elementary arithmetic can be carried out.

Now out of the statements in $F$ there are those that can be proven true or false, and there are necessarily, due to the first incompleteness theorem, those that can’t be proven true or false within $F$.

Let’s take an arbitrary such statement $a$.

What we can do from there on is the following: we can find an undecideable statement $g$ in $F$ by following Gödel’s constructive argument, and add it to the system $F$ as a new axiom arriving at a more powerful system $G$. Then find the statement $h$ in $G$ and so on.

Of course each of the systems we construct will be incomplete.

However, here comes my question. Is it always the case that $a$ (an arbitrary statement that we fixed in $F$) can be proven true after adding a finite amount of new axioms?

$\endgroup$
12
  • 1
    $\begingroup$ Add $a$ as an axiom, now you can prove $a.$ $\endgroup$
    – user147556
    Jul 6, 2021 at 14:57
  • $\begingroup$ @MichaelBarz oh sure, but what if we aren’t certain in the validity of $a$? We can add $g$ because it is known to be true (otherwise $F$ is inconsistent). In my question, I assume that we always add the Gödel’s statement until we can reach a system powerful enough to prove an unrelated statement $a$. My question is — if $a$ is true after all, will we always reach a proof of it, and whether this is even known $\endgroup$ Jul 6, 2021 at 14:59
  • 1
    $\begingroup$ By Godel's completeness theorem, an undecidable statement $a$ exists precisely because it is true in some models and false in other models. It is somewhat meaningless to ask about the validity of $a$--it depends on the model. Both $a$ and "not $a$" are consistent additions to your theory. $\endgroup$
    – user147556
    Jul 6, 2021 at 15:01
  • 2
    $\begingroup$ Perhaps what you're asking is this: Start with $F$, add its Godel sentence, then add the Godel sentence of that theory, and so on. After infinitely many steps, will you have a complete theory? The answer is no: the incompleteness theorem can be applied to the theory you get after infinitely many steps. $\endgroup$ Jul 6, 2021 at 15:04
  • 1
    $\begingroup$ @Prof. Legolasov Doesn't my comment answer your question? After infinitely many steps, the theory is still incomplete, so there is some statement that is neither provable nor disprovable. Let $b$ be such a statement. Now let $a$ be either $b$ or $\neg b$, whichever is true. Then $a$ is a true statement that was not provable in $F$ and that does not become provable after any finite number of steps of adding Godel sentences. $\endgroup$ Jul 6, 2021 at 16:20

2 Answers 2

2
$\begingroup$

Let $g_1$ be the Godel sentence of $F$, and let $F_1 = F + g_1$. In other words, $F_1$ is the formal system that is the same as $F$, except that $g_1$ is added as an additional axiom. Now let $g_2$ be the Godel sentence of $F_1$, and let $F_2 = F_1 + g_2$. In general, we let $F_{n+1} = F_n + g_{n+1}$, where $g_{n+1}$ is the Godel sentence of $F_n$. Now let $F_\omega$ be the formal system in which all of the statements $g_n$ are added to $F$ as additional axioms. Then the incompleteness theorem can be applied to $F_\omega$ as well. Now let $a$ be the Godel sentence of $F_\omega$. Then $a$ is true but not provable in $F_\omega$, and therefore it is not provable in any $F_n$.

$\endgroup$
2
$\begingroup$

Gödel sentences are by construction $\Pi^0_1$ statements, that is, they have the form "for all $n$ ...", where ... is a recursive statement (think "a statement that a computer can decide"). For instance, the typical Gödel sentence for a system $T$ coming from the second incompleteness theorem says that "for all $n$ that code a proof in $T$, $n$ is not coding a proof of a contradiction", and a similar observation holds for the sentence from the first incompleteness theorem.

Under mild assumptions on $T$ (say, the assumptions on the incompleteness theorem and that $T$ is true in the standard model of arithmetic), you could add to it all true $\Pi^0_1$ statements, many of which are not provable in $T$ and many of which are not Gödel sentences. The result is a theory to which the incompleteness theorem no longer applies (it is not recursive), and yet it is still far from complete and there are $\Pi^0_2$ statements that are not provable in it (assertions that certain recursive functions are total). There are similar results if you proceed to add all true $\Pi^0_2$ statements to this theory and so on.

The assumption that $T$ is true is perhaps too strong. We can say something very general even without this requirement: the other answer indicated that if we start with $T_0=T$ and recursively form $T_{n+1}$ by adding to $T_n$ its Gödel sentence, then the incompleteness theorem still applies to the union of the $T_n$. There is a general fact here: If $\{T_k: k\in\mathbb N\}$ is a recursively enumerable family of theories (meaning, there is an algorithm that generates all pairs $(\phi,n)$ such that $\phi$ is a sentence and $\phi\in T_n$), there is a $\Pi^0_1$ sentence which is simultaneously undecidable in all the theories $T_k$.

There are some excellent references for these and many additional results. In particular, I recommend "Aspects of incompleteness" by P. Lindström and "Metamathematics of first-order arithmetic" by P. Hájek and P. Pudlák.

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