My Math Forum Help me to understand Cantor please

 Topology Topology Math Forum

 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: 7,305
Thanks: 2443

Math Focus: Mainly analysis and algebra
Quote:
 Originally Posted by Jimbo You said I can't do this, but look I can
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 cotton-pickin' 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: 7,305
Thanks: 2443

Math Focus: Mainly analysis and algebra
Quote:
 Originally Posted by Jimbo 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
Each indinvidual $n \in \mathbb N$ is finite, but there are an infinite number of them. The numbers in a sequence (or the digits in a decimal) are indexed by the natural numbers, as are the elements in a list. In a finite decimal, there exists an $N \in \mathbb N$ such that there are no digits with an index greater than $N$. In an infinite decimal this is not the case: there is a decimal digit for every natural number - an infinite number of them.

There is no "at the limit". This is set theory not analysis. Here infinite means "non-terminating".

Quote:
 Originally Posted by Jimbo 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.
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: 7,305 Thanks: 2443 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 non-terminating 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: 7,305
Thanks: 2443

Math Focus: Mainly analysis and algebra
Quote:
 Originally Posted by Jimbo 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.
I think I agree with you on this. My lack of certainty is because I've never tried to explain this in terms of changing lengths of sequence or changing lists. This is mostly because they don't actually feature in the proof, but I'm trying to explain this as much as possible in your own terms.

Quote:
 Originally Posted by Jimbo It must matter what happens in the finite cases
False
Quote:
 Originally Posted by Jimbo 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.
True, true, true and true. But I think there is some confusion in here. Here are some points to get clear, some of which we agree on already:
1. All natural numbers are finite;
2. In a list every position is indexed by a natural number. The first element is indexed 1, the second is indexed 2, the third is indexed 3, ..., the $n$th is indexed $n$, ...: every index is finite because it is a natural number, but we can have an infinite list because there is an infinite quantity of natural numbers;
3. An infinite list is non-terminating: there is no last element and no end, the indexes just keep going - incrementing by one for each element of the list.
4. We have an infinite list of sequences, so each is indexed with a natural number;
5. Each of the sequences is infinite, but the elements of the sequence is indexed with a natural number - an infinite sequence is $\{a_1, a_2, a_3, \ldots, a_{n-1}, a_n, a_{n+1}, \ldots\}$. Again, an infinite sequence is non-terminating, there is no last element and no end, the indexed just keep going incrementing by one for each element of the sequence.
6. Since the list is infinite, we have an $k$th sequence in the list for any $k \in \mathbb N$. And since the sequence is infinite, it has a $k$th element $a_k$ for any $k \in \mathbb N$.
7. We have no need for non-finite indexes which is good, because there aren't any.

We could represent the list of sequences as follows:
$$\begin{matrix} a_{1,1} & a_{1,2} & a_{1,3} & \ldots & a_{1,n-1} & a_{1,n} & a_{1,n+1} & \ldots \\ a_{2,1} & a_{2,2} & a_{2,3} & \ldots & a_{2,n-1} & a_{2,n} & a_{2,n+1} & \ldots \\ a_{3,1} & a_{3,2} & a_{3,3} & \ldots & a_{3,n-1} & a_{3,n} & a_{3,n+1} & \ldots \\ \vdots & \ddots \\ a_{n-1,1} & a_{n-1,2} & a_{n-1,3} & \ldots & a_{n-1,n-1} & a_{n-1,n} & a_{n-1,n+1} & \ldots \\ a_{n,1} & a_{n,2} & a_{n,3} & \ldots & a_{n,n-1} & a_{n,n} & a_{n,n+1} & \ldots \\ a_{n+1,1} & a_{n+1,2} & a_{n+1,3} & \ldots & a_{n+1,n-1} & 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_{k-1,k-1}, 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 end-point, 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:
 Originally Posted by Jimbo 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.
This is false and it's a really important point. The integers are all finite. This means that every single one of them is a finite string of digits. This means that they have a definite start point and a definite end point. The real numbers consist of an integer part to the left of the decimal point (which is finite in length) but the part to the right of the decimal point is of infinite length. This means that it never terminates (all "terminating decimals" can be written in a non-terminating fashion: by adding an infinite string of zeros to the right hand end for example). You can multiply a real number by $10^m$ for any natural number $m$ and shift the decimal point as much as you like, but there will always be a finite string of numbers to the left of the decimal point and an infinite string of numbers to the right.

Quote:
 Originally Posted by Jimbo I'm not sure we're going anywhere, I may be a hopeless case
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:
 I think we are getting somewhere
Actually, I think we are too, I'm just aware of your freely given time.

Quote:
 although I think your alcohol level was showing a bit tonight.
Sorry (it's showing this morning too )

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