3
$\begingroup$

I managed to prove that given the axiom of choice, the class (or is it a set?) of countable ordinals is closed under exponentiation, since the axiom of choice implies that the countable union of countable sets is countable (although this is not true in ZF).

I managed to prove that $\omega^\omega$ is countable in ZF by comparing it to the set of polynomials in $\omega$ with natural coefficients, but am struggling to extend it to more general ordinals.

Any help would be most welcome. Thank you in advance

$\endgroup$
0

3 Answers 3

4
$\begingroup$

You're right that in ZF, the countable union of countable sets need not be countable. However, the countable union of counted sets is always countable: that is, if I have countably many sets $A_i$, and a set of injections $f_i: A_i\rightarrow \omega$, then $\bigcup A_i$ is indeed countable. The weird examples come when I have (in some model of ZF) a countable collection $\{A_i\}$ of countable sets, but I don't have a set of injections of the $A_i$s into $\omega$.

So the goal is to make $\alpha^\beta$ explicitly counted. Specifically:

Can you find an injection from $\alpha^\beta$ to $\omega$, given injections $f: \alpha\rightarrow\omega$ and $g:\beta\rightarrow\omega$?

HINT: it will be easier to do this if you work with the "explicit" description of ordinal exponentiation - that $\alpha^\beta$ is the set of all maps $\beta\rightarrow\alpha$ which are nonzero at only finitely many values, ordered lexicographically . . .

Note that the "given $f$ and $g$" can't be done away with: it is consistent with ZF that there is no map $H$ from $\{$countable ordinals$\}$ such that $H(\alpha)$ is an injection from $\alpha$ into $\omega$, that is, there's no "canonical" way to count each countable ordinal. (Indeed, such an $H$ existing implies that the union of countably many countable ordinals is countable - that is, that $\omega_1$ is regular!)

$\endgroup$
3
  • $\begingroup$ I didn't know about the "explicit" description before this - if I am reading it right (two maps are compared starting from the least significant ordinal), it doesn't seem like the lexicograhical ordering makes use of $f$ or $g$. Could you go into more detail here? $\endgroup$
    – HappyFeet
    Apr 26, 2016 at 0:19
  • $\begingroup$ @HappyFeet The lexicographic ordering itself doesn't make use of $f$ or $g$. However, it's also not what you want - you want a bijection between $\alpha^\beta$ and $\omega$! The point is to combine $f$ and $g$ with this explicit description. $\endgroup$ Apr 26, 2016 at 0:27
  • $\begingroup$ Would it go something like this: we can identify $\alpha^\beta$ with the set of all finite partial maps $\beta \rightarrow \alpha$ and thus with all finite sequences in $\beta \times \alpha$, and using $f$ and $g$, with the set of all finite sequences in $\omega \times \omega$. Since the set of finite sequences in $\omega \times \omega$ is countable, we are done. $\endgroup$
    – HappyFeet
    Apr 26, 2016 at 9:00
1
$\begingroup$

Here is a terribly indirect of proving this.

Supoose $\alpha, \beta$ are countable ordinals. Therefore there is a function $f$ with domain $\omega$, such that the even integers are in bijection with $\alpha$ (using $f$) and the odd numbers with $\beta$. In $L[f]$ we have that:

  1. $f$ is an element, so $\alpha$ $\beta$ are countable.
  2. $\sf ZFC$ holds.
  3. Ordinals and their arithmetic is the same as in $V$. It is easy to prove for addition, then use induction to get multiplication and exponentiation.

Therefore $\alpha^\beta$ is countable in $L[f]$, so the witness for countability lies there, and therefore in $V$.

$\endgroup$
7
  • $\begingroup$ The OP already knows that ZFC proves this. That is how the question begins. $\endgroup$
    – Asaf Karagila
    Apr 26, 2016 at 6:00
  • $\begingroup$ Oops, missed that. (Although of course to use this the OP needs to show that $L[f]$ always satisfies ZFC . . . :P) $\endgroup$ Apr 26, 2016 at 6:01
  • $\begingroup$ I said terribly indirect, and I meant it! $\endgroup$
    – Asaf Karagila
    Apr 26, 2016 at 6:02
  • 1
    $\begingroup$ (Also relevant, and shameless self promoting, arxiv.org/abs/1402.3048) $\endgroup$
    – Asaf Karagila
    Apr 26, 2016 at 6:06
  • $\begingroup$ Dammit, I had stuff I was supposed to do tomorrow . . . $\endgroup$ Apr 26, 2016 at 6:07
-1
$\begingroup$

The following argument is overkill and probably not helpful to you. However, I thought I'd add it anyways - just for the heck of it.

It's easy to verify that ordinal arithmetic (i.e. addition, multiplication, exponentiation) is absolute between transitive models of $\operatorname{ZF}^{-}$. In particular, for any $\alpha, \beta < \omega_{1}$, we may calculate $\alpha^\beta$ in $L_{\omega_1}$ and obtain the correct value. Since $L_{\omega_1} \cap \operatorname{On}= \omega_1$, this implies that $\alpha^\beta$ is countable.

$\endgroup$
7
  • $\begingroup$ How exactly do you show that ordinal exponentiation is absolute between transitive models of $ZF^-$ without already answering the question? $\endgroup$ Apr 25, 2016 at 19:35
  • $\begingroup$ @NoahSchweber By proving that the recursive definition is absolute, which is quite trivial. $\endgroup$ Apr 25, 2016 at 20:34
  • $\begingroup$ That's not enough - you need to also show that it doesn't move you outside of a transitive model of $ZF^-$. This is implicit in the statement "we may calculate $\alpha^\beta$ in $L_{\omega_1}$." But showing this is essentially solving (a more general version of) the problem. $\endgroup$ Apr 25, 2016 at 20:46
  • $\begingroup$ @NoahSchweber No, you don't. The recursion theorem is provable in $\operatorname{ZF}^{-}$. In particular, for any ordinals $\alpha, \beta \in L_{\omega_1}$ we can prove that there is some $\gamma$ such that $L_{\omega_{1}} \models \alpha^\beta = \gamma$. However, since this recursion is absolut between transitive models of $\operatorname{ZF}^{-}$, $\gamma$ is actually $\alpha^\beta$ (from $V$'s point of view). In particular, since $L_{\omega_{1}}$ only contains countable ordinals, it follows that $\alpha^\beta$ is countable. $\endgroup$ Apr 25, 2016 at 20:50
  • $\begingroup$ Why is the recursion theorem provable in $ZF^-$? It is, of course, but to actually prove it in $ZF^-$ you need to do . . . about the same amount of work as solving the problem! Your overkill solution relies on doing about the same amount of work, under the hood. $\endgroup$ Apr 25, 2016 at 21:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .