Roughly, countable sets can be put in a list.

Of course, any finite set works.

The naturals meet this criterion:

$$1,2,3,4,\dots.$$

None is skipped (they're all there).

Cantor's diagonal argument shows that the reals cannot be put in a list. It does this by taking an arbitrary list of real numbers, and showing that there will always be at least one missing.

The very clever trick is to produce such a missing real by changing a digit (along the diagonal) of the decimal representations of the numbers in the list.

Since the constructed number differs from each number in the list, we are done. (Of course, we need to get rid of duplicate decimal representations, like $0.2$ and $0.1\bar9,$ at the outset.)

One application is that the countable union of countable sets is countable. To prove it simply arrange them in an infinite array, and wind your way back and forth from the upper left hand corner to put them in a list.

In this connection, see "Cantor's pairing function".

Roughly, countable sets can be put in a list.

Of course, any finite set works.

The naturals meet this criterion:

$$1,2,3,4,\dots.$$

None is skipped (they're all there).

Also, $\Bbb Z$ is countable:

$$0,1,-1,2,-2,3,-3,\dots .$$

Cantor's diagonal argument shows that the reals cannot be put in a list. It does this by taking an arbitrary list of real numbers, and showing that there will always be at least one missing.

The very clever trick is to produce such a missing real by changing a digit (along the diagonal) of the decimal representations of the numbers in the list.

Since the constructed number differs from each number in the list, we are done. (Of course, we need to get rid of duplicate decimal representations, like $0.2$ and $0.1\bar9,$ at the outset.)

One application is that the countable union of countable sets is countable. To prove it simply arrange them in an infinite array, and wind your way back and forth from the upper left hand corner to put them in a list.

In this connection, see "Cantor's pairing function".