Prove that for any sets $A,B$, either there exists a surjection from $A$ to $B$, or vice versa I would like a proof that for any pair of sets $A,B$, either there exists a surjection from $A$ to $B$, or vice versa. This would prove that the usual order on cardinals has the connexity property.
Also, I would like to know if choice is required.
 A: Using axiom of choice, $A,B$ can be well ordered. Based on those well orders, one is an initial segment of the other one which enables to build a surjection.
A: First of all, the statement is false, since if $A=\varnothing$ and $B\neq\varnothing$ then there are no surjection from either set onto the other. But let's put that problem aside. The statement that any two non-empty sets admit a surjection in one direction or the other is equivalent to the Axiom of Choice, so it cannot be avoided.
Having said that, let me point out that working in $\sf ZF$, the pre-order defined by surjections (it is not provably antisymmetric: Cantor–Bernstein works for injections, but for surjections it requires using $\sf AC$) is a bit awkward to work with, so in general when one defines and studies the order on cardinals, one should attempt to use injections whenever possible.
Now. Here are a few ways to prove this, working in $\sf ZFC$.

*

*If you already know that cardinals are linearly ordered, simply show that there is a surjection from $A$ onto $B$ if and only if there is an injection from $B$ into $A$ (again, assuming it's not the case that exactly one set is empty).*


*Well-order both sets, then by the well-ordering comparability theorem, one order is an initial segment of the other, which provides us with an injection, which in turn provides us with a surjection in the other direction.


*Use Zorn's lemma/Teichmüller–Tukey lemma with the partial order of partial injections from $A$ to $B$. Then a maximal element in that family is an injection from $A$ to $B$ or vice versa, so it provides us with a surjection in the other direction.


*Fix a choice function from non-empty sets of $A$ and from non-empty sets of $B$. Now, suppose there is no surjection from $B$ onto $A$, and by [transfinite] recursion define a function which chooses a point from $A$ and assigns it a point in $B$, such that as long as there are points in $B$ that were not used yet, we keep choosing new ones. We can show that this process must exhaust $B$ well before we exhausted $A$, otherwise a surjection from $B$ onto $A$ would exist. When you're done, either repeat some fixed value (e.g. the last chosen point), or just restart choosing points from $B$.
There are many many equivalents to the Axiom of Choice, so there are probably other ways to prove this as well.

(*) To get a surjection from an injection we do not need the Axiom of Choice, so in fact the "only" use the Axiom of Choice is in producing a linear order to begin with.
