Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
@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
1  
@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

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer
    
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$

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.