The axiom of countable choice or axiom of denumerable choice, denoted AC
ω, is an
axiom
An axiom, postulate, or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Ancient Greek word (), meaning 'that which is thought worthy or ...
of
set theory
Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concern ...
that states that every
countable
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers ...
collection of
non-empty sets must have a
choice function
A choice function (selector, selection) is a mathematical function ''f'' that is defined on some collection ''X'' of nonempty sets and assigns some element of each set ''S'' in that collection to ''S'' by ''f''(''S''); ''f''(''S'') maps ''S'' to ...
. That is, given a
function ''A'' with
domain
Domain may refer to:
Mathematics
*Domain of a function, the set of input values for which the (total) function is defined
** Domain of definition of a partial function
** Natural domain of a partial function
**Domain of holomorphy of a function
* ...
N (where N denotes the set of
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called '' cardinal ...
s) 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 In mathematics, the axiom of dependent choice, denoted by \mathsf , is a weak form of the axiom of choice ( \mathsf ) that is still sufficient to develop most of real analysis. It was introduced by Paul Bernays in a 1942 article that explores wh ...
(DC), which in turn is weaker than the
axiom of choice
In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...
(AC).
Paul Cohen
Paul Joseph Cohen (April 2, 1934 – March 23, 2007) was an American mathematician. He is best known for his proofs that the continuum hypothesis and the axiom of choice are independent from Zermelo–Fraenkel set theory, for which he was award ...
showed that AC
ω is not provable in
Zermelo–Fraenkel set theory
In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such ...
(ZF) without the axiom of choice . 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
In set theory, an infinite set is a set that is not a finite set. Infinite sets may be countable or uncountable.
Properties
The set of natural numbers (whose existence is postulated by the axiom of infinity) is infinite. It is the only s ...
is
Dedekind-infinite
In mathematics, a set ''A'' is Dedekind-infinite (named after the German mathematician Richard Dedekind) if some proper subset ''B'' of ''A'' is equinumerous to ''A''. Explicitly, this means that there exists a bijective function from ''A'' onto ...
(equivalently: has a countably infinite subset).
AC
ω is particularly useful for the development of
analysis
Analysis ( : analyses) is the process of breaking a complex topic or substance into smaller parts in order to gain a better understanding of it. The technique has been applied in the study of mathematics and logic since before Aristotle (3 ...
, where many results depend on having a choice function for a countable collection of sets of
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
s. For instance, in order to prove that every
accumulation point
In mathematics, a limit point, accumulation point, or cluster point of a set S in a topological space X is a point x that can be "approximated" by points of S in the sense that every neighbourhood of x with respect to the topology on X also contai ...
''x'' of a set ''S'' ⊆ R is the
limit
Limit or Limits may refer to:
Arts and media
* ''Limit'' (manga), a manga by Keiko Suenobu
* ''Limit'' (film), a South Korean film
* Limit (music), a way to characterize harmony
* "Limit" (song), a 2016 single by Luna Sea
* "Limits", a 2019 ...
of some
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is called ...
of elements of ''S'' \ , one needs (a weak form of) the axiom of countable choice. When formulated for accumulation points of arbitrary
metric space
In mathematics, a metric space is a set together with a notion of '' distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general setti ...
s, the statement becomes equivalent to AC
ω. For other statements equivalent to AC
ω, see and .
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 interval
In mathematics, a (real) interval is a set of real numbers that contains all real numbers lying between any two numbers of the set. For example, the set of numbers satisfying is an interval which contains , , and all numbers in between. Other ...
s 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
*
*
*
*
{{DEFAULTSORT:Axiom Of Countable Choice
Axiom of choice