Axiom of countable choice

From Wikipedia, the free encyclopedia

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).

[edit] 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 An be the set of all 2n-element subsets of X. Since X is infinite, each An is nonempty. A first application of ACω yields a sequence (Bn : n=0,1,2,3,...) where each Bn is a subset of X with 2n elements.
The sets Bn are not necessarily disjoint, but we can define
C0 = B0
Cn= the difference of Bn and the union of all Cj, j<n.
Clearly each set Cn has at least 1 and at most 2n elements, and the sets Cn are pairwise disjoint. A second application of ACω yields a sequence (cn: n=0,1,2,...) with cn∈Cn.
So all the cn are distinct, and X contains a countable set. The function that maps each cn to cn+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.

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

 This mathematical logic-related article is a stub. You can help Wikipedia by expanding it.
Languages