 Axiom of countable choice

The axiom of countable choice or axiom of denumerable choice, denoted AC_{ω}, is an axiom of set theory, similar to the axiom of choice. It states that any countable collection of nonempty sets must have a choice function. Spelled out, this means that if A is a function with domain N (where N denotes the set of natural numbers) and A(n) is a nonempty set for every n ∈ N, then there exists a function f with domain N such that f(n) ∈ A(n) for every n ∈ N.
Paul Cohen showed that AC_{ω} is not provable in ZermeloFraenkel set theory without the axiom of choice (ZF).
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 (for arbitrary n) finite choice for a finite set of size n, and it is this latter result (which is an elementary theorem in combinatorics) that is provable by induction.
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 Dedekindinfinite (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 of a set S⊆R is the limit of some sequence of elements of S\{x}, one uses (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)^{[1]} and (Howard/Rubin 1998).^{[2]}
AC_{ω} is a weak form of the axiom of choice (AC). AC states that every collection of nonempty 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^{[3]} (and DC is strictly weaker than AC).
Use
As an example of an application of AC_{ω}, here is a proof (from ZF+AC_{ω}) that every infinite set is Dedekindinfinite:
 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 11 map from X into X which is not onto, proving that X is Dedekindinfinite.
References
 ^ Horst Herrlich, Choice principles in elementary topology and analysis, Comment.Math.Univ.Carolinae 38,3 (1997), pp. 545545
 ^ Paul Howard and Jean E. Rubin. Consequences of the axiom of choice. Providence, R.I.: American Mathematical Society, 1998.
 ^ Jech T.J., The Axiom of Choice, North Holland, 1973.
This article incorporates material from axiom of countable choice on PlanetMath, which is licensed under the Creative Commons Attribution/ShareAlike License.
Categories:
Wikimedia Foundation. 2010.
Look at other dictionaries:
Axiom of dependent choice — In mathematics, the axiom of dependent choices, denoted DC, is a weak form of the axiom of choice (AC) which is still sufficient to develop most of real analysis. Unlike full AC, DC is insufficient to prove (given ZF) that there is a… … Wikipedia
Countable set — Countable redirects here. For the linguistic concept, see Count noun. Not to be confused with (recursively) enumerable sets. In mathematics, a countable set is a set with the same cardinality (number of elements) as some subset of the set of… … Wikipedia
Axiom of choice — This article is about the mathematical concept. For the band named after it, see Axiom of Choice (band). In mathematics, the axiom of choice, or AC, is an axiom of set theory stating that for every family of nonempty sets there exists a family of … Wikipedia
Choice function — A choice function (selector, selection) is a mathematical function f that is defined on some collection X of nonempty sets and assigns to each set S in that collection some element f(S) of S. In other words, f is a choice function for X if and… … Wikipedia
Axiom schema of replacement — In set theory, the axiom schema of replacement is a schema of axioms in Zermelo Fraenkel set theory (ZFC) that asserts that the image of any set under any definable mapping is also a set. It is necessary for the construction of certain infinite… … Wikipedia
Axiom — This article is about logical propositions. For other uses, see Axiom (disambiguation). In traditional logic, an axiom or postulate is a proposition that is not proven or demonstrated but considered either to be self evident or to define and… … Wikipedia
Hereditarily countable set — In set theory, a set is called hereditarily countable if and only if it is a countable set of hereditarily countable sets. This inductive definition is in fact well founded and can be expressed in the language of first order set theory. A set is… … Wikipedia
Freiling's axiom of symmetry — ( AX ) is a set theoretic axiom proposed by Chris Freiling. It is based on intuition of Stuart Davidsonbut the mathematics behind it goes back to Wacław Sierpiński. Let A be the set of functions mapping numbers in the unit interval [0,1] to… … Wikipedia
List of mathematical logic topics — Clicking on related changes shows a list of most recent edits of articles to which this page links. This page links to itself in order that recent changes to this page will also be included in related changes. This is a list of mathematical logic … Wikipedia
List of set theory topics — Logic portal Set theory portal … Wikipedia