Use Cantor's Diagonalization on the set of Natural Numbers?

[bozar]

Homework Statement

This is actually only related to a problem given to me but I still would like to know the answer. From my understanding, Cantor's Diagonalization works on the set of real numbers, (0,1), because each number in the set can be represented as a decimal expansion with an infinite number of digits. This means 0.5 is not represented only by one digit to the right of the decimal point but rather by the "five" and an infinite number of 0s afterward.

My question then is can the set of natural numbers be represented similarly, ie instead of 5, have an infinite number of 0s preceding it (to the left of it) so the number is represented instead as ...000000005. Then the set of natural numbers can be aligned similarly as done in Cantor's Diagonalization with all numbers represented in its own row with each digit represented as d1, d2, d3, and so on with d being an element of {0,1,2,3,4,5,6,7,8,9}. The difference however would be that the digits in the rows, instead of going from left to right, would go from right to left. d1 would the the rightmost digit (the "ones" digit), d2 would be to the left, and so on. If we create a new number, n = d1d2d3d4... where dI = {1 if dII !=1, 2 if dII = 1}, then this new number will be different than every number in the table which should have represented all the natural numbers. Thus the set of natural numbers is not countable. Sorry if this was confusing, I didn't want to rewrite Cantor's Diagonalization but I didn't want to leave too much out.

Homework Equations

Everything.

The Attempt at a Solution

The only thing I can come up with is that natural numbers cannot be represented with an infinite number of 0s to the left of the number. However, I don't understand then how that differs from representing all decimals as having an infinite number of 0s to the right of the rightmost positive integer.

 

[Dick]

That is a creatively weird argument, I'll give you that. But if you change the first digit in ...00005 to a 1 then what natural number is that supposed to represent?

 

[bozar]

Thanks for the reply.

To answer your question: "But if you change the first digit in ...00005 to a 1 then what natural number is that supposed to represent? "

I'm assuming by "first digit" you mean the leftmost. Isn't that comparable to asking what changing the last digit of a decimal expansion in Cantor's Diagonalization would represent? It never really reaches there, right? My oddball diagonalization starts with the top right so the left most digit won't be changed until the end, which won't ever arrive.

So you know, the original homework problem was for me to find an error in a proof that showed the set (0,1) is countable. The proof assumes I can mirror a decimal expansion across the decimal point to get a natural number. For example, 0.5 will be 5, 0.15 will be 51, 0.91421 will be 12419. That's what got me started on this.

Thanks for any help.

 

[Dick]

edit: I actually have another dilemma that makes it worse. Instead of having zeroes to the left of a natural number, can I take a countably infinite subset of the natural numbers that is composed only of infinite numbers? And if so, then doesn't that also allow me to use Cantor's Diagonalization on the set to prove it uncountable?

Infinite strings of digits are generally uncountable. That doesn't prove the natural number are uncountable. I can represent the finite set {0,1} using infinite strings of digits. That doesn't prove it's uncountable.

 

[bozar]

Infinite strings of digits are generally uncountable. That doesn't prove the natural number are uncountable. I can represent the finite set {0,1} using infinite strings of digits. That doesn't prove it's uncountable.

Thanks for replying.

I think I have to take back that second attempt without the zeroes. I can't come up with a closed interval subset of the natural numbers that will allow me to use diagonalization to arrive at a new number in the subset. So scratch that. Thanks.

But I'm still confused about the original proposal, even if it is a bit odd. The diagonalization does in that case come up with a new number that is a natural number and is not listed even though all natural numbers should be listed.

 

[Dick]

So you know, the original homework problem was for me to find an error in a proof that showed the set (0,1) is countable. The proof assumes I can mirror a decimal expansion across the decimal point to get a natural number. For example, 0.5 will be 5, 0.15 will be 51, 0.91421 will be 12419. That's what got me started on this.

Thanks for any help.

Maybe we should just work on what's wrong with that proof. You can't 'mirror' a decimal expansion across the decimal point for every number in (0,1), can you? Only numbers that have a terminating decimal expansion. And they are countable.

 

[Dick]

Thanks for replying.

I think I have to take back that second attempt without the zeroes. I can't come up with a closed interval subset of the natural numbers that will allow me to use diagonalization to arrive at a new number in the subset. So scratch that. Thanks.

But I'm still confused about the original proposal, even if it is a bit odd. The diagonalization does in that case come up with a new number that is a natural number and is not listed even though all natural numbers should be listed.

100...0005 with an infinite number of zeros is not a natural number.

 

[bozar]

100...0005 with an infinite number of zeros is not a natural number.

Oh, that's where I'm going wrong. So an infinitely large number is not a natural number. I'll do some research to figure out why.

Thanks for the help. I think I know which way to go on my homework assignment now. And just because it's interesting, I ran into another http://mathforum.org/library/drmath/view/51845.html" (third post) who had the same argument that I'm having but constructed it better. He likewise was forced to try to define how a number with no defined leftmost digit would act.

Thanks for all the quick replies, I appreciate it.

 

[Dick]

I'll save you a little bit of trouble. 100...005 isn't a natural number because they are defined inductively. n=1 is the first one. Every natural number has a successor defined by n=n+1. The natural numbers are 1 and all of it's successors. You can prove by induction that they all have finite decimal expansions. 100...005 isn't one of them.