For any two sets $A,B$ , $|A|\leq|B|$ or $|B|\leq|A|$

Let $A,B$ be any two sets. I really think that the statement $|A|\leq|B|$ or $|B|\leq|A|$ is true. Formally:

$$\forall A\forall B[\,|A|\leq|B| \lor\ |B|\leq|A|\,]$$

If this statement is true, what is the proof ?

Solution 1:

This claim, the principle of cardinal comparability (PCC), is equivalent to the Axiom of Choice.

If the Axiom of Choice is true then Zorn's Lemma is true and a proof of the PCC is a classical application of Zorn's Lemma.

If PCC holds then using Hartogs' Lemma it is quite easy to show that The Well-Ordering-Princple holds, which in turn implies (easily) the Axiom of Choice.

A complete presentation of these (and some other) equivalences, is treated in a rather elementary fashion but including all the details, in the book: http://www.staff.science.uu.nl/~ooste110/syllabi/setsproofs09.pdf starting on page 31.

Solution 2:

This is true in $ZFC$ because of Zermelo's Well-Ordering Theorem; given two sets $A,B$, since they are well-orderable there exist alephs $\aleph_{\alpha},\aleph_{\beta}$ with $|A|=\aleph_{\alpha}$ and $|B|=\aleph_{\beta}$, since alephs are comparable, the cardinalities of $A$ and $B$ are comparable.

Furthermore, this is equivalent to the axiom of choice:

Now suppose the cardinalities of any two sets are comparable, let us prove Zermelo's Well-Ordering Theorem from this. Let $X$ be a set, then there must be an ordinal $\alpha$ such that $|X|\leq |\alpha|$, for otherwise the set of all ordinals equipotent to a subset of $X$ would contain the proper class of all ordinals; for all ordinals $\alpha$, $|\alpha|\leq |X|$ by the comparability condition, a contradiction. Hence $|X|\leq |\alpha|$ for some ordinal $\alpha$, and thus $X$ is well-orderable.

Hence the condition of comparability is equivalent to Zermelo's Well-Ordering Theorem, and thus it is equivalent to the axiom of choice.

Solution 3:

Your question was answered, but let me give you a much more general answer to your question.

The question asks whether or not the assumption that the class $(\rm Card,\leq)$ is linearly ordered implies the axiom of choice. The answer, as pointed, is yes. It follows from Hartogs theorem that every set can be well-ordered, and therefore the axiom of choice is true in such model.

There are two questions to ask further. Suppose we replace $\leq$ by $\leq^\ast$ which is the ordered defined by surjections, namely $|A|\leq^\ast|B|$ if and only if there is a surjection from a $B$ onto $A$, or if $A$ is empty. It is clear that assuming the axiom of choice $|A|\leq^\ast|B|$ if and only if $|A|\leq|B|$. However without the axiom of choice this is not true anymore and there are plenty of models where there are sets which can be mapped onto strictly larger sets.

It is further troublesome because $\leq^\ast$ need not be a partial order without the axiom of choice. While in ZF $|A|\leq|B|$ and $|B|\leq|A|$ imply together $|A|=|B|$ (this is the Cantor-Bernstein theorem), this is not true for $\leq^\ast$, and we can find models of ZF with two sets $A,B$ such that $|A|\leq^\ast|B|$ and vice versa, but $|A|\neq|B|$.

But we can still ask whether or not the assumption: $$\forall A\forall B(|A|\leq^\ast|B|\lor|B|\leq^\ast|A|)$$ implies the axiom of choice is true. The answer is yes, and this was proved by Lindenbaum in 1924 (although the first proof published only came 24 years later and was given by Sierpinski).

The proof is similar to the one derived from Hartogs theorem. We show that there is an ordinal $\kappa$ such that $\kappa\nleq^\ast|A|$, and therefore $|A|\leq^\ast\kappa$, and surjections from ordinals can be inversed and therefore $A$ inherits a well-order.

The second question is more order-theoretic in its nature. Linear orders do not permit antichains (except singletons, but we can disregard those for the sake of argument). So asking whether or not the cardinals are linearly ordered is asking whether or not there are no proper antichains of cardinals.

But what if we allow antichains? Is it possible to have a model in which there are two incomparable cardinals, but not three? What about a model in which there are $k$ incomparable cardinals, but not $k+1$?

It turns out that if we assert that every antichain is bounded by $k$, for any finite $k>1$, then the axiom of choice holds. Namely if whenever we are given $k$ sets there are two which are comparable in cardinality, then the axiom of choice holds. The proof of that was given by Tarski in 1964, and was rediscovered by Feldman, Orhon and Blass in 2007. I should remark that Feldman and Orhon gave one proof, and Blass gave another which is closer to Tarski's original proof.

Then we can ask whether or not this result carries to $\leq^\ast$, and this is also true. If between every $k$ sets there are two which are comparable in the $\leq^\ast$ order then the axiom of choice is true. Again this is true for every finite $k$, $k>1$.