Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Typed lambda syntax and capture-free term-family extraction

Definition
BergerSchwichtenberg1991V2_Syntax

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

lambda-calculusnormalization-by-evaluationtype-theory

The raw syntax of the simply typed lambda calculus, typing, substitution, α\alphaα-equivalence via binding trees, and long β\betaβ-normal forms. Standardization replaces bound names by indexed names derived from binding positions. Extraction chooses a fresh prefix beyond the length of every indexed name in its two samples.

Definition code
import Std

/-!
# Syntax, Long β-Normal Forms, and α-Standardization (Berger–Schwichtenberg 1991, Sections 1–2)

Source: Ulrich Berger and Helmut Schwichtenberg,
"An inverse of the evaluation functional for typed λ-calculus",
*Proceedings of the Sixth Annual IEEE Symposium on Logic in Computer Science (LICS 1991)*,
pp. 203–211, Sections 1–2 (pp. 204–205).

This module formalizes:
- Simple types (`Ty`) built from ground type `o` (`Ty.base`) by `→` (`Ty.arr`).
- Binary indices `k, l ∈ {0,1}*` (`Index`), indexed variables `x_k^ρ`, and general typed
  variables (`Var`).
- Concrete typed λ-terms (`Term`), typing (`HasType`), capture-avoiding substitution (`substTerm`),
  α-conversion (`AlphaEq`), βη-equality (`BetaEtaEq`), and long β-normal forms (`IsLongBetaNormal`,
  `IsLongBetaNeutral`).
- The bound-variable standardization mapping `α_k(r)` (`alphaRename`, p. 204), the term-family
  embedding `EMB : Λ → Λ^{{0,1}*}` (`EMB`, p. 204), and the extraction functional
  `EXTRACT : Λ^{{0,1}*} → Λ` (`EXTRACT`, pp. 204–205).
-/

namespace BergerSchwichtenberg1991V2

/-- Simple types built from a single ground type `o` by `→` (Section 1, p. 204):
`ρ, σ ::= o | ρ → σ`. -/
inductive Ty where
  | base : Ty
  | arr : Ty → Ty → Ty
  deriving DecidableEq, Repr

namespace Ty

/-- Iterated function type `σ₁ → ⋯ → σₖ → τ` associated to the right (p. 204). -/
def arrMany : List Ty → Ty → Ty
  | [], τ => τ
  | σ :: σs, τ => .arr σ (arrMany σs τ)

/-- Argument types `[σ₁, ..., σₖ]` of a type `ρ = σ₁ → ⋯ → σₖ → o`. -/
def argTypes : Ty → List Ty
  | .base => []
  | .arr σ τ => σ :: argTypes τ

end Ty

/-- Finite 0–1 sequence `k ∈ {0, 1}*` used as a binding position index (Section 2, p. 204). -/
abbrev Index := List Bool

/-- The empty 0–1 sequence `ε` (p. 205). -/
def epsIdx : Index := []

/-- The singleton sequence `0` (p. 205). -/
def zeroIdx : Index := [false]

/-- The singleton sequence `1` (p. 204). -/
def oneIdx : Index := [true]

/-- Concatenation `k * l` of 0–1 sequences (p. 204). -/
def appendIdx (k l : Index) : Index := k ++ l

/-- `IsPrefixOf k m` holds if `m = k * l` for some `l ∈ {0, 1}*` ("`m` extends `k`", p. 204). -/
def IsPrefixOf (k m : Index) : Prop :=
  ∃ l : Index, m = k ++ l

/-- Variable identifier: either an indexed variable `x_k` (`k ∈ {0,1}*`, Section 2, p. 204)
or an ordinary named variable `y_n` (`n : Nat`). -/
inductive VarName where
  | indexed : Index → VarName
  | named : Nat → VarName
  deriving DecidableEq, Repr

/-- Typed variable `x^ρ` (Section 1, p. 204). -/
structure Var where
  name : VarName
  ty : Ty
  deriving DecidableEq, Repr

/-- Indexed variable `x_k^ρ` of type `ρ` with index `k ∈ {0, 1}*` (Section 2, p. 204). -/
def indexedVar (ρ : Ty) (k : Index) : Var :=
  ⟨.indexed k, ρ⟩

/-- Concrete typed λ-terms (Section 1, p. 204):
constructed from typed variables `x^ρ` by application `(t^{ρ→σ} r^ρ)^σ` and abstraction
`(λx^ρ. s^σ)^{ρ→σ}`. -/
inductive Term where
  | var : Var → Term
  | app : Term → Term → Term
  | lam : Var → Term → Term
  deriving DecidableEq, Repr

namespace Term

/-- Left-associated iterated application `r s₁ ... sₖ` (Section 1, p. 204). -/
def appMany : Term → List Term → Term
  | r, [] => r
  | r, s :: ss => appMany (.app r s) ss

/-- Iterated lambda abstraction `λx₁ ... xₙ. r`. -/
def lamMany : List Var → Term → Term
  | [], r => r
  | x :: xs, r => .lam x (lamMany xs r)

end Term

/-- Typing relation `r ∈ Λ^ρ` (`HasType r ρ`, Section 1, p. 204). -/
inductive HasType : Term → Ty → Prop where
  | var (x : Var) :
      HasType (.var x) x.ty
  | app {t r : Term} {ρ σ : Ty} :
      HasType t (.arr ρ σ) →
      HasType r ρ →
      HasType (.app t r) σ
  | lam (x : Var) {s : Term} {σ : Ty} :
      HasType s σ →
      HasType (.lam x s) (.arr x.ty σ)

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

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

/-- A term `r` is closed if `FV(r) = ∅`. -/
def IsClosed (r : Term) : Prop :=
  freeVars r = []

/-- List of indices `l ∈ {0, 1}*` such that `x_l^σ` occurs free in `r` for some `σ`
(Section 2, p. 204: `{l ∈ {0,1}* | x_l free in r}`). -/
def freeIndices (r : Term) : List Index :=
  (freeVars r).filterMap (fun v =>
    match v.name with
    | .indexed l => some l
    | .named _ => none)

/-- All variables (both free and bound) occurring in `r`. -/
def allVars : Term → List Var
  | .var x => [x]
  | .app r s => allVars r ++ allVars s
  | .lam x r => x :: allVars r

/-- Maximum named-variable id occurring anywhere in `r`. -/
def maxNamedId : Term → Nat
  | .var ⟨.named n, _⟩ => n
  | .var ⟨.indexed _, _⟩ => 0
  | .app r s => Nat.max (maxNamedId r) (maxNamedId s)
  | .lam ⟨.named n, _⟩ r => Nat.max n (maxNamedId r)
  | .lam ⟨.indexed _, _⟩ r => maxNamedId r

/-- Maximum named-variable id across a list of terms. -/
def maxNamedIdList : List Term → Nat
  | [] => 0
  | t :: ts => Nat.max (maxNamedId t) (maxNamedIdList ts)

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

/-- Structural size of a raw term `r`. -/
def rawSize : Term → Nat
  | .var _ => 1
  | .app r s => rawSize r + rawSize s + 1
  | .lam _ r => rawSize r + 1

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

/-- Capture-avoiding substitution `r[s/x]` (Section 2, p. 204). -/
def substTerm (r : Term) (x : Var) (s : Term) : Term :=
  match r with
  | .var v => if v == x then s else .var v
  | .app t u => .app (substTerm t x s) (substTerm u x s)
  | .lam v body =>
      if v == x then
        .lam v body
      else if v ∈ freeVarOccurrences s then
        let freshId := Nat.max (maxNamedId body) (Nat.max (maxNamedId s) (maxNamedId (.var x))) + 1
        let v' : Var := ⟨.named freshId, v.ty⟩
        .lam v' (substTerm (renameFreeVar body v v') x s)
      else
        .lam v (substTerm body x s)
termination_by rawSize r
decreasing_by
  all_goals
    simp_wf
    simp [rawSize, renameFreeVar_rawSize]
    try omega

/-- Type-respecting simultaneous substitution `θ : Var → Term` (Section 3, p. 205 & Section 4, p. 207). -/
abbrev Substitution := Var → Term

/-- A substitution `θ` is well-typed (`IsWellTypedSubst θ`) if `θ(x^ρ) ∈ Λ^ρ` for every variable `x^ρ`. -/
def IsWellTypedSubst (θ : Substitution) : Prop :=
  ∀ x : Var, HasType (θ x) x.ty

/-- Identity substitution `θ_id(x) = x` (Section 4, p. 208). -/
def idSubst : Substitution := fun x => .var x

/-- Update a substitution `θ[x ↦ t]` (Section 4, p. 207). -/
def updateSubst (θ : Substitution) (x : Var) (t : Term) : Substitution :=
  fun y => if y == x then t else θ y

/-- Apply a simultaneous substitution `rθ` (with capture avoidance via fresh named variables). -/
def applySubst (θ : Substitution) (r : Term) : Term :=
  match r with
  | .var x => θ x
  | .app t u => .app (applySubst θ t) (applySubst θ u)
  | .lam v body =>
      let fvBody := (freeVars body).filter (· != v)
      let imgTerms := fvBody.map θ
      let imgFVs := imgTerms.foldr (fun t acc => freeVarOccurrences t ++ acc) []
      if v ∈ imgFVs then
        let freshId :=
          Nat.max (maxNamedId body)
            (Nat.max (maxNamedId (.var v)) (maxNamedIdList imgTerms)) + 1
        let v' : Var := ⟨.named freshId, v.ty⟩
        .lam v' (applySubst (updateSubst θ v (.var v')) body)
      else
        .lam v (applySubst (updateSubst θ v (.var v)) body)
termination_by rawSize r
decreasing_by
  all_goals
    simp_wf
    simp [rawSize]
    try omega

/-- A term with free variables named and bound variables identified by the path to their
binder. In both applications and abstractions, `0` descends to the first subterm and `1`
descends to the second subterm of an application. -/
inductive BindingTerm where
  | free : Var → BindingTerm
  | bound : Ty → Index → BindingTerm
  | app : BindingTerm → BindingTerm → BindingTerm
  | lam : Ty → BindingTerm → BindingTerm
  deriving DecidableEq, Repr

/-- Look up the path of the innermost binder of a variable in a scope. -/
def binderPath (v : Var) : List (Var × Index) → Option Index
  | [] => none
  | (x, p) :: scope => if v = x then some p else binderPath v scope

/-- Record the binder paths of a term, given the scope and path of its root. -/
def abstractBindings (scope : List (Var × Index)) (p : Index) : Term → BindingTerm
  | .var v =>
      match binderPath v scope with
      | none => .free v
      | some q => .bound v.ty q
  | .app r s =>
      .app (abstractBindings scope (p ++ zeroIdx) r) (abstractBindings scope (p ++ oneIdx) s)
  | .lam x r => .lam x.ty (abstractBindings ((x, p) :: scope) (p ++ zeroIdx) r)

/-- α-equivalence is equality of the trees of binder positions and free variables. -/
def AlphaEq (r s : Term) : Prop :=
  abstractBindings [] [] r = abstractBindings [] [] s

/-- Provable equality `r =_{βη} s` in the typed βη-calculus (Sections 1–2, pp. 203–204). -/
inductive BetaEtaEq : Term → Term → Prop where
  | of_alpha {r s : Term} : AlphaEq r s → BetaEtaEq r s
  | refl (r : Term) : BetaEtaEq r r
  | symm {r s : Term} : BetaEtaEq r s → BetaEtaEq s r
  | trans {r s t : Term} : BetaEtaEq r s → BetaEtaEq s t → BetaEtaEq r t
  | app {r r' s s' : Term} :
      BetaEtaEq r r' → BetaEtaEq s s' → BetaEtaEq (.app r s) (.app r' s')
  | lam (x : Var) {r s : Term} :
      BetaEtaEq r s → BetaEtaEq (.lam x r) (.lam x s)
  | beta (x : Var) (r s : Term) :
      BetaEtaEq (.app (.lam x r) s) (substTerm r x s)
  | eta (x : Var) (r : Term) :
      x ∉ freeVars r →
      BetaEtaEq (.lam x (.app r (.var x))) r

mutual
  /-- Long β-normal forms (Section 2, p. 204):
  `λx₁^{ρ₁} ... λxₙ^{ρₙ}. y^{σ₁ → ⋯ → σₖ → o} s₁^{σ₁} ... sₖ^{σₖ}` with `s₁, ..., sₖ` in
  long β-normal form and body `y s₁ ... sₖ` of ground type `o`. -/
  inductive IsLongBetaNormal : Ty → Term → Prop where
    | baseNeutral {t : Term} :
        IsLongBetaNeutral .base t →
        IsLongBetaNormal .base t
    | lam (x : Var) {σ : Ty} {r : Term} :
        IsLongBetaNormal σ r →
        IsLongBetaNormal (.arr x.ty σ) (.lam x r)

  /-- Neutral spine `y s₁ ... sₖ` whose arguments are in long β-normal form. -/
  inductive IsLongBetaNeutral : Ty → Term → Prop where
    | var (y : Var) :
        IsLongBetaNeutral y.ty (.var y)
    | app {t s : Term} {σ τ : Ty} :
        IsLongBetaNeutral (.arr σ τ) t →
        IsLongBetaNormal σ s →
        IsLongBetaNeutral τ (.app t s)
end

/-- Name every binder and its bound occurrences by prefixing its path with `k`. -/
def nameBindings (k p : Index) : BindingTerm → Term
  | .free v => .var v
  | .bound ρ q => .var (indexedVar ρ (k ++ q))
  | .app r s => .app (nameBindings k (p ++ zeroIdx) r) (nameBindings k (p ++ oneIdx) s)
  | .lam ρ r => .lam (indexedVar ρ (k ++ p)) (nameBindings k (p ++ zeroIdx) r)

/-- The bound-variable standardization `α_k(r)` of Section 2. The prefix `k` is
chosen fresh when an α-variant is needed. -/
def alphaRename (k : Index) (r : Term) : Term :=
  nameBindings k [] (abstractBindings [] [] r)

/-- Section 2 (p. 204): Term family representation `EMB : Λ → (Index → Λ)` defined by
`EMB r k := α_k(r)`. -/
def EMB (r : Term) (k : Index) : Term :=
  alphaRename k r

/-- Maximum length among a list of 0–1 sequences. -/
def maxIdxLength : List Index → Nat
  | [] => 0
  | l :: ls => Nat.max l.length (maxIdxLength ls)

/-- Indices of all variables in a term, including variable occurrences that a sample
standardization may have placed under a binder with the same name. -/
def allIndices (r : Term) : List Index :=
  (allVars r).filterMap (fun v =>
    match v.name with
    | .indexed l => some l
    | .named _ => none)

/-- Pick an all-zero prefix longer than every index in the two samples `F ε` and `F 0`.
Bounding every sampled occurrence gives a conservative bound on the indices of the
unchanged occurrences used by the paper. -/
def canonicalFreshIndex (F : Index → Term) : Index :=
  let len := Nat.max (maxIdxLength (allIndices (F epsIdx)))
                     (maxIdxLength (allIndices (F zeroIdx))) + 1
  List.replicate len false

/-- Section 2 (p. 205): Extraction functional `EXTRACT : Λ^{{0,1}*} → Λ` defined by
`EXTRACT(F) := F(k̂)`. -/
def EXTRACT (F : Index → Term) : Term :=
  F (canonicalFreshIndex F)

end BergerSchwichtenberg1991V2
Source
Ulrich Berger and Helmut Schwichtenberg (1991), An inverse of the evaluation functional for typed lambda-calculus, LICS, pp. 203–211, Sections 1–2, pp. 204–205. https://epub.ub.uni-muenchen.de/4261/1/4261.pdf
Read-back

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

Types, indices and terms

The types are generated by the base type BBB and a binary arrow constructor ρ→σ\rho\to\sigmaρ→σ. For a list of types σ\boldsymbol{\sigma}σ and result type τ\tauτ, iterated arrow construction sends ([],τ)([], \tau)([],τ) to τ\tauτ and (σ::σ,τ)(\sigma::\boldsymbol{\sigma},\tau)(σ::σ,τ) to σ→arrMany⁡(σ,τ)\sigma\to\operatorname{arrMany}(\boldsymbol{\sigma},\tau)σ→arrMany(σ,τ). The argument types of BBB form the empty list. The argument types of σ→τ\sigma\to\tauσ→τ are σ\sigmaσ followed by the argument types of τ\tauτ.

An index is any finite list of Boolean bits. The distinguished indices are ϵ=[]\epsilon=[]ϵ=[], [0][0][0] and [1][1][1], and index append is ordinary list concatenation k∥ℓk\mathbin{\|}\ellk∥ℓ. The prefix predicate for k,mk,mk,m holds exactly when there exists an index ℓ\ellℓ with m=k∥ℓm=k\mathbin{\|}\ellm=k∥ℓ. It allows equality of kkk and mmm and gives the empty index as a prefix of every index.

A variable name is either indexed by such a list or named by a natural number. A variable xxx consists of its name and a type type⁡(x)\operatorname{type}(x)type(x), both of which enter variable equality. Write xρ,kx_{\rho,k}xρ,k​ for the variable with indexed name kkk and type ρ\rhoρ. Raw terms are the occurrence var⁡(x)\operatorname{var}(x)var(x) of a variable, the application r sr\,srs of two raw terms, and the abstraction λx.r\lambda x.rλx.r of a raw term over a variable. Repeated application over an argument list starts with rrr at the empty list and, for a head sss, continues with r sr\,srs on the rest of the list. Repeated abstraction over an empty variable list returns the body. For a head xxx it constructs an outer λx\lambda xλx over the repeated abstraction on the rest of the list.

Typing is the inductively generated relation with the following rules. The term var⁡(x)\operatorname{var}(x)var(x) has type type⁡(x)\operatorname{type}(x)type(x). If ttt has type ρ→σ\rho\to\sigmaρ→σ and rrr has type ρ\rhoρ, then t rt\,rtr has type σ\sigmaσ. If sss has type σ\sigmaσ, then λx.s\lambda x.sλx.s has type type⁡(x)→σ\operatorname{type}(x)\to\sigmatype(x)→σ.

Variables and substitution

The list of free variable occurrences is [x][x][x] for var⁡(x)\operatorname{var}(x)var(x), the concatenation of the two lists for r sr\,srs, and the body's list with every entry equal to xxx filtered out for λx.r\lambda x.rλx.r. The list of free variables is this list with duplicate variables erased. A term is closed exactly when this latter list is empty. The free indices of a term are the indices of the indexed variables in its free-variable list, dropping natural-number names. Different free variables of different types with the same index can contribute that index more than once.

The list of all variables is [x][x][x] for var⁡(x)\operatorname{var}(x)var(x), the left list concatenated with the right list for r sr\,srs, and xxx prepended to the body's list for λx.r\lambda x.rλx.r. It includes binders and repeated occurrences. The maximum natural-number name is the name at a natural-number-named leaf, 000 at an indexed leaf, the maximum of the two maxima at application, the maximum of a natural-number-named binder and the body's maximum at its abstraction, and the body's maximum at an indexed binder. On a list of terms, take the maximum of their maxima, with 000 for the empty list.

Free-variable renaming from xxx to yyy changes the variable vvv at a leaf to yyy if v=xv=xv=x, and otherwise keeps vvv. It recurses in both children at an application. It keeps the binder vvv of λv.r\lambda v.rλv.r, leaving the body intact if v=xv=xv=x and recursing into the body otherwise. This operation accepts arbitrary raw terms and pairs of variables. Raw size gives 111 at a variable, the sum of child sizes plus 111 at an application, and the body size plus 111 at an abstraction. The free-variable renaming theorem states, for every raw rrr and variables x,yx,yx,y, that the raw size after this renaming equals the raw size of rrr.

To substitute sss for xxx in rrr, replace leaf xxx with sss, keep other leaves, and recurse on both children of an application. Under λv.u\lambda v.uλv.u, keep the entire abstraction when v=xv=xv=x. When v≠xv\ne xv=x and vvv occurs free in sss, take the variable v′v'v′ of type type⁡(v)\operatorname{type}(v)type(v) with natural-number name 1+max⁡(maxNamedId⁡(u),maxNamedId⁡(s),maxNamedId⁡(var⁡(x)))1+\max\bigl(\operatorname{maxNamedId}(u),\operatorname{maxNamedId}(s),\operatorname{maxNamedId}(\operatorname{var}(x))\bigr)1+max(maxNamedId(u),maxNamedId(s),maxNamedId(var(x))). Freely rename vvv to v′v'v′ in uuu, continue the substitution in that renamed body, and abstract over v′v'v′. When v≠xv\ne xv=x and vvv is absent from the free occurrences of sss, continue under the unchanged binder vvv.

A substitution θ\thetaθ is any function from variables to raw terms. It is well typed exactly when θ(x)\theta(x)θ(x) has type type⁡(x)\operatorname{type}(x)type(x) for every xxx. The identity substitution sends xxx to var⁡(x)\operatorname{var}(x)var(x). The update θ[x↦t]\theta[x\mapsto t]θ[x↦t] of any substitution θ\thetaθ sends xxx to ttt and every y≠xy\ne xy=x to θ(y)\theta(y)θ(y).

Simultaneously applying a substitution θ\thetaθ to a raw term sends var⁡(x)\operatorname{var}(x)var(x) to θ(x)\theta(x)θ(x) and recurses separately in the two children of an application. To apply it to λv.u\lambda v.uλv.u, let UUU be the list obtained by mapping θ\thetaθ over the free-variable list of uuu filtered to remove vvv. If vvv is free in any term of UUU, choose v′v'v′ of the same type as vvv with natural-number name 1+max⁡(maxNamedId⁡(u),maxNamedId⁡(var⁡(v)),maxNamedIdList⁡(U))1+\max\bigl(\operatorname{maxNamedId}(u),\operatorname{maxNamedId}(\operatorname{var}(v)),\operatorname{maxNamedIdList}(U)\bigr)1+max(maxNamedId(u),maxNamedId(var(v)),maxNamedIdList(U)). Otherwise choose v′=vv'=vv′=v. Return the abstraction over v′v'v′ whose body is the simultaneous substitution into uuu using θ[v↦var⁡(v′)]\theta[v\mapsto \operatorname{var}(v')]θ[v↦var(v′)]. The definitions of both single and simultaneous substitution apply to raw terms.

Binding trees and term relations

A binding tree is a free-variable leaf storing a full variable, a bound-variable leaf storing a type and an index, an application of two binding trees, or an abstraction storing a type and body tree. To look up a variable vvv in a scope list of variable–index pairs, take the index of the first pair whose variable equals vvv, with no result if there is no such pair. To abstract the bindings of a term relative to a scope and a current path ppp, send a variable leaf for vvv to its free leaf if the lookup fails and to a bound leaf storing type⁡(v)\operatorname{type}(v)type(v) and the looked-up path if it succeeds. In an application, recurse on the left at p∥[0]p\mathbin{\|}[0]p∥[0] and on the right at p∥[1]p\mathbin{\|}[1]p∥[1] with the same scope. In λx.r\lambda x.rλx.r, record an abstraction of type type⁡(x)\operatorname{type}(x)type(x) and recurse on rrr at p∥[0]p\mathbin{\|}[0]p∥[0] with (x,p)(x,p)(x,p) prepended to the scope. Two raw terms are α\alphaα-equivalent exactly when their binding trees with initial empty scope and empty path are equal.

The inductive βη\beta\etaβη relation on raw terms includes every α\alphaα-equivalent pair and has reflexivity, symmetry and transitivity. It is closed under application in both children and under abstraction over the same variable. Its β\betaβ rule relates (λx.r) s(\lambda x.r)\,s(λx.r)s to the result of the specified single substitution of sss for xxx in rrr, for all raw r,sr,sr,s and variables xxx. Its η\etaη rule relates λx.(r var⁡(x))\lambda x.(r\,\operatorname{var}(x))λx.(rvar(x)) to rrr for any raw term rrr and variable xxx absent from the free-variable list of rrr.

Long β\betaβ-normal and long β\betaβ-neutral forms are mutually inductive predicates of a type and term. A neutral term at BBB is normal at BBB. If rrr is normal at σ\sigmaσ, then λx.r\lambda x.rλx.r is normal at type⁡(x)→σ\operatorname{type}(x)\to\sigmatype(x)→σ. A variable occurrence is neutral at its variable's type. If ttt is neutral at ρ→σ\rho\to\sigmaρ→σ and sss is normal at ρ\rhoρ, then t st\,sts is neutral at σ\sigmaσ.

Reconstructing binders and extracting a term

Naming a binding tree with prefix kkk and current path ppp sends a free leaf for vvv to var⁡(v)\operatorname{var}(v)var(v) and a bound leaf with type ρ\rhoρ and stored path qqq to var⁡(xρ,k∥q)\operatorname{var}(x_{\rho,k\mathbin{\|}q})var(xρ,k∥q​). For an application it reconstructs the two trees at p∥[0]p\mathbin{\|}[0]p∥[0] and p∥[1]p\mathbin{\|}[1]p∥[1] respectively, with the same kkk. For an abstraction with stored type ρ\rhoρ, it names the binder xρ,k∥px_{\rho,k\mathbin{\|}p}xρ,k∥p​ and reconstructs its body at p∥[0]p\mathbin{\|}[0]p∥[0] with the same kkk. Renaming a raw term at index kkk builds its binding tree with empty scope and path and then names the tree with prefix kkk and empty path. The embedding EMB⁡(r)\operatorname{EMB}(r)EMB(r) is the function of kkk returning this renaming of rrr.

The maximum index length of a list of indices is 000 for the empty list and the maximum of the first index length and the tail's maximum for a nonempty list. The list of all indices of a raw term is obtained from the list of all variables, keeping the index of every indexed variable and dropping natural-number names. For any index-to-raw-term function FFF, the canonical index is the list of L+1L+1L+1 zeros where LLL is the maximum of the maximum index lengths of all indices of F(ϵ)F(\epsilon)F(ϵ) and F([0])F([0])F([0]). Thus these two samples determine the index, and when neither sample has an index of positive length it is [0][0][0]. The extraction operation EXTRACT⁡(F)\operatorname{EXTRACT}(F)EXTRACT(F) is FFF evaluated at this canonical index.

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