Consistency hierarchies and Gödel’s theorem

80 Views Asked by At

We know that for any theory $T$ that can interpret arithmetic, the recursive theory $T_{bad} = T + \mathop{Con}(T_{bad})$ is inconsistent, by Godel’s second incompleteness theorem. However, $T_{okay} = T + \mathop{Con}(T)$ may be consistent, and is consistent for any correct $T$.

Consider the infinite sequence of theories:

  1. $T_0$ = $T$ = the base theory
  2. $T_{n + 1}$ = $T_n$ + “$T_n$ is consistent”

Define $T_\omega = \bigcup^{\infty}_{i=0}T_i$.

  1. Is $T_\omega$ guaranteed to be inconsistent for $T$ that can interpret arithmetic?
  2. If the answer to 1 is “no”, what about the theory $T_L = \cup_iT_i$ for all ordinals $i$? Obviously, this only makes sense for sufficiently powerful theories, such as ZFC. It doesn’t make sense for PA, as there are no infinite ordinals in PA.
1

There are 1 best solutions below

0
On

Many variations of this question have been asked here and at mathoverflow, but at the moment I can't find an exact duplicate so I'm answering.


Under reasonable assumptions on $T$, the theory $T_\omega$ is consistent, computably axiomatizable, and incomplete. Specifically, the assumption that $T$ is sound is enough (and indeed more than enough). As a concrete example, $ZFC$ proves that $PA_\omega$ is consistent.

Re: your second question, let's first focus on $T=PA$ for concreteness. It turns out that there is no way to define $PA_\alpha$ for all ordinals $\alpha$, or even all countable $\alpha$. Basically, the issue is that to define $PA_\alpha$ we need to pick a "representation" of the ordinal $\alpha$ in the language of arithmetic. Once we hit a large enough countable $\alpha$, namely $\alpha=\omega_1^{CK}$, no such representation exists at all; and even before then, there is no way to pick a canonical representation of $\alpha<\omega_1^{CK}$ (basically: if there were, we'd get a representation of $\omega_1^{CK}$ itself).

Now at first glance it may seem like the issue is that $PA$ talks about numbers whereas we need to talk about ordinals, and so we may hope for a better situation with $ZFC$. But in fact the same problem occurs: in order to define $ZFC_\alpha$ we still need to pick a $ZFC$ formula defining $\alpha$, which $(i)$ won't exist in general (ignoring some subtleties) and $(ii)$ even when it does exist won't exist "uniformly" in $\alpha$.

Basically, we don't iterate consistency extensions along ordinals but rather representations of ordinals. Different theories may support well-behaved iterations to different extents - e.g. $ZFC$ gets us further than $PA$, in many senses - but will always fall short of "everything" and even before that point become "non-linear."

One relevant term here is Kleene's $\mathcal{O}$. This is a partial order corresponding to the "computable representations" of ordinals which have such representations (= those less than $\omega_1^{CK}$). "Canonical ordinal notation systems" basically amount to linearly-ordered initial segments of $\mathcal{O}$ - e.g. Cantor normal form lets us pick a canonical $n\in\mathcal{O}$ corresponding to a given $\alpha<\epsilon_0$, but doesn't help us past $\epsilon_0$.

(Note I use "initial segment" in its weak sense, here - "closed downwards," rather than "$<$ everything not in it." E.g. $\omega^{\omega^2+17}\cdot 3+42$ has lots of different notations but only one in the canonical notation system coming from Cantor normal form; meanwhile, the set of the canonical notations coming from Cantor normal form is closed downwards in the sense of $\mathcal{O}$.)

It's worth noting that this "representation" issue arises with other sorts of iteration ideas, like the Ershov, mastercode, or hyperarithmetic "hierarchies." There are also occasionally surprising robustness results here, to be fair: e.g. for $\alpha<\omega_1^{CK}$, while the "$\alpha$th iterate of the Turing jump" $J_\alpha$ is not a well-defined operation on sets it is well-defined on Turing degrees in the sense that if $m,n\in\mathcal{O}$ are "good representations" of $\alpha$ and $X$ is a set then iterating the jump along $m$ starting with $X$ and iterating the jump along $n$ starting with $X$ yields Turing equivalent sets.