Lemma 9: Diagonalization of binary multivariate basic functions
ProvedHofmannMoser.lemma_9This is Lemma 9 of Hofmann and Moser (TLCA 2015, p. 248), showing that evaluating a binary multivariate basic function on a duplicated argument yields a unary basic function.
Let be a finite nonempty constructor signature (FiniteConstructors C), and let (p : Fin 2 → BasicFunction C) be a pair of basic resource functions with multivariate evaluation (multivariateBasic p (fun _ ↦ v)). Then there exists a unary basic resource function (p' : BasicFunction C) such that for every ground constructor value (Value C),
This lemma justifies contracting shared variables in resource annotations via the sharing operator (Lemma 13) and the typing rule Typing.share.
import Definitions.Def_HofmannMoser_Potential universe u
namespace HofmannMoser
theorem lemma_9 {C : Nat → Type u} (S : FiniteConstructors C)
(p : Fin 2 → BasicFunction C) :
∃ p' : BasicFunction C, ∀ v : Value C,
multivariateBasic p (fun _ ↦ v) = p'.val v := by sorry
end HofmannMoserRead-back
What the Lean code literally says, in plain math · gemini-2.5-pro
Let be an arity-indexed family of constructor symbol types in universe . Suppose we are given:
- , a structure consisting of a finite list of dependent pairs containing every constructor for every , together with a proof that ;
- a pair of basic functions .
Here:
- is the inductive type of finite constructor trees over .
- A basic function is a function paired with an existential proof that for some tree automaton , where has a positive state count , a final state , and duplicate-free finite transition lists (supported on finitely many and nonempty for at least one ), and where is defined recursively by
- For any -tuple of basic functions and -tuple of values , is the left-folded product starting from . For and the constant pair , this is .
This theorem asserts that there exists a basic function such that for every value ,
Edge and degenerate cases:
- The conclusion uses plain existential quantification (, not unique existence), and does not depend on any representation policy in its statement.
- If is empty, is uninhabited so the pointwise equality holds vacuously for any , though exhibiting an inhabitant of still requires constructing a valid (for which provides
finite_rulesandhas_rule).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.