# Set Theory/Countability

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

Let be a collection of finite, totally ordered sets. Then is countable or finite.

**Proof:** To ease notation, define . First we claim that we may assume the to be disjoint. Indeed, if the are not disjoint, define a new family of sets as follows: Set and once are defined, set .
Now delete all empty sets from . 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 yields a numbering of the elements of , so that we may write We define a bijection as follows:

- .

This is injective, for if , then

- ;

if we have, for instance, , then note that , so that we must have , a contradiction, so that , and therefore , so that . It is furthermore surjective, since whenever , pick maximal so that

and then

- ;

note that , for else we get a contradictionn to the maximality of . 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 of finite sets is at most countable.

**Proof:** Using the axiom of countable finite choice, pick a total order on each and use that the countable union of finite totally ordered sets is countable. For the other direction, let be a sequence of non-empty finite sets, and pick a numbering of (which may also be finite, but then it's also possible to pick a numbering). Then define a sequence as thus: shall be the element of with the smallest number. Then is a sequence as required by the axiom of countable finite choice.

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

Let . Then is countable.

**Proof:** We write

- ,
**Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "/mathoid/local/v1/":): {\displaystyle S_n := \left\{T \subseteq \mathbb N \middle| |T| = n\}}**.

Each 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.