# Countability of the irrational numbers

• Nov 15th 2008, 12:30 PM
Mathstud28
Countability of the irrational numbers
One of the excersises in my book says "Is the set of all irrational numbers countable? Justify your response"

Here is what I said (For the sake of writing let $\mathbb{I}$ the set of irrationals):"

1. First let us establish that $\mathbb{Z}$ is an infintely countable set. This is readily seen since there is a 1-1 mapping of $\mathbb{N}$ onto $\mathbb{Z}$ so $\mathbb{N}\sim\mathbb{Z}$, thus the integers are countable.

2. Lemma: If $A$ is a countable set and if $B_n$ the set of all n-tuples $(a_1,a_2,\cdots,a_n)$ where $a_1,a_2,\cdots,a_n\in{A}$, then $B_n$ is countable.

3. So realizing that the rationals may be expressed as $\frac{m\in\mathbb{Z}}{n\in\mathbb{Z}}$. So now since if we express every rational number as $(m,n)$ we can show that the rationals may be expressed as a set of ordered pairs (2-tuples). We have that the rationals may be expressed as an analogue of #2 with $\mathbb{Q}$ expressed as $B_2$, and since $A=\mathbb{Z}$, a countable set, it follows that the rationals are countable.

4. Lemma: The set of all Real numbers is uncountable

5. Lemma: The union of any number of infinitely countable sets is countable.

6. Assume that $\mathbb{I}$ is countable, That would imply that $\mathbb{R}=\mathbb{Q}\cup\mathbb{I}$ is countable. A contradiction.

Therefore $\mathbb{I}$ is uncountable $\blacksquare$"

Does that look alright?
• Nov 15th 2008, 12:42 PM
Plato
It is well known that the set for rational numbers is countable. Cantor using the diagonal argument proved that the set [0,1] is not countable. Thus the irrational numbers in [0,1] must be uncountable. So basically your steps 4, 5, & 6, form the proof.
• Nov 15th 2008, 12:46 PM
Mathstud28
Quote:

Originally Posted by Plato
It is well known that the set for rational numbers is countable. Cantor using the diagonal argument proved that the set [0,1] is not countable. Thus the irrational numbers in [0,1] must be uncountable. So basically your steps 4, 5, & 6, form the proof.

Thank you very much Plato.
• Nov 15th 2008, 02:12 PM
ThePerfectHacker
We know that $|\mathbb{R}| = |\mathbb{R}\times \mathbb{R}|$. Let $f: \mathbb{R}\to \mathbb{R}\times \mathbb{R}$ be a bijection. Define $A = f[\mathbb{Q}]$ (that is the "image of $\mathbb{Q}$" i.e. $\{ f(x) | x\in \mathbb{Q} \}$). Of course, since $A\subseteq \mathbb{R}\times \mathbb{R}$ it is a set of ordered pairs, let $B = \text{dom}(A)$ (that is the first coordinates in this set of ordered pairs). Since $|B|\leq |A| = |\mathbb{Q}| = |\mathbb{N}|$ (why?) it means there is $x\in \mathbb{R}$ such that $x\not \in B$ since $|\mathbb{N}| < |\mathbb{R}|$. Therefore, $C = \{ x \} \times \mathbb{R}$ is disjoint with $A$ which means $C\subseteq (\mathbb{R}\times \mathbb{R}) - A$. But we know that $|C| = |\mathbb{R}|$ which means $|(\mathbb{R}\times \mathbb{R}) - A|\geq |\mathbb{R}| \implies |(\mathbb{R}\times \mathbb{R}) - A| = \mathbb{R}$. Finally, since $\mathbb{R}\times \mathbb{R}$ corresponds with $\mathbb{R}$ (with this bijection $f$) and $A$ corresponds with $\mathbb{Q}$ we can "substitute" to get $|\mathbb{R} - \mathbb{Q}| = |\mathbb{R}|$.
• Nov 15th 2008, 03:18 PM
Plato
I always wonder at efforts to reinvent the wheel.
Bertram Russell said, “If it is worth saying, then it can be said simply”.
• Nov 15th 2008, 03:35 PM
ThePerfectHacker
Quote:

Originally Posted by Plato
I always wonder at efforts to reinvent the wheel.
Bertram Russell said, “If it is worth saying, then it can be said simply”.

"If $|A| < |B|$ then $|B-A| = |A|$" can be proven but this requires choice.
In the demonstration above choice was avoided.
---

For Mathstud: If $A\subseteq \mathbb{R}$ is not uncountable we cannot conclude it must be countable. It turns out this statement is completely independent, and we cannot show whether it is true or false! Called Continuum Hypothesis. That is something you used implicitly in your attempted proof above.
• Nov 15th 2008, 05:37 PM
Mathstud28
Quote:

Originally Posted by ThePerfectHacker
"If $|A| < |B|$ then $|B-A| = |A|$" can be proven but this requires choice.
In the demonstration above choice was avoided.
---

For Mathstud: If $A\subseteq \mathbb{R}$ is not uncountable we cannot conclude it must be countable. It turns out this statement is completely independent, and we cannot show whether it is true or false! Called Continuum Hypothesis. That is something you used implicitly in your attempted proof above.

Where in my proof did I assert anything was countable?
• Nov 15th 2008, 05:42 PM
ThePerfectHacker
Quote:

Originally Posted by Mathstud28
Where in my proof did I assert anything was countable?

Sorry about that! I thought your said to prove $|\mathbb{I}| = |\mathbb{R}|$. In that case assuming $\mathbb{I}$ is countable and arriving at countadiction is not sufficient. But that is not what the problem was asking, it was just asking to show it is uncountable. In that case you are correct.
• Nov 15th 2008, 05:43 PM
Mathstud28
Quote:

Originally Posted by ThePerfectHacker
Sorry about that! I thought your said to prove $|\mathbb{I}| = |\mathbb{R}|$. In that case assuming $\mathbb{I}$ is countable and arriving at countadiction is not sufficient. But that is not what the problem was asking, it was just asking to show it is uncountable. In that case you are correct.

Whew! Jeez TPH you scared me for a second (Giggle)
• Nov 15th 2008, 10:20 PM
CaptainBlack
Quote:

Originally Posted by ThePerfectHacker
"If $|A| < |B|$ then $|B-A| = |A|$" can be proven but this requires choice.
In the demonstration above choice was avoided.
---

You need qualification on what A and B are since this is not true for finite sets.

CB
• Nov 16th 2008, 12:42 AM
Opalg
Quote:

Originally Posted by Plato
Bertram Russell said, “If it is worth saying, then it can be said simply”.

Just for the record, I think it's Ludwig Wittgenstein rather than Bertrand Russell who said that.

More accurately, what Wittgenstein actually wrote (in the preface to Tractatus Logico-Philosophicus) was "Was sich überhaupt sagen lässt, lässt sich klar sagen" ("What can be said at all can be said clearly").

Russell certainly advocated the use of plain English, as in his essay How I Write, but I can't find anywhere where he used the words quoted above.