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

-
Note that the ordinals (so also sets of ordinals) are intrisically well-ordered, so we don't need choice principles until we try to wellorder power sets of ordinals or their subsets... – tomasz Aug 11 '12 at 20:52
@tomasz: So it suffices to prove that a countable union of enumerated countable sets is countable? If so, go ahead and make that an answer, and I'll accept it. – Cameron Buie Aug 11 '12 at 21:11
I can't tell right away (and I don't even know if that is even true...), it still does not seem obvious to me, so I will refrain from that for now. :) Note that, while intrisically well-ordered, countable sets of ordinals may not be intrisically enumerated. It might follow, but I'm not sure how, if at all. – tomasz Aug 11 '12 at 21:17
@DamianSobota: I think read somewhere that there are models of ZF$\neg$C where the real numbers are a countable union of countable sets. – tomasz Aug 11 '12 at 23:43
@Damian: The Feferman-Levy model is such that both the real numbers and $\omega_1$ are countable union of countable sets (different sets, though); in the second Cohen model there is a countable family of pairs whose union is uncountable; there are many many many more examples of this sort of behavior too. – Asaf Karagila Aug 12 '12 at 6:20

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

-
Do you think there is any fairly straightforward way to prove this elementarily? In particular, is there any hope to that $\omega^\alpha$ is countable for countable $\alpha$ (that would be enough to show the fact at the very least for $\varepsilon_i$ for finite $i$)? – tomasz Aug 11 '12 at 23:50
My argument shows that $\omega^\alpha$ is countable whenever $\alpha$ is, without using AC. The point is that you may assume AC without loss of generality, since the meaning of $\omega^\alpha$ is absolute to $L$, where AC holds. But I see, perhaps you want a direct argument not using $L$? – JDH Aug 12 '12 at 0:01
I edited my answer to give a direct argument for the case of $\omega^\alpha$, and I believe that this kind of method can be pushed up to $\epsilon_\alpha$. – JDH Aug 12 '12 at 0:15
Thanks. :) I thought about pretty much the same thing, but I wasn't familiar with this definition of ordinal exponentiation, so I didn't want to use it without understanding it well by myself. Now that you have pointed out that it is just writing out in Cantor normal form, it seems obvious... – tomasz Aug 12 '12 at 0:17
Only one problem I have with this. Saying that $\varepsilon_\alpha$ is countable means that there exists a bijection between $\omega$ and $\varepsilon_\alpha$. While $\varepsilon_\alpha$ is certainly defined the same way in any model of ZF, and while there certainly exist such bijections for any countable $\alpha$ in $L$ or other models of ZFC, I don't see why such bijections must exist in all models of ZF. Can you shed any light on that? – Cameron Buie Aug 13 '12 at 17:10

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$

-
I fear that you've used some choice in your last proof, in step 2: "Choose... a sequence of enumerations...." Perhaps it's avoidable, and such a sequence can be constructed (or otherwise proven to exist), but I'm not sure we can necessarily conclude that $$\prod_{\alpha<\gamma}B(\omega,\varepsilon_\alpha)\neq\emptyset,$$ where by $B(X,Y)$ I denote the set of bijections $X\to Y$. Can you shed any light on that? – Cameron Buie Aug 13 '12 at 23:35
@CameronBuie: No, the sequence is "chosen" in the sense that it is the one supplied by hypothesis of the theorem, in the same way $\beta$ is "chosen". The proof really constructs all the objects by transfinite recursion, so you may rephrase it that way if it will make you more convinced. – tomasz Aug 13 '12 at 23:36
Ah! I misinterpreted the Theorem. That makes more sense. – Cameron Buie Aug 13 '12 at 23:37