Foundation Primitive Recognition Calculus Omniscience Lpo Imp Markov

The omniscience ladder

In constructive mathematics, a binary sequence is an infinite list of yes-or-no answers, and the Limited Principle of Omniscience (LPO) asks a stark question: for any such sequence, can you always say either it is all no, or it has a yes somewhere? In classical mathematics the answer is trivially yes, because every statement is either true or false. In constructive mathematics, where proofs must build their conclusions, LPO is unprovable: it would let you decide an infinite search in finite time. This is the omniscience content of the real-number trichotomy, the claim that every real number is less than, equal to, or greater than zero.

Markov's Principle is a weaker and more practical request. It says: if you know a binary sequence is not all no, then a search for a yes will eventually succeed. This is the constructive principle of an unbounded search that is known to terminate. The theorem lpo_imp_markov in the framework's machine-checked library of formal theorems proves the obvious direction: if you have full omniscience, you can find the yes directly, so the known-to-halt search is subsumed. The proof is choice-free, meaning it does not rely on the axiom of choice, and it is only a few lines long.

The interesting content is in the reverse direction. The library also proves that LPO is exactly equivalent to the conjunction of two weaker principles: the Weak Limited Principle of Omniscience (WLPO), which decides whether a sequence is all no, and Markov's Principle, which finds the yes. This pins LPO precisely between the two: WLPO gives you the global bit, Markov gives you the terminating search, and together they recover full omniscience. The proof is again choice-free.

In Recognition Science, this ladder of omniscience principles is part of the primitive recognition calculus, the formal groundwork for how the framework handles infinite searches and decidability. The declaration lpo_imp_markov does not claim that LPO or Markov's Principle holds in the framework's logic; it only proves the implication between them. It does not claim that the search always terminates, only that if it is known to succeed, it does. It does not claim that WLPO alone implies LPO, which is false without Markov.

/-- `LPO ⇒ Markov`: full omniscience subsumes the known-to-halt search. Choice-free. -/
theorem lpo_imp_markov (h : LPO) : MarkovPrinciple := by
  intro α hne
  rcases h α with hall | hex
  · exact absurd hall hne
  · exact hex

/-- `LPO ⇒ Markov`: full omniscience subsumes the known-to-halt search. Choice-free. -/
theorem lpo_imp_markov (h : LPO) : MarkovPrinciple := by
  intro α hne
  rcases h α with hall | hex
  · exact absurd hall hne
  · exact hex

/-- **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⟩

What this page does not claim

LPO or Markov's Principle are asserted to hold in the framework's logic. The search in Markov's Principle always terminates, only that it does when known to succeed. WLPO alone implies LPO.

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: