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

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


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

Union of countable sets is countable:

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


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

Subset of a countable set is countable,

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


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

  • 5
    $\begingroup$ Seems easier to to just come up with a bijective map between $(0,1)$ and $\mathbb R$, like $x\mapsto\tan\pi(x-\frac12)$ $\endgroup$ – MPW Oct 13 '15 at 13:20
  • $\begingroup$ What is your definition of "countable"? I ask because the backward part seems shaky to me. $\endgroup$ – Cameron Buie Oct 13 '15 at 13:36
  • $\begingroup$ @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. $\endgroup$ – 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.

  • $\begingroup$ 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. -.- $\endgroup$ – tmaric Oct 13 '15 at 15:07
  • $\begingroup$ Well, what does your intuition tell you that "countable" should mean? $\endgroup$ – Cameron Buie Oct 13 '15 at 18:57
  • $\begingroup$ 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. $\endgroup$ – tmaric Oct 14 '15 at 7:59
  • $\begingroup$ 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. $\endgroup$ – Cameron Buie Oct 14 '15 at 12:34
  • $\begingroup$ 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). $\endgroup$ – 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.


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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