# 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).

## 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. (Recall that a section is a right inverse). In fact, there may be many such sections: having the freedom to choose among them is why this is called “choice”.

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$).

### $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.

### 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 every Dedekind real number is a Cauchy real number (the converse is always true); more generally, $WCC$ is enough to justify sequential reasoning in analysis. See Bridges et al (1998).

## References

• Douglas Bridges, Fred Richman, and Peter Schuster (1998). A weak countable choice principle. Available from Fred Richman’s Documents.

Revised on December 9, 2013 11:31:07 by Anonymous Coward (66.108.247.12)