If one of two sets has larger cardinality, there is a map onto the other set

Question

Let A and B be sets with the cardinality of A less than or equal to B. Show there exists an onto map from B to A.

I am struggling with this proof. I don't know how to show this. Any help would be greatly appreciated

Answer 1

A not empty There exists an injective map $f:A\rightarrow B$, there exists an inverse $g:f(A)\rightarrow A$. Let $a\in A$, $h:B\rightarrow A$ defined by $h(x)= g(x), x\in f(A)$ otherwise $h(x)= a$

Answer 2

The basic gist is that we know (from the definition of cardinality) that there exists an injective function from $A$ to $B$. We'll then use this function and it's properties to define a surjective function from $B$ to $A$.

By the definition of cardinality we have

$$ |A| \leq |B| \Leftrightarrow \exists \; f:A \rightarrow B \ni f \mbox{ is injective.} $$

If $B'$ is the image if $f$ in $B$ then let $g':B' \rightarrow A$ be defined such that $\forall b' \in B'$ we have $g'(b') = \{a \in A | f(a) = b'\}$. We need to show that this mapping is well-defined ($\forall b' \in B'$), single valued, and onto $A$.

Well defined: Because $B'$ is the image of $A$ we know that $f:A\rightarrow B'$ is surjective. This means that

$$ \forall b' \in B' \;\; \exists a \in A \;\; \ni \;\; f(a) = b'. $$

Thus $g'$ is defined $\forall b' \in B'$.

Single valued: Assume $g'$ is not single valued. This means that $\exists a_1, a_2\in A$ with $a_1 \neq a_2$ and $b' \in B'$ such that $f(a_1) = f(a_2) = b'$. But because $f$ is injective this implies that $a_1=a_2$. This is a contradiction and thus $g'$ is single valued.

Onto: Because $f:A \rightarrow B'$ is well defined we have that

$$ \forall a \in A \;\; \exists b'_a\in B' \;\; \ni \;\; f(a)=b'_a. $$

So given any $a\in A$ we have that $g'(b'_a) = a$ and thus $g'$ is surjective.

To finish the proof you just need to define $g:B \rightarrow A$ such that $g(b)=g'(b)$ if $b \in B'$ and $g(b)= \mbox{ any element from A you want }$ otherwise.

This argument can be cleaned up a bit but it should get you where you need to go.