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-emptysets must have a choice function. That is, given a functionA with domainN (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.
Each set in the countablesequence of sets (Si) = S1, S2, S3, ... contains a non-zero, and possibly infinite (or even uncountably infinite), number of elements. The axiom of countable choice allows us to arbitrarily select a single element from each set, forming a corresponding sequence of elements (xi) = x1, x2, x3, ...
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 pointx 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 An be the set of all 2n-element subsets of X. Since X is infinite, each An is non-empty. The 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 between 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. The 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.
axiom, countable, choice, axiom, countable, choice, axiom, denumerable, choice, denoted, acω, axiom, theory, that, states, that, every, countable, collection, empty, sets, must, have, choice, function, that, given, function, with, domain, where, denotes, natur. The axiom of countable choice or axiom of denumerable choice denoted ACw 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 Each set in the countable sequence of sets Si S1 S2 S3 contains a non zero and possibly infinite or even uncountably infinite number of elements The axiom of countable choice allows us to arbitrarily select a single element from each set forming a corresponding sequence of elements xi x1 x2 x3 Overview EditThe axiom of countable choice ACw 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 ACw is not provable in Zermelo Fraenkel set theory ZF without the axiom of choice Potter 2004 ACw holds in the Solovay model ZF ACw 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 ACw 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 ACw For other statements equivalent to ACw see Herrlich 1997 and Howard amp 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 Vw O and the set of proper and bounded open intervals of real numbers with rational endpoints Use EditAs an example of an application of ACw here is a proof from ZF ACw 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 non empty The first application of ACw 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 defineC0 B0 Cn the difference between Bn and the union of all Cj j lt n dd Clearly each set Cn has at least 1 and at most 2n elements and the sets Cn are pairwise disjoint The second application of ACw 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 References EditJech 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 Retrieved from https en wikipedia org w index php title Axiom of countable choice amp oldid 1107793567, wikipedia, wiki, book, books, library,
