Absurdity of Cantor's Diagonal Slash

[moving finger]

Cantor's diagonal slash has been used to argue that the infinity of reals is uncountable, whereas the infinity of integers is countable (hence the two infinities are different). I assume that readers are familiar with Cantor's diagonal slash argument.

What happens if we apply Cantor's diagonal slash to the integers? How can this be done? Think of the infinite binary tree, which starts at ground level as the trunk and splits in two (bifurcates) as we ascend; if we take the left branch then we assign 0 to the first binary digit, if the right branch then 1. At the next level we do the same...0 if we go left, 1 if we go right... and we ascend the binary tree all the way to infinity. In this way every possible infinite sequence of binary digits is represented somehow or other (mapped out) by a path up the tree; and every path up the tree corresponds to a unique infinite sequence of binary digits.

For those who are curious, the number of routes up the tree is equal to 2^n (where n is the number of levels), and the number of nodes (branches) in the tree is equal to (2^n)-1.

Now we can arrange all of these paths in an infinite x infinite binary matrix, of form similar to the infinite x infinite matrix of real numbers that Cantor used for his diagonal slash. What happens if we perform Cantor's diagonal slash on this infinite binary matrix? According to Cantor, we produce a new infinite binary sequence which is NOT contained within the original matrix (nor is it contained on the infinite binary tree). But how can this be? The matrix contains every possible route up the binary tree, there IS no other route not contained in the matrix.

What does this show?

That Cantor's diagonal slash argument is meaningless when applied to infinite matrices.

 

[master_coda]

Now we can arrange all of these paths in an infinite x infinite binary matrix, of form similar to the infinite x infinite matrix of real numbers that Cantor used for his diagonal slash.

You're assuming this is possible. You haven't provided a method for actually placing all of these paths into a matrix.

Note that not all possible paths will correspond to an integer; so you can't use the fact that the integers are countable to produce a listing of all possible paths.

What does this show?

That Cantor's diagonal slash argument is meaningless when applied to infinite matrices.

Actually, it shows that the set of all possible paths through an infinite binary tree is uncountable. Unless you can produce some separate proof that the set is countable, you haven't found a contradiction.

 

[CrankFan]

What does this show?

It shows that your understanding of the proof and related issues is poor.

For starters you need to figure out if you're talking about the collection of all vertices/nodes in the tree or the collection of all paths. You seem to be talking about either at any given point in your argument but they are different things. For example we can't have:

In this way every possible infinite sequence of binary digits is represented

and

if we take the left branch then we assign 0 to the first binary digit, if the right branch then 1. At the next level we do the same...0 if we go left, 1 if we go right... [then] (where n is the number of levels), and the number of nodes (branches) in the tree is equal to (2^n)-1.

 

[Hurkyl]

Cantor's diagonal argument is clearer in a more algebraic form.

Suppose f is a 1-1 mapping between the positive integers and the reals.

Let d_n be the function that returns the n-th digit of a real number.


Now, let's construct a real number, r. For the n-th digit of r, select something different from d_n(f(n)), and not 0 or 9.

Now, suppose f(m) = r. Then, the m-th digit of r must be d_m(r) = d_m(f(m)), but by construction that cannot be the m-th digit of r.


Therefore, no such f exists.

Thus, there is no 1-1 mapping between the positive integers and the reals.


The important thing to note is when I construct r, it really is a real number.


(by n-th digit, I mean to the right of the decimal point)

 

[moving finger]

You're assuming this is possible. You haven't provided a method for actually placing all of these paths into a matrix.

Each path to the top of the infinite binary tree is coded by a unique binary number of infinite digits. There are an infinite number of different paths. Each path (infinite binary number) can be a row of the matrix, and there will then be an infinite number of rows, hence we have an infinite by infinite matrix. This is conceptually no different to the construction of an infinite by infinite matrix of real numbers which is classically used to demonstrate Cantor's diagonal slash.

Note that not all possible paths will correspond to an integer; so you can't use the fact that the integers are countable to produce a listing of all possible paths.

Sorry, you are incorrect. Every possible path up to the top of the binary tree is coded by a unique binary integer (each of infinite length). There is no path which does not correspond to an integer.

Actually, it shows that the set of all possible paths through an infinite binary tree is uncountable. Unless you can produce some separate proof that the set is countable, you haven't found a contradiction.

It shows nothing of the kind. An infinite binary tree is simply a set of integers (binary integers). There are no real numbers involved. Each infinite binary integer in the tree can be paired uniquely with a correspionding unique decimal integer. If you believe the set of infinite binary integers is uncountable then this implies also that the set of decimal integers is uncountable (and I don't think you really believe that?). My "proof" that the set is countable is by pairing each binary integer (each path up the tree) with a corresponding unique decimal integer (and this can be done because each binary integer can be converted to a corresponding unique decimal integer)

 

[master_coda]

Sorry, you are incorrect. Every possible path up to the top of the binary tree is coded by a unique binary integer (each of infinite length). There is no path which does not correspond to an integer.

Any path with an infinite number of 1's in it does not correspond to an integer. Given any integer, the binary encoding of it will contain a finite number of 1's. That's why the diagonalization argument doesn't work on the integers; the "number" it constructs is not an integer.

 

[moving finger]

you need to figure out if you're talking about the collection of all vertices/nodes in the tree or the collection of all paths. You seem to be talking about either at any given point in your argument but they are different things.

My post explicitly refers to : "every path up the tree corresponds to a unique infinite sequence of binary digits."

I made the additional reference to the number of "nodes" simply out of passing interest (that the number of nodes is equal to the number of paths minus 1).

If you find this confusing then please delete all reference to the number of nodes - the argument (based purely on the number of paths) stands.

MF

In reply to Hurkyl, I show below essentially the same (fallacious) argument in the same algebraic form that he suggested in his post, in order to demonstrate that the original argument must be absurd :

Suppose f is a 1-1 mapping between the positive decimal integers and the positive binary integers from the infinite binary tree.

Let dn be the function that returns the n-th digit of an infinite binary integer.

Now, let's construct a new binary integer, r. For the n-th digit of r, select something different from dn(f(n)).

Now, suppose f(m) = r. Then, the m-th digit of r must be dm(r) = dm(f(m)), but by construction that cannot be the m-th digit of r.

The important thing to note is when I construct r, it really is a positive binary integer.

Therefore, no such f exists.

Thus, there is no 1-1 mapping between the positive decimal integers and the positive binary integers from the infinite binary tree.

However, this conclusion is absurd (every binary integer CAN be mapped to a unuique decimal integer), therefore there must be something wrong with Cantor's argument.

 

[moving finger]

Any path with an infinite number of 1's in it does not correspond to an integer. Given any integer, the binary encoding of it will contain a finite number of 1's. That's why the diagonalization argument doesn't work on the integers; the "number" it constructs is not an integer.

Can you tell me what is the binary coding of the decimal integer 9999... ? (where ... means "continue to infinity")

You claim that the binary coding of any integer will always contain a finite number of 1's. I don't see how an infinite decimal integer can be coded to a finite binary integer?

If an infinite number of binary 1's is not an integer, then what about any infinite string of binary digits? Would 1010101... be an integer? If not, why not? If it is not an integer, then what is it (it exists, and it is certainly not a real number)?

 

[master_coda]

Can you tell me what is the binary coding of the decimal integer 9999... ? (where ... means "continue to infinity")

You claim that the binary coding of any integer will always contain a finite number of 1's. I don't see how an infinite decimal integer can be coded to a finite binary integer?

If an infinite number of binary 1's is not an integer, then what about any infinite string of binary digits? Would 1010101... be an integer? If not, why not? If it is not an integer, then what is it (it exists, and it is certainly not a real number)?

Any integer can be represented with a finite number of digits; this is pretty much by definition. While I'm sure you can construct a model where "infinite decimal integers" means something, this model would no longer be countable, so applying the diagonal argument to it wouldn't be very interesting.

Cantor's argument relies upon the fact that every decimal expansion of the form $0.d_1d_2d_3...$ represents a real number. Not every decimal expansion of the form $...d_3d_2d_1$ is an integer, so you can't apply the same argument to the integers.

 

[moving finger]

Any integer can be represented with a finite number of digits; this is pretty much by definition.

I beg to differ. Two issues here :

The online Webster dictionary defines an Integer as "A complete entity; a whole number, in contradistinction to a fraction or a mixed number." In trawling through many other dictionaries I cannot find any definition which says an integer cannot comprise an infinite number of digits.

If we take your assertion "Any integer can be represented with a finite number of digits" at face value, then this means that there can be no concept of infinity at all when using integers; ie there can be no such thing as an infinite integer (no matter what base you define your integers in, binary, decimal or hexadecimal or whatever, an infinite integer MUST have an infinite number of digits.)

While I'm sure you can construct a model where "infinite decimal integers" means something, this model would no longer be countable, so applying the diagonal argument to it wouldn't be very interesting.

This is tantamount to saying that no concept of infinity is countable, and I think most mathematicians would disagree with you there. The infinite set of integers is generally acknowledged by most mathematicians as being a countable set.

Cantor's argument relies upon the fact that every decimal expansion of the form $0.d_1d_2d_3...$ represents a real number. Not every decimal expansion of the form $...d_3d_2d_1$ is an integer, so you can't apply the same argument to the integers.

Wrong. Cantor's argument relies upon the fact that the numbers he is working on have an infinite number of digits (it makes no difference whether these digits are to the left or right of the decimal point). My point is that an infinite string of integer digits is still an integer, and the argument therefore still works.

If both 999999... and 1111111... are indeed not integers (as you claim), then what are they?

 

[matt grime]

They aren't integers. Go learn some maths before criticizing it, and that doesn't mean scanning Websters.

A (positive) integer is a number which can obtained from adding 1 to itself a *finite* number of times.
Positions to the left and right of the decimal point do matter.
The strings you wrote out are not elements of the integers, nor R, with any reasonable interpretation of them.
They are elements of a p-adic system, though.

 

[Hurkyl]

there can be no such thing as an infinite integer

And that is exactly correct.

 

[Hurkyl]

Also, if you still think that Cantor's diagonal argument is flawed, try pointing out a flawed step.

 

[moving finger]

Quote:
there can be no such thing as an infinite integer

And that is exactly correct.

In 1874 Georg Cantor postulated that there is more than one level of infinity. The lowest level he called "countable infinity" and higher levels he called "uncountable infinities." The natural numbers are an example of a countably infinite set and the real numbers are supposed to be an example of an uncountably infinite set.

The postulate of a countably infinite set of integers is well accepted in set theory and number theory.

 

[moving finger]

They aren't integers. Go learn some maths before criticizing it, and that doesn't mean scanning Websters.

Hey, I wasn't the one who first referred to the "definition" of an integer.

A (positive) integer is a number which can obtained from adding 1 to itself a *finite* number of times.

And in which maths bible does it specify an integer can be obtained in this way only a *finite* number of times?

Positions to the left and right of the decimal point do matter.

Not for the diagonal slash argument they don't. It works equally well for either, as long as the total string of digits is infinite.

What you are arguing implies that the set of integers is not an infinite set. Suggest you go read about Cantor and his work on infinite sets before you go any further.

 

[moving finger]

if you still think that Cantor's diagonal argument is flawed, try pointing out a flawed step.

I have done this already in Post #7 of this thread, using your own argument to show the absurdity of Cantor's method (if you like, a kind of reductio ad absurdum argument)

What my post shows is that if Cantor's argument is used then we can show the number of binary integers is not equal to the number of decimal integers, which is absurd.

The only real argument presented against this so far in this thread has been the suggestion that there is no such thing as an infinite integer, which I think you will find is incorrect.

 

[matt grime]

And I think you'll find you are completely wrong. Integers in base 10 with the usual rules of presentation have only a finite number of non-zero digits. You should possibly hold back from telling some people who all have degrees or higher in mathematics or related areas things like that.

 

[chronon]

What you are arguing implies that the set of integers is not an infinite set.

Wrong.

Suppose for the sake of argument that we accept your definition of integers as being allowed to have an infinite number of digits. Then we can define a subset of those which only have a finite number of non-zero digits. Call them the fintegers. Then firstly

1) The fintegers are an infinite set. (Otherwise there would be a largest one. Can you tell me what it is?)

2) Cantor's diagonal argument shows that the real numbers can't be put into 1 to 1 correspondence with the fintegers

3) The fintegers are useful in everyday life, while your integers with an infinite number of digits aren't, so it would be the fintegers which appeared in dictionaries and the like.

 

[moving finger]

And I think you'll find you are completely wrong. Integers in base 10 with the usual rules of presentation have only a finite number of non-zero digits. You should possibly hold back from telling some people who all have degrees or higher in mathematics or related areas things like that.

It is well established in set theory that each of the sets of natural numbers, integers and rational numbers is countably infinite.

This means that each of these sets has infinite cardinality.

This means that there are infinitely many natural numbers, integers and rational numbers.

Any natural number or integer which is infinite must have an infinite number of digits.

Or perhaps you can explain how an infinite integer can have a finite number of digits?

 

[matt grime]

There is no such thing as an infinite integer. Spot the gap in your logic...

 

[moving finger]

Suppose for the sake of argument that we accept your definition of integers as being allowed to have an infinite number of digits. Then we can define a subset of those which only have a finite number of non-zero digits. Call them the fintegers. Then firstly

1) The fintegers are an infinite set.

Thank you! Since this is an infinite set of integers then the largest member of this set must be infinite, which in turn implies that it must have an infinite number of digits (unless you can explain how an infinite integer can be comprised of a finite number of digits)

 

[matt grime]

For the love of God... How can someone please explain to you that there is no such thing as an infinite member of $$\mathbb{N}$$ if you won't listen?

 

[chronon]

Thank you! Since this is an infinite set of integers then the largest member of this set must be infinite, which in turn implies that it must have an infinite number of digits (unless you can explain how an infinite integer can be comprised of a finite number of digits)

So you've just shown that my set of fintegers which was defined to exclude numbers with infinitely many digits must contain a number with infinitely many digits. Doesn't that worry you? Or don't you believe in finite numbers?

 

[CrankFan]

My post explicitly refers to : "every path up the tree corresponds to a unique infinite sequence of binary digits."

Well then you're not talking about integers, are you. See, that was confusing also. You say you're going to prove something about integers but the object of your proof is the set of reals.

The set of all sequences of 0s and 1s (of infinite length) has the same cardinality as the set of reals.

If you argue that all such sequences aren't countable then your result is consistent with Cantor's. I'd hesitate to call what you wrote a proof, but if you would at least recognize that you're not contradicting Cantor then perhaps you can avoid any more of this silliness.

 

[moving finger]

For the love of God... How can someone please explain to you that there is no such thing as an infinite member of $$\mathbb{N}$$ if you won't listen?

Its not only about listening, its about rational discussion and proof.

The cardinality of $$\mathbb{N}$$ is infinite (aleph0)

Let card(n) be the cardinality of the set of natural numbers from 1 to n inclusive

Then it is easy to show that card(n) = n

Let the largest possible natural number be Z. According to you, Z is finite. However, in that case card(Z) = Z (a finite number) and not aleph0 (infinity)

Where is the flaw in my logic?

 

[matt grime]

One of the flaws is you're assuming that the cardinality of Z, or N, is an element of Z or N. Neither of which is true. The cardinality of Z is not an element of Z.

 

[moving finger]

So you've just shown that my set of fintegers which was defined to exclude numbers with infinitely many digits must contain a number with infinitely many digits. Doesn't that worry you? Or don't you believe in finite numbers?

Nope. What this shows is that your set of fintegers cannot in fact have a largest member, because whatever finteger we choose to call the "largest finteger" we can always increment by 1, and generate an even larger finteger.

Applying this more generally to the integers, the largest integer must be infinite (because any finite "largest integer" we can always increment by 1 and generate an even larger largest integer)

 

[arildno]

The largest integer doesn't exist.

 

[moving finger]

One of the flaws is you're assuming that the cardinality of Z, or N, is an element of Z or N. Neither of which is true. The cardinality of Z is not an element of Z.

I never said it was.

Do you claim that the relationship card(n) = n (where card(n) is defined as the cardinality of the set of all integers between 1 and n inclusive) is false?

 

[moving finger]

The largest integer doesn't exist.

correction : The largest finteger (as defined by chronon) does not exist

 

[master_coda]

Its not only about listening, its about rational discussion and proof.

The cardinality of $$\mathbb{N}$$ is infinite (aleph0)

Let card(n) be the cardinality of the set of natural numbers from 1 to n inclusive

Then it is easy to show that card(n) = n

Let the largest possible natural number be Z. According to you, Z is finite. However, in that case card(Z) = Z (a finite number) and not aleph0 (infinity)

Where is the flaw in my logic?

There is no largest possible natural number. By assuming that it exists, you derive a false conclusion.

 

[chronon]

correction : The largest finteger (as defined by chronon) does not exist

Now we're getting somewhere. So do you accept the following

1) There is no largest finteger

2) The set of fintegers is infinite

3) Cantor's diagonal argument shows that set of reals cannot be put into 1-1 correspondence with the set of fintegers.

If you (A) accept these 3 statements and (B) start speaking the same language as everyone else and give the name integers to what I have called fintegers, then you have Cantor's proof

 

[CrankFan]

correction : The largest finteger (as defined by chronon) does not exist

You don't get to decide what the set of integers is, that was decided a long time ago. Everyone here, except you, seems to have a good idea of what the integers are.

If you want to talk about a set that is similar to the set of integers but not actually the same then you have to call that set something other than the integers, otherwise you're just babbling.

If you actually do want to talk about integers then start with a well known definition, something like: the smallest inductive subset of R, closed under negation. Once you settle on a standard definition the rest of the questions can be dealt with. If you can't settle on a standard definition then you simply don't know what the integers are. Sorry.

 

[matt grime]

I never said it was.

you did, here:

The cardinality of N is infinite (aleph0)

Let card(n) be the cardinality of the set of natural numbers from 1 to n inclusive

Then it is easy to show that card(n) = n

Let the largest possible natural number be Z. According to you, Z is finite. However, in that case card(Z) = Z (a finite number) and not aleph0 (infinity)

there is a difference between a set being finite, and its elements being finite.

Do you claim that the relationship card(n) = n (where card(n) is defined as the cardinality of the set of all integers between 1 and n inclusive) is false?

n isn't a priori a set, so it hasn't got a cardinality, but even allowing for this abuse of notation, what on Earth does this have to do with card(N), unless you believe it to be an integer?

 

[HallsofIvy]

It is well established in set theory that each of the sets of natural numbers, integers and rational numbers is countably infinite.

This means that each of these sets has infinite cardinality.

This means that there are infinitely many natural numbers, integers and rational numbers.

Any natural number or integer which is infinite must have an infinite number of digits.

Or perhaps you can explain how an infinite integer can have a finite number of digits?

Yes, there are an infinitely many natural numbers (and so integers and rational numbers).,

Your next line does not follow has a logical "leap": saying that there are infinitely many natural numbers does NOT imply that there must exist "an infinite integer". There exist infinitely many integers, each of which is a finite number.

Since you mention rational numbers, we might point out that there exist infinitely many rational numbers of the form 1/2ⁿ: that is, there exist infinitely many rational numbers, between o and 1, each of which has a finite number of digits (is a terminating decimal).