Axiom of countable choice

Article on other languages:

• Axiom_spočetného_výběru
• 可数选择公理

	del.icio.us
	Digg
	Furl
	Reddit
	Rojo
	Add to OnlyWire

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 (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 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

This article incorporates material from axiom of countable choice on PlanetMath, which is licensed under the GFDL.