Tilted Forum Project Discussion Community - View Single Post - Cantor-Schroder-Bernstein Theorem

CSflim · 09-16-2003, 11:42 AM

I can answer the question to the different "sizes" in a fairly straight forward way.

All you need to do is take the sets N, Z and R.

N = Natural numbers, i.e. the numbers that we count with, positive whole numbers. 0,1,2,3,4,5,6,7,8,9...
Z = Integers: Positive whole numbers, zero and negative whole numbers. ...-4,-3,-2,-1,0,1,2,3,4...
R = Real numbers: All numbers that can be plotted on the number line:
-4.5, 2.7, 0.00001, pi, e, phi, etc.

Now as we can see N, Z and R are all infinite sets. The question is, are they all the same size?

Well compare N and Z. Surely Z is bigger, seeing as how it contains everything in N plus a whole lot more? Surely Z is twice as big? Well actually N and Z are the same size.

We can "count" all of the integers, by pairing them off with natural numbers.

Code:


N  -  Z
-------
0  :  0
1  :  1
2  : -1
3  :  2
4  : -2
5  :  3
6  : -3
7  :  4
8  : -4  
.
.
.
...etc.

you can continue this list for as long as you like, and you will always have a Natural Number to pair off to an Integer, i.e. both sets are the same size.

Now, the question remain, can we do the same thing for R? Actually we can't.
We can prove this.

Assume that R is countable. We will set up a list, pairing each N to an R. We needn't use any particular order for R.
In fact, just for simplicity, lets limit ourselves to just real numbers between 0 and 1.

Code:


N  -  R
0  :  0.789412334...
1  :  0.200000141...
2  :  0.319859632...
3  :  0.333333333...
4  :  0.999406180..
5  :  0.840369747...
6  :  0.897863254...
7  :  0.470940646...
8  :  0.789789789...
.
.
.
...etc

We now have a list which is infinitely long. We now need to prove that there exists a Real number (lying between 0 and 1) which is not on this list.

Easily done:
We construct a new number, which is not on our list as such:

Code:

N  -  R
0  :  0.789412334...
1  :  0.200000141...
2  :  0.319859632...
3  :  0.333333333...
4  :  0.999406180..
5  :  0.840369747...
6  :  0.897863254...
7  :  0.470940646...
8  :  0.789789789...
.
.
.

0.709309249...
we now add 1 to each digit, (letting 9+1=0)
0.810410350...
This number is necessarily not on our list, as it differs from each entry by at least one digit!
If we add this number to our list, we will be in no better of a position.
Hence we can see that N is the same size as Z, but smaller than R, even though they are all infinitely big!

dimbulb, I can see that you already knew this, but I think that it's a great proof to use to show people who refuse to accept that there is such a thing as "big infinity" and "small infinity"

.
Plus I think that itt also makes it easier to "visualise" the different "infinities".

As for your original post...what exactly is your question? Are you looking for a proof of this theorem?
"stupid theorem, and I don't need to be able to prove this,"
Didn't quite get what you're asking? Is it that, you don't "need" to be able to prove it, but that you would like to?

09-16-2003, 11:42 AM	#4 (permalink)
CSflim Sky Piercer Location: Ireland	I can answer the question to the different "sizes" in a fairly straight forward way. All you need to do is take the sets N, Z and R. N = Natural numbers, i.e. the numbers that we count with, positive whole numbers. 0,1,2,3,4,5,6,7,8,9... Z = Integers: Positive whole numbers, zero and negative whole numbers. ...-4,-3,-2,-1,0,1,2,3,4... R = Real numbers: All numbers that can be plotted on the number line: -4.5, 2.7, 0.00001, pi, e, phi, etc. Now as we can see N, Z and R are all infinite sets. The question is, are they all the same size? Well compare N and Z. Surely Z is bigger, seeing as how it contains everything in N plus a whole lot more? Surely Z is twice as big? Well actually N and Z are the same size. We can "count" all of the integers, by pairing them off with natural numbers. Code: N - Z ------- 0 : 0 1 : 1 2 : -1 3 : 2 4 : -2 5 : 3 6 : -3 7 : 4 8 : -4 . . . ...etc. you can continue this list for as long as you like, and you will always have a Natural Number to pair off to an Integer, i.e. both sets are the same size. Now, the question remain, can we do the same thing for R? Actually we can't. We can prove this. Assume that R is countable. We will set up a list, pairing each N to an R. We needn't use any particular order for R. In fact, just for simplicity, lets limit ourselves to just real numbers between 0 and 1. Code: N - R 0 : 0.789412334... 1 : 0.200000141... 2 : 0.319859632... 3 : 0.333333333... 4 : 0.999406180.. 5 : 0.840369747... 6 : 0.897863254... 7 : 0.470940646... 8 : 0.789789789... . . . ...etc We now have a list which is infinitely long. We now need to prove that there exists a Real number (lying between 0 and 1) which is not on this list. Easily done: We construct a new number, which is not on our list as such: Code: N - R 0 : 0.789412334... 1 : 0.200000141... 2 : 0.319859632... 3 : 0.333333333... 4 : 0.999406180.. 5 : 0.840369747... 6 : 0.897863254... 7 : 0.470940646... 8 : 0.789789789... . . . 0.709309249... we now add 1 to each digit, (letting 9+1=0) 0.810410350... This number is necessarily not on our list, as it differs from each entry by at least one digit! If we add this number to our list, we will be in no better of a position. Hence we can see that N is the same size as Z, but smaller than R, even though they are all infinitely big! dimbulb, I can see that you already knew this, but I think that it's a great proof to use to show people who refuse to accept that there is such a thing as "big infinity" and "small infinity" . Plus I think that itt also makes it easier to "visualise" the different "infinities". As for your original post...what exactly is your question? Are you looking for a proof of this theorem? "stupid theorem, and I don't need to be able to prove this," Didn't quite get what you're asking? Is it that, you don't "need" to be able to prove it, but that you would like to? __________________ Last edited by CSflim; 09-16-2003 at 11:53 AM..