Lesson 3

Theorem. Countable sets satisfy the following properties:

1. The union of two countable sets is countable.
2. A subset of a countable set is either finite or countable.
3. An infinite set contains a countable subset.
4. The union of a finite or countable number of countable sets is countable. (In other words, the Cartesian product of two countable sets is countable.)
5. Adding at most a countable set to an infinite set does not change its cardinality. (In other words, if \(A\) is infinite and \(B\) is finite or countable, then \(A \cup B\) is in one-to-one correspondence with \(A\).)

Proof.

1. The union of the sets \(\{a_{1}, a_{2}, \dotsc\}\) and \(\{b_{1}, b_{2}, \dotsc\}\) can be enumerated as \(\{a_{1}, b_{1}, a_{2}, b_{2}, \dotsc\}\) (and skipping repetitions).
2. List the countable set \(\{a_{1},a_{2}, \dotsc\}\) and cross out some elements to leave the subset we are interested in—it will be either finite or countable.
3. Such a subset can be collected greedily: take any element, then take the next one, then another, and so on. At each step, we will be able to take an element because the original set is infinite.
4. Let \(\{A_{1}, A_{2}, \dotsc\}\) be our sets. Write an infinite (downward and rightward) table: in the first row write all the elements of \(A_{1}\), in the second row all the elements of \(A_{2}\), and so on. After that, we can enumerate the elements of the table diagonally (as in the theorem above), skipping repetitions and empty spaces (empty spaces may occur if some of the \(A_{i}\) are finite or if there are finitely many of them).
5. Assume that \(A \cap B = \varnothing\) (if not, we can remove the elements of \(B\) that are in \(A\): this does not change the fact that \(B\) is finite or countable). Select a countable subset \(C\) of \(A\) and construct a bijection between \(C\) and \(C \cup B\). Leave the other elements of \(A\) as they are.