16
$\begingroup$

I'm quite sure I'm missing something obvious, but I can't seem to work out the following problem (web search indicates that it has a solution, but I didn't manage to locate one -- hence the formulation):

Prove that there exists a surjection $2^{\aleph_0} \to \aleph_1$ without using the Axiom of Choice.

Of course, this surjection is very trivial using AC (well-order $2^{\aleph_0}$). I have been looking around a bit, but an obvious inroad like injecting $\aleph_1$ into $\Bbb R$ in an order-preserving way is impossible.

Hints and suggestions are appreciated.

$\endgroup$
1
  • $\begingroup$ Huh, the question and both answers received a downvote now. I wonder... $\endgroup$
    – Asaf Karagila
    Aug 10, 2017 at 12:20

2 Answers 2

18
+100
$\begingroup$

In what follows, by a "real", I mean a subset of $\omega\times\omega$, that is, a binary relation on $\omega$. (You can start with a bijection $\pi:\mathbb R\to\mathcal P(\omega\times\omega)$, which can be constructed without choice, so this is fine.)

If this relation happens to be a well-order of $\omega$ in order type $\omega+\alpha$, map the real to $\alpha$. Otherwise, map the real to $0$. This map is a surjection.

By the way, without choice, you cannot inject $\aleph_1$ into $\mathbb R$.

$\endgroup$
9
  • 1
    $\begingroup$ Why not map an order type of $\alpha$ to $\alpha$? Why write it as $\omega + \alpha$? (I mean, why ignore the subsets of $\omega\times \omega$ encoding finite well orders?) $\endgroup$ May 31, 2013 at 16:41
  • $\begingroup$ Thank you. As I expected, it wasn't really hard, just an idea eluding me. $\endgroup$
    – Lord_Farin
    May 31, 2013 at 16:44
  • 1
    $\begingroup$ @JasonDeVito It is not important. I did it this way simply so I didn't have to say something to distinguish a well-order of $0$ from one of $1$ (both give empty relations). $\endgroup$ May 31, 2013 at 16:44
  • 1
    $\begingroup$ @AndresCaicedo Late to the game, but you can avoid the "order type 0/1" problem by using reflexive well-orders instead of irreflexive well-orders (for which order type zero is the empty set and order type 1 is a singleton of an ordered pair). $\endgroup$ May 16, 2015 at 3:57
  • 1
    $\begingroup$ @MarioCarneiro Sorry for the late reply. Yes, thank you, this simple change avoids the issue. (We map a reflexive well-ordering of a subset of $\omega$ to its order type, and all other binary relations to $0$.) $\endgroup$ Aug 10, 2017 at 17:02
13
+50
$\begingroup$

One of my favorite ways is to fix a bijection between $\Bbb N$ and $\Bbb Q$, say $q_n$ is the $n$th rational.

Now we map $A\subseteq\Bbb N$ to $\alpha$ if $\{q_n\mid n\in A\}$ has order type $\alpha$ (ordered with the usual order of the rationals), and $0$ otherwise.

Because every countable ordinal can be embedded into the rationals, for every $\alpha<\omega_1$ we can find a subset $\{q_i\mid i\in I\}$ which is isomorphic to $\alpha$, and therefore $I$ is mapped to $\alpha$. Thus we have a surjection onto $\omega_1$.

$\endgroup$
24
  • $\begingroup$ “Every countable ordinal can be embedded into the rationals” — is this true without choice? The standard proof of it I know uses (countable) choice, and I can’t see how to do without. $\endgroup$ May 31, 2013 at 19:30
  • 2
    $\begingroup$ Peter, yes. It's true without the axiom of choice. You use transfinite induction over the ordinals. There is absolutely no use of countable choice. $\endgroup$
    – Asaf Karagila
    May 31, 2013 at 19:57
  • 2
    $\begingroup$ @Asaf The confusion IMO arose because you said "Induction" where you meant "Recursion". Peter's approach inducts over "there exists an embedding of $\alpha$ in $\Bbb Q$" and this argument, in its most natural form, requires choice. Whereas the recursive approach can avoid choice by using a fixed order-preserving bijection $\Bbb Q \to (0,1)$ (I think; there may be an issue with selecting a cofinal sequence without choice). So you were actually discussing different things. $\endgroup$
    – Lord_Farin
    May 31, 2013 at 23:06
  • 1
    $\begingroup$ I didn't say it was possible to avoid the confusion; I merely tried to put my finger on the cause. But it's bedtime; perhaps it could be insightful to have a QA pair address this, seeing as it causes extended confusion. But that's for tomorrow. $\endgroup$
    – Lord_Farin
    May 31, 2013 at 23:12
  • 1
    $\begingroup$ I think the real point is that $\mathbb Q$ is universal in the sense that any countable linear order embeds into $\mathbb Q$. This has nothing to do with ordinals, and is proved by recursion (on an enumeration of the given linear order), with choice not playing a role anywhere ($\mathbb Q$ is countable, so there are canonical ways of choosing elements at each stage of the recursion); the argument resembles (but is simpler than) the well-known back-and-forth proof that any countable dense linear order without endpoints is isomorphic to $\mathbb Q$. $\endgroup$ Aug 2, 2017 at 17:16

You must log in to answer this question.

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