HOME

TheInfoList




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 truth, true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Greek ''axíōma'' () 'that which is thought worthy or fit' o ...

axiom
of
set theory Set theory is the branch of mathematical logic that studies Set (mathematics), 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, i ...
that states that every
countable In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...
collection of
non-empty #REDIRECT Empty set #REDIRECT Empty set #REDIRECT Empty set#REDIRECT Empty set In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algeb ...

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 to each set ''S'' in that collection some element ''f''(''S'') of ''S''. In other words, ''f'' is a ...
. That is, given a
function Function or functionality may refer to: Computing * Function key A function key is a key on a computer A computer is a machine that can be programmed to carry out sequences of arithmetic or logical operations automatically. Modern comp ...
''A'' with
domain Domain may refer to: Mathematics *Domain of a function In mathematics, the domain of a Function (mathematics), function is the Set (mathematics), set of inputs accepted by the function. It is sometimes denoted by \operatorname(f), where is th ...
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 total order, ordering (as in "this is the ''third'' largest city in the country"). In common mathematical terminology, w ...
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 choiceIn mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ha ...
(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#Infinite Cartesian products, Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the a ...

axiom of choice
(AC).
Paul Cohen Paul Joseph Cohen (April 2, 1934 – March 23, 2007) was an American mathematician A mathematician is someone who uses an extensive knowledge of mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ...
showed that ACω, is not provable in
Zermelo–Fraenkel set theory In set theory illustrating the intersection of two sets 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 ...
(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 illustrating the intersection (set theory), intersection of two set (mathematics), sets. Set theory is a branch of mathematical logic that studies Set (mathematics), sets, which informally are collections of objects. Although any ...
is Dedekind-infinite (equivalently: has a countably infinite subset). ACω is particularly useful for the development of
analysis Analysis is the process of breaking a complex topic or substance Substance may refer to: * Substance (Jainism), a term in Jain ontology to denote the base or owner of attributes * Chemical substance, a material with a definite chemical composit ...
, where many results depend on having a choice function for a countable collection of sets of
real number In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no g ...
s. For instance, in order to prove that every
accumulation point In mathematics, a limit point (or cluster point or accumulation point) of a Set (mathematics), 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 (mathematics), neighbourhood ...
''x'' of a set ''S'' ⊆ R is the
limit Limit or Limits may refer to: Arts and media * Limit (music), a way to characterize harmony * Limit (song), "Limit" (song), a 2016 single by Luna Sea * Limits (Paenda song), "Limits" (Paenda song), 2019 song that represented Austria in the Eurov ...
of some
sequence In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...

sequence
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 Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...
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 Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ge ...
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