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


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$

  • $\begingroup$ what do you mean by a not empty? $\endgroup$ – Daniel Oct 15 '15 at 1:06
  • $\begingroup$ A contains at least one element a $\endgroup$ – Tsemo Aristide Oct 15 '15 at 1:13
  • $\begingroup$ ohhhhhhh. ok you meant set A is not empty. so this proves that there is an onto map from B to A? $\endgroup$ – Daniel Oct 15 '15 at 1:15

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.

  • $\begingroup$ @Jesse no problem! Glad it was useful. $\endgroup$ – Luke Oct 15 '15 at 2:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.