nLab
countable choice

Countable choice

Idea

The axiom of countable choice (CCCC), also called AC ωAC_\omega or AC NAC_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 XX be any set and let p:XNp\colon X \to \mathbf{N} be a surjection. Then the axiom of countable choice states that pp 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\mathbf{N} to any other set contains (in the 2-poset Rel) a functional entire relation.

Variations

COSHEPCOSHEP & DCDC

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 COSHEPCOSHEP, is the axiom of dependent choice (DCDC). In general, DCDC is enough to justify results in analysis involving sequences.

AC 00AC_{00}

Sometimes in foundations it is useful to consider a weaker version of countable choice, called AC 00AC_{00}. This states that any entire relation from N\mathbf{N} to itself contains a functional entire relation. In terms of surjections, this states that any surjection p:XNp\colon X \to \mathbf{N} has a section if XX is a subset of N×N\mathbf{N} \times \mathbf{N} and pp is the restriction to XX of a product projection. AC 00AC_{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 (WCCWCC) states that a surjection p:XNp\colon X \to \mathbf{N} has a section if, whenever mnm \neq n, at least one of the preimages p *(m)p^*(m) and p *(n)p^*(n) is a singleton. WCCWCC follows (for different reasons) from either CCCC or excluded middle. On the other hand, WCCWCC 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)