Math Is Fun Forum

Stanley_Marsh

Member

Registered: 2006-12-13

Posts: 345

Set Theory Again

Prove whether the set of all  irrational real numbers countable.

I think it's uncountable

Then I think the set of rational number is countable and closed

then its complement the set of irrational is open , thus uncountable.

I don't know If I have misunderstood these math concepts.

Please give a proof

Last edited by Stanley_Marsh (2007-03-31 19:40:39)

---

Numbers are the essence of the Universe

Zhylliolom

Real Member

Registered: 2005-09-05

Posts: 412

Re: Set Theory Again

Try it this way. First prove that R is uncountable (you can do this by proving the open interval (0, 1) is uncountable, if you need a clue how to do this then ask). Then prove that Q (the set of rational numbers) is countable (using Cantor's diagonal argument). Then prove that the union of two countable sets is countable. From here you can argue that if I (the set of irrational numbers) is countable, then

(how do you type union without LaTeX? I can only make ∩ ) is countable, contrary to R's uncountability. Thus I must be uncountable.

This is probably a slightly sloppy way to prove it, as I threw it together pretty quickly. But it works.

Just remember this. If a set is countable (as in countably infinite), then it may be written S = {s[sub]1[/sub], s[sub]2[/sub], ...}, that is, you can index the elements of S with the naturals, or in other words there is a one-to-one correspondence between S and N. So if you want to prove a set is countable, you should show that there exists an indexing of the set using the naturals. For example, to prove T = {1, 3/2, 2, 5/2, 3, 7/2, ...} is countably infinite, you just need to give such an indexing. Here is one: t[sub]n[/sub] = (n + 1)/2. Now to prove that a set is uncountable, you need to show that no such indexing will give you every element of the set. These are the standard methods you should use to prove countability and uncountability.

Last edited by Zhylliolom (2007-03-31 20:25:24)

Stanley_Marsh

Member

Registered: 2006-12-13

Posts: 345

Re: Set Theory Again

this question is from the Rudin's book , he just simply mention   there is a one-to-one correspondence between S and N if S is countable, and that is .It's more like a handbook than a textbook.
  and I haven't learned about Cantor's diagonal argument  ,About proving the open interval (0, 1) is uncountable , Can I do it this way?
  Assume it's countable then the set

   I am borrowing the Euclid's proving there are infinite primes method.

Last edited by Stanley_Marsh (2007-03-31 21:22:14)

---

Numbers are the essence of the Universe

Stanley_Marsh

Member

Registered: 2006-12-13

Posts: 345

Re: Set Theory Again

The proof of Rational being countable is given in the book

---

Numbers are the essence of the Universe

Zhylliolom

Real Member

Registered: 2005-09-05

Posts: 412

Re: Set Theory Again

Your attempt doesn't quite do the trick. Here's a way to do it:

Assume that (0, 1) is countable, so that there exists some sequence {s[sub]n[/sub]} such that for any point x ∈ (0, 1), x is also a term of this sequence. Since 0 < s[sub]n[/sub] < 1, we can write s[sub]n[/sub] = 0.u[sub]n,1[/sub]u[sub]n,2[/sub]u[sub]n,3[/sub]..., where each u[sub]n,i[/sub] takes a value from 1 to 9. Now consider the real number y given by the decimal y = 0.v[sub]1[/sub]v[sub]2[/sub]v[sub]3[/sub]..., where

No term of {s[sub]n[/sub]} can be equal to y, since y differs from each s[sub]i[/sub] in the i[sup]th[/sup] decimal place. But y ∈ (0, 1). Then the terms of {s[sub]n[/sub]} do not constitute the interval (0, 1). Thus (0, 1) is uncountable, and since this set is contained in R, R is uncountable as well.

As you can see, the approach to proving the uncountability of a set is to state the set as generically as possible in terms of natural indices and then show that writing the set this way will leave out some element that is supposed to be included.

I don't quite understand what you wrote. First, you make it look as though S is finite (with k elements). Also, if S was finite (as you seem to imply) and consisted of only rational numbers, then sure it's possible that s[sub]i[/sub] might not be in S, but s[sub]i[/sub] would be another rational number. Then from your argument we can say since this happens, Q is uncountable, which is certainly false. Here, let me restate your argument for R for Q instead and tell me if you agree:

Stanley_Marsh

Member

Registered: 2006-12-13

Posts: 345

Re: Set Theory Again

What I wanted to do was , to show that there is always one new real number  between two real number  , if the set of real is countable, then between two element , there is always a new element in Real , but not in the set , contradict with the definition of the set which contains all real numbers. thus real number is uncountable.

---

Numbers are the essence of the Universe

Zhylliolom

Real Member

Registered: 2005-09-05

Posts: 412

Re: Set Theory Again

That will show that R is an infinite set, but it doesn't tell us whether it is countably or uncountably so. Q also has the property that between any two of its elements lies another number in Q. But Q is countable. So your method only shows that a set is infinite (by demonstrating that there are an endless amount of elements) but it does not address the concept of countability. It needs to show that there exists an indexing of the set using the natural numbers/one-to-one correspondence to N (or that there doesn't) to demonstrate countability (uncountability). You need to stick with the definitions as closely as possible; infinity can trip you up pretty easily if you try to work with it through intuition alone.

Last edited by Zhylliolom (2007-04-01 10:18:32)

Stanley_Marsh

Member

Registered: 2006-12-13

Posts: 345

Re: Set Theory Again

Yah , right , your method shows that whatever S_n be , there is a y to avoid it.

---

Numbers are the essence of the Universe