You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Language 1.2: induction and structural recursion over nested inductive types #278
A language-1.2 theorem cannot quantify over every value of a nested inductive type. SPEC.md §17.12 ("Recursive data (language 1.2)", rules 6 and 7) admits induction only on a self-recursive inductive "with no nested occurrence and no mutual group", and structural recursion decreases only on Nat, List, or such an inductive: "a nested or mutual type has no single structural eliminator for one function."
The types that matter most are nested. JSON is the canonical case: in UOR-Foundation/MCP, Json has constructors array (List Json) and object (List (String * Json)). The codec's defining property, that parsing the encoder's output returns the value (UOR-Foundation/mcp#18), is a statement over every Json value. Under the current rules it can only be checked on instances (UOR-Foundation/mcp#20), not proved. The same holds for any tree whose children sit in a list, map or option, such as the Grove type the production evidence of §17 exercises.
Item
A proof form for nested inductive types: the nested eliminator Lean generates for a nested inductive (or an equivalent, such as size-indexed induction whose hypothesis the closed proof forms can use), with the binding order of its hypotheses fixed by the eliminator descriptor, as §16.9 fixes it for induction today. Structural recursion over a nested occurrence, through List elements, should follow the same rule, so that a function over a nested type and the theorem about it have the same shape.
Accepted when
A theorem quantifying over every value of a nested inductive, where some constructor holds a List of the type, is proved and verified under the pinned Lean with an exact axiom policy, and a missing case is refused with a registered diagnostic.
A register row, a scenario and a negative fixture exist for the new form (R3, R5).
Needed by UOR-Foundation/mcp#18 (the universal round-trip theorem of the JSON text codec).
For the maintainer. The engineering lead of UOR-Foundation/MCP and UOR-Foundation/lexlean-mcp would like to deliver this issue on release/v0.4, since it is a language-1.2 proof form. The round-trip theorem of UOR-Foundation/mcp#18 needs it.
Proposed order, as the #91 stage-4 series does it:
An R3 skeleton PR: a register row in §31, its scenario, and a failing negative fixture.
The implementation, stacked on the skeleton:
an eliminator descriptor for nested inductives, and the binding of their hypotheses;
the lowering to Lean's generated nested recursor (T.rec with the auxiliary motives Lean derives for List T fields) or to induction ... using;
structural recursion through List elements, under the same rule.
The change moves the language-1.2 identity, so it would land alone, with one regeneration and one full gate.
Questions for you:
Which slot fits the identity waves you have planned?
Do you prefer the nested-recursor lowering, or a size-indexed induction whose hypothesis the closed proof forms may use?
An agent will post the detailed design here before writing code.
Design for #278, for the maintainer to confirm before any implementation PR. Agent lexlean-nested-induction, working for the engineering lead of UOR-Foundation/MCP. Base: release/v0.4 at 979606797.
Order of work: an R3 skeleton PR (register rows, scenarios, failing named tests, one negative fixture) goes up now, since it commits to nothing irreversible. The implementation PRs wait for your answer to the questions at the end.
What I checked in Lean 4.32.1 (installed lean, run on this machine)
The induction tactic refuses a nested type: The induction tactic does not support the type Json because it is a nested inductive type. So the current induction lowering (induction x with | ctor ... =>) cannot be extended.
Lean generates a multi-motive recursor for a nested type. For Json with array (List Json) and object (List (String × Json)), Json.rec has four motives, in this order: motive_1 : Json, motive_2 : List Json, motive_3 : List (String × Json), motive_4 : String × Json. Its minor premises are, in order, the constructors of Json, then nil, cons of List Json, then nil, cons of List (String × Json), then mk of the pair. Json.rec_1..rec_3 are the same term at the other motives. For inductive Rose (α) | node : α → List (Rose α) → Rose α, Rose.rec has motive_1 : Rose α, motive_2 : List (Rose α) and the minors node, nil, cons.
The motive order is breadth-first discovery, not depth-first. For A | c1 : List (Option A) → List A → A | c2 : Option (List A) → A × A → A | c3 : Except Nat A → A, the motives are A, List (Option A), List A, Option (List A), A × A, Except Nat A, Option A: the maximal nested applications of the fields of A's constructors, in field order, then the new ones found in the constructors of each earlier member, in member order. Minors follow the motive order; within a member the constructor order is Lean's (List: nil, cons; Option: none, some; Except: error, ok; product: mk).
A minor premise takes the constructor's fields, then one hypothesis per field whose type is a motive's type, in field order, e.g. cons : (head : Json) → (tail : List Json) → motive_1 head → motive_2 tail → motive_2 (head :: tail) and Except.error takes none, Except.ok takes one.
induction j using Json.rec (motive_2 := …) (motive_3 := …) (motive_4 := …) elaborates, with motive_1 taken from the goal, and leaves one goal per minor premise, in minor-premise order. A with | nil … | cons … alternative list is refused (Duplicate alternative name nil) as soon as two members have a nil, so the lowering must name goals positionally, with next x y z =>, which works and renames the inaccessible hypotheses in binding order.
A hand-written Lean file in exactly the shape below proves leaves j ≤ size j for all j : Json (mutual structural size/leaves families, intros; simp only [defs] at *; all_goals (repeat' split); all_goals omega per goal, which is the linear_arithmetic lowering) and #print axioms reports propext and Quot.sound (a policy is strictly sorted, so [Quot.sound, propext]). This is a prototype of the target text, not LexLean output; the implementation PR records the observed set from the real build.
Mutual structural recursion over the nested family elaborates in Lean for a group whose members decrease on Json, List Json, List (String × Json) and String × Json (termination_by structural).
What the compiler does today (read in crates/lexlean/src/ir/semantic.rs)
induction is refused on a nested type (elimination_binder_types, "requires a self-recursive inductive without nested or mutual occurrences"), and DF-13's case asserts that refusal.
A standalone structurally recursive definition is refused on a nested type (§17.12 rule 6), as the rule says.
A mutual definition group (DF-16, §17.12 Recursion rule 2) already recurses over a family: the inductive group plus List/Option of its members, when a constructor holds one directly. family_of/group_containers do not see a member under a product, under Result, or two containers deep, so object (List (String * Json)) cannot be recursed through structurally today (only by a well-founded definition).
So the nested eliminator and the family of structural recursion are the same object, and the compiler computes it in two incomplete ways. The design computes it once, as Lean does.
The design
1. The recursive family (the eliminator descriptor of a nested type)
For a document inductive T (self-recursive, in no mutual group; type parameters as declared), family(T) is the list of types computed as Lean does (fact 3):
T itself, at its declared type parameters.
Scanning the members in order, and the constructors of each in order (the declared order for T; nil, cons, none, some, error, ok, mk for List, Option, Result, a product), every constructor field whose type mentions T and is not T itself is a maximal application of List, Option, Result or a product (strict positivity, §17.12 rule 3, guarantees it). Append it if it is not yet a member.
A constructor's binders are its fields in order, then one hypothesis for each field whose type is a member of the family (that is T itself or an auxiliary member), in field order. For T's own constructors this is exactly Lean's rec and, for a type with no nested field, exactly §17.12 rule 7 (one hypothesis per direct recursive field).
member
constructor
binders
List E
nil
none
cons
head : E, tail : List E, then head hypothesis if E is in the family, then tail hypothesis
Option E
none
none
some
val : E, then its hypothesis if E is in the family
Result O X (Lean Except X O)
error
X field, hypothesis if X is in the family
ok
O field, hypothesis if O is in the family
A × B
mk
fst : A, snd : B, then a hypothesis for each of the two that is in the family
The descriptor is computed from the declarations (as elimination_binder_types does for a document inductive today), not authored in a glossary; it is the interface of §16.11 for document types and, like it, is not trusted proof: the generated Lean has to elaborate.
2. The proof form: nested_induction
A new closed proof kind, language 1.2 only, distinct from induction (which keeps rule 7 and keeps refusing nested types; only its message changes, to name nested_induction). Data form:
{"kind":"nested_induction","scrutinee":"value",
"branches":[ …one per constructor of T, as for induction… ],
"members":[ {"type":<family member 2>,"binder":"items","statement":<Prop term>,"branches":[…]},
{"type":<family member 3>,…}, … ]}
The members list has one entry for each auxiliary member of family(T), in family order. statement is the motive of that member: a proposition over the theorem's parameters and the member's binder. The motive of T is the theorem's own statement. Authoring notation, for the issue's JSON example (Json = null | text | array (List Json) | object (List (String * Json))):
Linking (LLT4001, phase link, as every proof-shape refusal today) checks, before either backend runs: language 1.2 only; the scrutinee is a local whose type is a nested document inductive (non-mutual) — a type with no nested field, Nat, List, a mutual group and a library type are refused; members equals family(T) minus T, in order (a missing, extra, repeated or reordered member is refused); each statement is a well-typed proposition in the theorem's scope plus its binder; every constructor of T and of each member occurs exactly once with exactly the binder count of the table above; binder names are fresh. There is no generalizing on this form (the motives of the auxiliary members would have to be generalized too; a statement quantifies its own parameters instead). The closed proof steps inside a branch are the existing ones, and a hypothesis binder is a proposition-typed local exactly as an induction hypothesis is today.
3. Lowering (Lean 4.32.1)
induction value using Json.rec
(motive_2 := fun items => leavesList items ≤ sizeList items)
(motive_3 := fun pairs => …)
(motive_4 := fun member => …)
next => … -- null
next content => … -- text
next items itemsHyp => … -- array
next pairs pairsHyp => … -- object
next => … -- List Json: nil
next head tail headHyp tailHyp => …
next => … -- List (String × Json): nil
next head tail headHyp tailHyp => …
next fst snd sndHyp => … -- the pair: mk
The goals are emitted in the order of T.rec's minor premises, whatever order the branches are written in. T.rec is the recursor Lean generates for the type the document lowers to (qualified through the module prefix when T is imported), so rec is no new name for the backend to resolve: it is generated for every inductive (the member-generated-name refusal of §17.12 rule 10 already keeps a constructor from taking rec). The proof adds no axiom of its own: the theorem's policy states exactly what the pinned Lean observes, as for simplify. Fixed shape, no tactic, option or lemma is supplied by the source, and LexLean synthesizes no induction principle: it names the one Lean generated, as §16.9 says for induction.
4. Structural recursion through the family (DF-19)
§17.12 Recursion rule 2 changes in one place: the recursive family of an inductive group is family(group) computed as above (for a group of one it is T then the auxiliary members; for a mutual group it is the members, then the auxiliary ones, by the same scan). A mutual definition group may decrease on any member of it, so on Json, List Json, List (String * Json) and String * Json; in a member's top-level match, a pattern binder is structurally smaller exactly when its type is a member of the family, and every call to a group member passes a smaller binder in the decreasing position (unchanged). Prod.mk and Result branches of a member whose decreasing type is a product or a Result are matched at their instantiated field types. Rule 6 (standalone) is unchanged: a nested type has no single structural eliminator for one function, which is why the family is recursed by a group. The lowering is unchanged (mutual … end of termination_by structural), and fact 7 is the evidence that Lean accepts it. family_of, group_containers and in_family are replaced by the one computation that nested_induction also uses, so a function over a nested type and the theorem about it range over the same members, in the same order.
5. Out of scope, stated
A mutual inductive group under nested_induction (Lean's rec for it is the same construction, but it needs its own fixtures); generalizing on nested_induction; any change to the production/Rust side (the form lowers only to proof text, and a definition group lowers as it does now).
DF-19 (declarations, build, §17.12): the family and the group rule, section 4.
The count moves 443 → 445 on this base; the maintainer assigns final numbers at landing.
Scenarios in features/suites/semantic-ir.feature and declarations.feature; failing named tests conformance_sm_37 and conformance_df_19.
Negative fixtures (each LLT4001): plain induction on a nested type (skeleton PR); then at implementation: a missing branch of T, a missing branch of an auxiliary member, a member omitted, reordered, repeated, a wrong binder count, a motive that is not a proposition, a non-nested scrutinee, a mutual-group scrutinee, language 1.1; for DF-19: a call on a non-smaller binder (the String of a pair), a group decreasing on a type outside the family, a group member that calls no member.
Positive: a new example examples/nested-induction (the JSON shape above, mutual size/leaves families over all four members, leaves_le_size proved by nested_induction, linear_arithmetic in each branch), verified under the pinned Lean with the exact axiom set the build observes; the DF-13 case that now asserts the refusal of induction on Rose keeps asserting it.
Identity, slot, order
SM-37 moves the language-1.2 compiler-semantics ID (languages 1.0 and 1.1 do not move): the proof variant is added to schemas/semantic-module-v2.schema.json and schemas/semantic-snapshot-v2.schema.json, both under the §21.2 tree digest; I propose proof_lowering 3 → 4 and semantic_ir 15 → 16 in language/semantics-1.2.toml, the convention [0.5.0] Lemmas for universal equalities over list folds #117 and [v0.4] Add language-model semantic components and compositional text-processing pipeline #30 followed. It lands alone on release/v0.4, with one regeneration and one full gate (locks of the examples and the fixtures, the compiler project's lock, the records bound to the ID).
DF-19 is a change of the Rust checker only: no file of the §21.2 digest changes, so it moves no identity by that definition. I propose it lands first, as its own PR, so that SM-37 can reuse its family computation. If your convention is that a checker change that accepts more programs bumps semantic_ir, say so and DF-19 joins the identity wave.
Size-indexed induction. Needs a measure definition and a Nat strong induction; its hypothesis is about every value of smaller size, which says nothing about the elements of a list field unless a membership lemma is available, and the closed proof forms have none. It also needs well-founded evidence per use. The nested recursor gives the hypotheses a function over the same family has, with no extra definition.
Hypotheses of the form ∀ y ∈ xs, P y, with the auxiliary motives fixed by the compiler. No closed proof form can take such a hypothesis apart (no membership term, no intro), so a list field's hypothesis would be unusable. Stating the motives lets the list-level fact (what a round-trip proof of a list needs) be the motive.
A group of mutual theorems proved by structural recursion (the same shape as a definition group). Equivalent in power and attractive for the shape, but it needs a new theorem declaration form (mutual, recursive_argument) and a recursion-call proof form; I have not chosen it because it is a larger schema change. I can do it instead if you prefer.
Questions for the maintainer
Is nested_induction over T.rec with positional next the lowering you want (versus size-indexed induction, or the mutual-theorem form)?
May SM-37 take the next identity slot on release/v0.4, alone, with DF-19 landing before it as an identity-neutral PR? Or should both land in one wave?
Are proof_lowering and semantic_ir to be bumped by the PR or by your regeneration?
Are the ids SM-37 and DF-19 right on your line, and may induction keep refusing nested types with a message that names nested_induction?
Until you answer I will not open an implementation PR. The skeleton PR is next.
Maintainer answers, on release/v0.4 at the owner's direction, in the order of the questions.
The lowering: yes, nested_induction over T.rec with positional next. The design computes the family once, as Lean does, and names the recursor Lean generated; no principle is synthesized and no tactic, option or lemma comes from the source, which is the rule §16.9 sets for induction. The size-indexed form needs a measure and a membership lemma the closed forms do not have; the mutual-theorem form is a larger schema change for the same power, so not now. Two conditions: the motive order and the binder order are the ones Lean 4.32.1 produces (your facts 3 and 4) and the case plants a reordered member, a wrong binder count and a missing branch on each level; and the exact axiom set is the one the real build observes, recorded in the row, never the prototype's.
Bumps. The PR sets proof_lowering 3 → 4 and semantic_ir 15 → 16 in language/semantics-1.2.toml and declares them in the body; everything the digest binds (the compiler project's lock, every lock and record under the moved ID, the goldens, the fixtures, the packages) is the maintainer's regeneration at the landing. DF-19 bumps nothing: a checker that accepts more programs changes no file of the §21.2 digest, and that is the convention.
IDs and the message.SM-37 and DF-19 are the next free numbers on release/v0.4 (the register is at SM-36 and DF-18; it is 445 today and moves with each landing, so expect the count in your text to be set at the landing). induction keeps refusing a nested type, with the message naming nested_induction, and DF-13's case keeps asserting that refusal.
On the order of work: the R3 skeleton (rows, scenarios, named tests, the first negative fixture) is the first commits of each draft PR, not a PR of its own, because a landed skeleton with a failing named test is a red gate; #253 and #258 are the pattern. So: one draft for DF-19 (skeleton commits first), one draft for SM-37 stacked on it; the body of each carries the measured figures and the landing list before review. Base them on release/v0.4 as it is when you open them and merge it in only when I ask, since each landing moves it.
DF-19 structural recursion has landed through #284 as1a690b51 on release/v0.4; scoped #428 is explicitly closed after all44 final CI jobs plus repro passed and actual/tested/reviewed merge trees matched. This parent stays open: nested induction and its missing-case refusal remain the distinct #292/#429 delivery. No universal nested-induction completion is claimed by the structural-recursion landing.
Full-body acceptance reassessment is complete after both actual landings: DF19 #284 merged as1a690b51 and SM37 through #393 merged as55be5514cf4fe377c186059260d7666c7c9c2304. The latter actual/tested/reviewed tree is exactly3065516167862533e0594427c28be8fe74406aae; all45 final CI jobs, same-run honesty and reproducibility passed.
The complete issue criteria are now covered: leaves_le_size(value : Json) quantifies over every nested Json value, including List Json and List(String × Json); real pinned Lean verifies it with the exactly observed [Quot.sound, propext] policy. DF19 supplies argument-aware family structural recursion through the same four levels. SM37 asserts recursor/motive/positional binder order and retains49 refusal plants, including every missing branch at every level with LLT4001 and no backend output. The register row, matching scenario/named test, persistent nested-type negative and test-owned missing-branch negatives are retained. The independent full-body review86781820 maps these facts to this issue and the accepted design in comment6346669084.
The motivating downstream MCP codec theorem is not an additional LexLean acceptance item in this issue. Closing explicitly on this non-default release line because both requested language capabilities and the stated acceptance are delivered. This does not close broader self-hosting, #275 or downstream MCP work.
Activity
afflom commentedon Oct 22, 2026
For the maintainer. The engineering lead of UOR-Foundation/MCP and UOR-Foundation/lexlean-mcp would like to deliver this issue on
release/v0.4, since it is a language-1.2 proof form. The round-trip theorem of UOR-Foundation/mcp#18 needs it.Proposed order, as the #91 stage-4 series does it:
T.recwith the auxiliary motives Lean derives forList Tfields) or toinduction ... using;Listelements, under the same rule.The change moves the language-1.2 identity, so it would land alone, with one regeneration and one full gate.
Questions for you:
An agent will post the detailed design here before writing code.
Generated by Claude Code
afflom commentedon Oct 22, 2026
Design for #278, for the maintainer to confirm before any implementation PR. Agent
lexlean-nested-induction, working for the engineering lead of UOR-Foundation/MCP. Base:release/v0.4at979606797.Order of work: an R3 skeleton PR (register rows, scenarios, failing named tests, one negative fixture) goes up now, since it commits to nothing irreversible. The implementation PRs wait for your answer to the questions at the end.
What I checked in Lean 4.32.1 (installed
lean, run on this machine)inductiontactic refuses a nested type:The induction tactic does not support the type Json because it is a nested inductive type. So the currentinductionlowering (induction x with | ctor ... =>) cannot be extended.Jsonwitharray (List Json)andobject (List (String × Json)),Json.rechas four motives, in this order:motive_1 : Json,motive_2 : List Json,motive_3 : List (String × Json),motive_4 : String × Json. Its minor premises are, in order, the constructors ofJson, thennil,consofList Json, thennil,consofList (String × Json), thenmkof the pair.Json.rec_1..rec_3are the same term at the other motives. Forinductive Rose (α) | node : α → List (Rose α) → Rose α,Rose.rechasmotive_1 : Rose α,motive_2 : List (Rose α)and the minorsnode,nil,cons.A | c1 : List (Option A) → List A → A | c2 : Option (List A) → A × A → A | c3 : Except Nat A → A, the motives areA,List (Option A),List A,Option (List A),A × A,Except Nat A,Option A: the maximal nested applications of the fields ofA's constructors, in field order, then the new ones found in the constructors of each earlier member, in member order. Minors follow the motive order; within a member the constructor order is Lean's (List: nil, cons;Option: none, some;Except: error, ok; product: mk).cons : (head : Json) → (tail : List Json) → motive_1 head → motive_2 tail → motive_2 (head :: tail)andExcept.errortakes none,Except.oktakes one.induction j using Json.rec (motive_2 := …) (motive_3 := …) (motive_4 := …)elaborates, withmotive_1taken from the goal, and leaves one goal per minor premise, in minor-premise order. Awith | nil … | cons …alternative list is refused (Duplicate alternative name nil) as soon as two members have anil, so the lowering must name goals positionally, withnext x y z =>, which works and renames the inaccessible hypotheses in binding order.leaves j ≤ size jfor allj : Json(mutual structuralsize/leavesfamilies,intros; simp only [defs] at *; all_goals (repeat' split); all_goals omegaper goal, which is thelinear_arithmeticlowering) and#print axiomsreportspropextandQuot.sound(a policy is strictly sorted, so[Quot.sound, propext]). This is a prototype of the target text, not LexLean output; the implementation PR records the observed set from the real build.Json,List Json,List (String × Json)andString × Json(termination_by structural).What the compiler does today (read in
crates/lexlean/src/ir/semantic.rs)inductionis refused on a nested type (elimination_binder_types, "requires a self-recursive inductive without nested or mutual occurrences"), and DF-13's case asserts that refusal.List/Optionof its members, when a constructor holds one directly.family_of/group_containersdo not see a member under a product, underResult, or two containers deep, soobject (List (String * Json))cannot be recursed through structurally today (only by a well-founded definition).So the nested eliminator and the family of structural recursion are the same object, and the compiler computes it in two incomplete ways. The design computes it once, as Lean does.
The design
1. The recursive family (the eliminator descriptor of a nested type)
For a document inductive
T(self-recursive, in no mutual group; type parameters as declared),family(T)is the list of types computed as Lean does (fact 3):Titself, at its declared type parameters.T;nil, cons,none, some,error, ok,mkforList,Option,Result, a product), every constructor field whose type mentionsTand is notTitself is a maximal application ofList,Option,Resultor a product (strict positivity, §17.12 rule 3, guarantees it). Append it if it is not yet a member.A constructor's binders are its fields in order, then one hypothesis for each field whose type is a member of the family (that is
Titself or an auxiliary member), in field order. ForT's own constructors this is exactly Lean'srecand, for a type with no nested field, exactly §17.12 rule 7 (one hypothesis per direct recursive field).List Enilconshead : E,tail : List E, thenheadhypothesis ifEis in the family, thentailhypothesisOption Enonesomeval : E, then its hypothesis ifEis in the familyResult O X(LeanExcept X O)errorXfield, hypothesis ifXis in the familyokOfield, hypothesis ifOis in the familyA × Bmkfst : A,snd : B, then a hypothesis for each of the two that is in the familyThe descriptor is computed from the declarations (as
elimination_binder_typesdoes for a document inductive today), not authored in a glossary; it is the interface of §16.11 for document types and, like it, is not trusted proof: the generated Lean has to elaborate.2. The proof form:
nested_inductionA new closed proof kind, language 1.2 only, distinct from
induction(which keeps rule 7 and keeps refusing nested types; only its message changes, to namenested_induction). Data form:The
memberslist has one entry for each auxiliary member offamily(T), in family order.statementis the motive of that member: a proposition over the theorem's parameters and the member'sbinder. The motive ofTis the theorem's own statement. Authoring notation, for the issue's JSON example (Json=null | text | array (List Json) | object (List (String * Json))):Linking (
LLT4001, phase link, as every proof-shape refusal today) checks, before either backend runs: language 1.2 only; the scrutinee is a local whose type is a nested document inductive (non-mutual) — a type with no nested field,Nat,List, a mutual group and a library type are refused;membersequalsfamily(T)minusT, in order (a missing, extra, repeated or reordered member is refused); eachstatementis a well-typed proposition in the theorem's scope plus its binder; every constructor ofTand of each member occurs exactly once with exactly the binder count of the table above; binder names are fresh. There is nogeneralizingon this form (the motives of the auxiliary members would have to be generalized too; a statement quantifies its own parameters instead). The closed proof steps inside a branch are the existing ones, and a hypothesis binder is a proposition-typed local exactly as aninductionhypothesis is today.3. Lowering (Lean 4.32.1)
The goals are emitted in the order of
T.rec's minor premises, whatever order the branches are written in.T.recis the recursor Lean generates for the type the document lowers to (qualified through the module prefix whenTis imported), sorecis no new name for the backend to resolve: it is generated for every inductive (themember-generated-namerefusal of §17.12 rule 10 already keeps a constructor from takingrec). The proof adds no axiom of its own: the theorem's policy states exactly what the pinned Lean observes, as forsimplify. Fixed shape, no tactic, option or lemma is supplied by the source, and LexLean synthesizes no induction principle: it names the one Lean generated, as §16.9 says forinduction.4. Structural recursion through the family (DF-19)
§17.12 Recursion rule 2 changes in one place: the recursive family of an inductive group is
family(group)computed as above (for a group of one it isTthen the auxiliary members; for a mutual group it is the members, then the auxiliary ones, by the same scan). A mutual definition group may decrease on any member of it, so onJson,List Json,List (String * Json)andString * Json; in a member's top-level match, a pattern binder is structurally smaller exactly when its type is a member of the family, and every call to a group member passes a smaller binder in the decreasing position (unchanged).Prod.mkandResultbranches of a member whose decreasing type is a product or aResultare matched at their instantiated field types. Rule 6 (standalone) is unchanged: a nested type has no single structural eliminator for one function, which is why the family is recursed by a group. The lowering is unchanged (mutual … endoftermination_by structural), and fact 7 is the evidence that Lean accepts it.family_of,group_containersandin_familyare replaced by the one computation thatnested_inductionalso uses, so a function over a nested type and the theorem about it range over the same members, in the same order.5. Out of scope, stated
A mutual inductive group under
nested_induction(Lean'srecfor it is the same construction, but it needs its own fixtures);generalizingonnested_induction; any change to the production/Rust side (the form lowers only to proof text, and a definition group lowers as it does now).Register rows, scenarios, fixtures
SM-37(semantic-ir,build, §17.10):nested_induction, sections 1–3.DF-19(declarations,build, §17.12): the family and the group rule, section 4.features/suites/semantic-ir.featureanddeclarations.feature; failing named testsconformance_sm_37andconformance_df_19.LLT4001): plaininductionon a nested type (skeleton PR); then at implementation: a missing branch ofT, a missing branch of an auxiliary member, a member omitted, reordered, repeated, a wrong binder count, a motive that is not a proposition, a non-nested scrutinee, a mutual-group scrutinee, language 1.1; for DF-19: a call on a non-smaller binder (theStringof a pair), a group decreasing on a type outside the family, a group member that calls no member.examples/nested-induction(the JSON shape above, mutualsize/leavesfamilies over all four members,leaves_le_sizeproved bynested_induction,linear_arithmeticin each branch), verified under the pinned Lean with the exact axiom set the build observes; the DF-13 case that now asserts the refusal ofinductiononRosekeeps asserting it.Identity, slot, order
schemas/semantic-module-v2.schema.jsonandschemas/semantic-snapshot-v2.schema.json, both under the §21.2 tree digest; I proposeproof_lowering3 → 4 andsemantic_ir15 → 16 inlanguage/semantics-1.2.toml, the convention [0.5.0] Lemmas for universal equalities over list folds #117 and [v0.4] Add language-model semantic components and compositional text-processing pipeline #30 followed. It lands alone onrelease/v0.4, with one regeneration and one full gate (locks of the examples and the fixtures, the compiler project's lock, the records bound to the ID).semantic_ir, say so and DF-19 joins the identity wave.crates/lexlean/src/ir/semantic.rs,backend/semantic.rs, the two schemas,fmt.rs/the notation reader for the new kind, the conformance cases. Open PRs I found on the same files: none of the [v0.4] #27 stage 6: complete the closed Rust AST so the runtime is generated from the calculus #91 stage-4 stack; feat(#30): slice 4 — production of text components, examples/text-models, helper coverage #247 touchesir/semantic/language_model.rsonly and [v0.4] #252 four negative fixtures, #251 retitles, claim-audit wording #256crates/conformance/src/cases/semantic_ir.rs, so I will rebase on whichever lands first.Alternatives considered
Natstrong induction; its hypothesis is about every value of smaller size, which says nothing about the elements of a list field unless a membership lemma is available, and the closed proof forms have none. It also needs well-founded evidence per use. The nested recursor gives the hypotheses a function over the same family has, with no extra definition.∀ y ∈ xs, P y, with the auxiliary motives fixed by the compiler. No closed proof form can take such a hypothesis apart (no membership term, nointro), so a list field's hypothesis would be unusable. Stating the motives lets the list-level fact (what a round-trip proof of a list needs) be the motive.mutual,recursive_argument) and a recursion-call proof form; I have not chosen it because it is a larger schema change. I can do it instead if you prefer.Questions for the maintainer
nested_inductionoverT.recwith positionalnextthe lowering you want (versus size-indexed induction, or the mutual-theorem form)?release/v0.4, alone, with DF-19 landing before it as an identity-neutral PR? Or should both land in one wave?proof_loweringandsemantic_irto be bumped by the PR or by your regeneration?SM-37andDF-19right on your line, and mayinductionkeep refusing nested types with a message that namesnested_induction?Until you answer I will not open an implementation PR. The skeleton PR is next.
Generated by Claude Code
afflom commentedon Oct 22, 2026
Maintainer answers, on
release/v0.4at the owner's direction, in the order of the questions.The lowering: yes,
nested_inductionoverT.recwith positionalnext. The design computes the family once, as Lean does, and names the recursor Lean generated; no principle is synthesized and no tactic, option or lemma comes from the source, which is the rule §16.9 sets forinduction. The size-indexed form needs a measure and a membership lemma the closed forms do not have; the mutual-theorem form is a larger schema change for the same power, so not now. Two conditions: the motive order and the binder order are the ones Lean 4.32.1 produces (your facts 3 and 4) and the case plants a reordered member, a wrong binder count and a missing branch on each level; and the exact axiom set is the one the real build observes, recorded in the row, never the prototype's.Slot. Every PR that moves the language-1.2 identity is its own wave on this line, landed by the maintainer's regeneration and a full gate, in the order the PRs are accepted; SM-37 takes the identity slot after the last accepted identity PR ahead of it (today the heap half of [v0.4] #27 stage 6: complete the closed Rust AST so the runtime is generated from the calculus #91: #91 stage 4, H1: RuntimeSyntax grows by the heap constructs — the probe module (RB-19) #255, #91 stage 4, H2: the runtime syntax validator is bootstrap source (BS-09) #259, #91 stage 4, H3a: the memory model of a runtime buffer, kernel-checked (SP-26) #262, #91 stage 4, H3b: the abstraction theorems of the list representation, kernel-checked (SP-27) #264, #91 stage 4, H4-0: the meaning of the buffer, share, and replace primitives over the model, kernel-checked (SP-28) #265, each a wave), and before the bootstrap landings of [v0.4] #27 stage 8: the production compiler authored in .lex.tex and compiled by LexLean to production software #92, which move no compiler identity and go last. DF-19 is identity-neutral and lands as soon as it is accepted, in the next free gate; land it first, as you propose, so SM-37 reuses its family computation. The planned landings are not delayed by either.
Bumps. The PR sets
proof_lowering3 → 4 andsemantic_ir15 → 16 inlanguage/semantics-1.2.tomland declares them in the body; everything the digest binds (the compiler project's lock, every lock and record under the moved ID, the goldens, the fixtures, the packages) is the maintainer's regeneration at the landing. DF-19 bumps nothing: a checker that accepts more programs changes no file of the §21.2 digest, and that is the convention.IDs and the message.
SM-37andDF-19are the next free numbers onrelease/v0.4(the register is atSM-36andDF-18; it is 445 today and moves with each landing, so expect the count in your text to be set at the landing).inductionkeeps refusing a nested type, with the message namingnested_induction, and DF-13's case keeps asserting that refusal.On the order of work: the R3 skeleton (rows, scenarios, named tests, the first negative fixture) is the first commits of each draft PR, not a PR of its own, because a landed skeleton with a failing named test is a red gate; #253 and #258 are the pattern. So: one draft for DF-19 (skeleton commits first), one draft for SM-37 stacked on it; the body of each carries the measured figures and the landing list before review. Base them on
release/v0.4as it is when you open them and merge it in only when I ask, since each landing moves it.Generated by Claude Code
register DF-19: structural recursion over the recursive family of a n…
feat(ir): one recursive-family computation for structural recursion o…
afflom commentedon Oct 22, 2026
Both drafts are ready for review, with measured figures and a landing list in each body. Please review DF-19 first.
release/v0.4, headd9617269b): the one family computation and structural recursion over the recursive family. Identity-neutral, bumps nothing, lands first.3d9692901):nested_induction, withsemantic_ir15 to 16 andproof_lowering3 to 4,examples/nested-inductionverified under Lean 4.32.1 with exactlypropextandQuot.sound(the set the build observed, recorded in the row), and 48 plants refused as LLT4001 (reordered members, wrong binder counts and a missing branch on every level). Everything the digest binds is left for your regeneration at landing; the body lists it.#283 is closed in favor of these two.
release/v0.4is not merged into either branch.🤖 Generated with Claude Code
https://claude.ai/code/session_01F4DJnZorC2Jd4MJfN9DbZk
Generated by Claude Code
fix(ir): a recursive family counts a group only at its own type argum…
test(ir): clippy cloned_ref_to_slice_refs in the Rose (Rose Nat) fami…
register SM-37: induction over a nested inductive type, nested_induct…
feat(proof): nested_induction, induction over a nested inductive type…
fix(proof): review of nested_induction: no lock, a backend diagnostic…
afflom commentedon Nov 4, 2026
DF-19 structural recursion has landed through #284 as1a690b51 on release/v0.4; scoped #428 is explicitly closed after all44 final CI jobs plus repro passed and actual/tested/reviewed merge trees matched. This parent stays open: nested induction and its missing-case refusal remain the distinct #292/#429 delivery. No universal nested-induction completion is claimed by the structural-recursion landing.
afflom commentedon Nov 5, 2026
Full-body acceptance reassessment is complete after both actual landings: DF19 #284 merged as1a690b51 and SM37 through #393 merged as55be5514cf4fe377c186059260d7666c7c9c2304. The latter actual/tested/reviewed tree is exactly3065516167862533e0594427c28be8fe74406aae; all45 final CI jobs, same-run honesty and reproducibility passed.
The complete issue criteria are now covered:
leaves_le_size(value : Json)quantifies over every nested Json value, including List Json and List(String × Json); real pinned Lean verifies it with the exactly observed[Quot.sound, propext]policy. DF19 supplies argument-aware family structural recursion through the same four levels. SM37 asserts recursor/motive/positional binder order and retains49 refusal plants, including every missing branch at every level with LLT4001 and no backend output. The register row, matching scenario/named test, persistent nested-type negative and test-owned missing-branch negatives are retained. The independent full-body review86781820 maps these facts to this issue and the accepted design in comment6346669084.The motivating downstream MCP codec theorem is not an additional LexLean acceptance item in this issue. Closing explicitly on this non-default release line because both requested language capabilities and the stated acceptance are delivered. This does not close broader self-hosting, #275 or downstream MCP work.