Foundation Primitive Recognition Calculus Omniscience Wlpo And Markov Imp Lpo

The exact location of LPO

The Limited Principle of Omniscience, or LPO, is a statement about infinite binary sequences: for every sequence of true and false values, either every entry is false, or at least one entry is true. In classical mathematics this is a trivial consequence of the law of excluded middle. In constructive mathematics, where proofs must exhibit witnesses, it is unprovable: there is no general method to decide, for an arbitrary infinite sequence, whether a true entry exists. LPO is the omniscience content of the trichotomy law for real numbers, the statement that every real number is positive, negative, or zero.

Two weaker principles sit nearby. The Weak Limited Principle of Omniscience, WLPO, asks only whether a sequence is identically false or not; it does not demand a witness for a true entry. Markov's Principle asserts that if a sequence is not identically false, then it is true somewhere: it licenses an unbounded search that is known to succeed. Each is strictly weaker than LPO. The framework's machine-checked library of formal theorems proves the exact relationship: LPO holds if and only if both WLPO and Markov's Principle hold. The forward direction is immediate, since full omniscience subsumes both weaker statements. The reverse direction, the declaration wlpo_and_markov_imp_lpo, is the substantive result: deciding whether a sequence is identically false, plus a search that is known to terminate, together recover the full ability to find a true entry.

The proof is choice-free, meaning it does not rely on the axiom of choice. It works by taking the WLPO decision on a sequence: if the sequence is identically false, that settles the LPO disjunction; otherwise, the negation gives exactly the hypothesis Markov's Principle needs to produce the true entry. The two coordinates are the global bit, whether the sequence is everywhere false, and the terminating search, which locates the first true entry once it is known to exist. Full omniscience is precisely their conjunction.

This result pins down the logical relations among omniscience principles without assuming any of them. It does not prove LPO, WLPO, or Markov's Principle; it proves an equivalence among them. The framework does not claim that these principles hold in the constructive setting, only that their relative strength is exactly as stated. The theorem also does not touch the related Lesser Limited Principle of Omniscience, LLPO, which concerns sequences with at most one true entry and is strictly weaker than LPO.

/-- **The exact location of LPO**: `LPO ⇔ WLPO ∧ Markov`. The two coordinates
are the global bit (WLPO) and the terminating search (Markov); full omniscience
is exactly their conjunction. Choice-free. -/
theorem lpo_iff_wlpo_and_markov : LPO ↔ (WLPO ∧ MarkovPrinciple) :=
  ⟨fun h => ⟨lpo_imp_wlpo h, lpo_imp_markov h⟩,
   fun ⟨hw, hm⟩ => wlpo_and_markov_imp_lpo hw hm⟩

/-- `WLPO ∧ Markov ⇒ LPO`: deciding the Π⁰₁ statement, plus the known-to-halt search,
recovers full omniscience. Choice-free. This pins `LPO` exactly between the two
weaker principles. -/
theorem wlpo_and_markov_imp_lpo (hw : WLPO) (hm : MarkovPrinciple) : LPO := by
  intro α
  rcases hw α with hall | hne
  · exact Or.inl hall
  · exact Or.inr (hm α hne)

/-- `WLPO ∧ Markov ⇒ LPO`: deciding the Π⁰₁ statement, plus the known-to-halt search,
recovers full omniscience. Choice-free. This pins `LPO` exactly between the two
weaker principles. -/
theorem wlpo_and_markov_imp_lpo (hw : WLPO) (hm : MarkovPrinciple) : LPO := by
  intro α
  rcases hw α with hall | hne
  · exact Or.inl hall
  · exact Or.inr (hm α hne)

What this page does not claim

The theorem does not prove LPO, WLPO, or Markov's Principle; it proves an equivalence among them. The theorem does not address LLPO or any other omniscience principle beyond the three named. The theorem does not claim that any of these principles hold constructively, only that their relative strength is as stated.

Verify this page

Every tagged claim above names its theorem. To check one yourself rather than trust this page, elaborate the source module with Lean 4 and audit its axiom basis:

$ lake env lean IndisputableMonolith/Foundation/PrimitiveRecognitionCalculus/Omniscience.lean
expected axiom basis: [propext, Classical.choice, Quot.sound] (the Lean kernel's standard three; no RS-specific axioms)

A page whose claims cannot be reproduced this way does not ship. In production, every anchor links to the exact declaration in the public source release, and this block carries the build receipt for the page itself.

Derived articles

This page is generated by a question-recursion engine: the questions its answers raise become the next pages. The current agenda, with open targets marked red: