nLab
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\times 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^{*}(m)$ and $p^{*}(n)$ 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.

category: foundational axiom