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<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}|<m$

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}$, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikibooks.org/v1/":): {\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$