# Sequence of surjections imply choice

I am reading a paper where a side remark said that if a sequence $\langle g_\beta\colon\omega\to\beta\mid\beta<\omega_1\rangle$ is a sequence of surjections then $\omega_1$ is regular.

I have tried to proved the regularity of $\omega_1$ from this sequence by taking $\displaystyle\beta=\bigcup_{n<\omega}\beta_n$ for some countable ordinals and showing that $\beta$ is countable, i.e. to construct a surjection from $\omega$ onto $\beta$.

Let $p(k)=(r,s)$ the Cantor pairing function (or any other bijection of $\omega$ with $\omega^2$) then $$F(n) = g_r(s) \text{ where } p(n)=(r,s)$$

Then we have that for every $\alpha<\beta$ there is some $n<\omega$ such that $\alpha<\beta_n$, therefore $\alpha\in\operatorname{Rng}(g_n)$ therefore there is some $m<\omega$ such that $g_n(m)=\alpha$ and so $F(p^{-1}(n,m))=g_n(m)=\alpha$.

My question is (now that I have proved this fact) why this sequence of surjections cannot be created without some choice?

It seems to me that despite the fact that $\omega_1$ is singular, it is still true that for every $\alpha<\omega_1$ there exists a bijection with $\omega$. Can't there be some canonical choice of bijections?

For example, one can take $L^V$ where the GCH (and therefore choice) holds, define the sequence of surjections by taking the minimal in $<_L$ (the canonical ordering of $L$) for each ordinal.

Of course $\omega_1^L$ need not be $\omega_1^V$ but the argument why at some point all the bijections between countable ordinals and $\omega$ remain undefinable is unclear to me.

-

a. The existence of a sequence like this easily implies the existence of an $\omega_1$-sequence of distinct reals. But the existence of such a sequence contradicts the statement "all sets of reals have the perfect set property" (meaning, any set of reals is either countable or contains a perfect subset). To see this, note that if ${\mathfrak c}\ne\omega_1$, then the range of our sequence is a counterexample. Otherwise, the reals have size $\omega_1$, and an easy recursive construction allows us to build a set such that both it and its complement meet every perfect set (this is possible because there are ${\mathfrak c}$ many perfect sets). But then this set (a Bernstein set) contradicts the statement.
b. Another argument is by noting that using your sequence of bijections we can easily build an $\omega\times\omega_1$ Ulam matrix, thus showing that there are stationary subsets of $\omega_1$ whose complement is also stationary. Now, there are models of set theory without choice where $\omega_1$ is measurable and in fact every subset of $\omega_1$ either contains or is disjoint from a club set.
c. Finally, $\omega_1$ being singular is consistent. This holds, for example, in the Feferman-Levy model where the reals are a countable union of countable sets. (Note that the consistency strength used in a. is an inaccessible cardinal, in b. is a measurable cardinal, and in c. is just ZF.)
Andres: Thanks a lot, I am currently studying the Feferman-Levy model, and aware of the existence of a model in which $\omega_1$ is measurable. I was not aware of the perfect set property model, though. –  Asaf Karagila May 23 '11 at 16:17