My Math Forum Help me to understand Cantor please

 Topology Topology Math Forum

 March 10th, 2016, 12:01 PM #1 Senior Member   Joined: Mar 2016 From: UK Posts: 101 Thanks: 2 Help me to understand Cantor please Hi all, Hesitate to post, especially as I know this is a topic that won't die, even though it's done to death. However, I think I've narrowed down why I struggle to accept Cantor's arguments to a few quite simple points. This may go on a little, for which I apologise. However, hopefully if you can explain to me why my thoughts below are wrong, it might help a lot of people other than me . First problem: I don’t see why the diagonalization argument proves what Cantor says it proves: If I use R for convenience, knowing that Cantor uses a subset thereof, and we accept that I’m in a text editor that has limited character support or insufficiently skilled in the use of one that doesn't… If I summarise Cantor’s argument as: if there’s a bijection between N and R, then I can find a new element in R, that’s not in the bijection, therefore there is no bijection. Okay I get that, but it seems to me that if I can find a new bijection between N and the new extended R then it falls apart… I take R and do diagonalization I get a new value ‘d(R)’ that is not a member of R I define N’ = { n in N : n >= 2 } There is a bijective function ( +1 ) between N and N’ Therefore there is a bijection between N’ and R Therefore there is a bijection between N’ U { 1 } and R U { d(R) } We note that N’ U {1} = N This is essentially the same argument used to prove that 0.999…. = 1 ( if you expand 0.999 to be the sum over N of a series of 9 * 10^-n ). Second problem: A power set has greater cardinality that its parent set. Okay, the problem isn’t with that, the problem is that I don’t get how this extends to infinite sets: the actual size of the power set for a set of size ‘n’ is exactly 2^n, I don’t see how 2^n can ever not be a natural number, which if we say that the cardinality of the power set of N is greater than that of N itself, well, it can’t be a natural number. Seems like something of a contradiction. Third problem: A sequence of binary digits (mapped as Cantor does) is a rational number. Every digit represents the reciprocal of a power of two – it’s a fraction – and the sequence is a sum of those fractions ?????? Fourth problem: I don’t see how there is a bijection between sequences of binary digits and real numbers. Since 0.0111… = 0.1 at least some real numbers have two representations (I’d suggest all of them in fact?). I’ve seen an argument that only a countable subset of the real numbers are repeats but this is essentially a circular argument since it requires that the real numbers be uncountable for it to be useful – therefore you can’t use it as part of the proof that real numbers are uncountable. Fifth problem: If I take the sequence of binary digits and reflect it through the decimal point – or re-label the digits 2^0, 2^1, 2^2, etc rather than 2^-1 2^-2 etc. I get a natural number. They do get kind of big I admit, but I don’t see how that’s a problem. Thank you for your patience in the above and I hope you can shed some light on the problem for me. Jim
March 10th, 2016, 01:48 PM   #2
Math Team

Joined: Dec 2013
From: Colombia

Posts: 7,232
Thanks: 2411

Math Focus: Mainly analysis and algebra
Quote:
 Originally Posted by Jimbo Hesitate to post, especially as I know this is a topic that won't die, even though it's done to death. However, I think I've narrowed down why I struggle to accept Cantor's arguments to a few quite simple points.
I have no problem with explaining the proof to someone who wants to listen.

Quote:
 Originally Posted by Jimbo Okay I get that, but it seems to me that if I can find a new bijection between N and the new extended R then it falls apart…
The key step of Cantor's argument is the preliminary proof which shows that for every countable subset of the real numbers / infinite binary sequences, there is a real number / infinite binary sequence that is not in the countable subset. This proof does not require the list to be complete, but with it we prove that no list is complete. This is completely analogous to Euclid's proof that for every set of prime numbers there exists a prime that is not in the set, and the use of that result to prove that there are an infinite number of primes.

Quote:
 Originally Posted by Jimbo the actual size of the power set for a set of size ‘n’ is exactly 2^n, I don’t see how 2^n can ever not be a natural number
For an infinite set, the size of the set is not a natural number, so neither is the size of the power set.

Quote:
 Originally Posted by Jimbo A sequence of binary digits (mapped as Cantor does) is a rational number. Every digit represents the reciprocal of a power of two – it’s a fraction – and the sequence is a sum of those fractions
An infinite sum of rational terms is not necessarily rational. For example: $\sum \limits_{n=1}^\infty {1 \over n^2} = {\pi^2 \over 6}$ and $\sum \limits_{n=0}^\infty {1 \over n!} = \mathrm e$, and more trivially $0.1101000100000001\ldots = \sum \limits_{n=0}^\infty 10^{-2^n}$

Quote:
 Originally Posted by Jimbo I don’t see how there is a bijection between sequences of binary digits and real numbers.
A sequence of binary numbers can be seen as the digits after the "decimal" point in the binary representation of a number between zero and one. There is a representation like this for every decimal between zero and one because we have just changed the base.

Quote:
 Originally Posted by Jimbo If I take the sequence of binary digits and reflect it through the decimal point – or re-label the digits 2^0, 2^1, 2^2, etc rather than 2^-1 2^-2 etc. I get a natural number.
No you don't. At least, you don't if the sequence is infinite, which it is required to be in the Cantor proof. All natural numbers have a finite number of digits (because they are finite).

Last edited by v8archie; March 10th, 2016 at 01:56 PM.

 March 10th, 2016, 02:37 PM #3 Senior Member   Joined: Mar 2016 From: UK Posts: 101 Thanks: 2 Thanks, Struggling with the editor and quoting, apologies. I'm extremely happy to listen, but I won't promise to understand. When I don't, forgive me if I seem impertinent We may never get there of course ... sigh. c.f. Euclid's proof - all the primes are natural numbers, kind of by definition, therefore his proof also proves that for all subsets of natural numbers there are natural numbers that are not in the set (since some of the subset must be prime and this subset of the subset cannot contain all the primes). Which would suggest that the natural numbers are not countable - surely this is just the same argument Cantor is using for the Reals - and that's extremely uncomfortable. This doesn't address the point I try to make either - whenever we find a new real number we can re-count - and then the new set is still countable. For any new number not in the original countable set. Alternatively, this may restate the contradiction I struggle with: We can show that there is a bijection between the Natural numbers and the even natural numbers and also with the odd natural numbers. The union of the odds and the evens is the natural numbers. I just don't think that bijections or "countable" works for infinite sets. "for an infinite set the size of the set..." "no you don't ..." That feels like proof by definition, which I kind of struggle struggle with. The sums of series - fair cop, nice point, etc. Although of course that also depends upon the proof that the reals are not countable??????
 March 10th, 2016, 02:43 PM #4 Senior Member   Joined: Mar 2016 From: UK Posts: 101 Thanks: 2 "A sequence of binary numbers can be seen as the digits after the "decimal" point in the binary representation of a number between zero and one. There is a representation like this for every decimal between zero and one because we have just changed the base." Sorry, missed this. I understand that bit, what I don't get is that 0.011111.... = 0.1 (binary of course) and therefore there is no bijection. More than one sequence represents each individual real number. I.e. a proof that the sequences are uncountable is not a proof that the reals are uncountable since there is no 1 to 1 mapping between sequences and reals. thanks Jim
March 10th, 2016, 05:05 PM   #5
Math Team

Joined: Dec 2013
From: Colombia

Posts: 7,232
Thanks: 2411

Math Focus: Mainly analysis and algebra
Re: Euclid
Perhaps I should have been clearer. In the case of Euclid, he proved that for every finite set of primes, there exists a prime that is not in the set. From this the logical consequence is that the set of all primes is not finite. It is, in fact, countably infinite.

Cantor's proof pulls a similar trick, but on countably infinite sets. He proves that for every countably infinite set of real numbers/infinite binary sequences, there exists a real number/infinite binary sequence that is not in the set. From this the logical conclusion is that the set of real numbers/infinite binary sequences is not countably infinite.

Quote:
 Originally Posted by Jimbo This doesn't address the point I try to make either - whenever we find a new real number we can re-count - and then the new set is still countable.
But you can recount as many times as you like, whatever countable set you come up with cannot contain all of the real numbers/infinite binary sequences. If you accept the infinitude of primes, you must logically accept this argument that the real numbers/infinite binary sequences are uncountable because the arguments are precisely analogous.

Quote:
 Originally Posted by Jimbo We can show that there is a bijection between the Natural numbers and the even natural numbers and also with the odd natural numbers. The union of the odds and the evens is the natural numbers.
True, I don't know what your point is though.

Quote:
 Originally Posted by Jimbo I just don't think that bijections or "countable" works for infinite sets.
What do you mean "you don't think it works"? You just stated that you can form bijections between infinite sets, giving examples. "Countable" is a definition - that a bijection exists between a set and the natural numbers. It was probably Cantor's greatest insight to state that this is the rigorous mathematical definition of counting.

All natural numbers are finite because natural numbers are defined as:
• $1 \in \mathbb N$; and
• $n \in \mathbb N \implies (n+1) \in \mathbb N$
From this, if there were an infinite number $m \in \mathbb N$ then we would also have $(m+1) \in \mathbb N$. That is, a natural number bigger than infinity. Also, because 1 is finite, there would be a greatest finite natural number $p$ such that $(p+1)$ is infinite. Since all of these are not true, we conclude that the natural numbers are all finite.

The existence of irrational numbers does not require the real numbers to be uncountable.

Quote:
 Originally Posted by Jimbo I.e. a proof that the sequences are uncountable is not a proof that the reals are uncountable since there is no 1 to 1 mapping between sequences and reals.
If the sequences are countable, any infinite subset of a countably infinite set is itself countably infinite. This means that if the sequences were countable, the real numbers would be countable.

The real numbers with multiple binary representations (these are the terminating representations) each have exactly two representations. For example: 0.1000... and 0.0111.... The union of two countably infinite sets is itself countable (associate the members of the first set with the odd natural numbers and the members of the second with the even natural numbers). This means that if the real numbers were countable, the infinite binary sequences would also be countable.

 March 10th, 2016, 11:10 PM #6 Senior Member   Joined: Mar 2016 From: UK Posts: 101 Thanks: 2 Need to ponder Thank-you. I feel a slightly painful light at the back of my head, but I'm not convnced yet. I also worry that some of the reasoning is circular. I will need some (possibly significant but hopefully finite) time... I also feel the need to try to use the formatting better. Jim
March 11th, 2016, 05:36 AM   #7
Math Team

Joined: Dec 2013
From: Colombia

Posts: 7,232
Thanks: 2411

Math Focus: Mainly analysis and algebra
Quote:
 Originally Posted by Jimbo I feel a slightly painful light at the back of my head, but I'm not convnced yet. I also worry that some of the reasoning is circular.
This is quite difficult stuff to understand. In particular it challenges completely our preconceived views on various ideas. To understand it you have to abandon the idea that you know what certain things mean in an infinite context. In particular, anything that is not formally defined is not fixed.

I've just written a more comprehensive post on background to the subject here.

The definition of the natural numbers and the definition of what it means for a number to be "finite" are very close to each other, but both are reasonable on their own terms. The combination leads easily to the conclusion that numbers are finite.

Last edited by skipjack; March 11th, 2016 at 05:55 AM.

March 11th, 2016, 11:16 AM   #8
Senior Member

Joined: Mar 2016
From: UK

Posts: 101
Thanks: 2

Hi again, and thanks for your time, the post on the other forum was extremely helpful.

Note that here I may make some arguments similar to another poster. I am not he and I hope to be a bit more precise. Probably still wrong of course...

Okay, so I'm fairly comfortable with the natural number side of things, I'm going to ignore a couple of the side issues and go back to my "problem 1". I think debate there will hold the key.

I'm also going to proceed in this text as though the argument I use to re-count the set of Reals is correct to avoid pointlessly complex language. We can discuss whether or not it is actually correct thereafter. At the end of the day I wouldn't be here if I understood why I was wrong!

I think it's also important to note that I don't argue about the actual cardinality of the 3 sets in play - R, N, and sequences of binary digits - although there may be relevent consequences, I don't think my arguments address that - here I'm only arguing about Cantor's proof.

Quote:
 But you can recount as many times as you like, whatever countable set you come up with cannot contain all of the real numbers/infinite binary sequences.
I think that's the point - I can recount as many times as I want - while you can always find a new Real number, I can always find a new bijection. Why is one "always" better than the other?

I accept that this is completely contradictory to Cantor's conclusion - however that doesn't matter either. What my reasoning shows is that the argument he puts forward leads to a contradiction since he claims that if there is a bijection between his initial set and N then there is no bijection between his new set and N - but I can write one down. I.e. I believe my reasoning provides a counter-example to Cantor's conclusion. (This is also why I commented on the even / odd / natural number thing - it's very similar).

Essentially, if I could prove that Bond villains never had white cats, it wouldn't make it true. One counter example is sufficient.

Anyway, three possibilities:
1. my reasoning is flawed
2. his reasoning is flawed
3. his assertion that the natural numbers is countable leads to an axiomatic contradition

While I accept that the first is the most likely, I'd like to offer the following:

Cantor's proof relies upon the assertion that diagonalisation always creates a new number - for finite sets this is easy to see - for infinite sets of sequences - maybe, unsure - however for Real numbers I offer the set :

0.1
0.001
0.0001
...

Diagonalisation yields 0.0111... = 0.1 which is in the set.

One counter example is sufficient but actually there are an infinite number of examples analogous to this with the common feature of lots of '0' on the key diagonal, most of what is to the right of that is unimportant.

Also, if like Cantor I consider any infinite subset of the Real numbers, but ignore all the bit about the bijection with the Natural numbers and just do diagonalisation on it, according to Cantor's argument I can find a Real number that is not in that set. Since the set of all Real numbers is a subset of the Real numbers this implies that all the real numbers are not all the real numbers. I.e. the assertion that there is any function that can act upon any subset of the Real numbers and guarantee to find a new real number cannot be true as it leads directly to a contradiction.

Ultimately I think my problem is with the word "countable". I think it's very easy to write down but I don't think it means anything. "Countably infinite" is trying to force Natural number like behaviour on a thing which isn't a natural number.

Intuitively this makes sense - "you can't have more than infinity" - even if it's also really obvious that there are more Reals than Naturals, or indeed Naturals than Even Naturals.

If Cantor had argued the other way around - there's a bijection between R and N but look - I can find a new bijection between R and N' so that "frees up 1" - how would that be less valid? There is a symmetry between the two infinite sets and that is where the argument differs from Euclid - since he requires no comparison to a different set to prove the primes are infinite.

Jim

 March 11th, 2016, 11:21 AM #9 Senior Member   Joined: Mar 2016 From: UK Posts: 101 Thanks: 2 Oh, and I should add - I'm slowly drifing towards the end of beer bottle #3 - after this point I tend to find that my levels of coherence reduce but my levels of wisdom reduce more. So I may post a post of total drivel - if necessary, please ignore Jim
March 11th, 2016, 12:18 PM   #10
Math Team

Joined: Dec 2013
From: Colombia

Posts: 7,232
Thanks: 2411

Math Focus: Mainly analysis and algebra
Quote:
 Originally Posted by Jimbo I think that's the point - I can recount as many times as I want - while you can always find a new Real number, I can always find a new bijection. Why is one "always" better than the other?
Argument 1:
Step 1 of the proof is to show that given any list of real numbers, there is always (at least one) that is not on the list. If no list of real numbers contains all of the real numbers, any complete collection of real numbers must not be listable.

In reality, we can create an infinitude of real numbers that are not on your list. Cantor creates one that differs from the $n$th number on your list in the $n$th decimal place, but we can also create one that differs from the $n$th number on your list in the $(n+1)$th decimal place, and another that differs from the $n$th number on your list in the $(n+2)$th decimal place. In fact any injection $f:\mathbb N \to \mathbb N$ provides another example that is not on your list. I believe (but am not certain) that there are uncountably many such functions.

Argument 2:
Cantor's argument is exactly the same as Euclid's argument for the infinitude of primes. Euclid shows that any for any finite collection of primes there is a prime that is not in the collection. If no finite collection contains all of the primes, any complete collection of primes must not be finite.

If you believe in the infinitude of primes, you should believe in Cantor's argument, because it is essentially the same.

Quote:
 Originally Posted by Jimbo for Real numbers I offer the set : 0.1 0.001 0.0001 ... Diagonalisation yields 0.0111... = 0.1 which is in the set. One counter example is sufficient but actually there are an infinite number of examples analogous to this with the common feature of lots of '0' on the key diagonal, most of what is to the right of that is unimportant.
Good argument! But I think I can beat it, although these are just off the top of my head and possibly not totally rigorous.

Argument 1:
If you have a complete list of real numbers, you cannot possibly have them all with a zero in the $n$th place of the $n$th number on the list because there are as many numbers that start with a string of 1s that you must also include.

Argument 2:
If we work with decimals instead of binary numbers, we can avoid the problem. (Indeed, any non-binary base will do). I can create my new real number by taking every digit from the diagonal that is not a 3 (for example) and writing it as a 3. Every digit that is a 3 on the diagonal, I will write as a 2 (for example). In this way you never get a real number that has more than one representation in the decimals.

Quote:
 Originally Posted by Jimbo Since the set of all Real numbers is a subset of the Real numbers this implies that all the real numbers are not all the real numbers. I.e. the assertion that there is any function that can act upon any subset of the Real numbers and guarantee to find a new real number cannot be true as it leads directly to a contradiction.
It is this contradiction that is usually used as the punch-line for the proof. The point you are missing is that the set of real numbers that you start with must be listable. So the contradiction you find is that a complete set of real numbers cannot be formed into a list.

Quote:
 Originally Posted by Jimbo Ultimately I think my problem is with the word "countable".
Try "listable" as above. It is exactly the same, but intuitively a little easier to deal with.
Quote:
 Originally Posted by Jimbo Intuitively this makes sense - "you can't have more than infinity" - even if it's also really obvious that there are more Reals than Naturals, or indeed Naturals than Even Naturals.
But "infinity" isn't a number. So is it really "more than"? The big problem with all of this is that it is highly counter-intuitive. There is no reason whatsoever that we, who encounter only finite things, should have any accurate intuition about the infinite. My advice is to leave your intuition at the door and accept what logic tells you. That's not always so easy to do.

 Tags cantor, understand