Axiom of countable choice
# 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

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

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.
