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.

I encountered the following problem: If you sort sets by the following: $$A\lt B:\Leftrightarrow \exists f:A\rightarrow B\; injective,\quad \nexists g:B\rightarrow A \; injective$$ You receive the standard order of sets. Now obviously, $$\emptyset\le\{1\}\le\{1,2\}\le...\le\mathbb{N}\le\mathbb{R}\le\mathbb{R}^\mathbb{R}\le\mathbb{R}^{\mathbb{R}^\mathbb{R}}$$ Does the continuum hypothesis imply that there are no sets "inbetween" $\mathbb{R}$ and $\mathbb{R}^\mathbb{R}$, in other words, $$\nexists A: \mathbb{R}\lt A\lt\mathbb{R}^\mathbb{R}$$ and so on ($\nexists A: \mathbb{R}^\mathbb{R}\lt A\lt\mathbb{R}^{\mathbb{R}^\mathbb{R}}$)?

Does this order continue on and on, where a $\mathbb{N}$ gets replaced by a $\mathbb{R}$ and every second step, a $\mathbb{N}$ is added?

I am asking because I always saw the (aleph-) notation $\aleph_1:=2^{\aleph_0}$ but that doesnt tell me too much about this question; Basically my question is are $\aleph_n \;n\in\mathbb{N}_0$ all of the cardinalities there are? Is $|\mathbb{R}^{...^\mathbb{R}}|=\aleph_{k}$?

share|improve this question
Look here! –  Mauro Porta Dec 9 '12 at 12:10
add comment

2 Answers

up vote 3 down vote accepted

First of all, it is true that $|\mathbb R|=|\mathbb{R^N}|$ without any additional assumption beyond ZF.

Secondly, the usual order is by existence of injection rather than surjections. The reason is simple: without the axiom of choice the Cantor-Bernstein theorem still holds, so if there are injections from and to $A$ and $B$, then there is a bijection. The same does not hold for surjections without the axiom of choice. If we do assume choice, then the existence of an injection implies the existence of a surjection in the other direction. Let's assume the axiom of choice because it's going to make things slightly simpler.

The Continuum Hypothesis states that there is no set whose cardinality is strictly between the natural numbers and the real numbers. Alternatively this means that every uncountable set can be mapped onto the real numbers. The statement using aleph numbers would be $$\mathsf{CH}: 2^{\aleph_0}=\aleph_1$$

We could ask what about $\aleph_1$, namely does $2^{\aleph_1}=\aleph_2$? We can denote that as $\mathsf{CH}_1$, and more generally if $\alpha$ is an ordinal then $\mathsf{CH}_\alpha$ is the statement $2^{\aleph_\alpha}=\aleph_{\alpha+1}$.

The Generalized Continuum Hypothesis states $\forall\alpha.\mathsf{CH}_\alpha$. Namely, for all $\alpha$, $2^{\aleph_\alpha}=\aleph_{\alpha+1}$.

These ordinals, I should add, span much beyond the natural numbers. But they have a structure somewhat similar to them in some sense.

It is unprovable whether or not $\mathsf{CH}_\alpha$ holds for any $\alpha$, and we can produce models of ZFC in which it holds, and others in which it fails.

share|improve this answer
How do you create a bijection between $\mathbb{R}$ and $\mathbb{R}^\mathbb{N}$? I thought this were impossible... –  CBenni Dec 9 '12 at 12:46
Aside from that, thank you for clarifying this, we have yet to handle NSA in our studies, therefore, I dont know all to much; Your explanation was very comprehensible anyways. –  CBenni Dec 9 '12 at 12:54
I'm not sure what NSA means in this context. Non-standard analysis has (generally) little to do with the continuum hypothesis or ordinals. –  Asaf Karagila Dec 9 '12 at 17:56
add comment

There are a couple of issues here. First, your definition of $A>B$ is not necessarily equivalent to the usual definition of $|A|>|B|$ if the axiom of choice is not assumed. For the usual definition you want an injection from $B$ to $A$ but no injection from $A$ to $B$.

Next, $\aleph_1$ is definitely not defined to be $2^{\aleph_0}$. $\aleph_1$ is the smallest uncountable well-ordered cardinality; the statement that it is equal to $2^{\aleph_0}$, the cardinality of $\wp(\Bbb N),\Bbb N^{\Bbb N}$, and $\Bbb R$, is the continuum hypothesis, which is consistent with and independent of the usual axioms of set theory. It is consistent for $2^{\aleph_0}$ be almost any uncountable cardinal; it could be $\aleph_{\omega_1}$, for instance, which is far bigger than any of the $\aleph_k$ for $k\in\Bbb N$. In that case there would be uncountably many sizes between that of $\Bbb N$ and $\Bbb R$.

The cardinal numbers $\aleph_0,2^{\aleph_0},2^{2^{\aleph_0}}$, and so on form an increasing hierarchy sometimes denoted by $\beth_0,\beth_1,\beth_2$, and so on. The generalized continuum hypothesis is the assertion that $\beth_\xi=\aleph_\xi$ for each ordinal $\xi$; like the special case of the continuum hypothesis, it’s consistent with the usual axioms of set theory, but it’s also consistent that it fail badly. For more information see the Wikipedia article to which I linked above.

share|improve this answer
add comment

Your Answer


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.