Foundation Universal Forcing Natural Number Object Xor Bool True

The Boolean parity test

The declaration xorBool_true is a small but sharp piece of a larger argument about what counting is. It states a fact about Boolean algebra: for any Boolean value b, the exclusive-or operation with true yields the negation of b. In symbols, true xor b = not b. This is a standard identity, the kind a logic textbook would list without fanfare.

Within the Recognition Science framework, this identity becomes a stress test. The framework models a discrete ledger, a record of events, and asks what structure is forced by the mere act of maintaining such a record. One candidate realization of this ledger uses only two states, false and true, and defines a single step as flipping between them. The xorBool_true identity is what makes that step behave as a flip: applying it to false gives true, and applying it to true gives false.

The point of this construction is to test whether the framework's arithmetic survives when the visible carrier set is tiny. A critic might object that the framework smuggles in the natural numbers by assuming an infinite counting process. The Boolean realization answers that worry. Its carrier has only two elements, yet the iteration object, the thing that records how many steps have been taken, remains the full natural-number object. The framework proves that this iteration object is the same in every realization, including this two-state one.

The framework's machine-checked library of formal theorems shows the collapse explicitly. The interpretation map from the natural numbers to the two Boolean values is exactly the parity map: even numbers map to false, odd numbers to true. This map is not injective, so the visible states lose information. But the iteration object itself never collapses. The framework proves it is a natural-number object in the Lawvere sense, meaning it supports unique primitive recursion, the categorical definition of what the natural numbers are.

What xorBool_true does not claim is that the Boolean realization is a model of arithmetic in any ordinary sense. It does not claim that the two-element carrier is a model of Peano arithmetic, nor that the parity map is an isomorphism. The declaration is a lemma inside a larger proof, not a standalone result about Boolean algebra. Its role is to make precise the distinction between the visible carrier and the underlying iteration object, and to show that the latter is stable.

The consequence is a cleaner picture of what the framework means by "natural numbers." They are not a set of symbols or a carrier type; they are the structure of iteration itself, characterized by a universal property. A two-state system can still carry that structure, even though its observable behavior is just a flip. The xorBool_true identity is the hinge that makes the flip work, and the framework's theorems show that the hinge does not break the counting.

/-- One step of the Boolean strict realization is `xor true _`, which is
boolean negation. -/
private theorem xorBool_true (b : Bool) : xorBool true b = !b := by
  cases b <;> rfl

/-- The Lawvere universality statement: any two realizations have iteration
orbits that satisfy the natural-number-object property, hence are
canonically equivalent. -/
noncomputable def universal_forcing_via_NNO
    (R S : LogicRealization.{0, 0}) : R.Orbit ≃ S.Orbit :=
  IsNaturalNumberObject.equiv (realizationOrbit_isNNO R) (realizationOrbit_isNNO S)

/-- The Boolean strict-realization interpretation is the parity map.

This is the formal statement that the iteration count survives even when
the orbit-as-set collapses to `{false, true}`. -/
theorem interpret_eq_parity (n : LogicNat) :
    StrictLogicRealization.interpret strictBooleanRealization n =
      Nat.bodd (LogicNat.toNat n) := by
  induction n with
  | identity => rfl
  | step n ih =>
      show xorBool true (StrictLogicRealization.interpret strictBooleanRealization n) =
        Nat.bodd (Nat.succ (LogicNat.toNat n))
      rw [xorBool_true, ih, Nat.bodd_succ]

/-- Even though the carrier image collapses, the iteration object is the
full `LogicNat`. Concretely: the interpretation map is not injective. -/
theorem interpret_collapses :
    ¬ Function.Injective
      (StrictLogicRealization.interpret strictBooleanRealization) := by
  intro hinj
  have h0 :
      StrictLogicRealization.interpret strictBooleanRealization LogicNat.identity =
        Nat.bodd 0 := interpret_eq_parity _
  have h2 :
      StrictLogicRealization.interpret strictBooleanRealization
        (LogicNat.step (LogicNat.step LogicNat.identity)) =
          Nat.bodd 2 := interpret_eq_parity _
  have hbodd : (Nat.bodd 0 : Bool) = Nat.bodd 2 := by decide
  have hboth :
      StrictLogicRealization.interpret strictBooleanRealization LogicNat.identity =
        StrictLogicRealization.interpret strictBooleanRealization
          (LogicNat.step (LogicNat.step LogicNat.identity)) := by
    rw [h0, h2, hbodd]
  have hne : LogicNat.identity ≠ LogicNat.step (LogicNat.step LogicNat.identity) :=
    LogicNat.zero_ne_succ _
  exact hne (hinj hboth)

/-- Initiality of an NNO in the category of pointed endomap algebras. -/
def isInitial (h : IsNaturalNumberObject z s) :
    PeanoObject.IsInitial (toPeano h) where
  lift := fun B =>
    { toFun := h.recursor B.zero B.step
      map_zero := h.recursor_zero B.zero B.step
      map_step := fun n => h.recursor_step B.zero B.step n }
  uniq := by
    intro B f g
    funext n
    have hf := h.recursor_unique B.zero B.step f.toFun f.map_zero f.map_step n
    have hg := h.recursor_unique B.zero B.step g.toFun g.map_zero g.map_step n
    rw [hf, hg]

What this page does not claim

The Boolean carrier is not a model of Peano arithmetic. The parity map is not an isomorphism between the natural numbers and the Boolean values. The xorBool_true identity alone does not establish the natural-number object property.

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/UniversalForcing/NaturalNumberObject.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: