Foundation Primitive Recognition Calculus Grow Forced Trichotomy Forced Order De

A decidable order

In mathematics, a relation is decidable when a mechanical procedure can always determine, in finite time, whether it holds. For the natural numbers, deciding whether one number is less than another is a finite computation: you count upward from zero and see which one you reach first. The declaration forced_order_decidable establishes the same property for the framework's primitive ledger, a discrete record of recognition events. It shows that the structural order on the framework's forced positions, the objects called DistinctionNat, is decidable without appealing to any principle of omniscience.

The proof is constructive: the order relation itself is defined by a structural recursion on the two positions, and that recursion is the decision procedure. The theorem leq_total_bool proves that for any two positions, one is structurally below the other or vice versa. The companion theorem leq_trichotomy_bool proves a strict trichotomy: exactly one of strictly-below, balanced, or strictly-above holds. Both are proved by induction on the structure of the positions, using only case splits on decidable Booleans. The machine-checked library of formal theorems records that the axiom audit for these results is empty: no choice principle, no classical logic instance, no appeal to the integers.

This matters because the real-number analogue of trichotomy is famously non-constructive. Deciding whether one real number is less than another, equal to it, or greater than it is equivalent to the limited principle of omniscience, a non-constructive axiom. The framework's forced order avoids that entirely. Its carrier is a discrete structure, not a continuum, so comparison is a finite computation. The declaration forced_order_decidable is the formal witness: it packages the decidable instance so that any later theorem can use it directly.

What the declaration does not claim is broader. It does not claim that the framework's order is the usual order on natural numbers, nor that it embeds into the integers. The library deliberately keeps the structural order separate from any numeric display. It does not claim that the real-number trichotomy becomes constructive; it only shows that the forced discrete carrier has a decidable order. And it does not claim that every relation in the framework is decidable. The declaration is a local fact about one specific order on one specific carrier.

/-- The forced order relation is decidable WITHOUT `Classical`: the structural
`Bool` recursion `leq` is itself the decision procedure. Deciding `<` on the
forced carrier is a finite computation, not an act of omniscience. -/
def forced_order_decidable (a b : DistinctionNat) : Decidable (leq a b = true) :=
  inferInstance

/-- The forced structural order on `DistinctionNat` is total: for any two forced
orbit positions, one is structurally below the other. Proved by induction on the
carrier; no `omega`, no `ℤ`, no classical instance. `#print axioms` is empty. -/
theorem leq_total_bool (a b : DistinctionNat) :
    leq a b = true ∨ leq b a = true := by
  induction a generalizing b with
  | zero => exact Or.inl rfl
  | succ a ih =>
      cases b with
      | zero => exact Or.inr rfl
      | succ b =>
          have := ih b
          unfold leq
          simpa using this

/-- Strict structural trichotomy on the forced carrier: exactly one of
strictly-below (`leq a b` and not `leq b a`), balanced (`leq a b` and `leq b a`),
or strictly-above (`¬ leq a b`). Pure case split on two decidable Booleans;
`#print axioms` is empty. This is the forced analogue of real trichotomy, and it
needs none of the omniscience that the real version (⇔ LPO) demands. -/
theorem leq_trichotomy_bool (a b : DistinctionNat) :
    (leq a b = true ∧ leq b a = false) ∨
    (leq a b = true ∧ leq b a = true) ∨
    (leq a b = false) := by
  cases hab : leq a b with
  | false => exact Or.inr (Or.inr rfl)
  | true =>
      cases hba : leq b a with
      | false => exact Or.inl ⟨rfl, rfl⟩
      | true => exact Or.inr (Or.inl ⟨rfl, rfl⟩)

What this page does not claim

The declaration does not prove that the real-number trichotomy is constructive. It does not claim that the forced order embeds into the integers or matches the usual natural-number order. It does not establish that every relation in the framework is decidable.

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/Grow/ForcedTrichotomy.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: