$\varepsilon$-number countability without choice

Let $\alpha\mapsto\varepsilon_\alpha$ be the enumeration of the $\varepsilon$-numbers--that is, those $\alpha$ such that $\omega^\alpha=\alpha$--by the ordinals.

If we know that countable unions of countable sets are countable, (slightly weaker than countable choice), then we can show fairly easily that $\varepsilon_\alpha$ is countable iff $\alpha$ is countable.

I think I saw a result at some point that $\varepsilon_0$ is countable without relying on any choice principle (though I can't recall where I saw that). Is this true? More generally, for which $\alpha$ can we conclude that $\varepsilon_\alpha$ is countable in ZF?

Update: I have been able to prove (in ZF) that if $\varepsilon_\alpha$ is countable, then $|\alpha|<\aleph_1$, so that's one direction. I'm still a bit uncertain about the answers I've got so far.

Solution 1:

This is not quite as simple as JDH's solution, but I think it is more elementary, and I put so much thought into it that I think it will be a waste not to write it down. I hope it's correct...

First, notice the following simple fact:

Suppose that we have a sequence $\alpha_i$, $i<\omega$ of countable ordinal numbers, such that there is a procedure which, given $\alpha_i,\alpha_{i+1}$, and an enumeration of $\alpha_i$, yields a unique enumeration of $\alpha_{i+1}$. Then $\bigcup_{i<\omega}\alpha_i$ is countable.

This is true because we can just fix an enumeration of $\alpha_0$, and then uniquely define enumerations of all other $\alpha_j$s, leaving the remaining proof straightforward.

As per JDH's answer, for countable $\alpha$ we have that $\omega^\alpha$ can be defined as the order type of the set of functions from $\alpha$ to $\omega$ of finite support with lexicographic ordering. In particular, for countable $\alpha$, $\omega^\alpha$ is countable.

From this we have the lemma:

There is a procedure which, given arbitrary countable ordinal $\alpha$ and an enumeration of $\alpha$, yields an unique enumeration of $\omega^\alpha$.

Proof:

1. Fix a bijection $\varphi:\omega^\omega\to \omega$.
2. Suppose we have an ordinal $\alpha$ and a fixed, bijective enumeration $\eta$ of $\alpha$.
3. Put $A=\{f:\alpha\to \omega\vert f\textrm{ finitely supported}\}$, and $h:\omega^{\alpha}\to A$ the canonical bijection.
4. Then define $\overline{\eta}:A\to \omega^\omega$ by $f\mapsto f\circ \eta^{-1}$.
5. Then $h\circ \overline \eta\circ\varphi$ is a bijection between $\omega^\alpha$ and $\omega$.

From this and the above fact we can derive the following corollary:

Let $\alpha$ be a countable ordinal, and define $\alpha_0=\alpha$, $\alpha_{j+1}=\omega^{\alpha_j}$. Then $\bigcup_{j<\omega}\alpha_j$ is countable.

Proof: From the lemma the sequence $\alpha_j$ satisfies the hypotheses of the fact, so we're done.

From this, we can easily see that for $\alpha=\omega$ we get that $\varepsilon_0$ is countable, and for countable $\alpha=\varepsilon_j+1$ we get that $\varepsilon_{j+1}$ is countable.

I suppose this can probably be somehow generalized to jump through limit indices...

Edit for generalization: The first fact stated at the beginning of the answer can be somewhat generalized. Instead of $\omega$, $\alpha_i$ can be indexed by arbitrary countable ordinal, and the procedure can take instead a sequence $f_i$ of enumerations of all preceding elements of the $\alpha_i$ sequence, and it will be true for pretty much the same reasons.

Now, to prove that all countable-indexed $\varepsilon$ numbers are countable, we need only the following fact:

Suppose $\gamma$ is a countable limit ordinal, and for each $\alpha<\gamma$, $\varepsilon_\alpha$ is countable. Then there exists a procedure which, given a nonzero $\beta\leq \gamma$ and a sequence $f_\alpha$ enumerations of respective $\varepsilon_\alpha$ for $\alpha<\beta$, yields a unique enumeration $f_\beta$ of $\varepsilon_\beta$.

Proof

1. Fix an enumeration $\Gamma$ of $\gamma$, and a bijection $\Omega:\omega\times\omega\to\omega$, and another $\varphi:\omega^\omega\to\omega$.
2. Choose arbitrary nonzero $\beta\leq\gamma$ and a sequence of enumerations $f_\alpha:\varepsilon_\alpha\to \omega$.

3. If $\beta$ is a successor:

   • Put $\eta:\varepsilon_{\beta-1}+1\to\omega$ defined by $\eta(\varepsilon_{\beta-1})=0$, $\eta(\alpha)=f_{\beta-1}(\alpha)+1$ for $\alpha<\varepsilon_{\beta-1}$.
   • Construct a sequence $\alpha_0=\varepsilon_{\beta-1}+1,\alpha_{j+1}=\omega^{\alpha_j},j<\omega$, along with a sequence of enumerations $\eta_j:\alpha_j\to\omega$ as described in the first lemma, using $\varphi$ fixed above.
   • Then, put $g_1:\varepsilon_\beta\to\bigsqcup_{i<\omega} \alpha_i\subseteq \omega \times \varepsilon_\beta$ defined by $g_1(x)=(n_x,x)$ where $n_x$ is the least number $n$ such that $x\in \alpha_n$
   • Put $g_2:\bigsqcup_{i<\omega} \alpha_i\to \omega\times\omega$ defined by $g_2(n,x)=(n,\eta_n(x))$.
   • Then $\Omega\circ g_2\circ g_1:\varepsilon_\beta\to\omega$ is injective and we're done.

4. If $\beta$ is limit:

   • put $h_1:\varepsilon_\beta \to \bigsqcup_{\alpha<\beta} \varepsilon_\alpha\subseteq \beta \times \varepsilon_\beta$ defined by $h_1(x)=(\zeta_x,x)$ where $\zeta_x$ is the least $\zeta$ such that $x\in \varepsilon_\zeta$.
   • Put $h_2:\bigsqcup_{\alpha<\beta} \varepsilon_\alpha\to \omega\times \omega$ defined by $h_2(\zeta,x)=(\Gamma(\zeta),f_\zeta(x))$.
   • Then $\Omega\circ h_2\circ h_1:\varepsilon_\beta\to \omega$ is injective and we're done.

This should, with small modifications, show that $\lvert \varepsilon_\alpha\rvert=\lvert \alpha\rvert+\aleph_0$

Solution 2:

Indeed you do not need the axiom of choice to prove that $\epsilon_\alpha$ is countable for every countable ordinal $\alpha$.

To see this, observe first that the meaning of $\epsilon_\alpha$ is the same in the set-theoretic universe $V$ as it is in $L$, where ZFC holds. Furthermore, in ZFC an elementary proof by transfinite induction shows that the cardinality of the ordinal $\epsilon_\alpha$ is precisely $\max\{|\alpha|,\omega\}=|\alpha+\omega|$. Your observation about $\epsilon_0$ is simply the first case of this, with the later cases not really any more difficult. Combining these two observations, in $V$ with only ZF we get a bijection between $\epsilon_\alpha$ and $\alpha+\omega$, and so if $\alpha$ is countable in $V$---whether or not it is countable in $L$---then so is $\alpha+\omega$ and we conclude that $\epsilon_\alpha$ is countable in $V$, as desired.

To respond to your comment below, let me describe a direct argument showing that $\omega^\alpha$ is countable whenever $\alpha$ is, without using the axiom of choice and without appealing to the constructible universe $L$.

One may proceed as follows. The ordinal $\omega^\alpha$ is precisely the order type of the finite support functions from $\alpha$ to $\omega$, where finite support means that only finitely many values are non-zero, ordered lexically as in our manner of ordering numbers by their digits. This is like a base-$\omega$ representation of the ordinals, using representations with $\alpha$ many digits (but only finitely many non-zero digits). That $\omega^\alpha$ is the order type as described can be proved by transfinite induction. Now, the point is that without AC we can prove that there are only countably many finite functions from a countable set to $\omega$, and thus $\omega^\alpha$ is countable whenever $\alpha$ is.

I believe that one may also develop such a concrete representation of $\epsilon_\alpha$, and use this concrete representation to prove that $\epsilon_\alpha$ is countable whenever $\alpha$ is, but I will leave this task for someone else, who will surely post it before long...