# Thread: A diagonalization example

1. ## A diagonalization example

I found the argument below on MathReference archive

all the finite sets of integers are countable, but not so for the infinite subsets. Here is a simple diagonalization argument. If the infinite sets are countable then the correspondence builds a list of all possible subsets. Build a new subset S as follows. Let n be in S iff n is not in the nth subset on the list. Therefore S cannot appear anywhere on the list. If S is in position n, then S contains n iff it doesn't. Every possible correspondence fails, because it misses some set S.

The bold part does not make sense to me. Could you please give me an explanation of that part? I would really appreciate that.

2. Suppose that $S \subseteq \mathbb{Z}$ is infinite and the collection of all such sets is countable.
Then we can give it a name, j, $S_j$.
Each subset of the integers is countable, so we can name each element $S_j = \left\{ {n_{j,k} :k \in \mathbb{Z}^ + } \right\}$.
Thus $n_{4,10}$ is the tenth element in the fourth set.
Now we have the ideal setup for a ‘diagonal argument’.

3. Originally Posted by Plato
Suppose that $S \subseteq \mathbb{Z}$ is infinite and the collection of all such sets is countable.
Then we can give it a name, j, $S_j$.
Each subset of the integers is countable, so we can name each element $S_j = \left\{ {n_{j,k} :k \in \mathbb{Z}^ + } \right\}$.
Thus $n_{4,10}$ is the tenth element in the fourth set.
Now we have the ideal setup for a ‘diagonal argument’.
That's very clear. Thank you very much!