Proof in ZF set theory involving surjection and cardinality

Question

Let $f$ $:A\rightarrow B$ be a surjection.

Show that $|B|$ < $2^{|A|}$.

Please can anyone lend a hand here?

Answer 1

Remember that "$\vert X\vert\le\vert Y\vert$" means "there is an injection from $X$ to $Y$." There are two pieces to this question:

• Showing that $B$ injects into $2^{A}$.

• Showing that $2^A$ does not inject into $B$.

For the first point, note that if $A$ surjects onto $B$, then we can "reverse" that to get an injection from $B$ to $A$ . . . using the axiom of choice. In ZF alone, that's not possible. And the problem is that a surjection $s: A\rightarrow B$ might be very non-injective, so it might not have a left inverse. So the problem is that $s$ might associate lots of elements of $A$ to a single element of $B$; do you seen, based on that, a way to associate a set of elements of $A$ to a single element of $B$? Do you see why that map is injective?

For the second point, if $2^A$ injects into $B$, then $B$ surjects onto $2^A$ (do you see why? this is provable in ZF, it's the converse that needs choice). Now, do you see why this is a problem? HINT: by assumption, $A$ surjects onto $B$ . . .

Answer 2

It is easy to see without choice that if there is a surjection from $A$ onto $B$, then there is an injection from ${\mathcal P}(B)$ into ${\mathcal P}(A)$, and the result follows from Cantor's theorem that $B<{\mathcal P}(B)$.

To define the injection, suppose $g:A\to B$ is onto. Define $f:{\mathcal P}(B)\to{\mathcal P}(A)$ by $$f(C)=\{a\in A\mid g(a)\in C\}$$ for $C\subseteq B$. It is easy to check that $f$ is injective, using that $g$ is onto: If $D\ne C$ are subsets of $B$ and $b\in D\setminus C$, then any $a\in A$ such that $g(a)=b$ is in $f(D)\setminus f(C)$.