Axiom of countable choice
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-empty sets must have a choice function. That is, given a function with domain (where denotes the set of natural numbers) such that is a non-empty set for every , there exists a function with domain such that for every .
Overview
The axiom of countable choice (ACω) 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 ACω is not provable in Zermelo–Fraenkel set theory (ZF) without the axiom of choice (Potter 2004). ACω holds in the Solovay model.
ZF+ACω suffices to prove that the union of countably many countable sets is countable. The converse statement "assuming ZF, 'every countable union of countable sets is countable' implies ACω" does not hold, as witnessed by Cohen's First Model.[1] ZF+ACω 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 point of a set is the limit of some sequence of elements of , 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. For example, has a choice function, where is the set of hereditarily finite sets, i.e. the first set in the Von Neumann universe of non-finite rank. The choice function is (trivially) the least element in the well-ordering. Another example is 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:
References
- ^ Herrlich, Horst (2006). "Section A.4". Axiom of Choice. Lecture Notes in Mathematics. Vol. 1876. Springer. doi:10.1007/11601562. ISBN 3-540-30989-6. Retrieved 18 July 2023.
- Jech, 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.