Is Cantor's Diagonal Argument Flawed in Its Application to Positive Integers?

[ahristov]

Hi
I've some trouble understanding (or maybe accepting) Cantor's diagonal argument. When I was young I had no trouble accepting it and it seemed perfectly logical, but after a long hiatus and returning to my original interests, I seem less than convinced (must be some age-related or brain decay issue :-)

Now let's say I have the set of all positive integers. This set is clearly countable/enuimerable, so I can place all its members in a sequential list. What stops me from applying the diagonal argument to this list, and getting a positive integer that does not belong to the set, which by definition contains all positive integer? what gives?

 

[Hurkyl]

Have you tried an example?

 

[ahristov]

An example of the original argument? yes of course. But the problem is that seemingly I can apply the same reasoning to just the integers to get a contradictory result and I don't see where the fault is...

 

[matt grime]

How do you propose to apply the diagonal argument to the list? Are you proposing to write the integers like this, in say binary:

...0000001
...0000010
...0000011and so on? We may go ahead and apply the argument to it and prove that the infinitely long string of digits has only finitely many non-zero entries on it. This will be difficult since you'll have to make the n'th digit (from the right) in the n'th string non-zero for all n greater than about 3 (since n>log_2 n for n>2). Trying other bases won't help: eventually n> log n for any base.Usually people try to misapply the argument to the (decimal) representations of rational numbers. In doing so at least they construct a real number. Erroneously they assume that it must be rational.

 

[Hurkyl]

An example of the original argument? yes of course.

No; I mean an example of the new 'argument'. (By the way, what sort of example did you apply the original argument to?)

But the problem is that seemingly I can apply the same reasoning to just the integers

Don't just say "it seems so" -- try it. Pick your favorite list of all integers and try to apply the diagonal argument. Have you obtained a result contradicting the hypothesis it was a list of all integers? (matt has already answered this question)

 

[HallsofIvy]

To reiterate matt grime: all natural numbers have a finite number of non-zero digits. The number you produce by "mimicing" Cantor's method may NOT have only a finite number of non-zero digits.

 

[ahristov]

No; I mean an example of the new 'argument'. (By the way, what sort of example did you apply the original argument to?)

Well, the typical set of reals in which you flip a digit (of their decimal representation) each time, producing a new real.

Don't just say "it seems so" -- try it. Pick your favorite list of all integers and try to apply the diagonal argument. Have you obtained a result contradicting the hypothesis it was a list of all integers? (matt has already answered this question)

Ok, let's say I have the list of integers. For each integer, I pick a random digit position (different from the ones picked previously), zero-padding if necessary and change it.

 

[ahristov]

To reiterate matt grime: all natural numbers have a finite number of non-zero digits. The number you produce by "mimicing" Cantor's method may NOT have only a finite number of non-zero digits.

Yes, but I have trouble seeing that the diagonal argument applied to integers implies an integer with an infinite number of digits. I mean, intuitively it may seem obvious that this is the case, but then again it's also obvious that for every integer n there's another integer n+1, and yet this does not imply there is an actual integer with an infinite number of digits, nevermind that n+1->inf when n->inf.

 

[matt grime]

Yes, but I have trouble seeing that the diagonal argument applied to integers implies an integer with an infinite number of digits.

If you took the natural listing that I gave, then it is clear that the diagonal argument produces the string

...1111100

which is not a natural number's binary expansion. For an arbitrary listing, then it will be hard to prove it directly (but it will still be true). Of course, we don't have to! It is up to you to demonstrate that this string which potentially has an infinite number of 1s in it doesn't.

 

[HallsofIvy]

You understand, don't you, that Cantor's method involves changing one digit for every number on the list. Suppose you were to do this: list all positive integers (that's easy). Now go through that list doing the following: if the nth digit of the nth integer is a "5", write a "6" for the nth digit of the new number.

If you did that to any infinite list of real numbers rather than integers, you would get a real number with all digits either "5" or "6"- and because your list is infinite, . That would have to be a real number that is NOT on the list (since it differs from the n^th number in the n^th decimal place) and so the set of all real numbers cannot be "listed"- is not "countable".

But with an infinite list of integers you would still get an infinite (because you get one digit from each integer) list of digits (all "5"s or "6"s) which is NOT an integer.

 

[Hurkyl]

Ok, let's say I have the list of integers.

Don't merely say you have a list: explicitly choose one! (Or, at least, choose an initial segment of such a list)

For each integer, I pick a random digit position (different from the ones picked previously), zero-padding if necessary and change it.

Again, don't just say... do.

(And preferably do all of this in the simplest possible way, so that you can see what's happening)

 

[ahristov]

But with an infinite list of integers you would still get an infinite (because you get one digit from each integer) list of digits (all "5"s or "6"s) which is NOT an integer.

Ok, understood. Wouldn't it be possible, though, that an infinite amount of these digits be zeros?

 

[ahristov]

If you took the natural listing that I gave, then it is clear that the diagonal argument produces the string

...1111100

which is not a natural number's binary expansion. For an arbitrary listing, then it will be hard to prove it directly (but it will still be true). Of course, we don't have to! It is up to you to demonstrate that this string which potentially has an infinite number of 1s in it doesn't.

matt, not to mean disrespect but I believe saying "it's so because it is" is not very illuminating, at least if you're trying to be didactic (as opposed to viewing this as a confrontation or who-knows-more contest). You of course don't have to prove that I'm wrong, but since you take the trouble of answering, you should at least try to prove that you are right, and not merely drop a statement and say it's true because you or some authority says so.

Anyawy HallsofIvy's reasoning has (almost) convinced me.

 

[matt grime]

I can prove it since the natural numbers are (by definition) countable, surely that proof is sufficiently obvious as to not require explicitly saying? Sorry if you don't like indirect proofs, but sometimes that is all you get. I did give you a constructive demonstration for the natural binary listing, and for the natural listing in any other base. It might well be possible to give a constructive proof for an arbitrary listing. Try it. The proof would probably require you to show that you can divide the list into chunks (probably of variable lengths) in such a way that at least one of the diagonal elements (i.e. the n'th digit in the n'th number in the list) must be zero via some counting argument.

 

[matt grime]

View it this way. Do your argument. You have two assumptions

a) That we have a bijection from N to N (the listing)
b) that the string produced has finitely many digits.

We know we have a contradiction, therefore one (or both) of these is false. That is all the argument tells us. On its own it is neither sufficient to prove the natural numbers are countable, nor that they are uncountable. We have no way of deciding which from this information alone. Thus if we wish to prove they are countable or otherwise, then we have to look elsewhere. Trivially they are countable. This proves that bijections exist. If f is such then it must be the case that b) is false.

The standard argument uses only one assumption: that there is a bijection from R to N - there is no assumption on the string produced yielding a real number - it does so by construction. Since we reach a contradiction, this must be false.

 

[HallsofIvy]

You understand, don't you, that Cantor's method involves changing one digit for every number on the list. Suppose you were to do this: list all positive integers (that's easy). Now go through that list doing the following: if the nth digit of the nth integer is a "5", write a "6" for the nth digit of the new number.

If you did that to any infinite list of real numbers rather than integers, you would get a real number with all digits either "5" or "6"- and because your list is infinite, . That would have to be a real number that is NOT on the list (since it differs from the n^th number in the n^th decimal place) and so the set of all real numbers cannot be "listed"- is not "countable".

But with an infinite list of integers you would still get an infinite (because you get one digit from each integer) list of digits (all "5"s or "6"s) which is NOT an integer.

Ok, understood. Wouldn't it be possible, though, that an infinite amount of these digits be zeros?

If you do it as I said, you all digits must be "5" or "6"- no "0"s allowed!

 

[ahristov]

View it this way. Do your argument. You have two assumptions

a) That we have a bijection from N to N (the listing)
b) that the string produced has finitely many digits.

Actually I'm not assuming that the produced number has a finite amount of non-zero digits (since it may have an infinite amount of leading zeros and still be an integer)

But anyway I've been convinced. Thanks to everyone for your answers

 

[matt grime]

Actually I'm not assuming that the produced number has a finite amount of non-zero digits (since it may have an infinite amount of leading zeros and still be an integer)

You (that's a generic you) are assuming that it is a finite number of non-zero digits when you assume it is an integer, and if it's assumed to not be an integer then there's no problem. I really don't understand how you can say otherwise. Having a leading infinite string of zeroes in no way contradicts the assumption that there must be a finite number of non-zero entries for it to represent an integer.

 

[manker]

Hi
Now let's say I have the set of all positive integers. This set is clearly countable/enuimerable, so I can place all its members in a sequential list. What stops me from applying the diagonal argument to this list, and getting a positive integer that does not belong to the set, which by definition contains all positive integer? what gives?

Hoping I may be permitted to make a belated contribution here.

Summarising the key points from some of the other posts:
The key to the problem is that the new 'number' generated by the diagonal argument will have an infinite number of non-zero digits resulting from the infinite number of leading zeros in the original numbers. Such a number is not an integer since, although the set of integers has an infinite number of members, each individual member is finite and must have a finite number of non-zero digits.

I can accept this, but my question is: if 'numbers' such as ...111111111 are not integers, what are they? Are they reals? If they are reals and whole numbers, why are they not integers? Do they actually exist at all? If not why not?

 

[HallsofIvy]

Hoping I may be permitted to make a belated contribution here.

Summarising the key points from some of the other posts:
The key to the problem is that the new 'number' generated by the diagonal argument will have an infinite number of non-zero digits resulting from the infinite number of leading zeros in the original numbers. Such a number is not an integer since, although the set of integers has an infinite number of members, each individual member is finite and must have a finite number of non-zero digits.

I can accept this, but my question is: if 'numbers' such as ...111111111 are not integers, what are they? Are they reals? If they are reals and whole numbers, why are they not integers? Do they actually exist at all? If not why not?

They are not anything. It is possible to combine symbols in ways that make no sense! That's one of them.

You are confusing "numbers" with "numerals". The way numbers are defined has nothing to do with numerals and certainly not with the base 10 numeration system.

 

[Hurkyl]

I can accept this, but my question is: if 'numbers' such as ...111111111 are not integers, what are they?

First, I'd like to point out that there's no a priori reason why a string of decimal digits should represent anything interesting at all. We do use finite strings of decimal digits as a numeral system for representing natural numbers, but that is simply a notational system; interpreting the string of digits '20' as being the natural number twenty is just an application of this system; it is not because the string '20' has any inherent meaning related to natural numbers.

That said, you could create a new number system whose numbers are left-infinite strings of decimal digits, and whose arithmetic operations are the obvious extensions of decimal number arithmetic. We could just call them the 'left-infinite decimal numbers' or something descriptive like that, but unless we need to start talking about this number system, it doesn't really need a name. In this system, '...111' denotes the number -1/9. (where I've used '-' to mean the additive inverse, and '/' to mean multiplication by the multiplicative inverse)

However, it turns out that if our radix was some prime p, this number system is something that mathematicians do study, usually called 'the p-adic integers'. However, I'm not completely sure what happens in base 10; I think the result would be some strange mixture of the 2-adic integers with the 5-adic integers.

But just to emphasize the point -- this is not an inherent meaning to left-infinite strings like '...111'. This is just one an example of a mathematical structure one can build whose elements can be notated with left-infinite strings.

 

[CRGreathouse]

I can accept this, but my question is: if 'numbers' such as ...111111111 are not integers, what are they? Are they reals? If they are reals and whole numbers, why are they not integers? Do they actually exist at all? If not why not?

...11111 is a character string.

It cannot be interpreted as an integer, a whole number, or a real number. It can be interpreted as a 10-adic. I'm not sure if there's any good way to interpret it as a an element of a free monoid, but that may be possible under some interpretation or extension.

However, it turns out that if our radix was some prime p, this number system is something that mathematicians do study, usually called 'the p-adic integers'. However, I'm not completely sure what happens in base 10; I think the result would be some strange mixture of the 2-adic integers with the 5-adic integers.

10-adics exist, but they're just a ring -- not a field.

 

[manker]

In this system, '...111' denotes the number -1/9. (where I've used '-' to mean the additive inverse, and '/' to mean multiplication by the multiplicative inverse)

I don't quite follow this. By -1/9 I take it you are denoting the number that could also be represented as the recurring decimal -0.1111 ... But how can that be if the latter denotes a real number while ...111 doesn't denote anything at all in our usual number systems. (I'm being careful not to confuse numbers and numerals here :-). Or do you mean the operations - and / applied to 1 and 9 in this new number system, in which 1 and 9 do not have their conventional meanings. I think I need to bone up on p-adic numbers!

I'm also wondering what number the symbol oo (infinity) represents (if any). What does it mean when we say 'as x approaches oo' ?

 

[Focus]

I'm also wondering what number the symbol oo (infinity) represents (if any). What does it mean when we say 'as x approaches oo' ?

Depends on the context. With limits if you say $$lim_{x->\infty} f(x) = y$$ you really mean that for all $$\epsilon >0$$ there is a $$\delta$$ such that $$\delta<x \Rightarrow |f(x)-y|<\epsilon$$.

Basically if I give you an interval to fix the difference between f(x) and y, you should be able to give me a number such that for x greater than that, we have the difference satisfied.

 

[manker]

Depends on the context. With limits if you say $$lim_{x->\infty} f(x) = y$$ you really mean that for all $$\epsilon >0$$ there is a $$\delta$$ such that $$\delta<x \Rightarrow |f(x)-y|<\epsilon$$.

What about in the context of set theory. Could $$\infty$$ mean the size of the set of integers (= aleph-0)? I can see from previous discussion that it could not be an element of that set.

 

[CRGreathouse]

I don't quite follow this. By -1/9 I take it you are denoting the number that could also be represented as the recurring decimal -0.1111 ... But how can that be if the latter denotes a real number while ...111 doesn't denote anything at all in our usual number systems.

First, there's no reason that two different strings can't represent the same number. Certainly 3.999... and 4.000... are the same real number.

But in the 10-adics, there's no such thing as a decimal point or anything 'to the right' of it. Think about it this way:

...111 x 9 = ...999.
...999 + 1 = ...000.

So 0, minus 1, divided by 9, gives ...111 in the 10-adics.

 

[Focus]

What about in the context of set theory. Could $$\infty$$ mean the size of the set of integers (= aleph-0)? I can see from previous discussion that it could not be an element of that set.

What you mean is cardinality. It isn't really a size of a set (by the way a set does not have to be one of integers), I would say its more closer to the number of elements in a set, but I don't like this wording either (I don't really have a satisfactory definition :shy:).

Aleph-null is the first cardinal, which is used to describe the set of natural numbers. Any non-finite set that you can inject into the naturals will also have cardinality aleph-null. However you can't do this with the real numbers which is why they have aleph-one cardinality. This you prove by using cantors diagonal argument via a proof by contradiction. Also it is worth noting that $$2^{\aleph_0}=\aleph_1$$ (I think you need the continuum hypothesis for this). Interestingly it is the transcendental numbers (i.e numbers that aren't a root of a polynomial with rational coefficients) like pi and e.

Sorry for the long post, hope this helps.

 

[manker]

But in the 10-adics, there's no such thing as a decimal point or anything 'to the right' of it.

Are you sure about that? The entry in Wikipedia (!) on p-adics (http://en.wikipedia.org/wiki/P-adic_number) indicates otherwise (see I've been doing my homework ). It seems to me you are referring to 10-adic integers.

 

[manker]

What you mean is cardinality.

Well yes that is what I meant by size.

Aleph-null is the first cardinal, which is used to describe the set of natural numbers.

Should that be the first infinite cardinal? Surely finite sets also have cardinality, so the first cardinal would be 0, being the cardinality of the empty set.

Sorry for the long post, hope this helps.

Yes it all helps, and I appreciate all of the responses.
I have to do some work now :grumpy: so no more posts today.

 

[Focus]

Should that be the first infinite cardinal? Surely finite sets also have cardinality, so the first cardinal would be 0, being the cardinality of the empty set.

Yeah true I blame it on the time (Im tired) :tongue2:

Yes it all helps, and I appreciate all of the responses.
I have to do some work now :grumpy: so no more posts today.

Well that's why I am browsing these forums, to not do work and not feel completely bad about it. I prey to God my supervisor is not on these forums.

 

[CRGreathouse]

Any non-finite set that you can inject into the naturals will also have cardinality aleph-null. However you can't do this with the real numbers which is why they have aleph-one cardinality.

Beth-one cardinality, not aleph-1. Unless you have the CH all you can say is that the reals have at least aleph-one cardinality.

Are you sure about that? The entry in Wikipedia (!) on p-adics (http://en.wikipedia.org/wiki/P-adic_number) indicates otherwise (see I've been doing my homework ). It seems to me you are referring to 10-adic integers.

I've never read that article, but yes I'm talking about the 10-adic integers. I imagine that in both ...111 = -1/9, though.

 

[HallsofIvy]

What you mean is cardinality. It isn't really a size of a set (by the way a set does not have to be one of integers), I would say its more closer to the number of elements in a set, but I don't like this wording either (I don't really have a satisfactory definition :shy:).

Aleph-null is the first cardinal, which is used to describe the set of natural numbers. Any non-finite set that you can inject into the naturals will also have cardinality aleph-null. However you can't do this with the real numbers which is why they have aleph-one cardinality. This you prove by using cantors diagonal argument via a proof by contradiction. Also it is worth noting that $$2^{\aleph_0}=\aleph_1$$ (I think you need the continuum hypothesis for this). Interestingly it is the transcendental numbers (i.e numbers that aren't a root of a polynomial with rational coefficients) like pi and e.

Sorry for the long post, hope this helps.

No, you don't need the continuum hypothesis to prove that $$2^{\aleph_0}= \aleph_1$$. You need the continuum hypothesis to prove that [tex]2^{\aleph_0}= \aleph_1= c[/itex] where c is the cardinality of the real numbers.

But what does "it" in "Interestingly it is the transcendental numbers (i.e numbers that aren't a root of a polynomial with rational coefficients) like pi and e" refer to? Not, presumably $\aleph_1= c$(assuming continuum hypothesis) because that includes all real numbers, not just transcendental numbers.

 

[CRGreathouse]

No, you don't need the continuum hypothesis to prove that $$2^{\aleph_0}= \aleph_1$$. You need the continuum hypothesis to prove that [tex]2^{\aleph_0}= \aleph_1= c[/itex] where c is the cardinality of the real numbers.

I differ. $$2^{\aleph_0}= \mathfrak{c}$$ because there's a bijection from an infinite bitstring to the reals, but getting $$2^{\aleph_0}=\aleph_1$$ (or $$\mathfrak{c}=\aleph_1$$ which is the same) requires CH.

 

[Focus]

No, you don't need the continuum hypothesis to prove that $$2^{\aleph_0}= \aleph_1$$. You need the continuum hypothesis to prove that [tex]2^{\aleph_0}= \aleph_1= c[/itex] where c is the cardinality of the real numbers.

I am sorry but you do need CH to prove that identity. That is what the CH exactly states that $$2^{\aleph_{\alpha}}= \aleph_{\alpha +1}$$.

 

[CRGreathouse]

That is what the CH exactly states that $$2^{\aleph_{\alpha}}= \aleph_{\alpha +1}$$.

More pedantry: that's the GCH. The CH says this only for $\alpha=0.$