Prove that the open interval $(0,1)\subset \mathbb{R}$ is uncountable if and only if $\mathbb{R}$ is uncountable.

$I = (0,1) = {x \in \mathbb{R} : 0 < x < 1}$

$\mathbb{N} \nsim I \iff \mathbb{N} \nsim \mathbb{R}$

Forward

$\mathbb{N} \nsim I \Rightarrow \mathbb{N} \nsim \mathbb{R}$

$\mathbb{N} \sim A$ and $\mathbb{N} \sim B \Rightarrow \mathbb{N} \sim A \cup B$

I can negate this statement in the following way

(1) $\mathbb{N} \nsim A \Rightarrow \mathbb{N} \nsim A \cup B$

I can pick $x_1, x_2 \in A$ such that either $\nexists f : A \to A' : x_1 \ne x_2, f(x_1) \ne f(x_2)$ , or $\exists y \in A' : y \ne f (x)$. It makes no difference if $(x_1, x_2) \in A$ breaks 1:1 or onto property of $f$, either way, $f(x_1), f(x_2) \in A \cup B$.

(1) is valid regardless if $\mathbb{N} \sim B$ or $\mathbb{N} \nsim B$, because such two $x_1, x_2 \in A$ break the countability of $A \cup B$.

Hence $\mathbb{N} \nsim A \Rightarrow \mathbb{N} \nsim A \cup B$. If I now use

$I^c = \{x \in \mathbb{R} : x \notin I\}$

then $I^c \cup I = \mathbb{R}$ and

$\mathbb{N} \nsim I \Rightarrow \mathbb{N} \nsim I \cup I^c \equiv \mathbb{N} \nsim \mathbb{R}$

Backward

$\mathbb{N} \nsim \mathbb{R} \Rightarrow \mathbb{N} \nsim I$

$\mathbb{N} \sim A$ and $B \subseteq A \Rightarrow \mathbb{N} \sim B$

negation of this statement

$\mathbb{N} \nsim A$ and $B \subseteq A \Rightarrow \mathbb{N} \nsim B$

gives

$\mathbb{N} \nsim \mathbb{R}$ and $I \subset \mathbb{R} \Rightarrow \mathbb{N} \nsim I$

My question: Is this proof correct?

Edit: I'm reading about real analsis from Abbot's "Understanding Analysis". This is how countability is defined there:

Definition 1.4.7. Two sets A and B have the same cardinality if there exists f : A → B that is 1–1 and onto. In this case, we write A ∼ B.

Definition 1.4.10. A set A is countable if N ∼ A. An infinite set that is not countable is called an uncountable set.

• Seems easier to to just come up with a bijective map between $(0,1)$ and $\mathbb R$, like $x\mapsto\tan\pi(x-\frac12)$ – MPW Oct 13 '15 at 13:20
• What is your definition of "countable"? I ask because the backward part seems shaky to me. – Cameron Buie Oct 13 '15 at 13:36
• @Cameron: $\mathbb{N} \sim A \Rightarrow \exists f A \to N : x_1, x_2 \in A, x_1 \ne x_2 \rightarrow f(x_1) \ne f(x_2)$ and $\forall n \in N \exists x \in A : n = f(x)$ - there is a function $f : A \to N$ that is both 1:1 and onto. – tmaric Oct 13 '15 at 14:16

I'm afraid that neither part is correct. The big issue is your attempts at negation. Remember: the negation of a true statement is a false statement! Instead of negating (which you're not doing correctly in either case), you might instead consider the contrapositive, but I digress.

Before I point out the issues, let me introduce some notation. If there is a one-to-one function $A\to B,$ let's denote that by $A\precsim B,$ and say that the cardinality of $A$ is no greater than the cardinality of $B.$ If there is a one-to-one function $A\to B,$ but there exists no one-to-one and onto function $A\to B,$ we'll denote that by $A\prec B,$ and say that the cardinality of $A$ is less than the cardinality of $B.$ So, what you are trying to prove is that $\Bbb N\prec\Bbb R$ if and only if $\Bbb N\prec I.$

In the first part, you claim that if $A$ is not a countable set, then regardless of $B$, we have that $A\cup B$ is not countable. But consider $A=\{0\},B=\Bbb N,$ for a counterexample!

In the second part, you claim that if $A$ is not a countable set, then neither is any subset of $A.$ But consider $A=\Bbb R,B=\Bbb N$ for a counterexample! The problem is that, in that other post, "countable" means either countably-infinite or finite (that is, $A$ is countable if and only if $A\precsim\Bbb N$)!

Now, we can make some adjustments to your approach. One direction is fairly straightforward, as you can prove that $(A\prec B)\wedge(B\precsim C)\implies A\prec C.$ Thus, in particular, $\Bbb N\prec I\implies\Bbb N\prec\Bbb R.$ Unfortunately, the reverse direction can't be proved from general principles only.

The most straightforward (perhaps only) way to proceed is to exhibit a one-to-one and onto function $I\to\Bbb R$ (or $\Bbb R\to I$, which amounts to the same thing). You can find numerous examples here.

• Thanks a lot! It will take a lot of time to get used to this way of thinking - even though I seem to understand the definition, my brain keeps trying to interpret countability intuitively. -.- – tmaric Oct 13 '15 at 15:07
• Well, what does your intuition tell you that "countable" should mean? – Cameron Buie Oct 13 '15 at 18:57
• I am an engineer, so I'm used to computation (calculus, I guess), not proofs. For example, if a set $S$ is empty, then it is hard for me to understand how can there exist a bijective function $f : S \to \mathbb{N}$. Also, if I write if (A and B) in a program, the sentinel fails as soon as A is false, in C++ when compiled in optimization mode, B is not evaluated at all. That's what I mean by getting used to the mathematical way of thinking. I find mathematics extremely interesting, but it is a very different world from what I have studied. – tmaric Oct 14 '15 at 7:59
• It certainly takes getting used to. Some things are just terminology to become familiar with (for instance, there cannot be a bijective function $\emptyset\to\Bbb N,$ but there is an injective function), and some things are a great deal more foreign. – Cameron Buie Oct 14 '15 at 12:34
• It will simply take more time than I expected. That is fine, all magic comes with a price. :) I've taught myself software design (don't mistake it with programming), so I know what awaits me and I have a solid plan (thanks to this site). – tmaric Oct 14 '15 at 13:59

As Cameron points out, your proofs have flaws.

Here, should you be interested, is a far simpler proof:

consider $$f(x) = \frac{x}{(1 - (2x - 1)^2}$$ This is a bijection from the interval to the real line. So they have the same cardinality.

Alternative:

$$f(x) = \frac{1 + \frac{2}{\pi} \arctan(x)}{2}$$ is a bijection from the real line to the interval $(0, 1)$.