Limited principle of omniscience

In constructive mathematics, the limited principle of omniscience (LPO) and the lesser limited principle of omniscience (LLPO) are axioms that are nonconstructive but are weaker than the full law of the excluded middle. They are used to gauge the amount of nonconstructivity required for an argument, as in constructive reverse mathematics. These principles are also related to weak counterexamples in the sense of Brouwer.

Definitions

The limited principle of omniscience states (Bridges & Richman 1987, p. 3):

LPO: For any sequence , , ... such that each is either or , the following holds: either for all , or there is a with . [1]

The second disjunct can be expressed as and is constructively stronger than the negation of the first, . The weak schema in which the former is replaced with the latter is called WLPO and represents particular instances of excluded middle.[2]

The lesser limited principle of omniscience states:

LLPO: For any sequence , , ... such that each is either or , and such that at most one is nonzero, the following holds: either for all , or for all .

Here and are entries with even and odd index respectively.

It can be proved constructively that the law of the excluded middle implies LPO, and LPO implies LLPO. However, none of these implications can be reversed in typical systems of constructive mathematics.

Terminology

The term "omniscience" comes from a thought experiment regarding how a mathematician might tell which of the two cases in the conclusion of LPO holds for a given sequence . Answering the question "is there a with ?" negatively, assuming the answer is negative, seems to require surveying the entire sequence. Because this would require the examination of infinitely many terms, the axiom stating it is possible to make this determination was dubbed an "omniscience principle" by Bishop (1967).

Variants

Logical versions

The two principles can be expressed as purely logical principles, by casting it in terms of decidable predicates on the naturals. I.e. for which does hold.

The lesser principle corresponds to a predicate version of that De Morgan's law that does not hold intuitionistically, i.e. the distributivity of negation of a conjunction.

Analytic versions

Both principles have analogous properties in the theory of real numbers. The analytic LPO states that every real number satisfies the trichotomy or or . The analytic LLPO states that every real number satisfies the dichotomy or , while the analytic Markov's principle states that if is false, then .

All three analytic principles if assumed to hold for the Dedekind or Cauchy real numbers imply their arithmetic versions, while the converse is true if we assume (weak) countable choice, as shown in Bishop (1967).

See also

References

  1. Mines, Ray (1988). A course in constructive algebra. Richman, Fred and Ruitenburg, Wim. New York: Springer-Verlag. pp. 4–5. ISBN 0387966404. OCLC 16832703.
  2. Diener, Hannes (2020). "Constructive Reverse Mathematics". arXiv:1804.05495 [math.LO].
  • Bishop, Errett (1967). Foundations of Constructive Analysis. ISBN 4-87187-714-0.
  • Bridges, Douglas; Richman, Fred (1987). Varieties of Constructive Mathematics. ISBN 0-521-31802-5.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.