# Set Theory/Countability

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

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

Proof: To ease notation, define ${\displaystyle T:=\cup _{n\in \mathbb {N} }S_{n}}$. First we claim that we may assume the ${\displaystyle S_{n}}$ to be disjoint. Indeed, if the ${\displaystyle S_{n}}$ are not disjoint, define a new family of sets as follows: Set ${\displaystyle S'_{1}:=S_{1}}$ and once ${\displaystyle S'_{1},\ldots ,S'_{n}}$ are defined, set ${\displaystyle S'_{n+1}:=S_{n+1}\setminus \cup _{k\leq n}S_{k}}$. Now delete all empty sets from ${\displaystyle (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 ${\displaystyle S_{n}}$ yields a numbering of the elements of ${\displaystyle S_{n}}$, so that we may write ${\displaystyle S_{n}=\{s_{n,1},\ldots ,s_{n,k_{n}}\}}$ We define a bijection ${\displaystyle f:T\to \mathbb {N} }$ as follows:

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

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

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

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

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

and then

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

note that ${\displaystyle j\leq |S_{n}|}$, for else we get a contradictionn to the maximality of ${\displaystyle n}$. Hence, we have a bijection. ${\displaystyle \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 ${\displaystyle \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 ${\displaystyle S_{n}}$ and use that the countable union of finite totally ordered sets is countable. For the other direction, let ${\displaystyle (S_{n})_{n\in \mathbb {N} }}$ be a sequence of non-empty finite sets, and pick a numbering of ${\displaystyle \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 ${\displaystyle (x_{n})_{n\in \mathbb {N} }}$ as thus: ${\displaystyle x_{n}}$ shall be the element of ${\displaystyle S_{n}}$ with the smallest number. Then ${\displaystyle (x_{n})_{n\in \mathbb {N} }}$ is a sequence as required by the axiom of countable finite choice. ${\displaystyle \Box }$

Proposition (set of finite subsets of natural numbers is countable):

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

Proof: We write

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

Each ${\displaystyle 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. ${\displaystyle \Box }$