Given a set $A$ with cardinality $c$, there is a subset of $A$ having any cardinality less than $c$.

There is an injection from the subset $B$ to the set $A$, namely, the identity in which each element of $B$ maps to itself in $A$ (no axiom of choice needed; it is like choosing from pairs of shoes).

For $C$ a subset of $B$, and $B$ a subset of $A$, if $C$ and $B$ have different cardinality the identity injection shows this and also which one is smaller. The same can be applied to a set with size $2^c$ (the power set of $A$), and so on.

In this way all the cardinalities that are reached by Cantor's theorem are comparable. In a set of these cardinalities, that one which has an injection into all the others is least, so they are well ordered also. Cantor's Theorem reaches to aleph-omega, and large cardinal axioms are needed to go beyond that, so where is room left for incomparable cardinalities?

If one existed it would have to be the cardinality of a subset of one of the above cardinalities, so, it would be comparable to the others. Where am I going wrong?

  • $\begingroup$ What do you mean by "cardinalities that are reached by Cantor's theorem"? How do you compare $2^{\aleph_0},$ the cardinality of the set of all real numbers (or the set of all sets of natural numbers) with $\aleph_1,$ the cardinality of the set of all countable ordinal numbers? $\endgroup$ – bof Sep 1 '15 at 3:31
  • $\begingroup$ It is not at all like choosing from pairs of shoes, but it is still easy. $\endgroup$ – Cameron Buie Sep 1 '15 at 3:45
  • $\begingroup$ The axiom of choice(AC) is equivalent to "All sets are cardinally comparable", but without it your first sentence is not even meaningful. because "having cardinal less than c" may not mean anything for a set which is not a subset of A. It is consistent, without AC, that $2^{Aleph_0}$ and $Aleph_1$ are incomparable. $\endgroup$ – DanielWainfleet Sep 1 '15 at 3:56

If we let $\beth_0=\aleph_0$, $\beth_{\alpha+1}=2^{\beth_\alpha}$, and $\beth_\lambda=\sup_{\alpha<\lambda} \beth_\alpha$ for $\lambda$ a limit, then we certainly have $\alpha<\beta\iff\beth_\alpha<\beth_\beta$. Since the ordinals are linearly ordered, this means the cardinals of the form $\beth_\alpha$ are linearly orderd. So any two cardinals of this type are comparable. (I presume this type of cardinal is what you mean when you say " . . . reached by Cantor's theorem.")

The problem is, how do we know that every cardinal is of this type? The answer is, we don't - it is consistent with $ZF$ (in fact, with $ZFC$) that there are cardinals which are not equal to $\beth_\alpha$ for any $\alpha$. More generally, we can easily come up with a really big family of cardinals, any two of which are comparable - but we can't use this to conclude that every pair of cardinals are comparable, unless we can show that this family contains all the cardinals. And it turns out that we can't do that - at least, not in $ZF$ alone.

You can show that the $\beth$-numbers are cofinal - every cardinal is $<\beth_\alpha$ for some ordinal $\alpha$. However, this doesn't wind up telling us much. Concretely, it is consistent with $ZF$ that there are two sets of real numbers, $A, B\subseteq\mathbb{R}$, such that neither is smaller (i.e., can inject into) the other. Certainly both $A$ and $B$ are uncountable $(>\beth_0)$ and smaller than the size of $\mathbb{R}$ itself ($<\beth_1$) - the problem is, this ultimately doesn't tell us very much about $A$ and $B$ at all.

By the way, the $\beth$ cardinals might not be all the cardinals even if the axiom of choice does hold! The statement "all cardinals are of the form $\beth_\alpha$ for some ordinal $\alpha$" is a consequence of the Generalized Continuum Hypothesis, known to be independent from $ZFC$. The biggest family of "well-behaved" cardinals are the $\aleph$ numbers - the cardinalities of the ordinals. Since the ordinals are linearly ordered, any two $\aleph$-numbers are comparable; and the axiom of choice is equivalent to the statement, "every cardinal is an $\aleph$."


I'm not sure what you mean by "cardinalities that are reached by Cantor's theorem"; this is not standard terminology (as far as I know), so it's up to you to define what you mean by it.

Your assertion that "large cardinal axioms are needed" to go beyond $\aleph_\omega$ is probably based on a misunderstanding, unless you consider the axiom of replacement a large cardinal axiom.

I will give you an example of two sets which are not obviously comparable. Let $\omega$ be the set of all finite ordinals, which you may identify with the nonnegative integers.

One of the two sets is the power set $\mathcal P(\omega)$, the set of all subsets of $\omega$; its cardinality is $2^{\aleph_0},$ which is also the cardinality of the set $\mathbb R$ of all real numbers.

Let $W$ be the set of all well-ordering relations on $\omega.$ That is, an element of $W$ is a subset of $\omega\times\omega$ which satisfies certain conditions; I suppose you know what those conditions are, since you mentioned well-ordered sets in your question. Thus $W\subseteq\mathcal P(\omega\times\omega).$

Define an equivalence relation on the set $W,$ calling two elements $R_1,R_2\in W$ equivalent if $(\omega,R_1)$ and $(\omega,R_2)$ are isomorphic as ordered sets. Let $\Omega$ be the set of all equivalence classes for this equivalence relation. Thus $\Omega\subseteq\mathcal P(\mathcal P(\omega\times\omega)).$ The cardinality of the set $\Omega$ is called $\aleph_1.$

Do you consider $\mathcal P(\omega)$ and $\Omega$ sets whose cardinalities "can be reached by Cantor's theorem"? If so, how do you prove, without using the axiom of choice, that their cardinalities are comparable? That is, how do you construct an injection from one of those sets into the other? (You may as well concentrate your efforts on finding an injection from $\Omega$ into $\mathcal P(\omega),$ as that is the easier task.)

  • $\begingroup$ Note that $\aleph_1$ and $2^{\aleph_0}$ are comparable in the sense that there is a surjection from one to the other, although this is a much weaker notion of comparability. It is consistent with $ZF$, though, that even this fails: we can have two sets $A$ and $B$ (of reals, even!) such that neither surjects onto the other (or injects into the other, a fortiriori). $\endgroup$ – Noah Schweber Sep 1 '15 at 4:15

There is a fine point that you miss. You are not defining cardinals one by one. You are given a universe of set theory, with or without choice, and in this set theoretic universe you have cardinals using a definition that "works in every universe".

Are these cardinals totally ordered or not? That depends on the universe and its properties. But you're not defining and creating the set one by one. You were given these sets by a higher power, e.g. Macho Man Randy Savage.

Now you want to ask yourself, suppose our higher power told us that the axiom of choice failed, still $\aleph_0<2^{\aleph_0}<2^{2^{\aleph_0}}<\ldots$ is provable. Where are all the incomparable cardinals?

  1. The power set operation need not return well-ordered cardinals. We can prove that $\aleph_1$ exists without using the axiom of choice. But without this assumption, there might not be an injection from $\aleph_1$ to $2^{\aleph_0}$, and this would mean that the two cardinals are incomparable.

  2. What we described above is just one chain of length $\omega$. The cardinals make a proper class. What happens after this chain? Well. It could be that there is a unique least upper bound to the chain. It is consistent that there are $\omega$-chains with uncountably many incomparable upper bounds.

And in any case, just because $\aleph_0<2^{\aleph_0}$ does not mean that there are no other cardinals which are not $\aleph_0$ (or smaller) which are below the continuum.

The point is what the assumptions on your universe let prove. The universe itself is given. If you are just given $\sf ZF$, you cannot prove nor disprove the totality of the order of the cardinals. Despite the fact that exactly one of these options can happen, you just have no means knowing which one.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.