LLM-maintained and unaudited. This fork's changes and documentation are maintained with LLM agents and have not received an independent human audit. The main verification theorem is conditional on two open metatheoretic assumptions, described below.
This is a research fork of digama0/lean4lean, an implementation of the Lean 4 kernel in mostly pure Lean 4, with a formal specification and proofs connecting the implementation to it. The implementation derives from Lean's C++ kernel and can share its bugs. This fork extends the inductive-type specification and verification, changes some kernel checks, and develops the remaining metatheory. It grew out of other work and is not coordinated with upstream.
Upstream's addDecl.WF leaves inductive declarations as sorry, and its
Injectivity.lean states sort_inv, sort_forallE_inv and
forallE_inv_stratified with sorry proofs. Here the inductive case is proved
for flat and nested blocks, and a shape model proves the first two. The third,
with injectivity of inductive type formers, which inductives add, is the
explicit hypothesis VEnv.Injective.
- Verification status and trust assumptions
- Build and test
- Run the checker
- What this fork changes
- Findings and regression tests
- Design and proof guide
- Open metatheory
- Source map and contributing
| Area | Status |
|---|---|
| Declaration checking, including flat and nested inductives and quotient initialization | Lean4Lean.addDecl.WF is proved assuming VEnv.Injective, as are the supporting results that need injectivity. |
| Primitive projections, structure eta, recursor and quotient reduction | Specified and connected to the implementation; the verification uses the same injectivity hypothesis where needed. |
| Shape model | Sound for well-formed environments. Proves that a sort cannot equal a pi type, and that equal sorts have equivalent universe levels, without the injectivity hypothesis. |
| Injectivity of pi types and inductive type formers | Open. These are the two fields of VEnv.Injective. |
| Logical relation intended to establish injectivity | Incomplete at a recursor's full application (IndRecSat), especially K-like reduction and indexed iota reduction. |
| Church–Rosser and experimental developments | Unfinished. NormalEq.parRed has two sorry cases; Experimental contains further incomplete proofs. |
The Verify development is sorry-free, so addDecl.WF depends on no sorryAx;
VEnv.Injective enters as an explicit argument. The theorem states that
successful declaration checking preserves the formal environment invariant;
consistency of the type theory is a separate question. To check:
import Lean4Lean.Verify
#check @Lean4Lean.addDecl.WF
#print axioms Lean4Lean.addDecl.WFThe verification also trusts the runtime-model axioms in
Verify/Axioms.lean, Lean's proof checker, and the
compiler/runtime correspondence for native and opaque operations. The fork
corrects some inherited axiom statements and removes others; runtime comparison
tests exercise the rest.
Install elan, then run these commands from
the repository root. The toolchain is pinned in lean-toolchain
(currently Lean v4.33.0-rc2), and dependencies in
lake-manifest.json.
lake build
lake build Lean4Lean.Tests Lean4Lean.ExperimentalThe default build includes the library, executable, theory and verification.
Tests and experimental modules are separate targets. Unfinished theory and
experiments emit sorry warnings.
| Target | Contents |
|---|---|
lake build Lean4Lean |
Kernel library, without the verification proofs |
lake build lean4lean |
Command-line checker |
lake build Lean4Lean.Theory |
Abstract type theory and metatheory |
lake build Lean4Lean.Verify |
Implementation verification |
lake build Lean4Lean.Tests |
Regression suite, including compile-time runtime-model checks |
lake build Lean4Lean.Experimental |
Unfinished formalization experiments |
CI runs both replay modes as smoke tests:
lake exe lean4lean Init.Core
lake exe lean4lean --fresh Init.System.IOThe checker replays built .olean files; it does not read the export format
used by lake check and the Lean Kernel Arena.
Without a module argument, the checker infers the current package's main module from its Lake manifest. Otherwise, each module argument is a prefix: it checks all matching built modules. Ordinary replay checks each module against its imported environment and runs modules concurrently. Broad prefixes can use a large amount of memory; start with a single small module.
--fresh requires the prefix to match exactly one module. It rechecks that module
and its imports into a fresh environment; it does not rebuild the source files.
To check another package, build that package with the same toolchain, change to its directory, and run this fork's executable in that package's Lake environment:
lake env /path/to/lean4lean/.lake/build/bin/lean4lean MyPackage.Module| Option | Effect |
|---|---|
--fresh |
Recheck one module and all its imports from scratch |
-v, --verbose |
Print declarations as they are checked |
--compare |
Compare slow checks with Lean's C++ kernel |
--config=path.json |
Read fuel limits from a JSON file |
--config:field=value |
Override one fuel limit with a JSON value |
The configuration fields and defaults are in
FuelConfig.lean. File and field options are applied
in command-line order. Imported declarations are trusted in ordinary replay;
use --fresh when that distinction matters.
- Inductive declarations and their verification.
VInductDecl.WFspecifies mutual blocks, positivity, universes, large elimination, constructors, recursors and iota rules. Flat and nestedaddInductivepaths are connected toVEnv.addInduct, includingBoolandNat. Generated recursors and rules are proved well typed under the stated metatheoretic assumptions. - Primitive projections.
VExpr.projmodels projections directly, with typing, iota and structure-eta rules. Translation is syntactic and unique. Projection permissions are tested at the instantiated sort, including structures that may inhabitProp. - Context-sensitive checking. Support and simulation theorems describe which variables, universe parameters and constants a checker run can read. Caches and the equivalence manager track the scopes their facts depend on. Verification no longer assumes that typing or definitional equality can always be strengthened by dropping unused variables.
- Kernel checks and runtime models. Annotation definitions are checked before
stripping them; nested restoration, projection and reduction checks expose
conditions the proofs need. Simultaneous instantiation and abstraction are
modelled correctly, and the inconsistent
mkLevelIMaxCore_eqaxiom is removed. - Metatheory. A shape model proves sort separation and sort injectivity. A logical relation develops the remaining injectivity argument and makes its unresolved recursor case explicit.
These changes include deliberate acceptance differences from Lean's C++ kernel. See divergences.md for the behavior and reproducing tests, and bugs-found.md for upstream's existing bug catalogue.
The examples were found against the pinned toolchain. On v4.35.0 and
v4.36.0-rc1, Lean's kernel also rejects the BinderScope and FieldViews
declarations, but still accepts the loose-variable and _nested_1 declarations
in NestedInductive. Annotations and UnsafeEq use a custom prelude, which Lean's
kernel assumes it is not given; this fork checks those cases because its proofs
need them.
| Example | What is exercised |
|---|---|
| InductiveSpec | Generated recursors and iota/eta rules checked against Lean's kernel; primitive projections at instantiated universe levels |
| NestedInductive | Restoring nested blocks with nontrivial levels, metadata and let types |
| Annotations | A custom prelude whose non-identity annotation definitions let Lean generate ill-typed recursors; this fork checks the definitions |
| BinderScope | Equivalences and cached checks learned under a binder being reused outside its scope |
| FieldViews | Field domains with defaults and dead lets, including a structure accepted through a fact learned under a discarded field |
| PrimitiveScope | Primitive recognizers checking retained terms outside temporary binders, while still recognizing the prelude's primitives |
| AxiomModels, LevelStd | Runtime operations compared with their logical models, including open terms, repeated variables, metadata and universe levels |
| QuotInit | Quotient declarations matching Lean's, including binder information |
| DeclFVar, ReservedName, UnsafeEq | Malformed declaration inputs, the reserved panic constant, and unsafe Eq during quotient initialization |
The old instantiation model substituted one term at a time. Lean substitutes
simultaneously: (bvar 0).instantiate #[bvar 0, X] is bvar 0, not X. The old
abstraction model similarly mishandled loose bound variables and repeated
variables. The replacement models state simultaneous semantics; the old forms
are derived for the closed, distinct-variable inputs where they apply. A third
axiom, mkLevelIMaxCore_eq, equated two definitions that disagree on imax 1 u;
it was unused and has been removed. The tests cover only inputs on which the
runtime does not panic.
The specification states a block's constructor and recursor facts with its types declared but without its constructors. Index telescopes must already be types before the block exists, since an index cannot depend on the block's types. The implementation sometimes normalizes in a larger environment; simulation repeats those runs in the environment the specification needs.
Nested auxiliary types stand for occurrences of earlier types at parameters
mentioning the new block. They have motives, minor premises, recursors and iota
rules, but introduce no auxiliary type constants in the final specification.
The kernel's temporary auxiliary constants are eliminated when it restores the
block. AuxWF relates their declarations to the earlier types up to equivalent
universe levels, accommodating the simplification performed by level
instantiation.
restoreNested replaces an auxiliary application at its own arguments and
levels. It preserves metadata and checks that restored terms contain no
auxiliary constants; restored terms with lets are checked explicitly. Nested
occurrences are checked against the block's types as axioms, before relying on
the finished environment. The final insertion order may interleave each type
with its constructors and recursor, so AddInduct allows that order.
The proof starts in Verify/Environment/Inductive.lean.
Run.lean assembles the flat phases;
MkRecInfos.lean and
Rules.lean handle recursors;
NestedBranch.lean assembles the
nested path. Restoration in the theory is developed in
Nested.lean through
NestedWF.lean.
Primitive projections cannot always be represented by recursor applications:
the kernel can project from Foo.{1} even when Foo's recursor eliminates only
into Prop. Recording blocks in VEnv.inducts lets each projection rule identify
the structure's declaration and constructor telescope directly.
ProjAllowed describes when a projection from a possibly propositional type is
permitted. projEta requires those permissions for the expansion's projections.
The model can be more permissive than the kernel about dependencies of fields
after the projected field; soundness only needs the fields reached by the
projection. The Ex example in InductiveSpec exercises this distinction.
Lean's planned kernel renovation
removes projections from propositional structures with data fields, which
would change the cases ProjAllowed covers.
checkConstructors checks each field's declared domain, its form with lets
unfolded, and its view with annotations stripped. FieldsKeptWF and CtorDoms
provide the domain typings needed when a projection skips earlier fields.
These are established by simulation in the smaller contexts, and survive
nested restoration. The proof of inferProj.WF
therefore does not assume strengthening.
The checker compares structure names, checks projection indices and universe counts, and reduces only complete constructor applications. Quotient reduction also checks the constructor's type and relation against the eliminator. These checks avoid relying on additional unproved separation properties of type formers. divergences.md records the observable differences.
A fact learned under p : P a can depend on p without mentioning it. Proof
irrelevance can equate hI with I.mk a p, enabling an iota reduction that has
no known derivation after p leaves scope. Merely examining a cached term's
free variables does not justify keeping that fact.
Each cache entry and union-find link carries the deepest scope of the facts its
derivation consulted. Entries depending on a closed scope cease to be current;
other entries remain available. Keys need no extra label for their own free
variables because variable identifiers are fresh and a key mentioning a closed
variable cannot be queried again. withFreshId rejects an already declared
identifier.
Verify/Support proves support and simulation
separately from typing, so these properties do not themselves require
VEnv.Injective. The cache proofs rerun computations in the context where their
results are used, with facts above the allowed scope set aside by a ceiling.
ScopedEquivManager.lean and its
verification handle labelled equivalences.
Scope tracking costs about 16.7% on a local replay of Lean core (1155.5 versus 990.4 billion user-mode instructions), mostly from cache bookkeeping, larger state and the pair map.
Primitive recognizers likewise check retained closed terms outside the binders
where they discovered them. The kernel checks annotation definitions as
identities before stripping them and uses the total, cached Expr.anySubterm
instead of relying on an axiom for native subterm search.
The shape model is sound and distinguishes sorts and pi types, but does not
establish injectivity of pi domains/codomains or inductive parameters/indices.
The logical relation's remaining IndRecSat case must relate a recursor's
reduct at the type of its full application. K-like and indexed iota reduction
require a judgmental equality between the spine's indices and the constructor's
indices. Turning that equality into a relation at the motive's argument shape
is the unresolved conversion problem.
No counterexample to either injectivity assumption is known. Attempts to prove them through the current relation, or by induction on derivations, stop at this same step; the notes below record those arguments informally.
The verification also avoids assuming general strengthening, which the binder-scope examples suggest may fail, and uses support, simulation and explicit domain checks instead.
Research notes: the conversion gap and attempted injectivity arguments
The logical relation (LogRel/Rel.lean, RelS.lean) has every adequacy case but a recursor's
full application (IndRecSat), in its K-like case and its iota case at a type with indices.
Every use of the conjectures on addDecl.WF's path goes through unique typing or untyped defeq
composition (isDefEqArgs compares arguments without their types), so nothing weaker than full
injectivity serves; it has to come from the relation.
-
The gap.
T.rec mot m is hsteps when the indicesisequal the constructor'sidxjudgmentally (KFields.index; in the iota caseCtorParams'SubstRel). The reduct is typed atmot idx …, the spine atmot is …; converting between them goes through the motive'sPiDefEq, which needsisandidxrelated at a shape at or above the valuation'sρ_is. Judgmental equality alone does not give that: the relation is not known to be closed under conversion, and closure would itself giveforallE_inv. -
Normalization is not the obstacle: relevant terms need a weak head normal form only at non-
botshapes, and a recursor on a proof major steps by the K-like rule without reducing it,Acc's included. -
Tightness (in progress): a related pair's value shape lies below both terms' interpretations at the all-
botvaluation in the model with no given shapes (Tight,AxBelow). It keeps stuck values at shapes their interpretations reach. -
Every source of closure tried so far fails on depth. The relation is defined by recursion on depth, and adequacy needs it to agree across depths:
LR.DefEq.lift/TyDefEq.liftare used in both directions, and the application case relatesF Xat the function's depth and lowers the result to the goal's.- Depth-bounded adequacy (adequacy of the whole environment below a constant case's depth)
fails because the application case climbs depth:
f : (Nat → Nat) → Natneeds depth 2 for a result at depth 0, andInterpTyped.outmoves premises to the model's witness depth. - Saturation (pi clauses and related substitutions quantify only over arguments related at
every typed shape below their interpretation) gives adequacy from saturated substitutions
(
LE_Interp.substis an equivalence, valuations join), the identity substitution is saturated (variables atbot), and a firing condition stated with it makes both substitutions fire together. But "every shape below the interpretation" depends on the depth: at depthnit ranges over depth-nshapes.lift's direction from depthn'ton ≤ n'then needs arguments saturated at depthnto be saturated at depthn', which nothing gives; quantifying over every depth makesLR (n+1)refer to deeper relations. - Relational firing (the relation's reduction fires K-like and indexed iota steps only when
the indices are related to
idxat every shape below their interpretation, one depth down) settles the K and iota cases and the derived K-like equalities: a firing condition is a fact about the terms, and wherever adequacy needs it the index equality is a subderivation. It fails the same way: a spine can fire at depthn+1(indices related at every depth-nshape) and stay stuck at depthn+2, soliftandmono_lacross that depth relate two stuck spines at one depth and need their reducts related at the other. Firing at the interpretation's own depth is not well founded, since a spine's indices can be interpreted deeper than the spine is checked.
- Depth-bounded adequacy (adequacy of the whole environment below a constant case's depth)
fails because the application case climbs depth:
-
All three need the same missing fact: pairs related at every depth-
nshape below their interpretation are related at every deeper one. For judgmentally equal terms that is closure under conversion again. -
The K-like case needs injectivity itself, not only some closure. For
X Y : Type,Eq.rec (motive := fun T _ => T) (m : X) Y h : Ysteps tomwhenY ≡ X; relatingmatYisLR.convwithTyDefEq X Y, and whereXandYare pi types that is the relation of their domains,forallE_inv's content at the motive's argument depth. Any route through the relation must prove injectivity below a recursor's depth inside its constant case, from the one fact the case has,Y ≡ X. -
Other recursion orders do not supply it.
- Depth-free shapes ordered by structure: the size the motive conversion needs is bounded by
the motive's shape, as with depth, but the relation there comes from adequacy of the
derivation of
Y ≡ X, and adequacy at a shape needs constant cases at larger ones (the application case climbs, as with depth:(fun g => g 0) (fun _ => 5)at a depth-6 result needsfun _ => 5at depth 7 and the function at depth 8). The regress has no measure: each constant case appeals to another derivation in the whole environment. - Depth-uniform relations (the relation at depth
nagreeing with every deeper one on lifted shapes): depthn+1sees fields and graph entries depthndoes not, so relation at every depth-nshape never implies relation at depthn+1unless the terms are judgmentally equal and the relation is closed under conversion, the fact sought. - Firing and conversion decided by the model: the model gives
⟦X⟧ = ⟦Y⟧and, at sort shapes, equivalent levels (sort_inv), butTyDefEqat a pi shape asks for the domains' judgmental equality, which no interpretation determines; provingX ≡ Y ∧ tight → TyDefEq X Y aby induction onastops at the pi case, where it isforallE_inv.
- Depth-free shapes ordered by structure: the size the motive conversion needs is bounded by
the motive's shape, as with depth, but the relation there comes from adequacy of the
derivation of
-
So the logical relation, with constant cases quantified over arbitrary related substitutions, cannot close
IndRecSat's K-like case on its own. Closing it needs injectivity below each depth from an independent argument, such as a confluence proof for a reduction that includes the K-like and eta steps. -
No counterexample to
forallE_invorindApp_invis known. A failure needs a type-level redex whose major premise the theory equates with two different values; every rule that equates terms non-congruently is ruled out as a source:- Proof irrelevance equates proofs, never types, and only at one type. Large elimination out
of a proposition needs a single constructor whose non-proof fields appear among its indices
as variables (
LargeElimOK, as the kernel'sisLargeEliminator), so two constructor applications at one type differ only in proofs unless their indices already differ: a failure ofindApp_invis needed before proof irrelevance can produce one. The same holds forEq.rec's K-like computation,Acc, a quotient of a proposition (Quot.liftout of a proof ofQuot α rcomputes at a proof ofα) andQuot.lift's rule, whose left side repeatsαandr. - Structure eta expands deterministically, and on a type that may be a proposition only where every projection is allowed, so only proofs are projected; unit-like types hold no types.
- The remaining rules (beta, delta, iota, projections, the quotient's, partial definitions' recursive equations) have one rule per head, so they overlap only through proof irrelevance and eta.
- Proof irrelevance equates proofs, never types, and only at one type. Large elimination out
of a proposition needs a single constructor whose non-proof fields appear among its indices
as variables (
-
K-like reduction with an impredicative
Prop, where Gilbert–Cockx–Sozeau–Tabareau and Abel–Coquand locate the breakdown of the usual metatheory, gives no counterexample either:- A cast
Eq.rec (motive := fun T _ => T) m Y hcomputes only oncerefl X : Eq X Y, that isEq X X ≡ Eq X Y; no hypothesis or proof supplies a judgmental equality (there is no equality reflection), so it needsX ≡ Yor anindApp_invfailure first. - A
Prop-valued result (Eq X XagainstEq X Y) out of a proof needs a motive intoType, which is large elimination:Orand other non-subsingletons eliminate only intoProp, so proof irrelevance betweenOr.inl aandOr.inr bproduces no type equality. - Large elimination out of a proof computes from the spine's own indices, whatever the proof:
Lean's kernel does not reduce
K.rec … hforinductive K : Bool → Type → Prop | mk X : K true Xat a hypothesish(it does no K-like step there), while the spec derives it throughh ≡ K.mk Y, at the sameY → Natiota gives atK.mk Y. An index that is not a variable (mk n : I (n+1)) removes large elimination. - Abel–Coquand's non-normalizing proofs only loop: proof irrelevance already equates them
with every proof of their type, so they add no equality between types. Likewise
Accand other impredicative inductives inProp: unfoldingAcc.recthrough proof irrelevance is deterministic in the spine. - Every non-joinable peak between type-producing redexes therefore needs a proof typed at a
type former applied to arguments other than its own indices (
c fs : I idxwithI (ctorIdx fs) ≡ I idx,ctorIdx fs ≢ idx), which is a smallerindApp_invfailure in the major's typing derivation. Turning that regress into a proof needs the statement for every zigzag of steps, not only between type formers: transitivity passes through arbitrary redexes, which is where a confluence argument would be needed.
- A cast
-
Injectivity fails for heads that are not type formers, so the relation must not assume it there: a definition with an unused level parameter is equal at any two levels (
C.{0} ≡ C.{1}fordef C.{u} : Type := Nat), a definition can ignore its arguments, and a variable applied to proofs is equal at any two proofs. -
Induction on derivations (sketched, not formalized). The invariant is a typed relation
Inv Γ e e' T, defined by recursion on the head form ofTunder a deterministic type-level head reduction (beta, delta, iota, projections' iota, the quotient's rule, and for recursors of large-eliminating propositions only the K-like step, firing when the spine's indices equal the constructor's judgmentally, so that it never overlaps ordinary iota):- at a sort: if either side head-reduces to a head form, so does the other, and the two agree: equivalent sorts; pi types with related domains and codomains; the same type former, level and argument by level and argument; the same neutral head with related arguments;
- at a pi type: applications to related arguments are related (this absorbs lambda eta);
- at a structure: projections are related (structure eta); at a proposition: nothing (proof irrelevance); at an inductive type: the least relation closed under constructors and neutrals.
The recursion is on universe level and structure:
Propcontributes nothing, so impredicativity does not enter, and types without a head form (Acc.recunfolding forever) are covered by the clause that transfers having one.forallE_invandindApp_invare its sort clause. Unique typing at the components' sorts has to be carried along, asIsDefEq.uniqdoes. -
The rules, with the fundamental lemma stated under related substitutions:
- pass from the induction hypothesis:
symm,sortDF,forallEDF,lamDF(substitution),beta,eta,proofIrrel(a proposition's clause is empty),defeqDF(the type equality is a subderivation, so its sort clause moves the relation fromAtoB),projDF,projIota,projEta; - pass with a lemma:
bvar(determinism of the head reduction),constDF(reduction commutes withinstL, and the K-like firing condition moves along equivalent levels),trans(agreement composes once components' sorts agree),extra(the right side's typing is not a subderivation, so this needs an outer induction on the environment, asAdequacyHypsdoes); - fail:
appDFat a recursor spine, in the recursor's own case. Ordinary iota is a constant case like the logical relation's. The K-like step fails: it fires on a judgmental index equality with no derivation in the induction, and relating the reduct needs the relation between the motive at the spine's indices and at the constructor's. ForEq.rec (motive := fun T _ => T) (m : X) Y hthat isInvofX ≡ YatType, from an arbitrary derivation. Neither derivation size nor the stratification index bounds it:HasTypeStratified.defeqholds an unstratified conversion. Universe level grows the wrong way (the needed judgmentX ≡ Y : Typesits one universe abovem : Y). - Firing the K-like step only on syntactically equal indices, or on indices related by the
induction hypothesis, breaks congruence under proof irrelevance instead:
Eq.rec mot m Y h ≡ Eq.rec mot m Y (refl X)relates a stuck spine to one that computes. Allowing ordinary iota on proof majors as well brings an overlap with the K-like step whose reducts agree only byindApp_invon the major's typing, again an unbounded conversion.
- pass from the induction hypothesis:
-
So this route stops at the same place as the logical relation, the K-like case, and for the same reason: no measure decreases from the judgment being proved to the index equality that lets a K-like step fire.
| Path | Starting point |
|---|---|
| Main.lean, Replay.lean | CLI and replay |
| Environment.lean, TypeChecker.lean | Kernel entry points |
| Inductive/Add.lean, Inductive/Reduce.lean | Inductive declaration checking and reduction |
| Theory/Inductive.lean, Theory/Typing/Basic.lean | Inductive specification and typing rules |
| Verify/Environment.lean | Top-level declaration verification |
| Theory/Typing/Injectivity.lean | Explicit open hypotheses and proved sort properties |
| Theory/Typing/LogRel | Shape model and logical relation |
| Verify/Axioms.lean | Trusted runtime models |
| Tests, Experimental | Regressions and unfinished experiments |
For a review or proposed change, state which specification, implementation or proof obligation it affects, include a reproducer for behavior changes, and run the relevant build and replay checks above. New hypotheses and differences from Lean's kernel should be explicit. Reports about this fork should be filed here; establish whether an issue also occurs upstream before reporting it there.
The project retains upstream's Apache 2.0 license, copyright notices and author attribution. The LLM-maintenance notice applies to this fork's changes, not to upstream.