nLab axiom of multiple choice

The axiom of multiple choice

Context

Foundations

foundations

The basis of it all

 Set theory

set theory

Foundational axioms

foundational axioms

Removing axioms

The axiom of multiple choice

This article is about an axiom of constructive mathematics. Some set theory literature instead uses this name for an unrelated weakening of AC. For that notion, see (classical) axiom of multiple choice.

Idea

The axiom of multiple choice (AMC) is a weaker version of the axiom of choice, which can hold in constructive mathematics.

Statement

A set-indexed family {D c} cC\{D_c\}_{c\in C} of sets is said to be a collection family if for any cCc\in C and any surjection ED cE\twoheadrightarrow D_c, there exists a cCc'\in C and a surjection D cD cD_{c'}\twoheadrightarrow D_c which factors through EE.

Depending on the author, the axiom of multiple choice is one of the following statements:

  1. for every set XX, there exists a collection family {D c} cC\{D_c\}_{c\in C} such that XD cX\cong D_c for some cc (Michael Rathjen‘s formulation, attributed to Peter Aczel and Alex Simpson), or

  2. for every set XX, there exists a collection family {D c} cC\{D_c\}_{c\in C}, with CC inhabited, and a family of surjections {D cX} cC\{D_c \to X\}_{c\in C} (the formulation originally given by Ieke Moerdijk and Erik Palmgren), or

  3. for every set XX, the full subcategory (Set/X) surj(Set/X)_{surj} of the slice category Set/XSet/X consisting of the surjections has a weakly initial set (in Benno van den Berg‘s formulation; this is also called WISC).

The nLab uses the initialization AMC to cover either the first two formulations.

The third is a weaker condition, and while some may refer to as a “weak axiom of multiple choice”, van den Berg obviously does not; he calls his the AMC and the Moerdijk-Palmgren formulation rather the “strong axiom of multiple choice”.

Relationships to other axioms

  • Note that PP is a projective set if and only if the singleton family {P}\{P\} is a collection family. Therefore, since AC is equivalent to “all sets are projective,” it implies AMC.

  • An extension of this argument shows that COSHEP is sufficient to imply AMC.

  • The Reflection Principle? (RP) is equivalent to AMC (the one called strong AMC by van den Berg). RP is motivated by the regular extension axiom (REA) from constructive set theory. RP states that every map belongs to a representable class of small maps.

  • However, AMC does not imply countable choice or any of the other usual consequences of AC.

  • Rathjen proves that SVC also implies AMC. It follows that AMC holds in “most” models of set theory.

  • AMC implies WISC, and therefore also implies that the category of anafunctors between two small categories is essentially small. Thus WISC may be termed “weak axiom of multiple choice”.

  • A ΠW-pretopos satisfying the (weak) axiom of multiple choice is a predicative topos, or removing the word “weak”, we may speak of a strong predicative topos.

References

  • Ieke Moerdijk, Erik Palmgren, Type theories, toposes and constructive set theory: predicative aspects of AST (2000) (web)

  • Rathjen, “Choice principles in constructive and classical set theories”

In

WISC is called the “axiom of multiple choice”.

  • Jech, The Axiom of Choice (1973), ISBN : 0444104844 (New York)

Last revised on December 31, 2022 at 19:46:30. See the history of this page for a list of all contributions to it.