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.

... $\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$?

share|improve this question
1  
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
add comment

2 Answers

up vote 11 down vote accepted

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.

See, for example, Relationship between Continuum Hypothesis and Special Aleph Hypothesis under ZF


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

share|improve this answer
    
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
show 2 more comments

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

share|improve this answer
1  
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. –  Arthur Fischer 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
1  
@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. –  Arthur Fischer 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
add comment

Your Answer

 
discard

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.