Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
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
1  
@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
show 2 more comments

2 Answers 2

up vote 0 down vote accepted

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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