Existence of an injection Let $A$ and $B$ be two sets. Prove the existence of an injection from $A$ to $B$ or an injection from $B$ to $A$.
I don't know how to proceed, since I don't have any information on $A$ or $B$ to begin with.
Does anybody have a hint ?
 A: To prove the existence of an injection between two sets $A$ and $B$ from the Axiom of Choice, or from Zorn's Lemma (which is equivalent) the rough idea is that we build a bijection between larger and larger subsets of $A$ and $B$, starting with the empty function.
At every "step" we match one of the remaining elements of $A$ to one of the remaining elements of $B$, continuing until we run out of elements in one (or both) of the sets.  When we run out of elements in one of the sets, say in $A$ first, it means that we have matched every element of $A$ to an element of $B$, giving an injection $A \to B$.  If instead we run out of room in $B$ first, we get an injection $B \to A$.
There are two different ways to formalize this idea.  The first one uses the Axiom of Choice to choose, at every step, elements of $A$ and $B$ from among those which haven't yet been paired up, so that we can pair them up and extend our function.  Once we have a pair of "choice functions" $f$ and $g$ that choose elements of $A$ and $B$ for us respectively, the notion of proceeding by infinitely many "steps" is formalized using transfinite recursion.
Instead of using the combination of the Axiom of Choice and transfinite recursion, one can use Zorn's Lemma instead.  This works out to be essentially the same argument overall, but it has the advantage that it abstracts away the condition you need to check in order to apply transfinite recursion, so can just check this condition and you don't need to know how transfinite recursion works.
