# 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 ?

-
If $|A|\leq|B|$ and $|B|\leq|A|$ then $|A|=|B|$. Is this question just having you prove that you can compare the cardinality of sets? – emka Jan 2 '13 at 2:55
I know that $|A|\leq|B|,|B|\leq|A|\implies|A|=|B|$ This is the Schroeder-Bernstein Theorem. – Amr Jan 2 '13 at 2:57
I will put my statment more formally in the question – Amr Jan 2 '13 at 2:57
I am fairly certain that I have answered this at least this question at least twice on the site before. – Asaf Karagila Jan 2 '13 at 10:53
Here are some examples: math.stackexchange.com/questions/151904 math.stackexchange.com/questions/180951 math.stackexchange.com/questions/69774 and there are probably a couple more which are reasonably applicable. – Asaf Karagila Jan 2 '13 at 18:55

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.

-
It is more commonly known as the trichitomy. The abbreviation PCC is Partial Countable Choice in some places. – Asaf Karagila Jan 2 '13 at 10:52
@Asaf, I was using the terminology from the book I link to. – Ittay Weiss Jan 2 '13 at 11:06
I see. It's like how there is AMC in algebraic set theory which is completely different than AMC in material set theory. And those two abbreviations are actually the same name: axiom of multiple choice. – Asaf Karagila Jan 2 '13 at 11:09
Too many mathematical concepts to prevent dis-ambiguity. – Ittay Weiss Jan 2 '13 at 11:18

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.

-
your arguments use comparability of alephs leading to circularity. – Ittay Weiss Jan 2 '13 at 3:36
alephs are ordinals, and ordinals are comparable. You need $AC$ to show that the cardinal of a set is in a bijection with an aleph – Camilo Arosemena Jan 2 '13 at 3:41
I see! Nice solution! – Ittay Weiss Jan 2 '13 at 3:48

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

-
Asaf, could you please show me some links where I can find proofs of the results stated in your answer? Thanks. – Camilo Arosemena Jan 3 '13 at 1:42
Thanks for the nice answer (+1) – Amr Jan 3 '13 at 2:03
@CamiloArosemena: I think that the nicest place to see all this would be in my thesis which is not yet online. I will upload it soon and keep you posted. On my personal website (in the profile) you can find two blog posts which discuss these results as well. – Asaf Karagila Jan 3 '13 at 10:55
@CamiloArosemena: Let me know if you have read anything I wrote; and/or what you thought about it. The last sentence about the finite width of $\leq^\ast$ is a theorem of mine from my thesis. I hope to post it sometime this week (but I can't promise)! – Asaf Karagila Jan 12 '13 at 23:20
hope to check it soon – Camilo Arosemena Jan 13 '13 at 17:07