# prove set of irrational number is uncountable

• Aug 8th 2010, 02:07 AM
tsang
prove set of irrational number is uncountable

Prove the set of irrational number R\Q is uncountable.

I know the idea is try to find the bijection function, right? But I just cannot do it. Please help me with it. Thanks a lot.
• Aug 8th 2010, 02:29 AM
Vlasev
What things are you given? Are you given that R is uncountable?

You use bijections to prove sets are COUNTABLE, not uncountable. In this case you won't be able to find a bijection, i think.
• Aug 8th 2010, 03:09 AM
tsang
Quote:

Originally Posted by Vlasev
What things are you given? Are you given that R is uncountable?

You use bijections to prove sets are COUNTABLE, not uncountable. In this case you won't be able to find a bijection, i think.

Yes, sorry that I was a bit drunk, haha, of course, bijection is for COUNTABLE, I knew that, thanks.
And yes, I was given R is uncountable. I guess I have the idea is that prove union or intersection of uncountable is uncountable as well. But I just really don't know how to do in details. Please help me. Thanks a lot.
• Aug 8th 2010, 03:13 AM
Vlasev
You only need to show that the irrationals are the complement of the rationals.
• Aug 8th 2010, 03:19 AM
tsang
prove set of irrational number is uncountable
I was given R is uncountable. I guess I have the idea is that prove union or intersection of uncountable is uncountable as well. But I just really don't know how to do in details. Please help me. Thanks a lot.
• Aug 8th 2010, 03:21 AM
Plato
You know that $\displaystyle \mathbb{R}$ is uncountable and $\displaystyle \mathbb{Q}$ is countable.
The union of two countable set is countable.
So what does that mean about $\displaystyle \mathbb{Q}\cup (\mathbb{R}\setminus \mathbb{Q})?$
• Aug 8th 2010, 03:25 AM
tsang
Quote:

Originally Posted by Plato
You know that $\displaystyle \mathbb{R}$ is uncountable and $\displaystyle \mathbb{Q}$ is countable.
The union of two countable set is countable.
So what does that mean about $\displaystyle \mathbb{Q}\cup (\mathbb{R}\setminus \mathbb{Q})?$

Sorry, I still cannot get it. I just started Real Analysis course two weeks ago, so I haven't built enough foundation. Please help me with more details, I cannot thank you more.
• Aug 8th 2010, 04:39 AM
HallsofIvy
Not necessarily so. A bijection from a set A to the set of real numbers between 0 and 1 would prove that A is uncountable. A bijection always shows that two sets have the same cardinality.

Sorry: this was in response to Vsalev's post: "You use bijections to prove sets are COUNTABLE, not uncountable. In this case you won't be able to find a bijection, i think."
• Aug 8th 2010, 05:49 AM
Ares_D1
Quote:

Originally Posted by Plato
You know that $\displaystyle \mathbb{R}$ is uncountable and $\displaystyle \mathbb{Q}$ is countable.
The union of two countable set is countable.
So what does that mean about $\displaystyle \mathbb{Q}\cup (\mathbb{R}\setminus \mathbb{Q})?$

I see what you're doing here. The set $\displaystyle \mathbb{Q}\cup (\mathbb{R}\setminus \mathbb{Q})$ = $\displaystyle \mathbb{R}$, which we know is uncountable. We also know that $\displaystyle \mathbb{Q}$ is countable. But a number must either be rational or irrational, so it follows logically that $\displaystyle \mathbb{R}\setminus \mathbb{Q}$ must be uncountable.

Now, proving this formally... Could one more or less just follow the logic here, or is there a more rigorous approach? For instance, is it acceptable just to state $\displaystyle \mathbb{Q}\cup (\mathbb{R}\setminus \mathbb{Q})$ = $\displaystyle \mathbb{R}$ (which is obvious), or should we go about proving this first?
• Aug 8th 2010, 08:26 AM
HallsofIvy
that's a perfectly valid proof as it stands. The union of two countable sets is countable. (Have you proved that yet?)

If the set of all irrational numbers were countable then the set of all real numbers, the union of the set of irrational numbers and the set of rational numbers, would be the union of two countable set and so countable. That contradicts the fact that the set or all real numbers is uncountable.
• Aug 8th 2010, 08:54 AM
Ares_D1
Quote:

Originally Posted by HallsofIvy
that's a perfectly valid proof as it stands. The union of two countable sets is countable. (Have you proved that yet?)

If the set of all irrational numbers were countable then the set of all real numbers, the union of the set of irrational numbers and the set of rational numbers, would be the union of two countable set and so countable. That contradicts the fact that the set or all real numbers is uncountable.

Yep, got it. :)

I don't believe we've proved the union of two countable sets yet, so I'll avoid quoting the result directly in my final proof. Although, it really seems intuitive enough that I could and still get away with it.
• Aug 11th 2010, 12:05 AM
CaptainBlack
You can do this with a variant of Cantor's diagonal slash (I will be leaving out most of the hard work to leave something for the reader to do, that and I'm too lazy to do it myself)

We will be working with reals in the interval $\displaystyle $$[0,1) and with decimal expansions, so the decimal expansion of a real \displaystyle$$a$ in $\displaystyle $$[0,1) is \displaystyle 0.a_1a_2,...\ : \displaystyle a_i \in \{0,1,2,3,4,5,6,7,8,9\}. I will use the expressions "the decimal expansion of \displaystyle$$ a$ is periodic" or "$\displaystyle $$a is periodic" to mean the eventually the decimal expansion of \displaystyle$$ a$ becomes periodic.

----------------------------------------------------------------------

Lemma

A real in $\displaystyle $$[0,1) is rational if and only if it is periodic Proof Excersise for the reader (it can be looked up) ----------------------------------------------------------------------- Suppose the set or irrational numbers is enumerable and that \displaystyle x(i), i=1,2.. is an enumeration. Let \displaystyle x_{i,j} denote the \displaystyle$$ j$ th term in the decimal expansion of $\displaystyle x(i)$

Now we combine Cantor's slash argument with an idea of Liouville's, define the real $\displaystyle $$z with decimal expansion: \displaystyle z_k=\begin{cases} 1 &,{\text{if }} (\not\exists r: k=r!) \land (x_{k,k}= 0)\\ 0 &,{\text{if }} (\not\exists r: k=r!) \land (x_{k,k}\ne0)\\ 2 &,{\text{if }} (\exists r: k=r!) \land (x_{k,k}\ne 2)\\ 3 &,{\text{if }} (\exists r: k=r!) \land (x_{k,k}= 2)\\ \end{cases} Then \displaystyle z \in [0,1) and \displaystyle$$z$ is not periodic, so as $\displaystyle $$z differes from each irrational in our enumeration at at least one place in its' decimal expansion it is not in our enumeration and \displaystyle$$z$ is irrational. hence we have the required contradiction ...

CB
• Aug 11th 2010, 02:40 AM
Swlabr
Quote:

Originally Posted by CaptainBlack
You can do this with a variant of Cantor's diagonal slash (I will be leaving out most of the hard work to leave something for the reader to do, that and I'm too lazy to do it myself)

$\displaystyle \vdots$

CB

We can also use $\displaystyle cos(x): \mathbb{R} \rightarrow [-1, 1]$. Note that this is a surjection.

Noting that $\displaystyle cos(x) = cos(x+2\pi)$, if $\displaystyle x \in \mathbb{Q}$ then $\displaystyle x+2\pi \not\in \mathbb{Q}$. Thus, letting $\displaystyle f$ be the restriction of $\displaystyle cos(x)$ to $\displaystyle \mathbb{R}\setminus \mathbb{Q}$ we see that $\displaystyle f: \mathbb{R}\setminus \mathbb{Q} \rightarrow [-1, 1]$ is a surjection onto something with cardinality that of $\displaystyle \mathbb{R}$. This is sufficient.

(This is sufficient because if there exists a surjection from $\displaystyle A$ to $\displaystyle B$ then $\displaystyle |A| \geq |B|$. Similarly, if there exists an injection from $\displaystyle A$ to $\displaystyle B$ then $\displaystyle |A| \leq |B|$. Clearly the latter holds, and the former holds by what I just wrote about. Thus, $\displaystyle |\mathbb{R} \setminus \mathbb{Q}| = |\mathbb{R}|$, as required.)
• Aug 13th 2010, 02:52 AM
CaptainBlack
Quote:

Originally Posted by Swlabr
We can also use $\displaystyle cos(x): \mathbb{R} \rightarrow [-1, 1]$. Note that this is a surjection.

Noting that $\displaystyle cos(x) = cos(x+2\pi)$, if $\displaystyle x \in \mathbb{Q}$ then $\displaystyle x+2\pi \not\in \mathbb{Q}$. Thus, letting $\displaystyle f$ be the restriction of $\displaystyle cos(x)$ to $\displaystyle \mathbb{R}\setminus \mathbb{Q}$ we see that $\displaystyle f: \mathbb{R}\setminus \mathbb{Q} \rightarrow [-1, 1]$ is a surjection onto something with cardinality that of $\displaystyle \mathbb{R}$. This is sufficient.

(This is sufficient because if there exists a surjection from $\displaystyle A$ to $\displaystyle B$ then $\displaystyle |A| \geq |B|$. Similarly, if there exists an injection from $\displaystyle A$ to $\displaystyle B$ then $\displaystyle |A| \leq |B|$. Clearly the latter holds, and the former holds by what I just wrote about. Thus, $\displaystyle |\mathbb{R} \setminus \mathbb{Q}| = |\mathbb{R}|$, as required.)

This is quite nice, but it is a case of the formalism of the language used obscuring the idea, or at least increasing the work load required to see how nice a method it is. I blame Rudin myself, and Bourbaki for that matter.