Axiom of countable choice

The axiom of countable choice, denoted AC_ω, or axiom of denumerable choice, 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. Paul Cohen showed that AC_ω is not provable in Zermelo-Fraenkel set theory (ZF).

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 set of real numbers (considered as sets of Cauchy sequences of rationals).

AC_ω is a weak form of the axiom of choice (AC), which 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 (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.

---