Axiom of Countable Choice

The axiom of countable choice or axiom of denumerable choice, denoted AC_ω, is an axiom of set theory (a special case of 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 (ZF) without the axiom of choice (AC).

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.

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 x 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) and (Howard/Rubin 1998).

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 (and DC is strictly weaker than AC).