Cardinality and existence of injections

[jostpuur]

How do you prove that if [itex]\textrm{card}(X)\leq\textrm{card}(Y)[/itex] is not true, then [itex]\textrm{card}(X)\geq\textrm{card}(Y)[/itex] must be true?

In other words, if we know that no injection [itex]X\to Y[/itex] exists, how do we prove that an injection [itex]Y\to X[/itex] must exist?

This is not the same thing as what Cantor-Bernstein-Schroeder theorem answers, right?

 

[micromass]

How do you prove that if [itex]\textrm{card}(X)\leq\textrm{card}(Y)[/itex] is not true, then [itex]\textrm{card}(X)\geq\textrm{card}(Y)[/itex] must be true?

In other words, if we know that no injection [itex]X\to Y[/itex] exists, how do we prove that an injection [itex]Y\to X[/itex] must exist?

This is not the same thing as what Cantor-Bernstein-Schroeder theorem answers, right?

Hi jostpuur!

The answer I could give you depends on what you already know about set theory. The thing you mention is called "the trichotomy law for cardinals" and it is equivalent to something called "the axiom of choice".

There are several ways to prove the trichotomy law. The easiest way seems by using Zorn's lemma:

Let X and Y be arbitrary sets. We want an injection [itex]X\rightarrow Y[/itex] or [itex]Y\rightarrow X[/itex]. We must find a partial ordering such that the injections are the maximal objects, on this partial ordering, we would apply Zorn's lemma.
Let
[tex]F=\{f~\vert~f~\text{is an injection with}~Dom(f)\subseteq X,~Im(f)\subseteq Y\}[/tex]
And order F by
[tex]f\leq q~\Leftrightarrow~Dom(f)\subseteq Dom(g)~\text{and}~\forall x\in Dom(f):f(x)=g(x)[/tex]
Now we apply Zorn's lemma on F with this ordering and we find an injection f such that either [itex]Dom(f)=X[/itex] or [itex]Im(f)=Y[/itex]. In the first case, we have an injection [itex]X\rightarrow Y[/itex], in the second case, the inverse of f defines an injection [itex]Y\rightarrow X[/itex].
[/INDENT

Other proofs are also possible. For example, one can also show that the cardinality of every set is an "aleph", and since the alephs are totally ordered, so are the cardinalities of sets.​