# nLab countable choice

foundations

## Foundational axioms

foundational axiom

# Countable choice

## Idea

The axiom of countable choice ($CC$), also called $AC_\omega$ or $AC_N$, is a weak form of the axiom of choice; it says that the set of natural numbers is a projective object in Set. (Recall that the full axiom of choice states that every set is projective.) All the reasoning in this page is constructive.

## Definition

More explicitly, let $X$ be any set and let $p\colon X \to \mathbf{N}$ be a surjection. Then the axiom of countable choice states that $p$ has a section. If you phrase the axiom of choice in terms of entire relations, then countable choice states that any entire relation from $\mathbf{N}$ to any other set contains (in the 2-poset Rel) a functional entire relation.

## Variations

### $COSHEP$ & $DC$

Unlike the full axiom of choice, countable choice is often considered to be a constructively acceptable principle. In particular, it does not imply the principle of excluded middle. It is a consequence of COSHEP. A stronger version of countable choice, also a consequence of $COSHEP$, is the axiom of dependent choice ($DC$). In general, $DC$ is enough to justify results in analysis involving sequences.

### $AC_{00}$

Sometimes in foundations it is useful to consider a weaker version of countable choice, called $AC_{00}$. This states that any entire relation from $\mathbf{N}$ to itself contains a functional entire relation. In terms of surjections, this states that any surjection $p\colon X \to \mathbf{N}$ has a section if $X$ is a subset of $\mathbf{N} \times \mathbf{N}$ and $p$ is the restriction to $X$ of a product projection. $AC_{00}$ is enough to prove that every Dedekind real number is a Cauchy real number (the converse is always true).

### Weak countable choice

The axiom of weak countable choice ($WCC$) states that a surjection $p\colon X \to \mathbf{N}$ has a section if, whenever $m \neq n$, at least one of the preimages $p^*(m)$ and $p^*(n)$ is a singleton. $WCC$ follows (for different reasons) from either $CC$ or excluded middle. On the other hand, $WCC$ is enough to prove that the fundamental theorem of algebra in the sense that every non-constant complex polynomial has a root; see Bridges et al (1998).

## References

• Douglas Bridges, Fred Richman, and Peter Schuster (1998). A weak countable choice principle. PDF AMS PDF

Revised on August 2, 2014 07:29:37 by Toby Bartels (98.19.42.133)