# Without the Axiom of Choice, must two nonempty sets have a surjection between them? [duplicate]

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.

## marked as duplicate by Asaf Karagila♦ axiom-of-choice StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Oct 9 '18 at 15:59

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.

• You answered this, I answered the duplicate, and we both answered the duplicate of the duplicate. The circle is complete. – Asaf Karagila Oct 9 '18 at 16:00
• @Asaf Hehe. Figures... – Andrés E. Caicedo Oct 9 '18 at 16:05
• From you I would have expected not to use $\Theta$ "just like that", by the way. What's wrong with $\aleph^*$? – Asaf Karagila Oct 9 '18 at 16:05
• There was a convoluted reason: I used $\Theta$ because I wanted people to think of $\mathbb R$ under determinacy, where we have no infinite Dedekind-finite sets. – Andrés E. Caicedo Oct 9 '18 at 16:06
• Anyway, you should probably close this so we get the appropriate links. – Andrés E. Caicedo Oct 9 '18 at 16:07

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_{ and $$F_{>r}$$ are infinite, then there is no surjection from $$F_{ to $$F_{>r}$$ or from $$F_{>r}$$ to $$F_{.

• 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_{ can be ordered via your favorite well-ordering of $$\mathbb{Q}$$, and this yields an embedding of $$\omega$$ into $$\mathcal{P}(F)$$.

• Doesn't any model of non-AC give an easy counterexample due to Lindenbaum's theorem? You know, like discussed on the duplicate? :) – Asaf Karagila Oct 9 '18 at 16:06