# 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.

-
That means that if we write $g_n=g(n)$, then the sequence $\{g_1,g_2,\dots\}$ enumerates all of $B$, potentially with repetitions. Can you find an enumeration of $B$ that does not have repetitions? – Thomas Andrews Jan 25 '13 at 16:59
What you've done is OK. If $g$ is onto that means that the cardinality of $B$ is less or equal to the cardinality of $\mathbb{N}$, but that can't be since $B$ is uncountable. – chango Jan 25 '13 at 17:00
Since $g$ is surjective, $g^{-1}(x)$ is nonempty and so has a least element $a(x)$. Then $a(x)$ is a bijection between $B$ and a subset of $\mathbb{N}$, which is countable. – user7530 Jan 25 '13 at 17:01
@chango That isn't the definition of "less or equal" in cardinality, which is defined for $1-1$ functions. You are assuming a result which is a general case of what OP is trying to prove. – Thomas Andrews Jan 25 '13 at 17:09
@user7530: how do we know inverse function of $g$ exists ? I thought for inverse to exist, we must make sure the function is 1-1 and onto ? – Idonknow Jan 25 '13 at 17:12

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.

-
I thought if we want a set $S$to be countable, we need to extablish a one-to-one correspondence $f$ between $\mathbb{N}$ and $S$ and not subset of $\mathbb{N}$? – Idonknow Jan 25 '13 at 17:31

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$.

-