0
$\begingroup$

One such tuple is [2, 45, 342 ... onwards to infinity]. Another such tuple is [0, 1, 2, 3 ... onwards to infinity].

I think this set is countable because we can lay all of these sets out one below another in order. We can then order them one by one, which is a bijection to the natural numbers.

  • 0
    @DavidFaux If you can lay out these sets one below one another, tell me which tuple is the next one after $[0, 1, 2, 3, \ldots]$?2012-10-01

2 Answers 2

3

It is critical that tuples are of finite length, while your examples seem to be infinite. If you consider only finite ones, they are countable. If you consider infinite ones, you have all the subsets of $\mathbb N$, which is uncountable by Cantor's theorem

  • 0
    Actually König's lemma proves this one, rather than Cantor's theorem.2012-10-01
2

A famous proof of the uncountability of $\mathbb{R}$ can be applied to your set too.

If your set had an ordering $\{s_1,s_2,s_3,\ldots\}$ with each $s_i=[s_{i1},s_{i2},s_{i3}, \ldots]$, then we can construct an $s$ that is not in your ordering. Just define $s$'s $i$th entry to be something other than $s_{ii}$, and also something greater than all of the preceding entries of $s$ (to keep your condition of distinct natural numbers, and even keep the sequence sorted, if that is your intent). Then for all $i$, $s$ disagrees with $s_i$ in the $i$th position, and so $s\neq s_i$ for any $i$. So there never was an ordering that contained everything in your set in the first place.

  • 0
    @Erick I think my mistake was omitting the word distinct from my reading of OP's question. But I've edited my answer accordingly.2012-10-01