March 12th, 2016, 09:32 AM  #11 
Senior Member Joined: Mar 2016 From: UK Posts: 101 Thanks: 2 
Excellent response and you almost got me  but then I regressed. It might take me a while to formulate properly my reply. I see the argument and understand it better now  although to some extent I'm now drifting towards "what's the big deal  why does this tell us anything we didn't already know" (i.e. we already know that no set of Reals is complete since any two Real numbers must have more between them (hence Cantor's ability to use just [0,1] for his alleged proof ). I still don't really see how it proves R > N however  it still seems that if I can find a new bijection from R' ( = R U { d(R) } to N then that directly contradicts the proof and implies the proof must be flawed. "You said I can't do this, but look I can". Anyway, I need to express that better, . I don't want to just say the same things I've already said. The intuition thing is odd  intuitively there should be more of R than N  I mean there are loads of them , but equally there should be more of N than even N. The odd thing is, I completely accept that the latter is not true, but can't deal with the first one being correct. I am clearly very contrary! Back soon! Jim 
March 12th, 2016, 10:13 AM  #12 
Math Team Joined: Dec 2013 From: Colombia Posts: 6,877 Thanks: 2240 Math Focus: Mainly analysis and algebra  I don't argue that you can't create another list. I argue that because it is a list, it is necessarily incomplete. You can add one, ten, a million or a (countably) infinite quantity of numbers to your list if you like. But it will still be a list, and thus, by the diagonal argument, incomplete. One thing that might help is to look at how sets such as the rational numbers or the algebraic numbers are countable. We know they are countable because we have a counting scheme for them. (Both schemes actually include duplicates, but that just means that the rationals and algebraic numbers are subsets of countable sets and are thus countable.) Then think about how you might build a similar scheme for the real numbers. Don't spend too long on it, because it's impossible! But you might get some insight into the problems. 
March 12th, 2016, 10:40 AM  #13 
Senior Member Joined: Mar 2016 From: UK Posts: 101 Thanks: 2  Wait a cottonpickin' minute...
Back sooner than I expected for a side thought on diagonalization. For Cantor's proof to work, we must have that the sequence are all the same length and specifically infinite  we kind of do this intuitively but it's actually necessary because otherwise 0.1 = 0.10 = 0.100 etc. However, if the sequences are infinite then the basic premise that the n'th digit is different isn't useful anymore  in the limit, there is no n'th digit since for all n in N, n is not infinite. For a set that is actually infinite, we can't compare the n'th digits anymore. {note in real analysis and summing series we think of n > big, not actually being big so this doesn't impact anything there}. For any complete set of sequences of length n we can see that diagonalization will generate a sequence that isn't in the set  but it really isn't in the set since it's of length 2^n /= n  so it's no surprise and doesn't actually prove anything. At the limit, we can no longer consider the n'th digit because n is strictly finite. [aside: 2^n  c.f. power set proof] Summary  is there a proof (that doesn't reference the Natural numbers) that diagonalization is guaranteed to generate a new number on an infinite set of infinite sequences. 
March 12th, 2016, 10:55 AM  #14  
Math Team Joined: Dec 2013 From: Colombia Posts: 6,877 Thanks: 2240 Math Focus: Mainly analysis and algebra  Quote:
There is no "at the limit". This is set theory not analysis. Here infinite means "nonterminating". Unlikely. Countability/listability of a set is defined in relation to the natural numbers. They have to be in the proof. Last edited by v8archie; March 12th, 2016 at 11:43 AM.  
March 12th, 2016, 12:00 PM  #15 
Senior Member Joined: Mar 2016 From: UK Posts: 101 Thanks: 2 
Okay, I shall rephrase. For any complete set A of sequences of length n, diagonalisation yields a new sequence 's' which is 2^n digits long that differs from all numbers in S in the (n+1)th digit. for all n in N, the new sequence isn't in S anyway, because any sequence of length m>n is not in S and n+1 > n However, if we require an infinite set, then n+1 is no longer a valid concept  it doesn't exist  since if we can add one to n, then it n wasn't infinite. Ie. for diagonalisation to be guaranteed to yield a new number for an infinte set, we require that N not be countable. ? Jim 
March 12th, 2016, 12:17 PM  #16 
Math Team Joined: Dec 2013 From: Colombia Posts: 6,877 Thanks: 2240 Math Focus: Mainly analysis and algebra 
What happens for finite sequences (that is, terminating sequences) is irrelevant. The theorem talks only about infinite sequences. When we talk about infinite sequences we are talking not about terminating sequences of length $\infty$, but about nonterminating sequences. As long as the sequence we create doesn't terminate, it is another one of the same. The length of the sequence remains countable because a sequence is just a list of numbers. Just as adding sequences to your list doesn't stop it being a list, so an infinite sequence remains an infinite sequence even if you think you've added numbers to it.
Last edited by skipjack; March 13th, 2016 at 03:49 AM. 
March 12th, 2016, 02:57 PM  #17 
Senior Member Joined: Mar 2016 From: UK Posts: 101 Thanks: 2  Bit tiddly
Two comments: It doesn't matter whether or not it remains countable in this context  the whole point of this context is proving whether or not some things are countable  if we rely on something remaining or ceasing to be countable our argument is circular. and It must matter what happens in the finite cases because all natural numbers are finite  there are NO sequences for which there is an n'th digit where n is not finite. There are infinitely many such sequences where n is finite, but none where it is not. (read that again and tell me it isn't mad). For a set of sequences of size n, diagonalisation yields a sequence of length 2^n which must be a member of the whole set of sequences of length 2^n. Since each n is finite, each 2^n is also finite. There are always more numbers  be they integers or reals or whatever???? Alternatively (going decimal since you broke binary and it is now dead to me): There is a bijection between N and N' = { n in N : n = 10 m : m in N } badly written I think but  if I accept a bijection from any N to any N * 10, well I can always do it  really the integers are just a specialisation of the Reals  both are a sequences of (binary) digits and I can right or left shift as much as I want  as the sequences are countably long. I'm not sure we're going anywhere, I may be a hopeless case 
March 12th, 2016, 05:40 PM  #18  
Math Team Joined: Dec 2013 From: Colombia Posts: 6,877 Thanks: 2240 Math Focus: Mainly analysis and algebra  Quote:
False Quote:
We could represent the list of sequences as follows: $$\begin{matrix} a_{1,1} & a_{1,2} & a_{1,3} & \ldots & a_{1,n1} & a_{1,n} & a_{1,n+1} & \ldots \\ a_{2,1} & a_{2,2} & a_{2,3} & \ldots & a_{2,n1} & a_{2,n} & a_{2,n+1} & \ldots \\ a_{3,1} & a_{3,2} & a_{3,3} & \ldots & a_{3,n1} & a_{3,n} & a_{3,n+1} & \ldots \\ \vdots & \ddots \\ a_{n1,1} & a_{n1,2} & a_{n1,3} & \ldots & a_{n1,n1} & a_{n1,n} & a_{n1,n+1} & \ldots \\ a_{n,1} & a_{n,2} & a_{n,3} & \ldots & a_{n,n1} & a_{n,n} & a_{n,n+1} & \ldots \\ a_{n+1,1} & a_{n+1,2} & a_{n+1,3} & \ldots & a_{n+1,n1} & a_{n+1,n} & a_{n+1,n+1} & \ldots \\ \vdots \\ \end{matrix}$$ I hope that drives home the point that we have an infinite quantity of sequences, each with a finite index (the first subscript), and each sequence has an infinite quantity of elements, each with a finite index (the second subscript). Cantor's new sequence is formed by taking the sequence $\{a_{1,1}, a_{2,2}, a_{3,3}, \ldots, a_{k1,k1}, a_{k,k}, a_{k+1,k+1}, \ldots\}$ and changing every element to a different digit. Since neither the rows nor the columns of the matrix above have an endpoint, this diagonal sequence never runs out of members. It too is an infinite sequence (but is not one of the rows of the matrix. Quote:
I think we are getting somewhere, although I think your alcohol level was showing a bit tonight. I hope I've brought you a "moment of clarity". Last edited by skipjack; March 13th, 2016 at 04:00 AM.  
March 13th, 2016, 01:22 AM  #19  
Senior Member Joined: Mar 2016 From: UK Posts: 101 Thanks: 2  Quote:
Quote:
I think that where we're getting, however tortuous I'm making the journey, is to the heart of why I'm struggling. In fact, you very very nearly had me : Proposition: You can't index an infinite set using the natural numbers. Since each natural number is finite, any set indexed using them must be strictly finite also. Cantor's proof is that the proposition "countable" denies the possibility of constructing the set that Cantor uses to do his proof. but... The word "countable"  the bijection to the Naturals  is not required for this conclusion. In fact it's a complete distraction. ( We also don't need diagonalisation for it. ) The proof is NOT that you can always find another sequence, the proof is that the complete set of Reals is not representable by a set of sequences. This is different from proving they have different cardinality to the Natural numbers because I can pull the same trick for any infinite set  including the Natural numbers, since I can attempt to use a sequence to represent them, I can show that the set of sequences is not complete  because the elements of the sequence must be indexed  and therefore they are finite, therefore anything represented by an actual sequence must be finite. Any list of the Natural numbers must be incomplete  and I think we know this already. Countable is not a useful concept, in fact it's a paradox  it implies itself to be untrue. Last edited by skipjack; March 13th, 2016 at 04:03 AM.  
March 13th, 2016, 03:37 AM  #20 
Senior Member Joined: Mar 2016 From: UK Posts: 101 Thanks: 2 
Summary: There is no infinite sequence, because there is no infinite Natural number. Last edited by skipjack; March 13th, 2016 at 04:04 AM. 

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 