# nLab countable choice

foundations

## Foundational axioms

foundational axiom

# Countable choice

## Idea

The axiom of countable choice ($\mathrm{CC}$), also called ${\mathrm{AC}}_{\omega }$ or ${\mathrm{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:X\to 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 $N$ to any other set contains (in the 2-poset Rel) a functional entire relation.

## Variations

### $\mathrm{COSHEP}$ & $\mathrm{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 $\mathrm{COSHEP}$, is the axiom of dependent choice ($\mathrm{DC}$).

### ${\mathrm{AC}}_{00}$

Sometimes in foundations it is useful to consider a weaker version of countable choice, called ${\mathrm{AC}}_{00}$. This states that any entire relation from $N$ to itself contains a functional entire relation. In terms of surjections, this states that any surjection $p:X\to N$ has a section if $X$ is a subset of $N×N$ and $p$ is the restriction to $X$ of a product projection.

### Weak countable choice

The axiom of weak countable choice ($\mathrm{WCC}$) states that a surjection $p:X\to N$ has a section if, whenever $m\ne n$, at least one of the preimages ${p}^{*}\left(m\right)$ and ${p}^{*}\left(n\right)$ is a singleton. $\mathrm{WCC}$ follows (for different reasons) from either $\mathrm{CC}$ or excluded middle. On the other hand, $\mathrm{WCC}$ is enough to prove that every Dedekind real number is a Cauchy real number (the converse is always true); more generally, $\mathrm{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 September 5, 2011 15:20:34 by Toby Bartels (75.88.82.16)