Theorem 5.8 — Soundness of AARA
OpenGrodin2026.Revised.theorem_5_8Let be a typing derivation in the positive AARA fragment. If evaluating it in environment incurs cost and returns , then .
import Definitions.Def_Grodin2026_AARADerivations
namespace Grodin2026.Revised
/-- Theorem 5.8 of Grodin et al. If evaluating a graded AARA typing derivation on an
environment incurs cost `p` and returns `v`, that cost plus the potential of `v` is bounded
by the input environment's potential plus the derivation's grade. -/
theorem theorem_5_8 {Γ A : AARAType} {q : Nat} (d : AARADerivation Γ A q)
(δ : aaraValues Γ) (p : Nat) (v : aaraValues A) (h : d.eval δ = (p, v)) :
p + aaraPotential A v ≤ aaraPotential Γ δ + q := by
sorry
end Grodin2026.RevisedRead-back
What the Lean code literally says, in plain math · OpenAI Codex (GPT-6)
For every pair of type expressions and , every natural-number grade , and every derivation from to of grade , write for the values of a type expression . The available type expressions are free types on arbitrary small types, unit, tensor, sum, fixed-credit types, and list types with one or two natural-number credit coefficients. A free type uses its underlying values, unit has one value, tensor uses ordered pairs, sum uses a disjoint union, a fixed-credit type uses its underlying values, and each list type uses finite lists of element values. Derivations are generated by identity, sequential binding, spending, grade weakening, returning and reading free values, tensor, unit and sum rules, storing and releasing credit, and empty-list, cons and right-fold rules for both list types. The recursive evaluator takes an input in and returns a natural-number cost, given by summing the amounts at the spend rules executed during evaluation, paired with a result in . For every , , and , if then . The natural-number potential is zero for free and unit values, adds the two component potentials for a tensor, uses the selected component’s potential for a sum, and adds the fixed credit to the underlying potential for a fixed-credit type. For a list of length , it adds the potentials of every element occurrence to in the one-coefficient case or to in the two-coefficient case. The grades and costs include zero, both list types give their empty lists zero potential, and the input quantifier is vacuous when is empty.