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

Contents

Use

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^''n''-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^''n'' elements.
:The sets ''B''_''n'' are not necessarily disjoint, but we can define
:: ''C''_''0'' = ''B''_''0''
::''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^''n'' 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.
----