Axiom of countable choice

Each set in the countable sequence of sets (S_i) = S₁, S₂, S₃, ... contains a non-zero, and possibly infinite (or even uncountably infinite), number of elements. The axiom of countable choice allows us to arbitrarily select a single element from each set, forming a corresponding sequence of elements (x_i) = x₁, x₂, x₃, ...

The axiom of countable choice or axiom of denumerable choice, denoted AC_ω, is an axiom of set theory that states that every countable collection of non-empty sets must have a choice function. That is, given a function $A$ with domain $\mathbb {N}$ (where $\mathbb {N}$ denotes the set of natural numbers) such that $A(n)$ is a non-empty set for every $n\in \mathbb {N}$, there exists a function $f$ with domain $\mathbb {N}$ such that $f(n)\in A(n)$ for every $n\in \mathbb {N}$.

Overview

The axiom of countable choice (AC_ω) is strictly weaker than the axiom of dependent choice (DC), which in turn is weaker than the axiom of choice (AC). Paul Cohen showed that AC_ω is not provable in Zermelo–Fraenkel set theory (ZF) without the axiom of choice. DC, and therefore also AC_ω, hold in the Solovay model, constructed in 1970 by Robert M. Solovay as a model of set theory without the full axiom of choice, in which all sets of real numbers are measurable.

ZF+AC_ω suffices to prove that the union of countably many countable sets is countable. The converse statement "assuming ZF, 'every countable union of countable sets is countable' implies AC_ω" does not hold, as witnessed by Cohen's First Model. ZF+AC_ω also suffices to prove that every infinite set is Dedekind-infinite (equivalently: has a countably infinite subset).

AC_ω is particularly useful for the development of analysis, where many results depend on having a choice function for a countable collection of sets of real numbers. For instance, in order to prove that every accumulation point $x$ of a set $S\subseteq \mathbb {R}$ is the limit of some sequence of elements of $S\setminus \{x\}$, one needs (a weak form of) the axiom of countable choice. When formulated for accumulation points of arbitrary metric spaces, the statement becomes equivalent to AC_ω. For other statements equivalent to AC_ω, see Herrlich (1997) and Howard & Rubin (1998).

A common misconception is that countable choice has an inductive nature and is therefore provable as a theorem (in ZF, or similar, or even weaker systems) by induction. However, this is not the case; this misconception is the result of confusing countable choice with finite choice for a finite set of size $n$ (for arbitrary $n$), and it is this latter result (which is an elementary theorem in combinatorics) that is provable by induction. However, some countably infinite sets of non-empty sets can be proven to have a choice function in ZF without any form of the axiom of choice. For example, $V_{\omega }\setminus \{\emptyset \}$ has a choice function, where $V_{\omega }$ is the set of hereditarily finite sets, i.e. the first set in the Von Neumann universe of non-finite rank. The choice function is (trivially) the least element in the well-ordering. Another example is the set of proper and bounded open intervals of real numbers with rational endpoints.

Use

As an example of an application of AC_ω, here is a proof (from ZF + AC_ω) that every infinite set is Dedekind-infinite:

Let $X$ be infinite. For each natural number $n$, let $A_{n}$ be the set of all $n$-tuples of distinct elements of $X$. Since $X$ is infinite, each $A_{n}$ is non-empty. Application of AC_ω yields a sequence $(B_{n})_{n\in \mathbb {N} }$ where each $B_{n}$ is an $n$-tuple. One can then concatenate these tuples into a single sequence $(b_{n})_{n\in \mathbb {N} }$ of elements of $X$, possibly with repeating elements. Suppressing repetitions produces a sequence $(c_{n})_{n\in \mathbb {N} }$ of distinct elements, where

$c_{n}=b_{k}$, with $k=\min\{i\mid \forall _{j<n}b_{i}\neq c_{j}\}$.

This $i$ exists, because when selecting $c_{n}$ it is not possible for all elements of $B_{n+1}$ to be among the $n$ elements selected previously. So $X$ contains a countable set. The function that maps each $c_{n}$ to $c_{n+1}$ (and leaves all other elements of $X$ fixed) is a one-to-one map from $X$ into $X$ which is not onto, proving that $X$ is Dedekind-infinite.

References

This article incorporates material from axiom of countable choice on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.