# Cantor's Diagonal Theorem

• November 17th, 2011, 07:46 PM
chinglu
Cantor's Diagonal Theorem
Let's assume Cantor's Diagonal Theorem is correct.

That means there is a sequence of 0's and 1's that is not in the list of all sequences of 0's and 1's.

But, if that sequence is not in the list, then the list must not be complete, meaning the list is not the list of all sequences of 0's and 1's because it is missing at least one sequence.

Hence, the conclusion does not follow.
• November 18th, 2011, 05:05 AM
Strange
Quote:

Originally Posted by chinglu
Let's assume Cantor's Diagonal Theorem is correct.

What is "Cantor's Diagonal Theorem"? I am not familiar with it.

Quote:

That means there is a sequence of 0's and 1's that is not in the list of all sequences of 0's and 1's.

But, if that sequence is not in the list, then the list must not be complete, meaning the list is not the list of all sequences of 0's and 1's because it is missing at least one sequence.
That is a reasonable (if rather sloppily word) summary of Cantor's diagonal argument.

Quote:

Hence, the conclusion does not follow.
Which conclusion?
• November 18th, 2011, 05:32 PM
mathman
The conclusion of Cantor's theorem is that there is no COUNTABLE list.
• November 18th, 2011, 09:25 PM
chinglu
Quote:

Originally Posted by Strange
Quote:

Originally Posted by chinglu
Let's assume Cantor's Diagonal Theorem is correct.

What is "Cantor's Diagonal Theorem"? I am not familiar with it.

Quote:

That means there is a sequence of 0's and 1's that is not in the list of all sequences of 0's and 1's.

But, if that sequence is not in the list, then the list must not be complete, meaning the list is not the list of all sequences of 0's and 1's because it is missing at least one sequence.
That is a reasonable (if rather sloppily word) summary of Cantor's diagonal argument.

Quote:

Hence, the conclusion does not follow.
Which conclusion?

Do you have a sequence of 0's and 1's that is not in any list of all sequences as in Cantor's diagonal theorem. yes or no.
• November 18th, 2011, 09:26 PM
chinglu
Quote:

Originally Posted by mathman
The conclusion of Cantor's theorem is that there is no COUNTABLE list.

I am not talking about Cantor's theorem. That is different.

I am talking about the diagonal theorem.

Can you produce a sequence that is not in any list or all sequences?
• November 19th, 2011, 06:21 AM
Strange
What exactly are you trying to say? You seem to understand that, that as shown by Cantor's diagonal argument(1), any infinite sequence is incomplete and so .... Could you explain you point a little more clearly?

(1) "argument" not theorem.
• November 19th, 2011, 11:43 AM
Guitarist
chinglu: On this forum, as in life at large, if someone offers you the benefit of their wisdom, it is considered polite to reflect on it carefully, and ONLY after having done so, respond. You have not been "polite" in this sense.

Two members here have pointed out the obvious:

Cantor never had (nor ever will have) a "diagonal theorem" - he had a diagonal argument.

He used this to show

a) that the concept of uncountable infinity is valid, a surprise to his fellow mathematicians at the time

b) the real numbers are of uncountably infinite cardinality.

You also seem not to understand how the proof works - a proof, if I may say so, that is one the most elegant in all of mathematics. Specifically in your case, a "list" implies enumeration of all possible random strings of 0's and 1's, each of which is of countably infinite length.

The fact that in your OP you complain that the "list is not complete" simply serves to prove the case - there can be no such enumerable list. In other words, the number of countably infinite random strings of 0's and 1's is uncountable
• November 19th, 2011, 10:47 PM
chinglu
Quote:

Originally Posted by Guitarist
chinglu: On this forum, as in life at large, if someone offers you the benefit of their wisdom, it is considered polite to reflect on it carefully, and ONLY after having done so, respond. You have not been "polite" in this sense.

Two members here have pointed out the obvious:

Cantor never had (nor ever will have) a "diagonal theorem" - he had a diagonal argument.

He used this to show

a) that the concept of uncountable infinity is valid, a surprise to his fellow mathematicians at the time

b) the real numbers are of uncountably infinite cardinality.

You also seem not to understand how the proof works - a proof, if I may say so, that is one the most elegant in all of mathematics. Specifically in your case, a "list" implies enumeration of all possible random strings of 0's and 1's, each of which is of countably infinite length.

The fact that in your OP you complain that the "list is not complete" simply serves to prove the case - there can be no such enumerable list. In other words, the number of countably infinite random strings of 0's and 1's is uncountable

Let's see if I understand you correctly.

The uncountablility of the reals is based on an argument but not a proof.

In other words, it is not provable but an opinion.

Do I understand you correctly.

Anyway, write down the sequence so that I can teach you you are wrong.

Please keep in mind you are very smart and very correct, so you will write this sequence that is not in the list of all seqeunces of 0's and 1.s.

Let me see it.
• November 20th, 2011, 07:39 AM
Strange
Quote:

Originally Posted by chinglu
Let's see if I understand you correctly.

The uncountablility of the reals is based on an argument but not a proof.

The "diagonal argument" is the name of the proof. Call it the "diagonal proof" if it makes you happy.

Quote:

In other words, it is not provable but an opinion.

Do I understand you correctly.
Obviously not.

Quote:

Anyway, write down the sequence so that I can teach you you are wrong.

Please keep in mind you are very smart and very correct, so you will write this sequence that is not in the list of all sequences of 0's and 1.s.
Clearly you don't understand the proof. The point is if you produce a list, the proof shows how to create a new number that is not in the list.

So if you want to show the proof is wrong you need to demonstrate where the flaw in the logic is. As it is such a simple proof, that should be very easy, no?
• November 20th, 2011, 06:24 PM
mathman
To chinglu. You would learn a lot more by trying to understand the mathematical point of the Cantor theorem (argument, proof) rather than trying to disprove it by wordplay.
• November 20th, 2011, 06:50 PM
chinglu
Quote:

Originally Posted by mathman
To chinglu. You would learn a lot more by trying to understand the mathematical point of the Cantor theorem (argument, proof) rather than trying to disprove it by wordplay.

Let's just do this since you failed to produce a valid Cantor sequence.

First, the "argument" can't get off the ground using induction. Remember, the Cantor "argument" claims there exists a complement sequence of all sequences.

Therefore, to prove that notion, you need to prove a base step and the step n implies n + 1.

Why must this proof proceed this way? Because, the "argument" claims the list is countable by columns and rows which is based on the inductive set N. Whenever you want to make a claim using N, you must proceed by induction to remain consistent with the axiom of infinity.

Now, let's try to start the argument by induction. The base step must claim the first digit in the Cantor sequence is not in any row in the infinite list of rows. That digit must be 0 or 1. Therefore, whichever the Cantor "argument" uses, no sequence in the infinite list of rows can begin with the first Cator digit.

Therefore, the argument fails its required induction since that is clearly false that no row begins with the cantor first digit.

Now, to disprove the argument that is easy.

Let cn be a cantor sequence of length n.

Then the n + 1 row in the list is cn.

So, while cantor claims cn is not an initial sequence in the list of n rows, it is in fact in the n + 1 row contradicting the Cantor argument that cn is in the complement at stage n.

QED
• November 20th, 2011, 07:50 PM
Guitarist
Quote:

Originally Posted by chinglu
you failed to produce a valid Cantor sequence.

What is a "Cantor sequence", valid or otherwise?

Quote:

First, the "argument" can't get off the ground using induction.
Quite correct - Cantor's argument is a proof by contradiction, id est by assuming if there is a countable list of countably infinite sequences then we find a contradiction.

It is not an inductive proof.

I find it slightly depressing that one who seems not fully to understand Cantor's proof of the existence of sets with uncountable cardinality feels free to claim this proof is in error.

If you want me (or any others on this forum) to walk you through the proof, please ask politely
• November 20th, 2011, 08:00 PM
chinglu
Quote:

Originally Posted by Guitarist
Quote:

Originally Posted by chinglu
you failed to produce a valid Cantor sequence.

What is a "Cantor sequence", valid or otherwise?

Quote:

First, the "argument" can't get off the ground using induction.
Quite correct - Cantor's argument is a proof by contradiction, id est by assuming if there is a countable list of countably infinite sequences then we find a contradiction.

It is not an inductive proof.

I find it slightly depressing that one who seems not fully to understand Cantor's proof of the existence of sets with uncountable cardinality feels free to claim this proof is in error.

If you want me (or any others on this forum) to walk you through the proof, please ask politely

Oh, please walk me through it.

Pick he theorem or diagonal, I don't care.
• November 20th, 2011, 08:12 PM
chinglu
Quote:

Originally Posted by Guitarist
Quote:

Originally Posted by chinglu
you failed to produce a valid Cantor sequence.

What is a "Cantor sequence", valid or otherwise?

Quote:

First, the "argument" can't get off the ground using induction.
Quite correct - Cantor's argument is a proof by contradiction, id est by assuming if there is a countable list of countably infinite sequences then we find a contradiction.

It is not an inductive proof.

I find it slightly depressing that one who seems not fully to understand Cantor's proof of the existence of sets with uncountable cardinality feels free to claim this proof is in error.

If you want me (or any others on this forum) to walk you through the proof, please ask politely

Here is the funny part.

Either I am super smart or super stupid.

If you will post your "opinion" you call proof, we will find out.

I will warn you up front, you are going to lose.
• November 20th, 2011, 10:28 PM
PhysBang
Well, if you ever wanted to know if chinglu was lying about being in a logic program in a prestigious university, you can now know for certain that he was lying.
• November 21st, 2011, 09:20 AM
Guitarist
Quote:

Originally Posted by chinglu
Either I am super smart or super stupid.

Despite the temptation to express an opinion on this, I shall resist

Quote:

If you will post your "opinion" you call proof, we will find out.
As PhysBang says, it is rather difficult to accept that you are a student of logic anywhere, let alone a "prestigious institution". First, the proof is not mine, neither is it my "opinion" - it is Cantor's proof , not his "opinion". Do not conflate proof with opinion.; logicians understand the difference very well

Quote:

I will warn you up front, you are going to lose.
Lose what, dear boy? Your meaning is not clear - is this some sort of battle?

Whatever your meaning, it does not sound much like what I called a "polite request", so I decline your request
• November 21st, 2011, 04:19 PM
mathman
Note to Guitarist, et al. I give up.
• November 21st, 2011, 05:20 PM
PhysBang
Quote:

Originally Posted by mathman
Note to Guitarist, et al. I give up.

Wise choice. If you do an internet search, you will probably find an old thread on another message board where chinglu has already, verbatim, attempted this same thread. His mistakes will have been clearly explained to him there and he probably came here after being banned temporarily or permanently at that message board because of his responses on this topic.One can find several examples of this pattern on this board.
• November 21st, 2011, 08:48 PM
chinglu
Quote:

Originally Posted by Guitarist
Quote:

Originally Posted by chinglu
Either I am super smart or super stupid.

Despite the temptation to express an opinion on this, I shall resist

Quote:

If you will post your "opinion" you call proof, we will find out.
As PhysBang says, it is rather difficult to accept that you are a student of logic anywhere, let alone a "prestigious institution". First, the proof is not mine, neither is it my "opinion" - it is Cantor's proof , not his "opinion". Do not conflate proof with opinion.; logicians understand the difference very well

Quote:

I will warn you up front, you are going to lose.
Lose what, dear boy? Your meaning is not clear - is this some sort of battle?

Whatever your meaning, it does not sound much like what I called a "polite request", so I decline your request

Well, You and mathman decline to engage. You want to assure the crowd that is because I am "rude". But, any math person would be proud to demonstate their intellect.

Yet you 2 declare defeat and retreat in dishonor.

I will take on anyone in the world on this logic and win.

So, either accept my results or prove it false.
• November 21st, 2011, 08:50 PM
chinglu
Quote:

Originally Posted by PhysBang
Quote:

Originally Posted by mathman
Note to Guitarist, et al. I give up.

Wise choice. If you do an internet search, you will probably find an old thread on another message board where chinglu has already, verbatim, attempted this same thread. His mistakes will have been clearly explained to him there and he probably came here after being banned temporarily or permanently at that message board because of his responses on this topic.One can find several examples of this pattern on this board.

Otherwise prove you are correct.

That means prove my logic is false.
• November 21st, 2011, 11:43 PM
PhysBang
Quote:

Originally Posted by chinglu

Hah! I didn't even do a search and I was right!chinglu, you need to see professional help. You will feel much better once you do.
• November 22nd, 2011, 01:06 PM
Guitarist
Quote:

Originally Posted by chinglu
I will take on anyone in the world on this logic and win.

So, either accept my results or prove it false.

Well, leaving aside the soaring arrogance, I fail to understand why you think a forum discussion is about winners and losers. Care to explain?

Moreover, I am yet to be convinced that you fully understand Cantor's diagonal argument. First because you seem not to understand it is an argument with wide applicability, and not a theorem. Second because you have failed to present the argument in detail and then proceeded to show why it is wrong.

Yet you certainly claimed this. It is not my, nor anyone else's, job to defend established mathematics, it is you who challenged it.

Here is my challenge to you: First present, in detail, Cantor's argument as it exists in the literature (you haven't yet done this), then go through it line by line and point out the logical flaws.

You know you can do this, as you are the world's greatest logician. Right?
• November 22nd, 2011, 07:09 PM
chinglu
Quote:

Originally Posted by Guitarist
Quote:

Originally Posted by chinglu
I will take on anyone in the world on this logic and win.

So, either accept my results or prove it false.

Well, leaving aside the soaring arrogance, I fail to understand why you think a forum discussion is about winners and losers. Care to explain?

Moreover, I am yet to be convinced that you fully understand Cantor's diagonal argument. First because you seem not to understand it is an argument with wide applicability, and not a theorem. Second because you have failed to present the argument in detail and then proceeded to show why it is wrong.

Yet you certainly claimed this. It is not my, nor anyone else's, job to defend established mathematics, it is you who challenged it.

Here is my challenge to you: First present, in detail, Cantor's argument as it exists in the literature (you haven't yet done this), then go through it line by line and point out the logical flaws.

You know you can do this, as you are the world's greatest logician. Right?

Good post.

First, I used the term "lose" since you were making proclamations you could not support. That is a game and not a discussion in logic. Since you introduced the game, I thought I would give you the known outcome.

Now, in logic, we do not proceed by arguments. There is no such thing. We assume the axioms of set theory and first order logic and crank out proofs.

So, your insistence of clinging to your idea of an argument in logic is nothing more than clinging to an opinion.
So, the argument is square in nature, here is an example.

010101...
101010...
110000...
111101...
111010...
111000...
...
...
...
Now, for each entry in the matrix on the diagonal set cantor(r) = ~d(M(r,c)),where r=c and ~ means the opposite of the digit.
Looking above in bold, that means the cantor sequence for the first 6 positions is 111001.

In other words, there is a 0 at r=0, c=0 so the first digit is 1.

Next, there is a 0 at r=1, c=1 so the 2nd digit is 1.

Proceed as above out to infinity and this is supposed to construct a sequence that is not in the list.

This is supposed to work for all lists. But, look more in detail how I am building the list. Look at stage 5, the cantor sequence is 11100. But you can see below in red that although that sequence is not in the first 5 rows, it is in the 6th row. So cantor's argument cannot rule out this sequence for all rows in the list.

Therefore, for every finite cantor sequence in the argument, that sequence appears in the next row. Hence, for example according to cantor, there is no cantor sequence of length 5 11100 , since it is in the 5th position in the list.

Since the list, by assumption, is coutably infinite with the rows, that means I have the power of infinity on my side, I am able to continuously outflank the finite Cantor sequence of length n-1 at the nth stage. Hence, the cantor argument fails. It is therefore, impossible to construct a sequence that is not in the "complete" list.

010101...
101010...
110000...
111101...
111010...
111000...
• November 22nd, 2011, 10:57 PM
PhysBang
The number referenced by diagonalization is not created after the fifth number in the sequence, it is created after all of them. By the creation process, we know that if a number is in the list then it is definitely different from that number referenced by the diagonal method, one cannot add more numbers to the list.
• November 23rd, 2011, 08:04 PM
chinglu
Quote:

Originally Posted by PhysBang
The number referenced by diagonalization is not created after the fifth number in the sequence, it is created after all of them. By the creation process, we know that if a number is in the list then it is definitely different from that number referenced by the diagonal method, one cannot add more numbers to the list.

I think you make an excellent point here.
But, what we have available with inductive arguments is the Kleene recursion theorem. We as humans, based on our limitations and ZFC set theory only have constructive processes based on prior events given the the Kleene recursion theorem.
So, we are able to define a construction of sequences based on prior knowledge. So, there is not defined list.
Remember, Cantor did all of his work before the liar's paradox and the recursion theorem. So, he used an undiciplined listing methodology not backed up with proof from foundations of modern set theory.
Therefore, one is not allowed to make listing claims unless it can be backed up with transfinite recursion.
So, in the construction I provided, the next row always contains the cantor sequence and then another digit which does not even matter since the next row wil contain that.
I proceed by transfinite induction on the columns and allow the rows to roam free since the columns are not bound to the rows.
That was the whole con game played by Cantor. He wanted to convince you the construction of the rows was bound to the columns for all n.
• November 24th, 2011, 07:21 AM
PhysBang
Sigh.

Kleene's theorem is not relevant here. No argument about computability is relevant here because it is an assumption that we have an ordered list of all the elements of the list. If you deny that assumption, then fine, but you can't make an assumption and then also make an assumption that contradicts it. That's crazy.
• November 24th, 2011, 12:45 PM
Guitarist
Just in case any casual reader might be wondering if chinglu has a point, I present the "conventional" argument. Go compare

Suppose that there exist a random sequence of 1's and 0's which, as a set, has countably infinite cardinality. Then by the definition of a sequence of this sort, it makes sense to refer to the n-th element in the sequence where .

Suppose further that there exists a countable infinity of such sequences, each one unique. Then it makes sense to refer to the n-th sequence. Let's call it as

Putting these together, it makes sense to refer to the n-th element of All with me so far?

This implies that, as sets, the cardinality of each is equal to the cardinality of the set of ALL such sequences. Which in turn implies there exists an array generated by "listing" the which is square iff these 2 cardinalities are the same.

I assert that the existence of a "true" diagonal of any array implies it is square, where I DEFINE the "true" diagonal as the sequence for which

for each and all , the n-th element in is the n-th element in

Now by assumption, the "list" of all is complete. This implies there exists for some particular such that the p-th element is NOT the p-th element in . Call it for "complement"

BUT, by construction of the diagonal, the p-th element of is the p-th element in , and yet by the definition of the complement, the p-th element in is NOT the p-th element in

the p-th element in is NOT the p-th element in .

So as defined does not exist, our array cannot be square and as sets the cardinality of any sequence cannot be equal to the cardinality of the list of all such sequences.

It remains as an exercise for the reader (as they say) to show the the cardinality of the list is strictly greater than that of any sequence
• November 24th, 2011, 10:55 PM
chinglu
Quote:

Originally Posted by Guitarist
Just in case any casual reader might be wondering if chinglu has a point, I present the "conventional" argument. Go compare

Suppose that there exist a random sequence of 1's and 0's which, as a set, has countably infinite cardinality. Then by the definition of a sequence of this sort, it makes sense to refer to the n-th element in the sequence where .

Suppose further that there exists a countable infinity of such sequences, each one unique. Then it makes sense to refer to the n-th sequence. Let's call it as

Putting these together, it makes sense to refer to the n-th element of All with me so far?

This implies that, as sets, the cardinality of each is equal to the cardinality of the set of ALL such sequences. Which in turn implies there exists an array generated by "listing" the which is square iff these 2 cardinalities are the same.

I assert that the existence of a "true" diagonal of any array implies it is square, where I DEFINE the "true" diagonal as the sequence for which

for each and all , the n-th element in is the n-th element in

Now by assumption, the "list" of all is complete. This implies there exists for some particular such that the p-th element is NOT the p-th element in . Call it for "complement"

BUT, by construction of the diagonal, the p-th element of is the p-th element in , and yet by the definition of the complement, the p-th element in is NOT the p-th element in

the p-th element in is NOT the p-th element in .

So as defined does not exist, our array cannot be square and as sets the cardinality of any sequence cannot be equal to the cardinality of the list of all such sequences.

It remains as an exercise for the reader (as they say) to show the the cardinality of the list is strictly greater than that of any sequence

Pretty good.

Your reasoning fails the pigeon hole principle.

The number of the first row is defined as 0 and the number of the first column is defined as 0.

Let’s recursively define a sequence construction as follows.

The base case is the empty sequence. At row 0 and column 0, the sequence is empty.

We now invoke a recursive definition.

To construct the list of the n +1 sequence, copy the nth row to the n + 1 row and then concatenate a 0 in the nth column for all sequences for rows <= n but for the n + 1 row concatenate a 1.

Here is how this works.

The base stage is the empty sequence.

The 1st stage is
0
1
The 2nd stage is
00
10
11
The 3rd stage is
000
100
110
111
Now, the whole point of the “cantor argument” is that on the diagonal, the cantor opposite sequence does not exist for all sequences.

Let’s look at stage 1. The cantor sequence is 1 because at row 0 and column 0 the digit is 0. It is always the opposite.
But look, at stage 1, that 1 digit is in the 2nd row. So, the cantor sequence is not missing. It is in row 2.

In general, this logic recursively outflanks the cantor argument proving it is impossible to construct a sequence of 0’s and 1’ not in the list of all sequences since the so called missing cantor sequence of length n is always in the n+1 row.

QED
• November 24th, 2011, 10:58 PM
chinglu
Quote:

Originally Posted by Guitarist
Just in case any casual reader might be wondering if chinglu has a point, I present the "conventional" argument. Go compare

Suppose that there exist a random sequence of 1's and 0's which, as a set, has countably infinite cardinality. Then by the definition of a sequence of this sort, it makes sense to refer to the n-th element in the sequence where .

Suppose further that there exists a countable infinity of such sequences, each one unique. Then it makes sense to refer to the n-th sequence. Let's call it as

Putting these together, it makes sense to refer to the n-th element of All with me so far?

This implies that, as sets, the cardinality of each is equal to the cardinality of the set of ALL such sequences. Which in turn implies there exists an array generated by "listing" the which is square iff these 2 cardinalities are the same.

I assert that the existence of a "true" diagonal of any array implies it is square, where I DEFINE the "true" diagonal as the sequence for which

for each and all , the n-th element in is the n-th element in

Now by assumption, the "list" of all is complete. This implies there exists for some particular such that the p-th element is NOT the p-th element in . Call it for "complement"

BUT, by construction of the diagonal, the p-th element of is the p-th element in , and yet by the definition of the complement, the p-th element in is NOT the p-th element in

the p-th element in is NOT the p-th element in .

So as defined does not exist, our array cannot be square and as sets the cardinality of any sequence cannot be equal to the cardinality of the list of all such sequences.

It remains as an exercise for the reader (as they say) to show the the cardinality of the list is strictly greater than that of any sequence

I tried to explain to you already, I do not enter into games unless I already know the outcome.

You need to address your internal errors in order to operate in God's world, mathematics.
• November 25th, 2011, 07:06 AM
agingjb
I suppose Cantor's diagonal argument is rather challenging (although it's really not that hard). Then again the observation that a countable subset of reals can be covered by a sequence of intervals of arbitrarily small total length ought also to be sufficient to establish that countable sets do not exhaust the reals.
• November 25th, 2011, 01:16 PM
Guitarist
Quote:

Originally Posted by chinglu

You need to address your internal errors in order to operate in God's world, mathematics.

chinglu The fact that you fail to understand the purpose of Cantor's diagonal argument is forgiveable; your arrogance and rudeness when combined with your incomprehension are not.

Any further instances of this sort of behaviour will result in a ban