Diagonal Dash - Proof of uncountably many integers....

charlieroot

Was lying in bed last night, couldn't sleep so I got to thinking about Cantor's diagonal dash style proofs. So I came up with this proof that there are uncountably many integers (its false, I think, but it wasn't obvious to me straight away.).

Firstly, you can represent any integer using its prime factorisation as follows.

2 = (1,0,0,0,....)
3 = (0,1,0,0,....)
4 = (2,0,0,0,....)

Basic idea is that the nth position is the power of the nth prime dividing the integer.

Now take the integers and list them (we'll exclude negative integers and one here for simplicity)

1. 2 = (1,0,0,0....)
2. 3 = (0,1,0,0,....)
3. 4 = (2,0,0,0,....)
4. 5 = (0,0,1,0,....)
5. 6 = (1,1,0,0...)
6. 7 = (0,0,0,1,....)

And so on.


You can now "construct" an integer which is not in the list á la Cantor. Where the nth entry differs from the nth entry of the nth integer in the list. And so you have constructed an integer which is not in the list. Proving that there are uncountably many integers.

So does anyone see why its false, (not trying to be smart in asking this, just wondering if you see the fault in my reasoning? I'm not 100% sure about my reason for it being false. I can't quite make the argument rigorous enough to complete satisfy myself anyway).

Regards,
Noel.

P.S. Instead of prime factorisation you could just use a representation in any base, which would work just as well.

ecksor

You can now "construct" an integer which is not in the list á la Cantor. Where the nth entry differs from the nth entry of the nth integer in the list. And so you have constructed an integer which is not in the list.

I don't follow how you justify that this new integer you've constructed isn't already in the list.

charlieroot

ecksor wrote:

I don't follow how you justify that this new integer you've constructed isn't already in the list.

Its differs in the nth place to the nth integer in the list and so is different to every integer in the list.

Noel.

ecksor

I don't see it. As far as I can tell you've already listed all the positive integers so by definition the thing you've constructed was already in the list.

carl_

well, it is wrong because the mapping from naturals to integers is ..

f: N -> Z
f(n) = {n/2 when n is even, (1-n)/2 when n is odd}

I'm confused by your argument as well. Should your list not be:
1. 2 = (1,0,0,0,....)
2. 3 = (0,1,0,0,....)
3. 4 = (2,0,0,0,....)
4. 5 = (0,0,1,0,....)
5. 6 = (1,1,0,0,....) etc. ?

charlieroot

carl_ wrote:

well, it is wrong because the mapping from naturals to integers is ..

f: N -> Z
f(n) = {n/2 when n is even, (1-n)/2 when n is odd}

I'm confused by your argument as well. Should your list not be:
1. 2 = (1,0,0,0,....)
2. 3 = (0,1,0,0,....)
3. 4 = (2,0,0,0,....)
4. 5 = (0,0,1,0,....)
5. 6 = (1,1,0,0,....) etc. ?

Your quite right. The entry I had for 4 should as you correctly mentioned be (2,0,0,....) other than that I think its fine.

charlieroot

ecksor wrote:

I don't see it. As far as I can tell you've already listed all the positive integers so by definition the thing you've constructed was already in the list.

Its actually not in the list. Suppose its the nth integer in the list, but the "integer" I've contructed differs from the nth integer listed in the nth entry.



Noel.

charlieroot

carl_ wrote:

well, it is wrong because the mapping from naturals to integers is ..

f: N -> Z
f(n) = {n/2 when n is even, (1-n)/2 when n is odd}

This is an alternative mapping. But it doesn't show that there is a problem with my mapping and the construction of there being an integer not in the list.

ecksor

charlieroot wrote:

Its actually not in the list. Suppose its the nth integer in the list, but the "integer" I've contructed differs from the nth integer listed in the nth entry.

That sounds like you're talking about a finite list and trying to construct the next one like a proof of the infinity of primes, but you've already constructed an infinite list of all positive integers.

Perhaps I'm just being dense but ...

The fundamental theorem of arithmetic tells us that each positive integer has a unique prime factorisation, which is essentially what you're describing in your vector or tuple or whatever you want to call it. Conversely, each unique list of prime factors corresponds to a unique integer, no? So, why is it that your supposedly new integer isn't already in the list you constructed. Surely you've already listed all the positive integers.

Crumbs

Any new integer that you construct must necessarily be greater than n, so you can still retain one-to-one countability with the natural numbers ???

tbjw

charlieroot wrote:

Was lying in bed last night, couldn't sleep so I got to thinking about Cantor's diagonal dash style proofs. So I came up with this proof that there are uncountably many integers (its false, I think, but it wasn't obvious to me straight away.).

Firstly, you can represent any integer using its prime factorisation as follows.

2 = (1,0,0,0,....)
3 = (0,1,0,0,....)
4 = (2,0,0,0,....)

Basic idea is that the nth position is the power of the nth prime dividing the integer.

Now take the integers and list them (we'll exclude negative integers and one here for simplicity)

1. 2 = (1,0,0,0....)
2. 3 = (0,1,0,0,....)
3. 4 = (2,0,0,0,....)
4. 5 = (0,0,1,0,....)
5. 6 = (1,1,0,0...)
6. 7 = (0,0,0,1,....)

And so on.


You can now "construct" an integer which is not in the list á la Cantor. Where the nth entry differs from the nth entry of the nth integer in the list. And so you have constructed an integer which is not in the list. Proving that there are uncountably many integers.

So does anyone see why its false, (not trying to be smart in asking this, just wondering if you see the fault in my reasoning? I'm not 100% sure about my reason for it being false. I can't quite make the argument rigorous enough to complete satisfy myself anyway).

Regards,
Noel.

P.S. Instead of prime factorisation you could just use a representation in any base, which would work just as well.

You can construct a new sequence of integers (a_1,a_2,...) as you claim. The problem is that this does not correspond to a finite integer if infinitely many of the entries are nonzero, and this is what happens if you try carrying out the construction.

You *have* demonstrated that the set of sequences of integers is not countable, but that is a well-known fact.

Toy

To see why it fails, simply re-order your list like this:

(1,0,0,0,...) = 2
(0,1,0,0,...) = 3
(0,2,0,0,...) = 9
(1,1,0,0,...) = 6
(1,2,0,0,...) = 18
(2,0,0,0,...) = 4
(2,1,0,0,...) = 12
(2,2,0,0,...) = 36
(0,0,1,0,...) = 5
(0,0,2,0,...) = 25
(0,0,3,0,...) = 125

Which clearly includes all sequences (with finitely many non-zero entries, that is. i.e. integers)

(of course look at the list of integers on the right and ask yourself (without considering the left) is it complete...?)