Proving a set is uncountable

Question

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!

Answer 1

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.

Answer 2

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?

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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}$?

Answer 7

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.