# What's the difference between saying that there is no cardinal between $\aleph_0$ and $\aleph_1$ as opposed to saying that…

... $\aleph_1$ is the immediate successor of $\aleph_0$?

I was reading the wiki article on $\aleph_1$ where a distinction is made between the two. If there's isn't a cardinal between $\aleph_1$ and $\aleph_0$, the implication is that they must follow one another so why must one need AC to assert that $\aleph_1$ is the smallest after $\aleph_0$?

-
Without the axiom of choice, it is conceivable that there is a cardinal $\kappa$ such that $\aleph_0 < \kappa$ but neither $\aleph_1 \le \kappa$ nor $\kappa \le \aleph_1$. – Zhen Lin Dec 5 '12 at 11:50

It is consistent without the axiom of choice that there are uncountable sets which cannot be well-ordered, and every infinite set whose cardinality is smaller is necessarily countable. It could also be the case that there are smaller cardinalities, but none which are strictly between $\aleph_0$ and the uncountable set.

Indeed there are three different definitions of successor cardinals when the axiom of choice fails (although the existence of one [for every set] implies choice; there is another which is provable without choice; and a third which is independent).

It is consistent, if so, that there are several successors to $\aleph_0$. It is always true that $\aleph_1$ is the successor of $\aleph_0$, and that it is the minimal aleph above it.

In particular it is consistent that the real numbers form such set.

Edit: I have some free time so here are different variants of "successor". This is taken from Jech The Axiom of Choice (p. 163), the original definition is due to Tarski.

Let $\frak p$ and $\frak q$ be cardinals such that $\frak p<q$.

1. $\frak q$ is the $1$-successor of $\frak p$ if whenever $\frak m$ is such that $\frak p\leq m\leq q$ then $\frak p=m$ or $\frak q=m$.
2. $\frak q$ is the $2$-successor of $\frak p$ if whenever $\frak m$ is such that $\frak p < m$ then $\frak q\leq m$.
3. $\frak q$ is the $3$-successor of $\frak p$ if whenever $\frak m$ is such that $\frak m < q$ then $\frak m\leq p$.

Now we see that it is always true that $\aleph_1$ is a $1$- and $3$-successor of $\aleph_0$. However it is consistent that so are the real numbers themselves.

The assertion that $\aleph_1$ is a $2$-successor of $\aleph_0$ is equivalent to every uncountable set $X$ has an injection from $\omega_1$ into $X$. In fact just requiring that $\aleph_0$ has a $2$-successor is enough.

It is consistent that there are several $1$-successors to $\aleph_0$, and that there is a $1$-successor which is not $3$-successor.

For the real numbers it holds that if their cardinal is a $1$-successor of $\aleph_0$ then it is a $3$-successor of $\aleph_0$.

Interestingly, it is consistent that there is a proper class of $1$-successors to $\aleph_0$.

-
You wrote "it could also be the case that there are smaller cardinalities but none which are strictly between $\aleph_0$ and the countable of such set." It's not clear to me what those cardinalities are smaller compared to. And also, is the last line a typo and you were going for $\aleph_1$ in place of 'the countable of such set'? – Mark Dec 9 '12 at 15:31
@Mark: It is possible to have a cardinal $A$ which is a $1$-successor of $\aleph_0$, but there is some $B<A$ such that $B$ is incomparable with $\aleph_0$. This means that $A$ is not $3$-successor of $\aleph_0$. As for the alleged typo, I'm not sure where it is. – Asaf Karagila Dec 9 '12 at 17:59
The alleged typo was probably what Mark quoted. $\:$ There's also probably a typo either in Jech or in the bottom part of your answer; the definition of 1-successor currently does not require $\: \mathfrak{p} < \mathfrak{q}$. $\;\;$ How would one show your last sentence? $\:$ (The issue is Dedekind cardinals.) $\;\;\;\;$ – Ricky Demer May 9 '13 at 6:51
@Ricky: If you look at the edit history, you will see that I have corrected the typo he referred to. In any case you are right, I forgot the first line stating that $\frak p<q$; and there was another typo in the first definition. As for my last sentence -- which one in [the previous version of] the answer, or in the comment, or elsewhere? – Asaf Karagila May 9 '13 at 14:42
I knew you had corrected the typo he referred to; I just wanted to indicate that I thought he was not $\;$ referring to anything else. $\:$ Also, I meant "For the real numbers it ...". $\;\;\;$ – Ricky Demer May 9 '13 at 17:58

Generally $\aleph_1$ is the cardinal notation of the smallest infinite ordinal not in one-to-one correspondence with $\omega = \mathbb{N}$. As such, there is nothing between $\aleph_0$ and $\aleph_1$:

Suppose that $X$ were a set and $\aleph_0 \leq | X | < \aleph_1$. Then there is a one-to-one function $f : X \to \omega_1$, and we may use such a function to define a well-ordering of $A$: $x \leq y$ iff $f(x) \leq f(y)$. Then the order-type of this well-ordering must be strictly less than $\omega_1$, and so by definition of $\omega_1$ there must be a bijection from $X$ onto $\omega$, so actually $\aleph_0 = |X|$. (Note that the above argument did not use Choice anywhere.) Therefore $\aleph_1$ is an immediate successor of $\aleph_0$.

However, if you do not assume the Axiom of Choice, I do not think you can turn the an into the: i.e., it might be possible that $\aleph_0$ has an immediate successor different from $\aleph_1$. (It is certainly possible that there is a cardinal $\mathfrak{p} > \aleph_0$ such that neither $\mathfrak{p} \leq \aleph_1$ nor $\aleph_1 \leq \mathfrak{p}$ hold, but I am turning myself into knots trying to get an immediate successor of $\aleph_0$.) This is because if you do not assume the Axiom of Choice, then not all sets can be well-ordered, and the cardinality of a non-well-orderable set need not be comparable with a specific aleph, i.e., the cardinality of an ordinal.

• A common example (though not exactly the focus of this question) is an infinite Dedekind-finite set: a set $D$ which is not equinumerous to any finite set, but yet there is no injection $\omega \to D$. It follows that the cardinals $\aleph_0$ and $| D |$ are not comparable, since the required witnessing functions do not exist. (That $\aleph_0 \not\leq |D|$ is by definition of Dedekind-finite; that $|D| \not\leq \aleph_0$ follows because if there was an injection $f : D \to \omega$, the range of $f$ must be infinite, and we could use that to construct an injection $\omega \to D$.)

• Another common example is that $\mathcal{P} ( \mathbb{N} )$ need not be well-orderable. By Cantor's Theorem we know that $\aleph_0 = | \mathbb{N} | < | \mathcal{P} ( \mathbb{N} ) |$, but in this situation the cardinals $\aleph_1$ and $| \mathcal{P} ( \mathbb{N} ) |$ need not be comparable. Thus there must be at least two incomparable immediate successors of $\aleph_0$.

-
In your last paragraph it's not clear to me that "$\mathcal{P}(\mathbb{N})$ is incomparable with $\aleph_1$" implies that that $\aleph_0$ has an immediate successor besides $\aleph_1$". (Although it is consistent that $\mathcal{P}(\mathbb{N})$ is such a successor.) – Trevor Wilson Dec 5 '12 at 16:38
@TrevorWilson: My intuitions here a quite a bit weaker than Asaf's, and his input would likely (certainly?) be better; as it stands, I am half ready to delete. My original thought would be to take a infinite Dedekind-finite set $D \subseteq \mathbb{R}$. Of course, $\aleph_0 \not\leq | D |$, but we would have $\aleph_0 < |D| + \aleph_0$. By hope would be that some such $D$ could be found to make this sum an immediate successor which would have to be different than $\aleph_1$. But I must admit I am having trouble squaring this circle. – arjafi Dec 6 '12 at 10:41
@Arthur Fischer: In Set Theory by Thomas Jech, the author writes that "one cannot prove without the Axiom of Choice that $\omega_1$ is not a countable union of countable sets." That is to say, without AC, the uncountability of $\omega_1$ is unprovable. It negates what you wrote in the second paragraph that nowhere was AC used, doesn't it? – Mark Dec 6 '12 at 10:44
@Matt: NO! Some amount of Choice (Countable Choice) is required to show that countable unions of countable sets are countable. There are models of ZF (e.g.,the Feferman-Levy model) in which $\mathbb{R}$ is a countable union of countable sets. But the uncountability of $\mathbb{R}$ is a ZF theorem. The uncountability of $\omega_1$ is a definition. – arjafi Dec 6 '12 at 10:48
Arthur, you should make it more explicit. If $\mathbb R$ cannot be well-ordered it does not mean that CH holds. You need to require more (e.g. Solovay's model or Truss' variants which does not require inaccessible). – Asaf Karagila Dec 6 '12 at 11:14