Proving $(A\le B)\vee (B\le A)$ for sets $A$ and $B$

For any pair of sets $A$ and $B$, we can define $A\le B$ iff there exists injection $f\colon A\rightarrow B$. I am trying prove that $$(A\le B)\vee (B\le A).$$

I have tried assuming $\neg (A\le B)$, then proving $B\le A$ by constructing the required injection, but I haven't been able to make any progress. Any hints, etc. would be appreciated.

EDIT

Assuming $\neg (A\le B)$, can you prove there exists a surjection $f: A\rightarrow B$? Then it would be easy, by applying AC, to construct an injection $g: B\rightarrow A$

Solution 1:

There is no way to construct a surjection without an appeal to the axiom of choice. If there was then we could have proved that between every two (non-empty) sets there exists a surjection in some direction. This already implies the axiom of choice.

So in order to carry out any construction you will have to tell us what sort of appeals to the axiom of choice you are willing to use.

• If you are willing to use Zorn's lemma then it will be easy to assume $\lnot(A\leq B)$ and show that the partial order $$\Big<\{f\subseteq B\times A\mid f\text{ is an injection}\},\subseteq\Big>$$ satisfies the condition that every chain is bounded (the increasing union of injections is an injection), and a maximal element must be an injection from $B$ into $A$.

• If you are willing to use the well-ordering theorem then it is just a matter of proving that if $\alpha$ and $\beta$ are ordinals, and $\alpha\nleq\beta$ then $\beta<\alpha$. So if $|A|=\alpha$ and $|B|=\beta$ we are done.

• If you only want to use the axiom of choice itself. Let $F_A,F_B$ be choice functions from the non-empty subsets of $A$ and $B$ respectively. Proceed by transfinite recursion to define a sequence of partial injections:

  1. $f_0=\varnothing$.
  2. If $f_\alpha$ was defined, let $f_{\alpha+1}=f_\alpha\cup\{\langle F_B(B\setminus\operatorname{dom}(f_\alpha)),F_A(A\setminus\operatorname{rng}(f_\alpha))\}$. Then $f_{\alpha+1}$ is an injection because $f_\alpha$ was an injection, and the only element we added to the range came from outside the range of $f_\alpha$.
  3. If $f_\alpha$ was defined for all $\alpha<\delta$, for a limit ordinal $\delta$ then $f_\delta=\bigcup_{\alpha<\delta} f_\alpha$. It is not hard to see that $f_\delta$ is an injection, otherwise some $\alpha<\delta$ would have witnessed otherwise, in contradiction to the induction hypothesis.

  Now we argue that the recursion has to stop because $A$ and $B$ are sets, so there is no injection from the class of ordinals into any of them; but if the recursion carries all the way through the ordinals then $\alpha\mapsto F_A(A\setminus\operatorname{rng}(f_\alpha))$ is an injection into $A$ and the obvious one with $\operatorname{dom}(f_\alpha)$ defines an injection into $B$.

  So the recursion halts at some point, let $f$ be the union of all the defined $f_\alpha$. If $f$ is injective from $B$ into $A$ then we are done, otherwise its domain is a proper subset of $B$ and $f$ is surjective, or else we can continue one more step (because both $B\setminus\operatorname{dom}(f)$ and $A\setminus\operatorname{rng}(f)$ are non-empty). So either $f$ is an injection from $B$ into $A$ or $f^{-1}$ is an injection from $A$ into $B$.

This list can grow with pretty much every equivalent to the axiom of choice, some will be longer and some will be shorter. But there's no "explicit" way to construct a surjection because that would amount to proving the axiom of choice holds.

Solution 2:

This statement is equivalent to the Axiom of Choice, so you'll need to use some variant of Choice:

• Using the Well-Ordering Theorem, this just reduces to either
  • showing that the statement holds for all ordinal numbers, which is pretty easy (at least using the von Neumann definition of ordinals); or
  • noting that given two well-ordered sets, one is always order-isomorphic to an initial segment of the other.
• Using Zorn's Lemma, consider the partial order of all partial injections $A \to B$ ordered by extension. Show that this satisfies the hypothesis of Zorn's Lemma, and then show that any maximal element of this ordering either has domain $A$ or range $B$. (Not the easiest proof of this result, but none too difficult.)