Axiom of countable choice
Encyclopedia
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 non-empty 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 number
s) and A(n) is a non-empty 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 Zermelo-Fraenkel 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 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 number
s. 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 space
s, the statement becomes equivalent to ACω. For other statements equivalent to ACω, see (Herrlich 1997) and (Howard/Rubin 1998).
ACω is a weak form of the axiom of choice (AC). AC states that every collection of non-empty 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 (and DC is strictly weaker than AC).
Axiom
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 delimit the realm of analysis. In other words, an axiom is a logical statement that is assumed to be true...
of set theory, similar to the axiom of choice. It states that any countable collection of non-empty sets must have a choice function. Spelled out, this means that if A is a function
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
with domain
Domain (mathematics)
In mathematics, the domain of definition or simply the domain of a function is the set of "input" or argument values for which the function is defined...
N (where N denotes the set of natural number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s) and A(n) is a non-empty 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
Paul Cohen (mathematician)
Paul Joseph Cohen was an American mathematician best known for his proof of the independence of the continuum hypothesis and the axiom of choice from Zermelo–Fraenkel set theory, the most widely accepted axiomatization of set theory.-Early years:Cohen was born in Long Branch, New Jersey, into a...
showed that ACω is not provable in Zermelo-Fraenkel 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 Dedekind-infinite
Dedekind-infinite set
In mathematics, a set A is Dedekind-infinite if some proper subset B of A is equinumerous to A. Explicitly, this means that there is a bijective function from A onto some proper subset B of A. A set is Dedekind-finite if it is not Dedekind-infinite.A vaguely related notion is that of a...
(equivalently: has a countably infinite subset).
ACω is particularly useful for the development of analysis
Mathematical analysis
Mathematical analysis, which mathematicians refer to simply as analysis, has its beginnings in the rigorous formulation of infinitesimal calculus. It is a branch of pure mathematics that includes the theories of differentiation, integration and measure, limits, infinite series, and analytic functions...
, where many results depend on having a choice function for a countable collection of sets of real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s. For instance, in order to prove that every accumulation point of a set S⊆R is the limit
Limit (mathematics)
In mathematics, the concept of a "limit" is used to describe the value that a function or sequence "approaches" as the input or index approaches some value. The concept of limit allows mathematicians to define a new point from a Cauchy sequence of previously defined points within a complete metric...
of some sequence
Sequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the 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 space
Metric space
In mathematics, a metric space is a set where a notion of distance between elements of the set is defined.The metric space which most closely corresponds to our intuitive understanding of space is the 3-dimensional Euclidean space...
s, the statement becomes equivalent to ACω. For other statements equivalent to ACω, see (Herrlich 1997) and (Howard/Rubin 1998).
ACω is a weak form of the axiom of choice (AC). AC states that every collection of non-empty sets must have a choice function. AC clearly implies the axiom of dependent choice
Axiom of dependent choice
In mathematics, the axiom of dependent choices, denoted DC, is a weak form of the axiom of choice which is still sufficient to develop most of real analysis...
(DC), and DC is sufficient to show ACω. However ACω is strictly weaker than DC (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 Dedekind-infinite:- Let X be infinite. For each natural number n, let An be the set of all 2n-element subsets of X. Since X is infinite, each An is nonempty. A first application of ACω yields a sequence (Bn : n=0,1,2,3,...) where each Bn is a subset of X with 2n elements.
- The sets Bn are not necessarily disjoint, but we can define
- C0 = B0
- Cn= the difference of Bn and the union of all Cj, j<n.
- Clearly each set Cn has at least 1 and at most 2n elements, and the sets Cn are pairwise disjoint. A second application of ACω yields a sequence (cn: n=0,1,2,...) with cn∈Cn.
- So all the cn are distinct, and X contains a countable set. The function that maps each cn to cn+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.