Set Theory/Countability

From Wikibooks, open books for an open world
Jump to navigation Jump to search

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.