# 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*with domain

**N**(where

**N**denotes the set of natural numbers) such that

*A*(

*n*) is a non-empty set for every

*n*∈

**N**, there exists a function

*f*with domain

**N**such that

*f*(

*n*) ∈

*A*(

*n*) for every

*n*∈

**N**.

## Overview[edit]

The axiom of countable choice (AC_{ω}) is strictly weaker than the axiom of dependent choice (DC), (Jech 1973) which in turn is weaker than the axiom of choice (AC). Paul Cohen showed that AC_{ω} is not provable in Zermelo–Fraenkel set theory (ZF) without the axiom of choice (Potter 2004). AC_{ω} holds in the Solovay model.

ZF+AC_{ω} suffices to prove that the union of countably many countable sets is countable. The converse statement "assuming ZF, 'every countable union of countable sets is countable' implies AC_{ω}" does not hold, as witnessed by *Cohen's First Model*.^{[1]} ZF+AC_{ω} 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 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_{ω}. For other statements equivalent to AC_{ω}, see Herrlich (1997) and Howard & Rubin (1998).

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. 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*_{ω} − {Ø} has a choice function, where *V*_{ω} is the set of hereditarily finite sets, *i.e.* the first set in the Von Neumann universe of non-finite rank. The choice function is (trivially) the least element in the well-ordering. Another example is the set of proper and bounded open intervals of real numbers with rational endpoints.

## Use[edit]

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 non-empty. The 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 between*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. The 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[edit]

**^**Herrlich, Horst (2006).*Axiom of Choice*. Section A.4: Springer. ISBN 3-540-30989-6. Retrieved 18 July 2023.`{{cite book}}`

: CS1 maint: location (link)

- Jech, Thomas J. (1973).
*The Axiom of Choice*. North Holland. pp. 130–131. ISBN 978-0-486-46624-8. - Herrlich, Horst (1997). "Choice principles in elementary topology and analysis" (PDF).
*Comment. Math. Univ. Carolinae*.**38**(3): 545. - Howard, Paul; Rubin, Jean E. (1998). "Consequences of the axiom of choice".
*Providence, R.I*. American Mathematical Society. ISBN 978-0-8218-0977-8. - Potter, Michael (2004).
*Set Theory and its Philosophy : A Critical Introduction*. Oxford University Press. p. 164. ISBN 9780191556432.

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