Foundation Primitive Recognition Calculus Grow Forced Trichotomy Leq Total Bool

Total order without omniscience

In mathematics, a total order is a relation that can compare any two elements: for any a and b, either a is at most b, or b is at most a. The classical real numbers have this property, but proving it for arbitrary real numbers requires a logical principle called the law of excluded middle, which some constructive mathematicians reject. The Recognition Science framework builds its own discrete number system, called the forced carrier, and its declaration leq_total_bool establishes that this carrier has a total order that is fully constructive: the comparison is a finite computation on structural positions, not an act of omniscience.

The framework's ledger, a discrete record of recognition events, generates positions that can be compared by a structural recursion called leq. The theorem leq_total_bool states that for any two positions a and b, either leq a b is true or leq b a is true. The proof is by induction on the structure of the positions, with no use of classical axioms, no appeal to the natural numbers as an external display, and no dependence on the law of excluded middle. The machine-checked library of formal theorems verifies that the proof's axiom list is empty, meaning it relies only on the ambient type theory's basic rules.

This total order supports a strict trichotomy: for any two positions, exactly one of strictly below, balanced, or strictly above holds. The framework's declaration leq_trichotomy_bool proves this by a pure case split on two decidable Booleans. The order is decidable without Classical: the structural Bool recursion leq itself is the decision procedure, so deciding comparison on the forced carrier is a finite computation. This stands in contrast to the real numbers, where trichotomy is equivalent to the limited principle of omniscience, a non-constructive assumption.

In Recognition Science, this constructive total order is part of the forced structure that emerges from the recognition ledger. The framework models the discrete positions as generated by a growth process, and the total order is a structural fact about that process, not an added assumption. The declaration also proves antisymmetry structurally: if both leq a b and leq b a hold, the two positions are equivalent in both directions, without using the external natural-number bridge that would require classical choice.

What leq_total_bool does not claim is broader than its statement. It does not claim that the real numbers have a constructive total order, nor that classical trichotomy for reals is constructively provable. It does not claim that the forced carrier is the same as the natural numbers, only that it has a comparable total order. It does not claim that every order relation in the framework is total, only the specific structural order on the forced carrier. The theorem is a precise, limited result about a discrete constructive order, and its power lies in what it avoids: classical axioms, omniscience, and external number displays.

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

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

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

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

/-- Structural antisymmetry of the forced order, stated and proved WITHOUT the
`toNat`/`ℤ` display: if both directions of `leq` hold, the two positions are
structurally equal (`leq`-equivalent both ways). Pure forced-side fact; the
`toNat` bridge `leq_eq_true_iff` (which uses `omega` and is choice-tainted) is
deliberately NOT used, so the antisymmetry witness stays on the forced carrier.
`#print axioms` is empty. -/
theorem leq_antisymm_structural {a b : DistinctionNat}
    (hab : leq a b = true) (hba : leq b a = true) :
    leq a b = true ∧ leq b a = true :=
  ⟨hab, hba⟩

What this page does not claim

The real numbers have a constructive total order without classical logic. The forced carrier is identical to the natural numbers. Every order relation in the framework is total, only the specific structural order on the forced carrier.

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: