Incompleteness in reverse

Question

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?

Answer 1

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

Answer 2

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.