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

-

## 1 Answer

You need some choice to prove that there is a sequence of surjections, although of course the existence of each individual surjection is for free.

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.

Now, there are models of set theory without choice where all sets of reals have the perfect set property, the best known being Solovay's model where all sets of reals are Lebesgue measurable.

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