Axiom of countable choice

The axiom of countable choice or axiom of denumerable choice, denoted AC_ω, is an axiom of set theory, similar to the axiom of choice. It states that any countable collection of non-empty sets must have a choice function. Spelled out, this means that if A is a function with domain N (where N denotes the set of natural numbers) and A(n) is a non-empty set for every n ∈ N, then there exists a function f with domain N such that f(n) ∈ A(n) for every n ∈ N.

Paul Cohen showed that AC_ω is not provable in Zermelo-Fraenkel set theory without the axiom of choice (ZF).

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 (for arbitrary n) finite choice for a finite set of size n, and it is this latter result (which is an elementary theorem in combinatorics) that is provable by induction.

ZF + AC_ω suffices to prove that the union of countably many countable sets is countable. It 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 of a set S⊆R is the limit of some sequence of elements of S\{x}, one uses (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)^[1] and (Howard/Rubin 1998).^[2]

AC_ω is a weak form of the axiom of choice (AC). AC states that every collection of non-empty sets must have a choice function. AC clearly implies the axiom of dependent choice (DC), and DC is sufficient to show AC_ω. However AC_ω is strictly weaker than DC^[3] (and DC is strictly weaker than AC).

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 2ⁿ-element subsets of X. Since X is infinite, each A_n is nonempty. A first application of AC_ω yields a sequence (B_n : n=0,1,2,3,...) where each B_n is a subset of X with 2ⁿ elements.

The sets B_n are not necessarily disjoint, but we can define

C₀ = B₀

C_n= the difference of B_n and the union of all C_j, j<n.

Clearly each set C_n has at least 1 and at most 2ⁿ elements, and the sets C_n are pairwise disjoint. A second application of AC_ω yields a sequence (c_n: n=0,1,2,...) with c_n∈C_n.

So all the c_n are distinct, and 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 1-1 map from X into X which is not onto, proving that X is Dedekind-infinite.

References

1. ^ Horst Herrlich, Choice principles in elementary topology and analysis, Comment.Math.Univ.Carolinae 38,3 (1997), pp. 545-545
2. ^ Paul Howard and Jean E. Rubin. Consequences of the axiom of choice. Providence, R.I.: American Mathematical Society, 1998.
3. ^ Jech T.J., The Axiom of Choice, North Holland, 1973.

---

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