Axiom of non-choice

From HandWiki
Short description: Axiom of set theory

In constructive set theory, the axiom of non-choice[1] is a version of the axiom of choice limiting the choice to just one.

Formal statement

If for each element [math]\displaystyle{ x }[/math] of set [math]\displaystyle{ A }[/math] there is exactly one [math]\displaystyle{ y }[/math] such that a property holds, then there exists a function [math]\displaystyle{ f }[/math] with domain [math]\displaystyle{ A }[/math] that maps each element [math]\displaystyle{ x }[/math] of [math]\displaystyle{ A }[/math] to an element [math]\displaystyle{ f(x) }[/math] such that the given property holds. Formally, the axiom can be stated as follows:

[math]\displaystyle{ \forall x \in A \; \exists! y \; \psi(x,y) \; \to \; \exists f \; (\operatorname{Function}(f) \and \operatorname{Domain}(f)=A \text{ and } \forall x \in A \; \psi(x,f(x))) }[/math]

Discussion

In ZF (classical Zermelo–Fraenkel set theory without the axiom of choice), this is a theorem derivable from the axiom of replacement.

In intuitionistic Zermelo–Fraenkel set theory, IZF, this statement is derivable from other axioms, since functions are defined as graphs in IZF. In this case [math]\displaystyle{ f }[/math] can be defined as[math]\displaystyle{ f = \{ (x,y) \mid \psi(x,y) \} }[/math] and it follows from the definition that it is actually a function.

The difference from the regular axiom of choice is that the choice of [math]\displaystyle{ y }[/math] is unique for each [math]\displaystyle{ x }[/math].

References

  1. Myhill, John. "Constructive Set Theory." The Journal of Symbolic Logic 40, no. 3 (1975): 347-82. Accessed May 21, 2021. doi:10.2307/2272159.

External links

  • Michael J. Beeson, Foundations of Constructive Mathematics, Springer, 1985