recursor
recursor supplies the primitive recursion operator for the LogicNat inductive type, allowing maps out of the forced naturals to be defined by a base value and a successor step. Researchers establishing categorical models of arithmetic cite it to witness that LogicNat satisfies the Lawvere NNO universal property in Type. The definition is realized by direct pattern matching on the two constructors of LogicNat.
claimDefine the operator $r : (X : Type) → X → (X → X) → LogicNat → X$ by pattern matching on the forced naturals: $r(X, b, s)(identity) := b$ and $r(X, b, s)(step n) := s(r(X, b, s) n)$.
background
The module bridges the strict categorical realization of UniversalForcing to Mathlib's CategoryTheory by showing that LogicNat admits the algebraic content of a natural-number object in Type. LogicNat is the inductive type whose constructors are identity (the zero-cost multiplicative identity in the orbit) and step (one further iteration of the generator), mirroring the smallest subset of positive reals closed under multiplication by the self-similar fixed point and containing 1.
proof idea
The definition is realized by Lean's built-in pattern matching on the LogicNat inductive type, with the identity case returning the supplied base and the step case applying the step function to the recursive call on the predecessor.
why it matters in Recognition Science
This definition populates the recursor field of the IsNaturalNumberObject structure for LogicNat, as required by logicNat_isNNO. It is used downstream in isInitial to lift to the initial object in the category of pointed endomap algebras and in tick_isNNO to establish that Tick satisfies the Lawvere NNO universal property. It thereby supplies the recursion principle needed for the arithmetic invariance results in UniversalForcingSelfReference.
scope and limits
- Does not prove the uniqueness clause of the NNO universal property.
- Does not construct a full category instance whose objects include LogicNat.
- Does not invoke Mathlib's HasInitialObject or Limits machinery.
- Does not transport the equivalence LogicNat ≃ Nat inside this declaration.
formal statement (Lean)
51def recursor {α : Type*} (base : α) (step : α → α) : LogicNat → α
52 | LogicNat.identity => base
53 | LogicNat.step n => step (recursor base step n)
54