prove set of irrational number is uncountable

**tsang** · August 8th 2010, 02:07 AM

Hi, can friends here please help me with this question? I'm really struggling with it.

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.

**Vlasev** · August 8th 2010, 02:29 AM

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.

**tsang** · August 8th 2010, 03:09 AM

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.

**Vlasev** · August 8th 2010, 03:13 AM

You only need to show that the irrationals are the complement of the rationals.

**tsang** · August 8th 2010, 03:19 AM

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.

**Plato** · August 8th 2010, 03:21 AM

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

**tsang** · August 8th 2010, 03:25 AM

Originally Posted by Plato

You know that $\mathbb{R}$ is uncountable and $\mathbb{Q}$ is countable.
The union of two countable set is countable.
So what does that mean about $\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.

**HallsofIvy** · August 8th 2010, 04:39 AM

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."

**Ares_D1** · August 8th 2010, 05:49 AM

Originally Posted by Plato

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

I see what you're doing here. The set $\mathbb{Q}\cup (\mathbb{R}\setminus \mathbb{Q})$ = $\mathbb{R}$ , which we know is uncountable. We also know that $\mathbb{Q}$ is countable. But a number must either be rational or irrational, so it follows logically that $\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 $\mathbb{Q}\cup (\mathbb{R}\setminus \mathbb{Q})$ = $\mathbb{R}$ (which is obvious), or should we go about proving this first?

**HallsofIvy** · August 8th 2010, 08:26 AM

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.

**Ares_D1** · August 8th 2010, 08:54 AM

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.

**CaptainBlack** · August 11th 2010, 12:05 AM

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 $$$[0,1)$ and with decimal expansions, so the decimal expansion of a real $$$a$ in $$$[0,1)$ is $0.a_1a_2,...\ :$ $a_i \in \{0,1,2,3,4,5,6,7,8,9\}$ .

I will use the expressions "the decimal expansion of $$$ a$ is periodic" or " $$$ a$ is periodic" to mean the eventually the decimal expansion of $$$ a$ becomes periodic.

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

Lemma

A real in $$$ [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 $x(i), i=1,2..$ is an enumeration. Let $x_{i,j}$ denote the $$$ j$ th term in the decimal expansion of $x(i)$

Now we combine Cantor's slash argument with an idea of Liouville's, define the real $$$ z$ with decimal expansion:

$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 $z \in [0,1)$ and $$$z$ is not periodic, so as $$$z$ differes from each irrational in our enumeration at at least one place in its' decimal expansion it is not in our enumeration and $$$z$ is irrational. hence we have the required contradiction ...

CB

**Swlabr** · August 11th 2010, 02:40 AM

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)

$\vdots$

CB

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

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

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

**CaptainBlack** · August 13th 2010, 02:52 AM

Originally Posted by Swlabr

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

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

(This is sufficient because if there exists a surjection from $A$ to $B$ then $|A| \geq |B|$ . Similarly, if there exists an injection from $A$ to $B$ then $|A| \leq |B|$ . Clearly the latter holds, and the former holds by what I just wrote about. Thus, $|\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.

Thread: prove set of irrational number is uncountable

LinkBack

Thread Tools

Display

prove set of irrational number is uncountable

prove set of irrational number is uncountable

Similar Math Help Forum Discussions

Prove that z=log base p (qr) is an irrational number

Prove that e is an irrational number!�ee is is an irrational number!

Prove that the square root of a non-square number is irrational

Discrete Math - Prove that if x is irrational, then 1/x is irrational?

[SOLVED] Uncountable: A is a countable subset of an uncountable set X, prove X \ A un

Search Tags