# A paradox about cardinality of ALL and arithmetic hierarchies ― Did I just prove that ZFC is inconsistent?

This problem arose when I tried to find the arithmetic hierarchy that $$\mathsf{ALL}$$, the class of all formal languages over a finite alphabet, corresponds to (like how $$\mathsf{R} = \Delta^0_1$$ and $$\mathsf{RE} = \Sigma^0_1$$).

Since the cardinality of $$\mathsf{ALL}$$ is $$\beth_1$$, I thought that, using a sufficiently large ordinal number as the subscript should cover all decision problems.

Formally, let $$\Omega$$ be the smallest ordinal number whose cardinality is $$\beth_1$$. Existence of such ordinal number is justified by the well-ordering principle (which is equivalent to the Axiom of Choice). By the halting problem, $$\Sigma^0_o$$ has infinitely many more elements than $$\Delta^0_o$$ for every non-limit ordinal number $$o$$. As a consequence, $$\Delta^0_\Omega = \Sigma^0_\Omega = \Pi^0_\Omega$$ has at least $$\aleph_0 \times \beth_1 = \beth_1$$ elements.

On the other hand, let $$\Omega'$$ be the smallest ordinal number whose cardinality is strictly bigger than $$\beth_1$$. By a similar argument as above, $$\Delta^0_{\Omega'}$$ has a cardinality strictly bigger than $$\beth_1$$. This contradicts against that $$\Delta^0_{\Omega'}$$ is still a subset of $$\mathsf{ALL}$$. What am I missing?

• How do you define arithmetic hierarchy for uncountable ordinals? Usually this kind of definition assumes a fixed ordinal notation. Commented Jun 14 at 8:41
• @pcpthm For limit ordinals, the union of all arithmetic hierarchies of all smaller ordinals. Commented Jun 14 at 8:58
• If you just take the union, then that hierarchy will collapse at $\omega+1$. The issue is $i$ in "the Turing machine can call $\Sigma_i$-oracle" is independent of the input in your definition, but the machine is in $\Sigma_{i+1}$, so $\Sigma_{\omega+1} = \Sigma_{\omega}$. Commented Jun 14 at 9:27
• Should not the cardinality of $\mathsf{ALL}$ be $\aleph_0$? Since every grammar must be defined with a finite string, there are $\aleph_0$ strings of finite lengths, and there are only $\aleph_0$ possible input strings for each language? So you have $\aleph_0 \times \aleph_0 = \aleph_0$. Commented Jun 14 at 12:04

The issue is that you've glossed over how you're making sense of $$\Sigma^0_\alpha$$ for $$\alpha$$ an arbitrary ordinal. While successor ordinals pose no problem, limit ordinals take us to the thorny issue of notations; see e.g. Kleene's $$\mathcal{O}$$. Things are relatively simple up until the first noncomputable ordinal $$\omega_1^{CK}$$ (which is of course still countable); this gives the hyperarithmetic hierarchy. With more work we can continue up through $$\omega_1^L$$ which may not be countable, the relevant term being mastercodes.
However, no trick at all will let us continue past $$\omega_1$$ while preserving the key properties of the arithmetical hierarchy (and so your appeal to the relativized halting problem breaks down here). The issue is that we want $$\Sigma^0_{\alpha+1}$$ to be $$X'$$, the Turing jump of some language $$X$$ which "corresponds to" the previous level of our hierarchy. But the only way such an $$X$$ can possibly exist is if the previous level of our hierarchy was countable! No matter what definition you use, $$\Sigma^0_{\omega_1}$$ will not be countable, and so either your hierarchy will stop there or you'll lose the connection with Turing jumps (in which case you won't have your non-collapse result).