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. 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 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. These include V_{ω}− {Ø} and 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.
References
- 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.