If there exists a function that maps A onto B , show that A is also uncountable Let $A$ and $B$ be sets and suppose $B$ is uncountable.If there exists a function that maps $A$ onto $B$ , show that $A$ is also uncountable.
My attempt is proof by contradiction. Suppose A is countable. Then there exists a function $$h:\mathbb{N} \rightarrow A$$ where $h$ is one-to-one correspondence. Since a function maps A onto B, say $f$, then $$f:A \rightarrow B$$ is onto. Let $$g:\mathbb{N} \rightarrow B$$ Then $g(x)=f(h(x))$ . Then $g$ is onto since $f$ and $h$ are onto. Then I stuck here.
 A: Your strategy is good, but ideally you would want the function $f$ to be a one-to-one correspondence. You can extract one from the function you already have with this lemma:
Lemma. If $f:A \to B$ is onto, then there exists a one-to-one correspondence $f':A'\to B$ for some $A' \subseteq A$.
Proof. Let $\leq_A$ be a total ordering on $A$ and for any $b \in B$, let $A(b)$ be the minimum element $a \in A$ (with respect to $\leq_A$) such that $f(a) = b$. Then let $A' = \{A(b) \mid b \in B\}$ and the function $f'$ equivalent to $f$ defined only on $A'$ is a one-to-one correspondence from $A'$ to $B$.
A: Here is an elaboration on my comment.
Suppose, for contradiction, that $A$ is countable, and define $g:\mathbb{N}\to B$ as you have. Since $g$ is surjective, the inverse image $g^{-1}(x)$ is nonempty for each $x\in B$, and so has a least element $a(x)$.
Let $S\subset \mathbb{N}$ be the image of $a$. We have:


*

*$a: B\to S$ is surjective, by construction;

*$a$ is injective. Indeed, if $a(x)=a(y)$, then $x=g(a(x))=g(a(y))=y$.


Therefore $a$ is a bijection between $B$ and $S$. Since $S$ is countable, $B$ must be as well, a contradiction.
The above assumes you've shown that a subset of $\mathbb{N}$ is countable; if you haven't and need help proving this lemma let me know.
