0
$\begingroup$

I found this proof in a StackExchange thread and found it pretty understandable and simple:

"The other answers give some sort of formula, like you were trying to do. But, the simplest way to see that the set of all finite subsets of $\mathbb{N}$ is countable is probably the following.

If you can list out the elements of a set, with one coming first, then the next, and so on, then that shows the set is countable. There is an easy pattern to see here. Just start out with the least elements.

$$\emptyset, \{1\}, \{2\}, \{1, 2\}, \{3\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}, \{4\}, \ldots$$

In other words, first comes $\{1\}$, then comes $\{2\}$. Each time you introduce a new integer, $n$, list all the subsets of $[n] = \{1, 2, \ldots, n\}$ that contain $n$ (the ones that don't contain $n$ have already showed up). Therefore, all subsets of $[n]$ show up in the first $2^{n}$ elements of this sequence."

I understand how it applies for finite subsets of N, but I cant really pinpoint of why it would not apply to a set of all subsets of N. We could continue this scheme for ever, couldnt we? I assume that I think in a wrong way about infinity but I am not quite sure. Any help is greatly appreciated!

2 Answers 2

1

Therefore, all subsets of [n] show up in the first 2n elements of this sequence.

Presumably, by "[n]", the writer meant "the set of all positive integers up to and including n". Given any finite subset S, if we take n to be the largest element of S, then S is a subset of [n]. There are $2^n$ subsets of [n], so once we're listed all of them, S must be on that list. So S must show up in the first $2^n$ subsets on the list.

The reason this logic fails for infinite subsets is that infinite subsets don't have a largest element.

1

It is because every set on this list is of finite size, and so no set in this list would ever be of infinite size. So, for example, the set of all even numbers would never show up in this list.

As an analogy: Every set in this list of subsets is of finite size, just as every number in the list 1,2,3,4,... is a finite number. The fact that the list of subsets as indicated is an infinite list only means that there are infinitely many finite subsets, just as there are infinitely many finite numbers in the infinite list 1,2,3,4,...