Limited Principle of Omniscience

Idea

The Limited Principle of Omniscience (LPO) is a logical principle primarily discussed in constructive mathematics and type theory. It represents a specific, restricted version of the law of excluded middle ($LEM$) applied to infinite sequences.

Definition

For any sequence of bits $f:\mathbb{N}\to 2$, $LPO$ asserts the following disjunction: $(\exists n\in \mathbb{N}.f(n)=1)\vee (\forall n\in \mathbb{N}.f(n)=0)$

In computational terms, $LPO$ claims that it is always possible to determine, in a finite amount of time, whether an infinite sequence contains at least one $1$ or consists entirely of $0$s.

Constructive Context

In classical mathematics, $LPO$ is a trivial theorem. However, in constructive logic (such as intuinistic logic or the internal logic of a topos), $LPO$ is generally not accepted as an axiom because it lacks a computational procedure.

• To prove the left side $(\exists n)$, one must produce a specific index $n$.
• To prove the right side $(\forall n)$, one must provide a proof that no such $n$ exists.

Since an algorithm cannot inspect an infinite sequence in finite time, $LPO$ is considered non-constructive.

Mathematical Equivalences

$LPO$ is equivalent to several other significant statements in analysis and logic:

1. Equality for reals: For any real number $x$, $(x=0)\vee (x\ne 0)$.
2. the halting problem: The existence of a general decision procedure for whether a Turing machine halts.

Varieties of Omniscience

$LPO$ is part of a hierarchy of principles with varying degrees of “non-constructivity”:

• Lesser Limited Principle of Omniscience (LLPO): Asserts that if a sequence has at most one $1$, we can decide if that $1$ appears at an even or odd index. This is weaker than $LPO$ and is related to the Intermediate Value Theorem.
• Weak Limited Principle of Omniscience (WLPO): Asserts $(\forall n.f(n)=0)\vee \neg (\forall n.f(n)=0)$.

---

References

1. Bridges, D., & Richman, F. (1987). Varieties of Constructive Mathematics. Cambridge University Press.
2. Troelstra, A. S., & van Dalen, D. (1988). Constructivism in Mathematics: An Introduction. North-Holland.

Would you like me to demonstrate how $LPO$ is used to prove the decidability of equality for real numbers using Cauchy sequences?