The $δ$-calculus: from distinction to arithmetic
Jonathan Washburn, Milan Zlatanović
math.LO
Jul 31, 2026 · v1
TL;DR
Main results on the δ-calculus, number tower, and recognition-quotient classification are formalized in Lean 4 over Mathlib with axiom audits.
Abstract
Let $δ$ denote the primitive act of distinction, formally realized as the one-step extension $r \mapsto Sr$ of a finite record. We study the inductively generated $δ$-orbit and its first-order arithmetic presentation $\mathbb{N}_δ$. The corresponding $δ$-calculus is an intuitionistic first-order proof system over the signature $\{0,S,+,\cdot\}$. Every derivation carries a ledger recording the use of the law of excluded middle, the limited principle of omniscience, Markov's principle, and induction on quantified formulas. The last entry does not affect whether a derivation is forced. If a closed formula is derivable in the forced fragment, then it is true in the standard model. Starting from $δ$, we construct a choice-free number tower $δ\leadsto \mathbb{N}_δ\hookrightarrow \mathbb{Z}_δ\hookrightarrow \mathbb{Q}_δ$. The metatheoretic number systems $\mathbb{N}$, $\mathbb{Z}$, and $\mathbb{Q}$ each admit an explicit injection into $\mathbb{N}_δ$. We also classify the recognition quotients of the additive monoid $(\mathbb{N}_δ,+,0)$. Assuming the law of excluded middle, every recognizer is either injective or has a kernel congruence $\equiv_{i,p}$, with index $i$ and period $p$, for a unique pair $i\ge 0$, $p\ge 1$. In the noninjective case the quotient is isomorphic to the finite monogenic monoid $M(i,p)$. We price this classification with the ledger, determining which nonconstructive principles each form requires. If the congruence is decidable and an explicit pair of distinct related elements is given, the classification is forced. If the congruence is decidable and different from equality, Markov's principle is needed. For an arbitrary congruence, the dichotomy requires the law of excluded middle. The reverse implications show that the last two prices cannot be lowered. The main results are formalized in Lean 4.
Problem
Formalize how natural-number structure is generated from a primitive act of distinction via one-step record extension, and classify the logical principles required for derivations and for classifying recognition quotients of the resulting monoid.
Approach
An intuitionistic first-order δ-calculus over {0,S,+,·} is defined, with each derivation carrying a ledger recording use of EM, LPO, MP, and quantified induction. From δ a choice-free number tower N_δ↪Z_δ↪Q_δ is built. Recognition quotients of the additive monoid (N_δ,+,0) are classified via index-period congruences, and each classification form is priced by the nonconstructive principle it requires. The main results and their exact ledger prices are formalized in Lean 4 over Mathlib.
Results
The forced fragment is sound in the standard model; every recognizer is injective or has kernel congruence ≡_{i,p} giving a finite monogenic monoid M(i,p). Three classification forms are forced, MP-conditional, and EM-conditional respectively, with reverse implications showing prices are exact. Lean axiom audits show most declarations use only propext and Quot.sound, with the classical forms additionally requiring Classical.choice.
| Result | Lean declaration |
|---|
| Proposition 1.5 | bootstrap_initiality |
| Theorem 2.1 | sound_forced |
| Theorem 5.7 | recognizer_dichotomy |
| Theorem 6.11 | nat_catalogue_forced |
| Theorem 6.14 | nat_catalogue_classical |
Main results and their Lean 4 declarations