Foundation Universal Forcing Strict Categorical Mathlib Recursor Succ

The successor step

In mathematics, a natural number object is a way to build the counting numbers from two ingredients: a starting point and a rule for taking one step forward. The theorem recursor_succ states that applying a recursive rule to the successor of a number is the same as applying the rule once, then continuing recursively from the result. In symbols, for any starting value base, any step function step, and any counting number n, the equation recursor base step (succ n) = step (recursor base step n) holds. This is one of the two equations that define how recursion works on the natural numbers.

The classical background comes from category theory, where a natural number object (NNO) in a category is a triple (N, zero, succ) such that for any object A with a base point and a self-map, there is a unique morphism from N to A making the obvious diagram commute. In the category of types, this universal property says exactly that primitive recursion is possible and unique. The theorem recursor_succ is the second half of that property: it guarantees the step case works, while its companion recursor_zero handles the base case. Together with a uniqueness theorem, they certify that the type LogicNat behaves exactly like the usual natural numbers for the purpose of defining functions by recursion.

In Recognition Science, this declaration is part of a bridge between the framework's own construction of the counting numbers and the standard mathematical library. The framework models its foundational objects as a discrete ledger, a record of events with no gaps, and it needs a rigorous way to talk about stepping from one entry to the next. The theorem proves that its LogicNat type satisfies the algebraic content of a natural number object in the category of types, witnessed by a machine-checked library of formal theorems. The proof is constructive: the recursion principle is defined by pattern matching, and the two equations hold by definitional equality, meaning they are true by the very way the recursor is written.

What the theorem does not claim is equally precise. It does not assert that LogicNat is literally the same object as the standard natural numbers; it only proves an equivalence in recursive content. It does not construct a full category instance with initial objects, which would require extra machinery. And it says nothing about the physical world, about recognition costs, or about the forcing chain that derives constants like the golden ratio. The declaration is a structural fact about how one formal system of counting relates to another, useful because it lets the framework borrow standard results without rebuilding them.

The practical consequence is that any function definable by primitive recursion on the usual natural numbers can be transported to LogicNat and back, so the framework's internal arithmetic is interchangeable with the classical one. A reader who wants to know whether the framework's numbers behave correctly can check this one equation and see that the successor step is exactly the recursive step, nothing more. That is the whole content of the theorem, and it is exactly what the name promises.

theorem recursor_succ {α : Type*} (base : α) (step : α → α) (n : LogicNat) :
    recursor base step (LogicNat.succ n) = step (recursor base step n) := rfl

/-- The NNO universal property on `LogicNat` in `Type`: uniqueness. -/
theorem nno_universal_uniqueness {α : Type*} (base : α) (step : α → α)
    (f g : LogicNat → α)
    (hf_zero : f LogicNat.zero = base)
    (hf_succ : ∀ n, f (LogicNat.succ n) = step (f n))
    (hg_zero : g LogicNat.zero = base)
    (hg_succ : ∀ n, g (LogicNat.succ n) = step (g n)) :
    f = g := by
  funext n
  induction n with
  | identity =>
      rw [show LogicNat.identity = LogicNat.zero from rfl, hf_zero, hg_zero]
  | step k ih =>
      rw [show LogicNat.step k = LogicNat.succ k from rfl, hf_succ k, hg_succ k, ih]

theorem recursor_zero {α : Type*} (base : α) (step : α → α) :
    recursor base step LogicNat.zero = base := rfl

theorem recursor_succ {α : Type*} (base : α) (step : α → α) (n : LogicNat) :
    recursor base step (LogicNat.succ n) = step (recursor base step n) := rfl

What this page does not claim

The theorem does not prove that LogicNat is identical to the standard natural numbers, only equivalent in recursive content. It does not construct a full category instance with initial object machinery. It says nothing about physical recognition costs or the derivation of constants like the golden ratio.

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/Strict/CategoricalMathlib.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: