Developing new theories by transfinitely iterating the Godel sentence construction

97 Views Asked by At

In Turing's Ph. D thesis "Systems of Logic Based on Ordinals", he writes of a simple way to use Gödel's incompleteness theorem to devise a transfinite sequence of new theories. The sequence proceeds via transfinite recursion as follows:

  1. Begin with some theory $T_0$.
  2. For any theory $T_n$ in the sequence, define the theory $T_n+1$ as the theory $T_n \cup G(T_n)$, where $G(T_n)$ is the Gödel sentence for the theory $T_n$.
  3. For any limit ordinal $o$, the theory $T_o$ is the union of all previous theories, or $T_o = \cup \left\{T_n:n<o \right\}$

Turing then goes on to show that if one starts with $T_0 = PA$, that one does not get a complete theory $T_\alpha$ for any countable $\alpha$. I believe the same result holds for $T_0 = ZFC$

My question is, starting with either $PA$ or $ZFC$, what do we know about the first ordinal which does lead to a complete theory? Do we get a complete theory at $T_{\omega_1}$, for instance? This would be the first theory that is not recursively axiomatizable, and hence Gödel's theorem doesn't pertain to it. But is $\omega_1$ enough?

1

There are 1 best solutions below

4
On BEST ANSWER

By the incompleteness theorem, there is no extension of PA that is (a) complete and (b) consistent and (c) has a recursively enumerable set of axioms. Since every $T_\alpha$, if it exists at all, is an extension of PA, this hints that something can't be quite right here.

There's also a problem with speaking about $T_{\omega_1}$ at all, because such a theory would be one where you've added a new axiom uncountably many times -- but there are only countably many different formulas in the language of PA that you could conceivably add.

But there's a problem much before that, namely that your step 2 will stop working. Gödel's construction doesn't start with a theory as an abstract set of axioms, but takes an input a particular algorithm for recognizing the axioms in the set. So speaking about "the Gödel sentence" for $T_n$ requires you to have an algorithm for the theorems of $T_n$, and that stops being possible long before you reach $\omega_1$.

In order to describe $T_\alpha$, it appears that you'd need an algorithmic description of the structure of the ordinal $\alpha$, because that's how you constructed $T_\alpha$ itself. That stops being possible at all at $\omega_1^{CK}$, the Church-Kleene ordinal, which is smaller than $\omega_1$. So if you manage to construct $T_{\omega_1^{CK}}$, you no longer have a way of defining $T_{\omega_1^{CK}+1}$.

And even before $\omega_1^{CK}$ there's a possible problem, namely that some countable ordinals can have many different algorithmic descriptions where it may not be provable from any particular theory that they happen to describe the same ordinal. That is a problem when you reach a limit ordinal $\alpha$ and just describe $T_{\alpha}$ as a mathematical union of the previous theories. This doesn't offer any guidance about which algorithm for $\alpha$ you should use to construct a Gödel sentence that you can elevate to an axiom in $T_{\alpha+1}$. It is quite plausible that at some point $T_{\alpha}$ itself cannot prove that the various algorithms for $\alpha$ are equivalent. From that point on, your process may proceed in several nondeterministic directions.

So the best you can possibly do -- and I'm far from sure there are not additional problems lurking here! -- is to define a procedure that takes a particular ordinal notation as input and produces a sequence of extensions of PA indexed by the ordinal you have a notation for. But different notations for the same ordinal may give you different extension sequences. At least all of the new axioms in any of the branches will be true in $\mathbb N$, so one could imagine taking the union of all the theories in all the branches, producing a new consistent theory that one could somewhat plausibly argue for calling $T_{\omega_1^{CK}}$. I don't immediately see a reason to expect this combined theory to be complete. It will definitely not be recursively axiomatized, so there's no $T_{\omega_1^{CK}+1}$ to continue with.