Set Theory/Countability

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

Let $(S_n,{\le }_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{\text{'}}_1:=S_1$ and once $S{\text{'}}_1,\dots ,S{\text{'}}_n$ are defined, set $S{\text{'}}_{n+1}:=S_{n+1}\setminus {\cup }_{k\le 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},\dots ,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^{\prime },j^{\prime }})$, then

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

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

$\sum _{l=1}^n|S_l|<m$

and then

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

note that $j\le |S_n|$, for else we get a contradictionn to the maximality of $n$. Hence, we have a bijection. $◻$

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. $◻$

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$, Failed to parse (unknown function "\middle"): {\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. $◻$