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 RThis 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 relabel 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,305 Thanks: 2443 Math Focus: Mainly analysis and algebra  Quote:
Quote:
Quote:
Quote:
Quote:
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 recount  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,305 Thanks: 2443 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:
Quote:
Quote:
All natural numbers are finite because natural numbers are defined as:
The existence of irrational numbers does not require the real numbers to be uncountable. Quote:
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
Thankyou. 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,305 Thanks: 2443 Math Focus: Mainly analysis and algebra  Quote:
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 recount 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:
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 counterexample 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:
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. Sorry this is wordy and thanks in advance for your forbearance. 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,305 Thanks: 2443 Math Focus: Mainly analysis and algebra  Quote:
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:
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 nonbinary 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:
Try "listable" as above. It is exactly the same, but intuitively a little easier to deal with. But "infinity" isn't a number. So is it really "more than"? The big problem with all of this is that it is highly counterintuitive. 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 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
cantor set  anjuzz  New Users  3  July 15th, 2014 06:51 AM 
Cantor Problem  kaybees17  Real Analysis  2  December 2nd, 2013 07:45 AM 
Cantor  kingsandqueens  Number Theory  14  November 24th, 2010 05:22 AM 
The Cantor set  Jamers328  Calculus  2  November 9th, 2008 02:33 PM 
Cantor Space  kryptos  Real Analysis  0  November 20th, 2006 05:26 PM 