Theorem 5.7 — Equivalence of the Calf and potential interpretations
OpenGrodin2026.Revised.theorem_5_7Let be any positive AARA type. Its compositional Calf interpretation is isomorphic to , where is the potential function in Figure 2.
import Definitions.Def_Grodin2026_AARATypes
namespace Grodin2026.Revised
/-- Theorem 5.7 of Grodin et al. For every positive AARA type, its compositional Calf
interpretation is equivalent to the potential type built from the value set and Figure 2
potential function. -/
theorem theorem_5_7 (A : AARAType) :
Nonempty (CompEquiv (interpPositiveAARA A)
(PotentialType (aaraValues A) (aaraPotential A))) := by
sorry
end Grodin2026.RevisedRead-back
What the Lean code literally says, in plain math · OpenAI Codex (GPT-6)
For every type expression built from free types on arbitrary small types , a unit type, binary products and disjoint sums, a credit constructor with parameter , and list constructors with parameters or , there exists an isomorphism between the following two computation types. The value type is for a free type, a singleton for the unit type, the product or disjoint sum of the component value types for the two binary constructors, the underlying value type for credit, and the type of finite lists of underlying values for either list constructor. In both computation types the concrete and abstract carriers are , with exactly when and . Charging sends to . In the first computation type, the map from the concrete to the abstract carrier acts on zero-cost inputs by recursion on . Free and unit values are returned at cost zero. A product applies the two component maps at zero input cost, sums their output costs, and pairs the output values. A disjoint sum applies the map for the chosen summand at zero input cost and keeps the tag on the output value. Credit applies the underlying map and adds to its output cost. A list applies the underlying map to each element at zero input cost, keeps the output elements in order, and sums their costs together with a credit on each element. This credit is for the one-parameter list and starts at and increases by at each step for the two-parameter list. The empty list is returned at cost zero. For general input , the map adds to the cost of the zero-cost output for . In the second computation type the map sends to . The natural-valued function is zero on free and unit values, adds the two component potentials on a product, takes the chosen summand’s potential on a disjoint sum, and adds to the underlying potential for credit. On a list of length , it sums the potential of every element occurrence and adds for the one-parameter list or for the two-parameter list, where for or . The isomorphism consists of a forward pair of maps and a reverse pair , acting separately on the concrete and abstract carriers. All four maps preserve order and commute with charging by every natural number. They satisfy and . At each carrier the forward and reverse maps compose to the identity in both orders. Free types may be empty, lists may be empty, and credit parameters may be zero.