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.

I'm having a bit of trouble thinking of how to prove this homework problem.

Prove that a set $A$ is uncountable if there is an injective function $f:(0, 1)\rightarrow A$. I know $(0, 1)$ is uncountable, but I can't think of a proof to show that $A$ must be as well. Could I do it through contradiction and say that there is no injective function?

Thanks!

share|improve this question
    
What are your definitions of countable and uncountable? –  Chris Eagle Apr 15 '12 at 22:12
    
A set $A$ is countable if $A\approx\mathbb{N}$, and uncountable if it is neither finite nor countably infinite. –  roboguy12 Apr 15 '12 at 22:14
1  
You could approach it like this: First, show that $A$ has an uncountable subset (using $f$), and then, show: If a set has an uncountable subset, it is uncountable. –  Johannes Kloos Apr 15 '12 at 22:14
1  
Hopefully one of the 4 answers will help you along. Wait long enough and there may be 10. –  Eric Gregor Apr 15 '12 at 22:21
add comment

7 Answers 7

up vote 4 down vote accepted

If $A$ were countable, then $f((0,1))$, which is a subset of $A$, would also be also countable.

Since $f:(0,1) \to A$ is injective then $f:(0,1) \to f((0,1))$ is a bijective function, so $(0,1)$ would also be countable.

But $(0,1)$ is in fact uncountable, so $A$ is also uncountable.

share|improve this answer
    
Thanks! Someone else said something like this, but you made it super clear. –  roboguy12 Apr 15 '12 at 22:25
1  
@roboguy12: All the answers (and one comment) said exactly that. This answer, however, spelled it out in full while some of the other answers gave generalized arguments or hints. :-) –  Asaf Karagila Apr 15 '12 at 22:28
    
Ah, very true. Thank you all! –  roboguy12 Apr 15 '12 at 22:32
add comment

Lemma. If $A$ and $B$ are nonempty sets, and there is a one-to-one function $f\colon A\to B$, then there is a surjective function $g\colon B\to A$.

Proof. Let $a_0\in A$ (possible, since $A$ is nonempty). Define $g\colon B\to A$ as follows: $$g(b) = \left\{\begin{array}{ll} a_0 &\text{if }b\notin f(A);\\ a &\text{if }b\in f(A)\text{ and }f(a)=b. \end{array}\right.$$ Note that $g$ is well defined, since $f$ is one-to-one, so there is at most one $a\in A$ with $f(a)=b$. And $g$ is onto, because give $a\in A$, $g(f(a))=a$. $\Box$

Now, we are assuming that there exists an embedding $(0,1)\hookrightarrow A$. Therefore, there is a surjection $g\colon A\to (0,1)$. If $f\colon\mathbb{N}\to A$, then $g\circ f\colon \mathbb{N}\to (0,1)$ is a function that is not onto. Conclude that $f$ is not onto. Conclude that $A$ is not countable.

Alternatively, by contradiction: suppose $f\colon\mathbb{N}\to A$ is onto. Let $S\subseteq \mathbb{N}$ be the set of all natural numbers such that $f(n)\in (0,1)$ (we are vieweing $(0,1)$ as a subset of $A$ via the inclusion). Then $f$ would be an onto function from a countable set (every subset of $\mathbb{N}$ is countable) onto $(0,1)$, which contradicts the fact that $(0,1)$ is not countable.

share|improve this answer
add comment

I assume that you have the following facts at your disposal:

  1. $A$ is countable if there is an injection from $A$ into $\mathbb N$; or a surjection from $\mathbb N$ onto $A$. If $A$ is not countable then we say that $A$ is uncountable.
  2. We say that $|A|\le|B|$ if and only if there exists $f\colon A\to B$ which is injective.
  3. $|(0,1)|=|\mathcal P(\mathbb N)|$.
  4. For every set $A$ we have $|A|<|\mathcal P(A)|$.
  5. If $|A|\le |B|$ and $|B|\le|C|$ then $|A|\le|C|$.

Using these facts we can deduce that $|\mathbb N|<|(0,1)|\le|A|$. Can you see how?

share|improve this answer
add comment

The image of $f$ lies in $A$, and thus $A$ can be expressed as the union of $f((0,1))$ and $A\setminus f((0,1))$. So clearly $A$ is uncountable.

share|improve this answer
add comment

You are given that there is an injective function from $(0,1)$ to $A$. If $A$ were countable, there would be an injective function from $A$ to $\mathbb{N}$. What do you know about the compostion of injective functions? What does that say about the relationship of $(0,1)$ to $\mathbb{N}$?

share|improve this answer
add comment

How about just this: consider the set $B=\{f(x)∣x∈(0,1)\}$. You can pretty easily show that there's a bijection between $(0,1)$ and $B$, and that $B$ is a subset of $A$. Since $B$ is uncountable and $B\subseteq A$, $A$ is uncountable.

share|improve this answer
1  
Is $B$ a short for "Backwards"? Because your definition is backwards! :-) I think you meant to write $B=\{f(x)\mid x\in(0,1)\}$. –  Asaf Karagila Apr 15 '12 at 22:25
add comment

A set $A$ is countable iff there exists an injection $g:A\to\mathbb N$. So, if your set $A$ were countable, $g\circ f:(0,1)\to\mathbb N$ would be an injection and thus $(0,1)$ would have to be countable. Contradiction.

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.