Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Affine lambda calculus and reduction

Definition
AehligSchwichtenberg2002V2_Syntax

by kmehltretter82 · Nov 20, 2026 · Mathlib 0df444a (Lean v4.33.1)

implicit-complexitylambda-calculustype-theory

Finite linear types, typed variables, raw terms and affine typing. Eliminations are expressed as applications, with a closed step term in list iteration. Capture-avoiding substitution avoids enclosing binder names. Reduction contracts the eight conversions and descends into either side of an application.

Definition code
import Std

/-!
# Syntax, Typing, and Reductions for Aehlig–Schwichtenberg (2002, Sections 2–3), V2

V2 differs from V1 only in `substTerm`: renamed binders also avoid every enclosing binder
(see `substAux`). V1 could rename the inner binder of a tensor elimination to the outer one,
which made substitution and subject reduction fail.

Source: Klaus Aehlig and Helmut Schwichtenberg,
"A syntactical analysis of non-size-increasing polynomial time computation",
*Proceedings of the 15th IEEE Symposium on Logic in Computer Science (LICS 2000)*, pp. 84–91;
expanded version in *ACM Transactions on Computational Logic* 3(3), 2002, pp. 383–401
(arXiv:cs/0011037v2), Sections 2–3 (pp. 3–9).

This module formalizes:
- Definition 2.1: Finite linear types (`Ty`).
- Definition 2.2 & 2.3: Raw terms (`Term`) and constructor symbols (`Constructor`).
- Definition 2.4: Context-indexed affine linear typing `HasType Γ t τ` (`Γ ⊢ t^τ`), where
  eliminations for `×`, `B`, `⊗`, and `L(τ)` are written in application notation.
- Definition 3.1, 3.2, 3.3: Lists (`listEntryCount`, `IsListTerm`), conversions (`ConvStep`),
  one-step and multi-step reduction (`RedStep`, `RedStar`, `RedSteps`), normal forms (`IsNormal`),
  and almost closed terms (`IsAlmostClosed`).
-/

namespace AehligSchwichtenberg2002V2

/-- Definition 2.1 (Finite types, p. 3):
`ρ, τ ::= ⋄ | B | τ ⊸ ρ | τ ⊗ ρ | τ × ρ | L(τ)`. -/
inductive Ty where
  | diamond : Ty
  | bool : Ty
  | lolli : Ty → Ty → Ty
  | tensor : Ty → Ty → Ty
  | prod : Ty → Ty → Ty
  | list : Ty → Ty
  deriving DecidableEq, Repr

namespace Ty

/-- Binary numerals `L(B)` (Section 2, p. 3 & Corollary 4.9, p. 14). -/
def bin : Ty := .list .bool

/-- Iterated linear function type `τ₁ ⊸ ⋯ ⊸ τₙ ⊸ ρ`. -/
def lolliMany : List Ty → Ty → Ty
  | [], ρ => ρ
  | τ :: τs, ρ => .lolli τ (lolliMany τs ρ)

end Ty

/-- Typed variable `x^τ` (Section 2, p. 4). -/
structure Var where
  id : Nat
  ty : Ty
  deriving DecidableEq, Repr

/-- Definition 2.3 (Constructor symbols, p. 4):
`tt : B`, `ff : B`, `nil_τ : L(τ)`, `cons_τ : ⋄ ⊸ τ ⊸ L(τ) ⊸ L(τ)`, `⊗_{τ,ρ} : τ ⊸ ρ ⊸ τ ⊗ ρ`. -/
inductive Constructor where
  | tt : Constructor
  | ff : Constructor
  | nil : Ty → Constructor
  | cons : Ty → Constructor
  | tensorPair : Ty → Ty → Constructor
  deriving DecidableEq, Repr

/-- Type assignment for constructor symbols (Definition 2.3, p. 4). -/
def Constructor.ty : Constructor → Ty
  | .tt => .bool
  | .ff => .bool
  | .nil τ => .list τ
  | .cons τ => .lolli .diamond (.lolli τ (.lolli (.list τ) (.list τ)))
  | .tensorPair τ ρ => .lolli τ (.lolli ρ (.tensor τ ρ))

/-- Definition 2.2 (Terms, p. 4):
`r, s, t ::= x^τ | c | λx^τ. t | ⟨t, s⟩ | t s | {t}`. -/
inductive Term where
  | var : Var → Term
  | const : Constructor → Term
  | lam : Var → Term → Term
  | pair : Term → Term → Term
  | app : Term → Term → Term
  | brace : Term → Term
  deriving DecidableEq, Repr

namespace Term

/-- Multi-argument application `t s₁ ... sₙ`. -/
def appMany : Term → List Term → Term
  | t, [] => t
  | t, s :: ss => appMany (.app t s) ss

end Term

/-- A context `Γ` is a finite set of variables (Section 2, p. 4), represented as a list. -/
abbrev Context := List Var

/-- Disjointness of two contexts `Γ₁ ∩ Γ₂ = ∅`. -/
def DisjointCtx (Γ₁ Γ₂ : Context) : Prop :=
  ∀ v, v ∈ Γ₁ → v ∉ Γ₂

/-- Set-extensional union `Γ = Γ₁ ∪ Γ₂` with no disjointness requirement. -/
def IsCtxUnion (Γ₁ Γ₂ Γ : Context) : Prop :=
  ∀ v, v ∈ Γ ↔ (v ∈ Γ₁ ∨ v ∈ Γ₂)

/-- Set-extensional disjoint union `Γ = Γ₁, Γ₂` (Section 2, p. 4:
"For two contexts `Γ₁` and `Γ₂` the notation `Γ₁, Γ₂` stands for the union, expressing that
`Γ₁` and `Γ₂` are disjoint."). -/
def IsDisjointCtxUnion (Γ₁ Γ₂ Γ : Context) : Prop :=
  DisjointCtx Γ₁ Γ₂ ∧ IsCtxUnion Γ₁ Γ₂ Γ

/-- Free variable occurrences of a term `t`. -/
def freeVarOccurrences : Term → List Var
  | .var x => [x]
  | .const _ => []
  | .lam x t => (freeVarOccurrences t).filter (· != x)
  | .pair t s => freeVarOccurrences t ++ freeVarOccurrences s
  | .app t s => freeVarOccurrences t ++ freeVarOccurrences s
  | .brace t => freeVarOccurrences t

/-- Underlying set of free variables `FV(t)` (duplicate-free list). -/
def freeVars (t : Term) : List Var :=
  (freeVarOccurrences t).eraseDups

/-- Cardinality `|FV(t)|` of the set of free variables of `t`. -/
def freeVarCard (t : Term) : Nat :=
  (freeVars t).length

/-- Almost closed terms (Section 3, p. 8): terms with free variables of type `⋄` only. -/
def IsAlmostClosed (t : Term) : Prop :=
  ∀ v ∈ freeVars t, v.ty = .diamond

/-- Closed terms: terms with no free variables. -/
def IsClosed (t : Term) : Prop :=
  freeVars t = []

/-- Maximum variable id occurring anywhere in a term. -/
def maxVarId : Term → Nat
  | .var x => x.id
  | .const _ => 0
  | .lam x t => Nat.max x.id (maxVarId t)
  | .pair t s => Nat.max (maxVarId t) (maxVarId s)
  | .app t s => Nat.max (maxVarId t) (maxVarId s)
  | .brace t => maxVarId t

/-- Rename free occurrences of `x` to `y` in `t`. -/
def renameFreeVar (t : Term) (x y : Var) : Term :=
  match t with
  | .var v => if v == x then .var y else .var v
  | .const c => .const c
  | .lam v body => if v == x then .lam v body else .lam v (renameFreeVar body x y)
  | .pair r s => .pair (renameFreeVar r x y) (renameFreeVar s x y)
  | .app r s => .app (renameFreeVar r x y) (renameFreeVar s x y)
  | .brace r => .brace (renameFreeVar r x y)

/-- Structural size of a raw term used for termination of capture-avoiding substitution. -/
def rawSize : Term → Nat
  | .var _ => 1
  | .const _ => 1
  | .lam _ t => rawSize t + 1
  | .pair t s => rawSize t + rawSize s + 1
  | .app t s => rawSize t + rawSize s + 1
  | .brace t => rawSize t + 1

theorem renameFreeVar_rawSize (t : Term) (x y : Var) :
    rawSize (renameFreeVar t x y) = rawSize t := by
  induction t with
  | var v => simp only [renameFreeVar]; split <;> rfl
  | const c => rfl
  | lam v body ih =>
      simp only [renameFreeVar]
      split
      · rfl
      · simp [rawSize, ih]
  | pair r s ihr ihs => simp [renameFreeVar, rawSize, ihr, ihs]
  | app r s ihr ihs => simp [renameFreeVar, rawSize, ihr, ihs]
  | brace r ihr => simp [renameFreeVar, rawSize, ihr]

/-- Capture-avoiding substitution with an avoidance bound (V2 repair).

When a binder `v` is free in `s`, it is renamed to a fresh `v'` whose identifier exceeds
`bound`, the identifiers of the body and of `s`, and `x.id`. Descending under a binder raises
`bound` past that binder. Hence a renamed binder never coincides with an enclosing binder.
V1 chose the new identifier without `bound`, so the two binders of a tensor elimination
`t (λa. λb. r)` could become equal, which `(⊗⁻)` forbids. -/
def substAux (bound : Nat) (t : Term) (x : Var) (s : Term) : Term :=
  match t with
  | .var v => if v == x then s else .var v
  | .const c => .const c
  | .lam v body =>
      if v == x then
        .lam v body
      else if v ∈ freeVarOccurrences s then
        let freshId := Nat.max bound (Nat.max (maxVarId body) (Nat.max (maxVarId s) x.id)) + 1
        let v' : Var := ⟨freshId, v.ty⟩
        .lam v' (substAux freshId (renameFreeVar body v v') x s)
      else
        .lam v (substAux (Nat.max bound v.id) body x s)
  | .pair r u => .pair (substAux bound r x s) (substAux bound u x s)
  | .app r u => .app (substAux bound r x s) (substAux bound u x s)
  | .brace r => .brace (substAux bound r x s)
termination_by rawSize t
decreasing_by
  all_goals
    simp_wf
    simp [rawSize, renameFreeVar_rawSize]
    try omega

/-- Capture-avoiding substitution `t[s/x]` (Section 2, p. 4 & Definition 3.2, p. 7). -/
def substTerm (t : Term) (x : Var) (s : Term) : Term :=
  substAux 0 t x s

/-- Simultaneous substitution `r[t, s / x, y]` for two distinct variables `x, y`
(used in `⊗_{τ,ρ} t s (λx^τ, y^ρ. r) ↦ r[t, s / x, y]`, Definition 3.2, p. 7). -/
def substTwo (r : Term) (x y : Var) (t s : Term) : Term :=
  if y ∈ freeVarOccurrences t then
    let freshId := Nat.max (maxVarId r) (Nat.max (maxVarId t) (Nat.max (maxVarId s) (Nat.max x.id y.id))) + 1
    let y' : Var := ⟨freshId, y.ty⟩
    substTerm (substTerm (renameFreeVar r y y') x t) y' s
  else
    substTerm (substTerm r x t) y s

/-- Definition 2.4 (Typing `Γ ⊢ t^τ`, pp. 4–5). -/
inductive HasType : Context → Term → Ty → Prop where
  /-- `(Var)`: `Γ, x^τ ⊢ x^τ` -/
  | var {Γ Γ' : Context} (x : Var) :
      IsDisjointCtxUnion Γ [x] Γ' →
      HasType Γ' (.var x) x.ty
  /-- `(Const)`: `Γ ⊢ c^τ` -/
  | const (Γ : Context) (c : Constructor) :
      HasType Γ (.const c) c.ty
  /-- `(⊸⁺)`: from `Γ ∪ {x^τ} ⊢ t^ρ` infer `Γ ⊢ (λx^τ. t)^{τ⊸ρ}` -/
  | lam {Γ Γ' : Context} (x : Var) {t : Term} {ρ : Ty} :
      IsCtxUnion Γ [x] Γ' →
      HasType Γ' t ρ →
      HasType Γ (.lam x t) (.lolli x.ty ρ)
  /-- `(⊸⁻)`: from `Γ₁ ⊢ t^{τ⊸ρ}` and `Γ₂ ⊢ s^τ` infer `Γ₁, Γ₂ ⊢ (t s)^ρ` -/
  | app {Γ₁ Γ₂ Γ : Context} {t s : Term} {τ ρ : Ty} :
      IsDisjointCtxUnion Γ₁ Γ₂ Γ →
      HasType Γ₁ t (.lolli τ ρ) →
      HasType Γ₂ s τ →
      HasType Γ (.app t s) ρ
  /-- `(×⁺)`: from `Γ ⊢ t^τ` and `Γ ⊢ s^ρ` infer `Γ ⊢ ⟨t, s⟩^{τ×ρ}` -/
  | pair {Γ : Context} {t s : Term} {τ ρ : Ty} :
      HasType Γ t τ →
      HasType Γ s ρ →
      HasType Γ (.pair t s) (.prod τ ρ)
  /-- `(×₁⁻)`: from `Γ ⊢ t^{τ×ρ}` infer `Γ ⊢ (t tt)^τ` -/
  | projLeft {Γ : Context} {t : Term} {τ ρ : Ty} :
      HasType Γ t (.prod τ ρ) →
      HasType Γ (.app t (.const .tt)) τ
  /-- `(×₀⁻)`: from `Γ ⊢ t^{τ×ρ}` infer `Γ ⊢ (t ff)^ρ` -/
  | projRight {Γ : Context} {t : Term} {τ ρ : Ty} :
      HasType Γ t (.prod τ ρ) →
      HasType Γ (.app t (.const .ff)) ρ
  /-- `(B⁻)`: from `Γ₁ ⊢ t^B`, `Γ₂ ⊢ s^τ`, `Γ₂ ⊢ r^τ` infer `Γ₁, Γ₂ ⊢ (t ⟨s, r⟩)^τ` -/
  | boolElim {Γ₁ Γ₂ Γ : Context} {t s r : Term} {τ : Ty} :
      IsDisjointCtxUnion Γ₁ Γ₂ Γ →
      HasType Γ₁ t .bool →
      HasType Γ₂ s τ →
      HasType Γ₂ r τ →
      HasType Γ (.app t (.pair s r)) τ
  /-- `(⊗⁻)`: from `Γ₁ ⊢ t^{τ⊗ρ}` and `Γ₂, x^τ, y^ρ ⊢ s^σ` infer `Γ₁, Γ₂ ⊢ (t (λx^τ, y^ρ. s))^σ` -/
  | tensorElim {Γ₁ Γ₂ Γ₂' Γ : Context} {t s : Term} (x y : Var) {σ : Ty} :
      x ≠ y →
      IsDisjointCtxUnion Γ₂ [x, y] Γ₂' →
      IsDisjointCtxUnion Γ₁ Γ₂ Γ →
      HasType Γ₁ t (.tensor x.ty y.ty) →
      HasType Γ₂' s σ →
      HasType Γ (.app t (.lam x (.lam y s))) σ
  /-- `(L(τ)⁻)`: from `Γ ⊢ t^{L(τ)}` and `∅ ⊢ s^{⋄⊸τ⊸ρ⊸ρ}` infer `Γ ⊢ (t {s})^{ρ⊸ρ}` -/
  | listElim {Γ : Context} {t s : Term} {τ ρ : Ty} :
      HasType Γ t (.list τ) →
      HasType [] s (.lolli .diamond (.lolli τ (.lolli ρ ρ))) →
      HasType Γ (.app t (.brace s)) (.lolli ρ ρ)

/-- Definition 3.1 (Lists, p. 7):
Lists `ℓ` (with `n` entries) are terms of the form `cons_τ d₁ a₁ (... (cons_τ dₙ aₙ nil_τ))`. -/
def listEntryCount : Term → Option Nat
  | .const (.nil _) => some 0
  | .app (.app (.app (.const (.cons _)) _) _) l =>
      match listEntryCount l with
      | some k => some (k + 1)
      | none => none
  | _ => none

/-- Predicate asserting that `l` is a list in the sense of Definition 3.1 (p. 7). -/
def IsListTerm (l : Term) : Prop :=
  ∃ n, listEntryCount l = some n

/-- Definition 3.2 (Conversions, p. 7): `t ↦ t'`. -/
inductive ConvStep : Term → Term → Prop where
  | beta (x : Var) (t s : Term) :
      ConvStep (.app (.lam x t) s) (substTerm t x s)
  | projTt (t s : Term) :
      ConvStep (.app (.pair t s) (.const .tt)) t
  | projFf (t s : Term) :
      ConvStep (.app (.pair t s) (.const .ff)) s
  | ifTt (t s : Term) :
      ConvStep (.app (.const .tt) (.pair t s)) t
  | ifFf (t s : Term) :
      ConvStep (.app (.const .ff) (.pair t s)) s
  | tensorBeta (τ ρ : Ty) (t s : Term) (x y : Var) (r : Term) :
      x.ty = τ → y.ty = ρ → x ≠ y →
      ConvStep
        (.app (.app (.app (.const (.tensorPair τ ρ)) t) s) (.lam x (.lam y r)))
        (substTwo r x y t s)
  | iterNil (τ : Ty) (t s : Term) :
      ConvStep (.app (.app (.const (.nil τ)) (.brace t)) s) s
  | iterCons (τ : Ty) (d a l t s : Term) :
      IsListTerm l →
      ConvStep
        (.app (.app (.app (.app (.app (.const (.cons τ)) d) a) l) (.brace t)) s)
        (.app (.app (.app t d) a) (.app (.app l (.brace t)) s))

/-- Definition 3.3 (Reduction `t → t'`, p. 8). -/
inductive RedStep : Term → Term → Prop where
  | conv {t t' : Term} :
      ConvStep t t' → RedStep t t'
  | appLeft {t t' : Term} (s : Term) :
      RedStep t t' → RedStep (.app t s) (.app t' s)
  | appRight (t : Term) {s s' : Term} :
      RedStep s s' → RedStep (.app t s) (.app t s')

/-- Reflexive-transitive closure of reduction `t →* t'`. -/
inductive RedStar : Term → Term → Prop where
  | refl (t : Term) : RedStar t t
  | step {t s u : Term} : RedStep t s → RedStar s u → RedStar t u

/-- Exact `k`-step reduction chain `t →^k t'`. -/
inductive RedSteps : Nat → Term → Term → Prop where
  | zero (t : Term) : RedSteps 0 t t
  | succ {k : Nat} {t s u : Term} :
      RedStep t s → RedSteps k s u → RedSteps (k + 1) t u

/-- A term `t` is normal if there is no `t'` such that `t → t'` (Section 3, p. 8). -/
def IsNormal (t : Term) : Prop :=
  ¬ ∃ t', RedStep t t'

end AehligSchwichtenberg2002V2
Source
Klaus Aehlig and Helmut Schwichtenberg (2002), A syntactical analysis of non-size-increasing polynomial time computation, Definitions 2.1–2.4 and 3.1–3.3. https://arxiv.org/abs/cs/0011037
Read-back

What the Lean code literally says, in plain math · OpenAI Codex (GPT-6)

The types form the freely generated collection with two base types ◊\Diamond◊ and Bool\mathsf{Bool}Bool, binary arrow A⊸BA\multimap BA⊸B, tensor A⊗BA\otimes BA⊗B and product A×BA\times BA×B, and unary list constructor L(A)\mathsf L(A)L(A). Arrow chains associate to the right.

The binary list type is L(Bool)\mathsf L(\mathsf{Bool})L(Bool).

For a list of types [A1,…,Ak][A_1,\ldots,A_k][A1​,…,Ak​] and a result type RRR, the iterated arrow type is A1⊸(⋯⊸(Ak⊸R)⋯ )A_1\multimap(\cdots\multimap(A_k\multimap R)\cdots)A1​⊸(⋯⊸(Ak​⊸R)⋯), with result RRR for an empty list.

A variable xxx consists of a natural-number identifier id⁡(x)\operatorname{id}(x)id(x) and a type AxA_xAx​. Equality compares both entries, so different types may carry the same identifier.

The constructors are tt\mathsf{tt}tt, ff\mathsf{ff}ff, a constructor nilA\mathsf{nil}_AnilA​ and a constructor consA\mathsf{cons}_AconsA​ for every type AAA, and a constructor tpA,B\mathsf{tp}_{A,B}tpA,B​ for every ordered pair of types A,BA,BA,B.

The constants tt\mathsf{tt}tt and ff\mathsf{ff}ff have declared type Bool\mathsf{Bool}Bool. For every type AAA, the constants nilA\mathsf{nil}_AnilA​ and consA\mathsf{cons}_AconsA​ have declared types L(A)\mathsf L(A)L(A) and ◊⊸A⊸L(A)⊸L(A)\Diamond\multimap A\multimap\mathsf L(A)\multimap\mathsf L(A)◊⊸A⊸L(A)⊸L(A). For all types A,BA,BA,B, tpA,B\mathsf{tp}_{A,B}tpA,B​ has declared type A⊸B⊸(A⊗B)A\multimap B\multimap(A\otimes B)A⊸B⊸(A⊗B).

Raw terms are generated by variable nodes for variables, constant nodes for constructors, abstractions λx.r\lambda x.rλx.r with any variable binder and term body, pairs ⟨r,s⟩\langle r,s\rangle⟨r,s⟩ and applications rsrsrs with two term children, and braces {r}\{r\}{r} with one term child. The indices and children can be chosen before any typing judgment is given.

For a term rrr and a list of terms [s1,…,sk][s_1,\ldots,s_k][s1​,…,sk​], successive application gives ((r s1)⋯ ) sk((r\,s_1)\cdots)\,s_k((rs1​)⋯)sk​, associating to the left, and gives rrr when the list is empty.

A context is a list of variables, with the full identifier and type stored at each entry. The list can be empty or contain repeated variables.

Two contexts Γ1,Γ2\Gamma_1,\Gamma_2Γ1​,Γ2​ are disjoint if every variable belonging to Γ1\Gamma_1Γ1​ is absent from Γ2\Gamma_2Γ2​.

A context Γ\GammaΓ is a union of Γ1,Γ2\Gamma_1,\Gamma_2Γ1​,Γ2​ if, for every variable xxx, x∈Γx\in\Gammax∈Γ holds exactly when x∈Γ1x\in\Gamma_1x∈Γ1​ or x∈Γ2x\in\Gamma_2x∈Γ2​. The condition is insensitive to order and multiplicities.

A context Γ\GammaΓ is a disjoint union of Γ1,Γ2\Gamma_1,\Gamma_2Γ1​,Γ2​ if Γ1\Gamma_1Γ1​ and Γ2\Gamma_2Γ2​ have no common variable and, for every variable xxx, x∈Γx\in\Gammax∈Γ holds exactly when x∈Γ1x\in\Gamma_1x∈Γ1​ or x∈Γ2x\in\Gamma_2x∈Γ2​. Repetitions within either operand or the result are permitted.

The free-variable occurrence list of a term is the singleton list of its variable for a variable node and the empty list for a constant. At λx.r\lambda x.rλx.r it takes the free occurrence list of rrr and deletes all entries equal to xxx. At a pair or application it concatenates the occurrence lists of the left and right children in that order. At a brace it uses the occurrence list of its contents.

For every term rrr, the list FV⁡(r)\operatorname{FV}(r)FV(r) removes duplicates from the free-variable occurrence list of rrr, retaining the first occurrence of each distinct variable.

The free-variable cardinality of rrr is the length of FV⁡(r)\operatorname{FV}(r)FV(r), the number of distinct free variables of rrr.

A term rrr is almost closed if every member of FV⁡(r)\operatorname{FV}(r)FV(r) has type ◊\Diamond◊. In particular, this holds whenever FV⁡(r)\operatorname{FV}(r)FV(r) is empty.

A term rrr is closed if FV⁡(r)\operatorname{FV}(r)FV(r) is the empty list.

For a term rrr, M(r)M(r)M(r) is the maximum of 000 and every variable identifier in rrr, including the identifiers of abstraction binders.

For variables x,yx,yx,y and a term rrr, renaming free xxx to yyy in rrr replaces each variable node equal to xxx by yyy, leaves constants as they are and recurses into pairs, applications and braces. At an abstraction with binder xxx it returns that abstraction as it is. At other abstractions it keeps the binder and recurses into the body, which permits the new occurrences of yyy to be bound by an existing binder.

The raw syntax size S(r)S(r)S(r) is 111 for a variable or constant, 111 plus the body size for an abstraction or brace, and 111 plus the sum of the two child sizes for a pair or application.

For every term rrr and variables x,yx,yx,y, the raw syntax size of the result of renaming free xxx to yyy in rrr is S(r)S(r)S(r).

For a natural bound bbb, term rrr, variable xxx and replacement term sss, the substitution auxiliary function replaces a variable node by sss exactly when its variable equals xxx, preserves constants, and recurses with bound bbb into both children of pairs and applications and into the contents of braces. At a binder vvv it returns the whole abstraction if v=xv=xv=x. If v≠xv\ne xv=x and vvv occurs free in sss, it gives the binder a new identifier b′=1+max⁡(b,M(body),M(s),id⁡(x))b'=1+\max(b,M(\text{body}),M(s),\operatorname{id}(x))b′=1+max(b,M(body),M(s),id(x)) and keeps its type. It renames free occurrences of vvv in the body to the new variable, and recurses on the renamed body with bound b′b'b′. In the remaining case it preserves the binder and recurses on the body with bound max⁡(b,id⁡(v))\max(b,\operatorname{id}(v))max(b,id(v)).

Write r[x:=s]r[x:=s]r[x:=s] for substitution of sss for xxx in rrr, starting the auxiliary function with bound 000. A binder may be freshened by this operation even when xxx has no free occurrence in its body.

For terms r,t,sr,t,sr,t,s and variables x,yx,yx,y, the two-variable substitution returns (r[x:=t])[y:=s](r[x:=t])[y:=s](r[x:=t])[y:=s] if yyy is absent from the free occurrences of ttt. If yyy occurs free in ttt, it chooses y′y'y′ of yyy's type and identifier 1+max⁡(M(r),M(t),M(s),id⁡(x),id⁡(y))1+\max(M(r),M(t),M(s),\operatorname{id}(x),\operatorname{id}(y))1+max(M(r),M(t),M(s),id(x),id(y)). It renames free yyy to y′y'y′ in rrr, substitutes ttt for xxx in that result, then substitutes sss for y′y'y′. This function accepts any x,yx,yx,y, including x=yx=yx=y.

The typing relation Γ⊢r:A\Gamma\vdash r:AΓ⊢r:A is generated by the variable rule in any context containing that variable, and the constant rule in any context with the declared constant type. An abstraction λx.r\lambda x.rλx.r has type A⊸BA\multimap BA⊸B in Γ\GammaΓ if xxx has declared type AAA and rrr has type BBB in a union of Γ\GammaΓ and the singleton list [x][x][x]. An application rsrsrs has type BBB in a disjoint union of contexts typing rrr at A⊸BA\multimap BA⊸B and sss at AAA. The pair ⟨r,s⟩\langle r,s\rangle⟨r,s⟩ has type A×BA\times BA×B if rrr has type AAA and sss has type BBB in the same context. A term rrr of product type A×BA\times BA×B gives applications r ttr\,\mathsf{tt}rtt and r ffr\,\mathsf{ff}rff of types AAA and BBB in its context. If rrr has Boolean type and both sss and uuu have type AAA in a shared context disjoint from the context of rrr, then r⟨s,u⟩r\langle s,u\rangler⟨s,u⟩ has type AAA in their disjoint union. For distinct variables x,yx,yx,y of types A,BA,BA,B, respectively, r(λx.λy.s)r(\lambda x.\lambda y.s)r(λx.λy.s) has type CCC in a disjoint union of a context typing rrr at A⊗BA\otimes BA⊗B and a context Δ\DeltaΔ disjoint from [x,y][x,y][x,y], provided sss has type CCC in a union of Δ\DeltaΔ and [x,y][x,y][x,y]. If rrr has type L(A)\mathsf L(A)L(A) and hhh has type ◊⊸A⊸R⊸R\Diamond\multimap A\multimap R\multimap R◊⊸A⊸R⊸R in the empty context, r{h}r\{h\}r{h} has type R⊸RR\multimap RR⊸R in the context of rrr.

The optional list entry count CCC returns 000 on any nilA\mathsf{nil}_AnilA​, returns 1+C(l)1+C(l)1+C(l) on consA d a l\mathsf{cons}_A\,d\,a\,lconsA​dal if C(l)C(l)C(l) returns a number, and is undefined otherwise. It looks at the rightmost tail argument of each fully applied cons\mathsf{cons}cons, permits any parameters AAA on the constructors along that chain, and ignores the contents of the other two arguments.

A term lll qualifies as a list term if there is a natural number nnn such that C(l)C(l)C(l) returns nnn. Constructors with count 000 qualify.

The direct conversions are (λx.r)s⇝r[x:=s](\lambda x.r)s\leadsto r[x:=s](λx.r)s⇝r[x:=s], ⟨r,s⟩ tt⇝r\langle r,s\rangle\,\mathsf{tt}\leadsto r⟨r,s⟩tt⇝r, ⟨r,s⟩ ff⇝s\langle r,s\rangle\,\mathsf{ff}\leadsto s⟨r,s⟩ff⇝s, tt⟨r,s⟩⇝r\mathsf{tt}\langle r,s\rangle\leadsto rtt⟨r,s⟩⇝r and ff⟨r,s⟩⇝s\mathsf{ff}\langle r,s\rangle\leadsto sff⟨r,s⟩⇝s. They also include tpA,B t s (λx.λy.r)\mathsf{tp}_{A,B}\,t\,s\,(\lambda x.\lambda y.r)tpA,B​ts(λx.λy.r) converting to the two-variable substitution in rrr of ttt for xxx and sss for yyy, for distinct x,yx,yx,y with respective types A,BA,BA,B. The iteration conversions are nilA {h} s⇝s\mathsf{nil}_A\,\{h\}\,s\leadsto snilA​{h}s⇝s and consA d a l {h} s⇝h d a (l {h} s)\mathsf{cons}_A\,d\,a\,l\,\{h\}\,s\leadsto h\,d\,a\,(l\,\{h\}\,s)consA​dal{h}s⇝hda(l{h}s), with the latter requiring C(l)C(l)C(l) to return a number. The term arguments in these patterns range over raw terms.

A single step r→sr\to sr→s performs one direct conversion at the root or at a subterm reached by descending through any number of application nodes, on either side of each application.

For any terms r,sr,sr,s, the finite reduction relation r→∗sr\to^* sr→∗s holds exactly when a sequence of zero or more single steps goes from rrr to sss. Its reflexive case is available for every term.

For k∈Nk\in\mathbb Nk∈N and terms r,sr,sr,s, the relation of exactly kkk reductions from rrr to sss holds for k=0k=0k=0 precisely when r=sr=sr=s. For k+1k+1k+1 it holds exactly when a single step takes rrr to a term uuu and exactly kkk reductions go from uuu to sss.

A term is normal if it has no outgoing single step. In particular, abstractions, pairs and braces are normal at the root regardless of their contents.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me