Axiom of countable choice

The axiom of countable choice or axiom of denumerable choice, denoted AC_ω, is an axiom of set theory that states that every countable collection of non-empty sets must have a choice function. That is, given a function A {\displaystyle A} with domain N {\displaystyle \mathbb {N} } (where N {\displaystyle \mathbb {N} } denotes the set of natural numbers) such that A ( n ) {\displaystyle A(n)} is a non-empty set for every n ∈ N {\displaystyle n\in \mathbb {N} } , there exists a function f {\displaystyle f} with domain N {\displaystyle \mathbb {N} } such that f ( n ) ∈ A ( n ) {\displaystyle f(n)\in A(n)} for every n ∈ N {\displaystyle n\in \mathbb {N} } .

AC_ω is particularly useful for the development of mathematical 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 {\displaystyle x} of a set S ⊆ R {\displaystyle S\subseteq \mathbb {R} } is the limit of some sequence of elements of S ∖ { x } {\displaystyle S\setminus \{x\}} , one needs (a weak form of) the axiom of countable choice. When formulated for accumulation points of arbitrary metric spaces, the statement becomes equivalent to AC_ω.

The ability to perform analysis using countable choice has led to the inclusion of AC_ω as an axiom in some forms of constructive mathematics, despite its assertion that a choice function exists without constructing it.^[1]

As an example of an application of AC_ω, here is a proof (from ZF + AC_ω) that every infinite set is Dedekind-infinite:^[2]

Let X {\displaystyle X} be infinite. For each natural number n {\displaystyle n} , let A n {\displaystyle A_{n}} be the set of all n {\displaystyle n} -tuples of distinct elements of X {\displaystyle X} . Since X {\displaystyle X} is infinite, each A n {\displaystyle A_{n}} is non-empty. Application of AC_ω yields a sequence ( B n ) n ∈ N {\displaystyle (B_{n})_{n\in \mathbb {N} }} where each B n {\displaystyle B_{n}} is an n {\displaystyle n} -tuple. One can then concatenate these tuples into a single sequence ( b n ) n ∈ N {\displaystyle (b_{n})_{n\in \mathbb {N} }} of elements of X {\displaystyle X} , possibly with repeating elements. Suppressing repetitions produces a sequence ( c n ) n ∈ N {\displaystyle (c_{n})_{n\in \mathbb {N} }} of distinct elements, where

This i {\displaystyle i} exists, because when selecting c n {\displaystyle c_{n}} it is not possible for all elements of B n + 1 {\displaystyle B_{n+1}} to be among the n {\displaystyle n} elements selected previously. So X {\displaystyle X} contains a countable set. The function that maps each c n {\displaystyle c_{n}} to c n + 1 {\displaystyle c_{n+1}} (and leaves all other elements of X {\displaystyle X} fixed) is a one-to-one map from X {\displaystyle X} into X {\displaystyle X} which is not onto, proving that X {\displaystyle X} is Dedekind-infinite.^[2]

The axiom of countable choice (AC_ω) is strictly weaker than the axiom of dependent choice (DC),^[3] which in turn is weaker than the axiom of choice (AC). DC, and therefore also AC_ω, hold in the Solovay model, constructed in 1970 by Robert M. Solovay as a model of set theory without the full axiom of choice, in which all sets of real numbers are measurable.^[4]

Urysohn's lemma (UL) and the Tietze extension theorem (TET) are independent of ZF+AC_ω: there exist models of ZF+AC_ω in which UL and TET are true, and models in which they are false. Both UL and TET are implied by DC.^[5]

Paul Cohen showed that AC_ω is not provable in Zermelo–Fraenkel set theory (ZF) without the axiom of choice.^[6] However, some countably infinite sets of non-empty sets can be proven to have a choice function in ZF without any form of the axiom of choice. For example, V ω ∖ { ∅ } {\displaystyle V_{\omega }\setminus \{\emptyset \}} has a choice function, where V ω {\displaystyle V_{\omega }} is the set of hereditarily finite sets, i.e. the first set of non-finite rank in the Von Neumann universe. The choice function is: { ⟨W_n,W_k⟩ : k < n < ω ∧ W_k ∈ W_n ∧ ∀ j < k ( W_j ∉ W_n ) } where W_n = {W_k : k<n ∧ (n mod 2^k+1) ≥ 2^k} for n<ω. W lists every hereditarily finite set exactly once and is based on the binary numeral for n which has a 1 in each place corresponding to a k with W_k ∈ W_n. Another example is the set of proper and bounded open intervals of real numbers with rational endpoints.

ZF+AC_ω suffices to prove that the union of countably many countable sets is countable. These statements are not equivalent: Cohen's First Model supplies an example where countable unions of countable sets are countable, but where AC_ω does not hold.^[7]

There are many equivalent forms to the axiom of countable choice, in the sense that any one of them can be proven in ZF assuming any other of them. They include the following:^[8][9]

• Every countable collection of non-empty sets has a choice function.^[8]
• Every infinite collection of non-empty sets has an infinite sub-collection with a choice function.^[8]
• Every σ-compact space (the union of countably many compact spaces) is a Lindelöf space (every open cover has a countable subcover).^[8] A metric space is σ-compact if and only if it is Lindelöf.^[9]
• Every second-countable space (it has a countable base of open sets) is a separable space (it has a countable dense subset).^[8] A metric space is separable if and only if it is σ-compact.^[9]
• Every sequentially continuous real-valued function in a metric space is a continuous function.^[8]
• Every accumulation point of a subset of a metric space is a limit of a sequence of points from the subset.^[9]
• The Rasiowa–Sikorski lemma MA ( ℵ 0 ) {\displaystyle (\aleph _{0})} , a countable form of Martin's axiom: in a preorder with the countable chain condition, every countable family of dense subsets has a filter intersecting all the subsets. (In this context, a set is called dense if every element of the preorder has a lower bound in the set.)^[8]

This article incorporates material from axiom of countable choice on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.