proof

**DrunkenArse** · 06-09-2009 08:40 AM

a question of what mathematical proof is came up in my troll-bait thread that Xei took the bait out of yesterday. In answer I'm going to prove something that is of interest to almost everybody. Instead of putting this whole thing in that thread, I figured that it might be of interest to enough people to start a new thread. This is not a troll bait thread and I am willing to help anybody that wants to understand this proof but am not interested in arguing about it's legitimacy.That's the point of a proof. Any mathematician will back me up on this: It's true.

This is one of the more profound low-hanging fruits of pure mathematics. It is entirely useless thus far but is very pretty. The result is that there are different magnitudes of infinity. It was proven by a mathematician named Cantor sometime in the 1870's i believe.

We will prove this by proving that the set of real numbers between 0 and 1 is stricly larger then the set of natural numbers.

We start by assuming that they have the same 'size'. that means that we can put them into a one to one correlation so that each natural number is associated with one and only one real number in the range from 0 to 1 and that each real number in the range occurs exactly once in this association.

we don't really have a good way to write subscripts so read d1 as d sub 1.

then we can draw a diagram like this:

1 : d1 d2 d3 d4 d5 d6 d7 d8 d9 d10 .. .. ..
2 : d1 d2 d3 d4 d5 d6 d7 d8 d9 d10 .. .. ..
3 : d1 d2 d3 d4 d5 d6 d7 d8 d9 d10 .. .. ..
4 : d1 d2 d3 d4 d5 d6 d7 d8 d9 d10 .. .. ..

Interpret this as saying that dm in row n is the m'th digit of the real number associated with the number n.

now what we do is construct a new real number. I'll use e for it's digits to keep it separate. We do this by starting at d1 in row 1. If d1 row 1 = 6 then we set e1 to 7. If d1 row 1 is not 6 then we then we set it to 6. We then get e2 from d2 row 2 in the same way. e3 comes from d3 row 3 and, in general, we get em from dm row m. so the number e looks like .67676667667776767676776777677677776767676767676.. ........

The point of this is that we know that e is different from every real number that appears in our association because it differs in at least one digit. That means that we have a contradiction on our hands because we assumed that every real number does appear in the association. Because the only thing we assumed was that such an association exists and making that assumption allows us to construct a contradiction, we know that that assumption must be false. So the two sets must not have the same size. We also know that the real numbers must be larger because we have at least one that does not appear in association.

Thats it and that is mathematics.

**Xei** · 06-09-2009 03:02 PM

Good thread, I love this stuff.

I like the way that Penrose describes it though, it's a bit clearer.

Assume that you've established some one to one corrospondence between the naturals (1, 2, 3...) and the reals. It doesn't really matter what; for example:

1 : .7683...
2 : .7182...
3 : .0100...
4 : .1415...

And we assume that every real number has been included in the list.

However, if we construct a new real by taking the first digit from the first real and the second digit from the second real and so on, we will generate the following real:

.7101...

Now replace every digit 0 in this real by 1 and every digit not 0 by the digit 0:

.0010...

and hence we know by definition that this real is not in the original list, and hence there is no comprehensive mapping between the naturals and the reals.

To go into a little more detail, this is what mathematicians call 'uncountability', because if you think about it, when you count stuff, you are doing exactly this; assigning a natural number to each object. So what we are saying above is that not only are there an infinite number of reals, but you can't even count them, unlike the naturals.

Incedentally the rationals are countable. Say you have the rational

28/135.

Split this into its prime factors (none of which will be shared because they will cancel):

2.2.7 / 3.3.3.5 = 2^2.7 / 3^3.5

Now, double the power of each integer on top, and double and add one of each integer on the bottom. Then multiply them together:

2^4.7^2.3^7.5^3.

Hence you have a unique natural number for every rational number. You can get back to the rational by collecting all even powered numbers, halving the power, and then multiply them together to get the top of the fraction, and collecting all odd powered numbers, subtracting 1 and halving the power, then multiply them together, to get the bottom of the fraction.

Cool stuffs huh?

**DrunkenArse** · 06-09-2009 05:38 PM

Yeah, penrose's is much clearer. I forgot about it which is funny cause that books in my room.

I think that cantors "snake" proof that the rationals are countable is a bit clearer then penrose's though for someone that doesn't have a very high facility with arithmetical properties of the integers. here it is:

make a diagram as follows:

1/1 1/2 1/3 1/4 ......
2/1 2/2 2/3 2/4 .....
3/1 3/2 3/3 3/4 ......
4/1 4/2 4/3 4/4 ......
... ... .... ... ......

then we count them:

0 -> 1/1
1 -> 1/2
2 -> 2/1
3 -> 3/1
4 -> 2/2
5 -> 1/3
6 -> 1/4

because, following this pattern, every rational number is a finite distance from the starting point, they all get counted eventually. This proves that the size of the naturals is greater than or equal to the size of the set of rationals (greater than because, as you no doubt noticed, every rational has an infinite amount of representations in this diagram). But then the rationals contain the set of naturals so we can conclude that the size of the rationals is greater than or equal to the size of naturals. They are hence equal.

Thread: proof

LinkBack

Thread Tools

Display

proof

Bookmarks

Bookmarks

Posting Permissions