# Set Theory/Countability

Proposition (countable union of finite totally ordered sets is countable):

Let $(S_{n},\leq _{n})_{n\in \mathbb {N} }$ be a collection of finite, totally ordered sets. Then $\cup _{n\in \mathbb {N} }S_{n}$ is countable or finite.

Proof: To ease notation, define $T:=\cup _{n\in \mathbb {N} }S_{n}$ . First we claim that we may assume the $S_{n}$ to be disjoint. Indeed, if the $S_{n}$ are not disjoint, define a new family of sets as follows: Set $S'_{1}:=S_{1}$ and once $S'_{1},\ldots ,S'_{n}$ are defined, set $S'_{n+1}:=S_{n+1}\setminus \cup _{k\leq n}S_{k}$ . Now delete all empty sets from $(S_{n})_{n\in \mathbb {N} }$ . Either only finitely many sets are left, and the union is finite, or there are countably many left, so that we have a countable family of disjoint non-empty finite sets. Note that the total order on each $S_{n}$ yields a numbering of the elements of $S_{n}$ , so that we may write $S_{n}=\{s_{n,1},\ldots ,s_{n,k_{n}}\}$ We define a bijection $f:T\to \mathbb {N}$ as follows:

$f(s_{n,j}):=\sum _{l=1}^{n-1}|S_{l}|+j$ .

This is injective, for if $f(s_{n,j})=f(s_{n',j'})$ , then

$\sum _{l=1}^{n-1}|S_{l}|+j=\sum _{l=1}^{n'-1}|S_{l}|+j'$ ;

if we have, for instance, $n , then note that $j\leq |S_{n}|$ , so that we must have $j'=0$ , a contradiction, so that $n=n'$ , and therefore $j=j'$ , so that $s_{n,j}=s_{n',j'}$ . It is furthermore surjective, since whenever $m\in \mathbb {N}$ , pick $n$ maximal so that

$\sum _{l=1}^{n}|S_{l}| and then

$j:=m-\sum _{l=1}^{n}|S_{l}|$ ;

note that $j\leq |S_{n}|$ , for else we get a contradictionn to the maximality of $n$ . Hence, we have a bijection. $\Box$ Proposition (countable union of finite sets is countable iff axiom of countable finite choice):

The axiom of countable finite choice holds if and only if each countable union $\cup _{n\in \mathbb {N} }S_{n}$ of finite sets is at most countable.

Proof: Using the axiom of countable finite choice, pick a total order on each $S_{n}$ and use that the countable union of finite totally ordered sets is countable. For the other direction, let $(S_{n})_{n\in \mathbb {N} }$ be a sequence of non-empty finite sets, and pick a numbering of $\cup _{n\in \mathbb {N} }S_{n}$ (which may also be finite, but then it's also possible to pick a numbering). Then define a sequence $(x_{n})_{n\in \mathbb {N} }$ as thus: $x_{n}$ shall be the element of $S_{n}$ with the smallest number. Then $(x_{n})_{n\in \mathbb {N} }$ is a sequence as required by the axiom of countable finite choice. $\Box$ Proposition (set of finite subsets of natural numbers is countable):

Let $S:=\{T\subseteq \mathbb {N} |T{\text{ finite }}\}$ . Then $S$ is countable.

Proof: We write

$S=\bigcup _{n\in \mathbb {N} _{0}}S_{n}$ , $\displaystyle S_n := \left\{T \subseteq \mathbb N \middle| |T| = n\}$ .

Each $S_{n}$ has a total order, namely the Order Theory/Lexicographic order#lexicographic order, which is total. Therefore, we may apply the fact that the countable union of finite totally ordered sets is countable. $\Box$ 