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$
 A: For this to be true for general sets, you need the trichotomy principle, which is a consequence of the axiom of choice.
If $A,B$ are well-ordered, or countable, or finite, then you don't need AC and can prove directly.  Specifically, you map the smallest element of $A$ to the smallest element of $B$, and so on.  
A: One way is to use the Tukey-Teichmüller lemma:
Let $\mathscr F$ be the set of all partial injections (i.e., one-to-one relations) from $A$ to $B$.
$\mathscr F$ is of finite character:
Obviously, any finite subset of an element of $\mathscr F$ is an element of $\mathscr F$.
Let $f \subseteq A \times B$. If every finite subset of $f$ is one-to-one, then in particular each two-element subset of $f$ is one-to-one, so $f$ is one-to-one, and thus $f \in \mathscr F$.
So by the Tukey-Teichmüller lemma, $\mathcal F$ has a maximal element $g$. It should be easy to see why $g$ must be either left-total or right-total, and so either $g$ or $g^{-1}$ is an injection.
A: Until now I've only come up with a Zorn's Lemma way, which was inspired by the first bullet point of Asaf Karagila's answer: 
Proof.
Write $X:= \{f \subseteq {B \times A}:\text{f is an injection} \}$, then we have a partially ordered set $(X,\subseteq)$. 
For every totally ordered subset $Y$ of $X$, $\cup Y \subseteq {B \times A}$ is well-defined as every element in $Y$ is a subset of $B \times A$. 
Obviously, $\cup Y$ is an upper bound for $Y$. 
In order to use Zorn's Lemma, we need to prove that $\cup Y \in X$. For any $(b_1, a_1), (b_2, a_2) \in \cup Y$, there exist $f_1, f_2 \in Y$ such that $(b_1, a_1) \in f_1, (b_2, a_2) \in f_2$. 
Since $Y$ is totally ordered by set inclusion, we have $f_1 \subseteq f_2 \text{ or } f_2 \subseteq f_1$. We assume $f_1 \subseteq f_2$ without loss of generality. Hence we have $(b_1, a_1) \in f_2$. Since $f_2 \subseteq X$, we have $b_1 = b_2 \Rightarrow a_1 = a_2$ from well-definedness, and $b_1 \neq b_2 \Rightarrow a_1 \neq a_2$ from injectivity of $f_2$. This implies that $\cup Y$ is an injection.
Therefore, we have $\cup Y \in X$. By Zorn's Lemma, $X$ has at least one maximal element, call it $g$. Let $B' = dom(g)$.
We know that $g: B'\to A$ where $B'\subseteq B$ is an injection. Now we prove that $B' = B$. Suppose for sake of contradiction that $B' \neq B$, thus $B \backslash B'$ is non-empty. So there exists $b \in B \backslash B'$. There must also exist $a \in A \backslash g(B')$ (otherwise $A = g(B')$, so $f$ is also surjective. Its inverse $f^{-1} : A \to B'$ is hence an injection $A \to B$, a contradiction). Thus, $g \cap \{(b,a)\}$ is an injection in $X$, but $g$ is a proper subset of $g \cap \{(b,a)\}$, which contradicts that $g$ is the maximal element in $(X, \subseteq)$. Thus, $B^\prime=B$, there exists an injection from $B$ to $A$. Hence, $B$ has lesser or equal cardinality to $A$, as desired.
A: 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:


*

*$f_0=\varnothing$.

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

*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.
A: 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.)

A: This statement (usually known as Hartogs' Trichotomy Theorem) is equivalent to the axiom of choice in ZF.
If you want to prove it from Zorn's lemma, check for my answer to this question, in which I demonstrate that Zorn's lemma implies Zermelo's well-ordering theorem.
If you want to prove it directly, using the original statement of the axiom of choice, we first need to prove the following
Theorem: The axiom of choice implies Zermelo's well-ordering theorem
Demonstration: Let $A$ be a set, and let $f$ be a choice function for $\mathcal{P}(A)$, that is, $f$ is a function whose domain includes the set $\mathcal{P}(A)\setminus\{\varnothing\}$
, and is such that for each $B\subseteq A$, if $B\not=\varnothing$, then $f(B)\in B$.
Let $z$ be a set that does not belong to $A$ (that exists as a consequence, for example, of Cantor's theorem).
By transfinite induction over the ordinals we define the following On-sequence $(a_\alpha)_{\alpha\in\text{On}}$: for each ordinal $\alpha$:
$$a_\alpha=\begin{cases}
       \displaystyle    f(A\setminus\{a_\beta|\;\beta<\alpha\})\qquad\text{if }A\setminus\{a_\beta|\beta<\alpha\}\text{ is not empty} \\
       \displaystyle    z\qquad\qquad\qquad\qquad\quad\,\,\,\text{if }A\setminus\{a_\beta|\;\beta<\alpha\}=\varnothing
\end{cases}$$
Let $\alpha$ be an ordinal such that $A\setminus\{a_\beta|\;\beta<\alpha\}$ is not empty, and let $\beta_1,\beta_2<\alpha$ such that $\beta_1<\beta_2$. Then $a_{\beta_1}$ and $a_{\beta_2}$ are elements of $A$, and are different from each other, because $a_{\beta_2}=f(A\setminus\{a_\beta|\;\beta<\beta_2\})$, which is a element of $A\setminus\{a_\beta|\;\beta<\beta_2\}$, and $a_{\beta_1}$ does not belong to this set. Therefore, for each ordinal $\alpha$ such that $A\setminus\{a_\beta|\;\beta<\alpha\}\not=\varnothing$, the $\alpha$-sequence $\langle a_\beta|\;\beta<\alpha\rangle$ is an injective application from $\alpha$ to $A$.
But this cannot occur for every ordinal $\alpha$: suppose on the contrary that this is true for every ordinal $\alpha$. Then the On-sequence $(a_\alpha)_{\alpha\in\text{On}}$ is an injective class-function from the proper class On in the set $A$. By the axiom-schema of subsets, the image $\{a_\alpha|\;\alpha\in\text{On}\}$ is a set $-$ which we shall denote by $B$ $-$ because it is included in the set $A$. And, since $(a_\alpha)_{\alpha\in\text{On}}$ is injective (since $\beta<\alpha$ implies $a_\beta\not=a_\alpha$), the inverse class-relation $((a_\alpha)_{\alpha\in\text{On}})^{-1}:B\twoheadrightarrow\text{On}$ is a class-function from the set $B$ onto the propper class On. This contradicts the axiom-schema of replacement, which ensures that the image of a set via a class-function is always a set, and it cannot be a proper class like On.
Therefore, there are ordinals $\alpha$ for which $A\setminus\{a_\beta|\;\beta<\alpha\}=\varnothing$. Let $\alpha_0$ be the least ordinal such that $A\setminus\{a_\beta|\;\beta<\alpha_0\}=\varnothing$. Then we have
$$A=\{a_\beta|\;\beta<\alpha_0\}$$
And $\langle a_\beta|\beta<\alpha_0\rangle$ is an injective function from $\alpha_0$ onto $A$, that is, it is a bijective function from $\alpha_0$ onto $A$. But $\alpha_0$ has a natural well-order, $\in_{\alpha_0}$, and this well-order of $\alpha_0$ is transferred by the bijective function $\langle a_\beta|\;\beta<\alpha_0\rangle$ to a well- order of $A$, that is, the relation $<_R$ defined by:
$$\text{For all }\,\beta,\,\gamma<\alpha_0,\qquad a_\beta<a_\gamma\Leftrightarrow\beta<\gamma$$
And therefore, $A$ has a well-order; namely, $<_R$.

After proving that Zorn's lemma $-$ or the axiom of choice $-$ implies Zermelo's well-ordering theorem, then we finally can prove
Hartogs' trichotomy theorem: For any sets $A$ and $B$, $A\preccurlyeq B$ or $B\preccurlyeq A$
Demonstration: from Zermelo's well-ordering theorem, if $A$ and $B$ are sets, let $<_R$ and $\prec_S$ be well-orderings of $A$ and $B$ respectively. Then there exist unique ordinals $\alpha$ and $\beta$ such that $\langle A,<_R\rangle\cong\langle\alpha,\in_\alpha\rangle$ and $\langle B,\prec_S\rangle\cong\langle\beta,\in_\beta\rangle$. And then, since $A\approx\alpha$ and $B\approx\beta$, we then have that if $\alpha\leq\beta$, $A\preccurlyeq B$, and if $\beta\leq\alpha$, then $B\preccurlyeq A$

On the other hand, if you ever want to prove the other implication, that Hartogs' trichotomy theorem implies the axiom of choice, you may want to follow this argument:
Theorem: Hartogs' trichotomy theorem implies Zermelo's well-ordering theorem
Demonstration Let $A$ be a set. By Hartogs' theorem (c.f. page 50, theorem 4.33), there exists an ordinal $\alpha$ that is not shrinkable in $A$. By Hartogs' trichotomy principle, if $\alpha\not\preccurlyeq A$, then $A\preccurlyeq\alpha$, and $A$ is shrinkable in $\alpha$, therefore $A$ has a well-ordering, the one that is transferred from the well-order $\in_\alpha$ os $\alpha$ via an injective function from $A$ to $\alpha$.
Theorem: Zermelo's well-ordering principle implies the axiom of choice
Demonstration: Let $A$ be a set. By Zermelo's well-ordering theorem, there exists a relation $<_R\subseteq\,\big(\bigcup A\big)\times\big(\bigcup A\big)$ that well orders $\bigcup A$. Then the function $f$ of domain $A\setminus\{\varnothing\}$ defined by: for each $a\in A\setminus\{\varnothing\}$
$$f(a)=\text{the minimal element of }a\text{ in the sense of }<_R$$
Is a choice function for $A$, if $\varnothing\not\in A$. If $\varnothing\in A$, simply take $f\cup\{\langle \varnothing ,\varnothing\rangle\}$
Combining the last two results, we can easily conclude that the Hartogs' trichotomy theorem implies the axiom of choice
