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 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. The axiom of countable choice (ACω) is strictly weaker than the axiom of dependent choice (DC), 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 . 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. 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 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 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.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (54)

Related people (9)

Related units (8)

Related concepts (16)

Related courses (9)

Related lectures (42)

Lie groups in the symmetric group: Reducing Ulam's problem to the simple case

Nicolas Monod

Ulam asked whether all Lie groups can be represented faithfully on a countable set. We establish a reduction of Ulam's problem to the case of simple Lie groups. In particular, we solve the problem for all solvable Lie groups and more generally Lie groups w ...

San Diego2023

Representing location choice within activity-based models

Michel Bierlaire, Timothy Michael Hillel, Janody Pougala, Nicolas Jean Salvadé

Since the 70s, there has been a growing interest in activity-based modelling. This approach models the need to travel as a result of performing daily activities (Bowman and Ben-Akiva, 2001). Nevertheless, the activities need to be scheduled which involves ...

2022

Biocompatible Chitosan-Based Hydrogels for Bioabsorbable Wound Dressings

Maria-Alexandra Paun

Supramolecular hydrogels based on chitosan and monoaldehydes are biomaterials with high potential for a multitude of bioapplications. This is due to the proper choice of the monoaldehyde that can tune the hydrogel properties for specific practices. In this ...

MDPI2022

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 pairs of values can have arbitrarily small differences. Every real number can be almost uniquely represented by an infinite decimal expansion. The real numbers are fundamental in calculus (and more generally in all mathematics), in particular by their role in the classical definitions of limits, continuity and derivatives.

Dedekind-infinite set

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 some proper subset B of A. A set is Dedekind-finite if it is not Dedekind-infinite (i.e., no such bijection exists). Proposed by Dedekind in 1888, Dedekind-infiniteness was the first definition of "infinite" that did not rely on the definition of the natural numbers.

Axiom of dependent choice

In mathematics, the axiom of dependent choice, denoted by , is a weak form of the axiom of choice () that is still sufficient to develop most of real analysis. It was introduced by Paul Bernays in a 1942 article that explores which set-theoretic axioms are needed to develop analysis. A homogeneous relation on is called a total relation if for every there exists some such that is true. The axiom of dependent choice can be stated as follows: For every nonempty set and every total relation on there exists a sequence in such that for all In fact, x0 may be taken to be any desired element of X.

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics a

PHYS-460: Nonlinear dynamics, chaos and complex systems

The course provides students with the tools to approach the study of nonlinear systems and chaotic dynamics. Emphasis is given to concrete examples and numerical applications are carried out during th

MATH-432: Probability theory

The course is based on Durrett's text book Probability: Theory and Examples.
It takes the measure theory approach to probability theory, wherein expectations are simply abstract integrals.

Relations, Sequences, Summation CS-101: Advanced information, computation, communication I

Covers arithmetic progressions, lattices, formal verification, strings, explicit formulas, recurrence relations, closed formulas, and Cantor's Diagonal Argument.

Fixed points of the Ruelle-Thurston operator

Covers the fixed points of the Ruelle-Thurston operator and its applications in complex analysis.

Cantor's Diagonal Argument CS-101: Advanced information, computation, communication I

Explores Cantor's Diagonal Argument and the concept of uncountability through binary digit sequences.