Given sets $A$ and $B$. Can you show that either there exists an injective map of $A$ into $B$ (that is, a map such that each element of $A$ maps to an element of $B$ and no two elements of $A$ map to the same element of $B$) or there exists an injective map of $B$ into $A$ (or both). .
If this can be proven then the ordering of sets by their cardinality is a total ordering; if it is false, there are two sets $A$ and $B$ such that neither $|A|<|B|$ nor $|B|<|A|$. Of course, it might also be undecidable, in which case my question becomes has it been proven to be undecidable within ZF?
I strongly suspect that the ordering is total and that there is an easy proof but I can't come up with one.
In the absence of the axiom of choice the ordering need not be total. For example, you can have an amorphous set $A$: an infinite set that is not the disjoint union of two infinite subsets. This immediately implies that there is no injection from $\Bbb N$ to $A$, as that would immediately allow you to partition $A$ into two infinite subsets. There is also no injection from $A$ to $\Bbb N$, as that would have the same effect.