Without the Axiom of Choice, must two nonempty sets have a surjection between them? Let $A$ and $B$ be two nonempty sets. Can we show, without using the Axiom of Choice, that there must either be a surjection $A\to B$ or $B\to A$?
With Choice we can do this by using Zorn to obtain a maximal injective partial function $A\to B$, and then extending it to a surjection in one direction or the other.
 A: No, you cannot show this. For instance, it is consistent to have infinite Dedekind-finite sets whose power set is still Dedekind-finite. Now, if there is a surjection from $A$ to $\omega$, then there is an injection from $\omega$ (indeed, from $\mathcal P(\omega)$) to $\mathcal P(A)$, so $\mathcal P(A)$ is Dedekind-infinite.
Thus, if $\mathcal P(X)$ is infinite Dedekind-finite, then $X$ and $\omega$ are two non-empty sets with no bijections in either direction.

More generally, suppose that $X$ is not well-orderable, and let $\Theta$ be the first non-zero ordinal that $X$ does not surject onto. $\Theta$ clearly exists, since if $f:X\to\alpha$ is onto, then there is a partition of $X$ in type $\alpha$. The collection of partitions of $X$ is a set, and for any partition, there are only set-many orders we can put on its classes, so there are only set-many ordinals that work as $\alpha$. 
Ok. Clearly, $\Theta$ does not surject into $X$, or $X$ would be well-orderable, since a subset of $\Theta$ would be in bijection with $X$ (by picking least representatives from each preimage). So $X$ and $\Theta$ are an example.
A: The original Cohen model for ZF + $\neg$AC gives a counterexample. Cohen adjoins a family $F$ of reals such that very little structure exists on $F$; in particular, it's not hard to show that whenever $r\in\mathbb{R}$ is such that both $F_{<r}$ and $F_{>r}$ are infinite, then there is no surjection from $F_{<r}$ to $F_{>r}$ or from $F_{>r}$ to $F_{<r}$.


*

*Of course, when I say "not hard to show" that's relative: we need to already understand the construction Cohen gives, which is quite complicated. However, once its basic properties are developed the statement above is fairly immediate.


Incidentally, this example does not fall into the category Andres mentioned: while $F$ is Dedekind-finite, its powerset is not: the family $$\{F_{<q}:q\in\mathbb{Q}\}$$ can be ordered via your favorite well-ordering of $\mathbb{Q}$, and this yields an embedding of $\omega$ into $\mathcal{P}(F)$.
