Hacker News Reader

Is the set of integer sequences uncountably infinite? It seems like Cantor's diagonal argument would work here.

1. Number all sets from 0.

2. Construct a new set by picking the i^th number from each set.

Yes, one useful application of Cantor's theorem is to show that anything claiming to enumerate all integer sequences must fail to do so. That's assuming that the sequences can be infinite; if it were the Online Encyclopedia of Finite Integer Sequences, then it could succeed at enumerating all of them.

(As for the diagonal argument, make sure that the ith value of the counter-sequence DIFFERS from the ith value of the ith sequence. A sequence whose ith value matches the ith value of the ith sequence doesn't produce a contradiction, and could in fact be part of the encyclopedia.)

You don't even have to repeat the diagonal argument. There's a one-to-one correspondence between subsets of the natural numbers and sequences of elements from {0,1}. The i-th element is 1 if i is in the set, otherwise it's zero.

Reply on news.ycombinator.com