Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Two-zone arithmetic and computational content

Definition
ABHS2004V2_Arithmetic

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

implicit-complexityprogram-extractionrealizability

Sorted formulas, realizer and cleaned realizer types, and derivations with active and passive assumptions. The proof system includes the core axioms and the inference rules for quantifiers, connectives, and list induction.

Definition code
import Definitions.Def_ABHS2004V2_TermSystem

/-!
# Linear Arithmetic for Non-Size-Increasing Polytime Computation (ABHS 2004, Section 3)

Source: Klaus Aehlig, Ulrich Berger, Martin Hofmann, and Helmut Schwichtenberg,
"An arithmetic for non-size-increasing polynomial-time computation",
*Theoretical Computer Science* 318(1–2), 2004, pp. 3–27, Section 3 (pp. 10–19).

This module formalizes:
- Section 3.1: Predicate symbols (`PredSym`), formulas (`Formula`, Definition 3.1),
  abbreviations `bot`, `neg`, `iff` (Remark 3.2), computational content `tau` (Definition 3.3),
  type cleaning `cleanTy` and `tauClean` (Definition 3.4), and Harrop / computationally
  irrelevant formulas `IsHarrop` (Definition 3.5).
- Section 3.2: Assumption variables (`AssumpVar`), core axioms (Definition 3.8, equations
  (3)–(25)), raw proof terms (`ProofTerm`, Definition 3.6), and the two-zone natural
  deduction system `Derives Π Γ M A` (`Π | Γ ⊢ M : A`, Definition 3.7).
-/

namespace ABHS2004V2

/-- Predicate symbols different from the existence predicates `E_ρ`, including
equality `=_ρ` and arbitrary fixed-arity predicate symbols `P, Q` (Section 3.1, p. 10). -/
inductive PredSym where
  | eq (ρ : Ty) : PredSym
  | rel (id : Nat) (arity : List Ty) : PredSym
  deriving DecidableEq, Repr

/-- Arity (list of argument types) of a predicate symbol. -/
def PredSym.arity : PredSym → List Ty
  | .eq ρ => [ρ, ρ]
  | .rel _ tys => tys

/-- A list of terms `rs` is weakly typed according to the arity `tys` (Section 3.1, p. 10). -/
inductive WeaklyTypedList : List Term → List Ty → Prop where
  | nil : WeaklyTypedList [] []
  | cons {r : Term} {ρ : Ty} {rs : List Term} {ρs : List Ty} :
      WeaklyTyped r ρ →
      WeaklyTypedList rs ρs →
      WeaklyTypedList (r :: rs) (ρ :: ρs)

/-- Definition 3.1 (Formulas, p. 10):
`A, B, C ::= P(r⃗) | E_ρ(r) | A → B | A ⊗ B | A ∧ B | A ∨ B | ∀x^ρ A | ∃x^ρ A`. -/
inductive Formula where
  | pred : PredSym → List Term → Formula
  | existPred : Ty → Term → Formula
  | imp : Formula → Formula → Formula
  | tensor : Formula → Formula → Formula
  | conj : Formula → Formula → Formula
  | disj : Formula → Formula → Formula
  | all : Var → Formula → Formula
  | ex : Var → Formula → Formula
  deriving DecidableEq, Repr

namespace Formula

/-- The typing convention for the formulas of Definition 3.1. Predicate arguments
are weakly typed, which allows a term variable to occur more than once. -/
def WellFormed : Formula → Prop
  | .pred symbol args => WeaklyTypedList args symbol.arity
  | .existPred ρ term => WeaklyTyped term ρ
  | .imp A B | .tensor A B | .conj A B | .disj A B => WellFormed A ∧ WellFormed B
  | .all _ A | .ex _ A => WellFormed A

/-- Equality formula `r =_ρ s` (Section 3.1, p. 10). -/
def eqForm (ρ : Ty) (r s : Term) : Formula :=
  .pred (.eq ρ) [r, s]

/-- Remark 3.2 (p. 10): Falsity `⊥ := (tt =_B ff)`. -/
def bot : Formula :=
  eqForm Ty.bool Term.tt Term.ff

/-- Remark 3.2 (p. 10): Negation `¬A := A → ⊥`. -/
def neg (A : Formula) : Formula :=
  .imp A bot

/-- Bi-implication `A ↔ B := (A → B) ∧ (B → A)`. -/
def iffForm (A B : Formula) : Formula :=
  .conj (.imp A B) (.imp B A)

/-- Iterated implication `A₁ → ⋯ → Aₙ → B`. -/
def impMany : List Formula → Formula → Formula
  | [], B => B
  | A :: As, B => .imp A (impMany As B)

/-- Iterated universal quantification `∀ x₁ ... xₙ. A`. -/
def allMany : List Var → Formula → Formula
  | [], A => A
  | x :: xs, A => .all x (allMany xs A)

/-- Iterated existential quantification `∃ x₁ ... xₙ. A`. -/
def exMany : List Var → Formula → Formula
  | [], A => A
  | x :: xs, A => .ex x (exMany xs A)

/-- Relativized universal quantification `∀ x⃗. E(x⃗) → B` (p. 14, 26). -/
def allRel : List Var → Formula → Formula
  | [], B => B
  | x :: xs, B => .all x (.imp (.existPred x.ty (.var x)) (allRel xs B))

/-- Corollary 4.8 (p. 23): The formula `✸ := ∃ p^⋄. E_⋄(p)`. -/
def lozenge : Formula :=
  let p : Var := ⟨0, .diamond⟩
  .ex p (.existPred .diamond (.var p))

end Formula

/-- Free term variables `FV(A)` of a formula `A`. -/
def freeVarsFormula : Formula → List Var
  | .pred _ rs => (rs.foldr (fun r acc => freeVarOccurrences r ++ acc) []).eraseDups
  | .existPred _ r => freeVars r
  | .imp A B => (freeVarsFormula A ++ freeVarsFormula B).eraseDups
  | .tensor A B => (freeVarsFormula A ++ freeVarsFormula B).eraseDups
  | .conj A B => (freeVarsFormula A ++ freeVarsFormula B).eraseDups
  | .disj A B => (freeVarsFormula A ++ freeVarsFormula B).eraseDups
  | .all x A => (freeVarsFormula A).filter (· != x)
  | .ex x A => (freeVarsFormula A).filter (· != x)

/-- Maximum variable id occurring in a list of terms. -/
def maxVarIdList : List Term → Nat
  | [] => 0
  | r :: rs => Nat.max (maxVarId r) (maxVarIdList rs)

/-- Maximum variable id occurring anywhere in a formula. -/
def maxVarIdFormula : Formula → Nat
  | .pred _ rs => maxVarIdList rs
  | .existPred _ r => maxVarId r
  | .imp A B => Nat.max (maxVarIdFormula A) (maxVarIdFormula B)
  | .tensor A B => Nat.max (maxVarIdFormula A) (maxVarIdFormula B)
  | .conj A B => Nat.max (maxVarIdFormula A) (maxVarIdFormula B)
  | .disj A B => Nat.max (maxVarIdFormula A) (maxVarIdFormula B)
  | .all x A => Nat.max x.id (maxVarIdFormula A)
  | .ex x A => Nat.max x.id (maxVarIdFormula A)

/-- Rename free occurrences of term variable `x` to `y` in a formula `A`. -/
def renameFreeVarFormula (A : Formula) (x y : Var) : Formula :=
  match A with
  | .pred P rs => .pred P (rs.map (fun r => renameFreeVar r x y))
  | .existPred ρ r => .existPred ρ (renameFreeVar r x y)
  | .imp B C => .imp (renameFreeVarFormula B x y) (renameFreeVarFormula C x y)
  | .tensor B C => .tensor (renameFreeVarFormula B x y) (renameFreeVarFormula C x y)
  | .conj B C => .conj (renameFreeVarFormula B x y) (renameFreeVarFormula C x y)
  | .disj B C => .disj (renameFreeVarFormula B x y) (renameFreeVarFormula C x y)
  | .all v B => if v == x then .all v B else .all v (renameFreeVarFormula B x y)
  | .ex v B => if v == x then .ex v B else .ex v (renameFreeVarFormula B x y)

/-- Structural size of a formula used for termination of capture-avoiding substitution. -/
def formulaSize : Formula → Nat
  | .pred _ _ => 1
  | .existPred _ _ => 1
  | .imp B C => formulaSize B + formulaSize C + 1
  | .tensor B C => formulaSize B + formulaSize C + 1
  | .conj B C => formulaSize B + formulaSize C + 1
  | .disj B C => formulaSize B + formulaSize C + 1
  | .all _ B => formulaSize B + 1
  | .ex _ B => formulaSize B + 1

theorem renameFreeVarFormula_size (A : Formula) (x y : Var) :
    formulaSize (renameFreeVarFormula A x y) = formulaSize A := by
  induction A with
  | pred P rs => rfl
  | existPred ρ r => rfl
  | imp B C ihB ihC => simp [renameFreeVarFormula, formulaSize, ihB, ihC]
  | tensor B C ihB ihC => simp [renameFreeVarFormula, formulaSize, ihB, ihC]
  | conj B C ihB ihC => simp [renameFreeVarFormula, formulaSize, ihB, ihC]
  | disj B C ihB ihC => simp [renameFreeVarFormula, formulaSize, ihB, ihC]
  | all v B ih =>
      simp only [renameFreeVarFormula]
      split
      · rfl
      · simp [formulaSize, ih]
  | ex v B ih =>
      simp only [renameFreeVarFormula]
      split
      · rfl
      · simp [formulaSize, ih]

/-- Capture-avoiding substitution `A[s/x]` of term `s` for variable `x` in formula `A`. -/
def substFormula (A : Formula) (x : Var) (s : Term) : Formula :=
  match A with
  | .pred P rs => .pred P (rs.map (fun r => substTerm r x s))
  | .existPred ρ r => .existPred ρ (substTerm r x s)
  | .imp B C => .imp (substFormula B x s) (substFormula C x s)
  | .tensor B C => .tensor (substFormula B x s) (substFormula C x s)
  | .conj B C => .conj (substFormula B x s) (substFormula C x s)
  | .disj B C => .disj (substFormula B x s) (substFormula C x s)
  | .all v B =>
      if v == x then
        .all v B
      else if v ∈ freeVarOccurrences s then
        let freshId := Nat.max (maxVarIdFormula B) (Nat.max (maxVarId s) x.id) + 1
        let v' : Var := ⟨freshId, v.ty⟩
        .all v' (substFormula (renameFreeVarFormula B v v') x s)
      else
        .all v (substFormula B x s)
  | .ex v B =>
      if v == x then
        .ex v B
      else if v ∈ freeVarOccurrences s then
        let freshId := Nat.max (maxVarIdFormula B) (Nat.max (maxVarId s) x.id) + 1
        let v' : Var := ⟨freshId, v.ty⟩
        .ex v' (substFormula (renameFreeVarFormula B v v') x s)
      else
        .ex v (substFormula B x s)
termination_by formulaSize A
decreasing_by
  all_goals
    simp_wf
    simp [formulaSize, renameFreeVarFormula_size]
    try omega

/-- Simultaneous capture-avoiding substitution in a formula. -/
def substFormulaMany (A : Formula) (assignments : List (Var × Term)) : Formula :=
  match A with
  | .pred p args => .pred p (args.map fun term => substMany term assignments)
  | .existPred ρ term => .existPred ρ (substMany term assignments)
  | .imp B C => .imp (substFormulaMany B assignments) (substFormulaMany C assignments)
  | .tensor B C => .tensor (substFormulaMany B assignments) (substFormulaMany C assignments)
  | .conj B C => .conj (substFormulaMany B assignments) (substFormulaMany C assignments)
  | .disj B C => .disj (substFormulaMany B assignments) (substFormulaMany C assignments)
  | .all v B =>
      let active := assignments.filter fun (x, _) => x != v
      if substitutionCaptures active v then
        let id := max v.id (max (maxVarIdFormula B) (substitutionMaxId active)) + 1
        let fresh : Var := ⟨id, v.ty⟩
        .all fresh (substFormulaMany (renameFreeVarFormula B v fresh) active)
      else
        .all v (substFormulaMany B active)
  | .ex v B =>
      let active := assignments.filter fun (x, _) => x != v
      if substitutionCaptures active v then
        let id := max v.id (max (maxVarIdFormula B) (substitutionMaxId active)) + 1
        let fresh : Var := ⟨id, v.ty⟩
        .ex fresh (substFormulaMany (renameFreeVarFormula B v fresh) active)
      else
        .ex v (substFormulaMany B active)
termination_by formulaSize A
decreasing_by
  all_goals simp_wf
  all_goals simp only [formulaSize, renameFreeVarFormula_size]
  all_goals omega

/-- Definition 3.3 (Computational content, p. 11):
For a formula `A`, `tau A` (`τ(A)`) is the type of its potential realizers. -/
def tau : Formula → Ty
  | .existPred ρ _ => ρ
  | .pred _ _ => .unit
  | .imp A B => .lolli (tau A) (tau B)
  | .tensor A B => .tensor (tau A) (tau B)
  | .conj A B => .prod (tau A) (tau B)
  | .disj A B => .sum (tau A) (tau B)
  | .all _ A => tau A
  | .ex _ A => tau A

/-- Definition 3.4 (Cleaning of types, pp. 11–12): `c(ρ)`. -/
def cleanTy : Ty → Ty
  | .unit => .unit
  | .diamond => .diamond
  | .lolli ρ σ =>
      let cρ := cleanTy ρ
      let cσ := cleanTy σ
      if cσ == .unit then .unit
      else if cρ == .unit then cσ
      else .lolli cρ cσ
  | .tensor ρ σ =>
      let cρ := cleanTy ρ
      let cσ := cleanTy σ
      if cσ == .unit then cρ
      else if cρ == .unit then cσ
      else .tensor cρ cσ
  | .prod ρ σ =>
      let cρ := cleanTy ρ
      let cσ := cleanTy σ
      if cσ == .unit then cρ
      else if cρ == .unit then cσ
      else .prod cρ cσ
  | .sum ρ σ => .sum (cleanTy ρ) (cleanTy σ)
  | .list ρ => .list (cleanTy ρ)

/-- Cleaned computational content `τ^c(A) := c(τ(A))` (p. 12). -/
def tauClean (A : Formula) : Ty :=
  cleanTy (tau A)

/-- Definition 3.5 (Harrop / computationally irrelevant formulas, p. 12):
A formula `A` has no computational content (is Harrop / c.i.) iff `τ^c(A) = U`. -/
def IsHarrop (A : Formula) : Prop :=
  tauClean A = .unit

/-- Formula containing neither existence predicates `E_ρ` nor disjunctions `∨`
(Proposition 4.2(1), p. 20 & Corollary 4.11, p. 26). -/
def IsExistAndDisjFree : Formula → Prop
  | .pred _ _ => True
  | .existPred _ _ => False
  | .imp A B => IsExistAndDisjFree A ∧ IsExistAndDisjFree B
  | .tensor A B => IsExistAndDisjFree A ∧ IsExistAndDisjFree B
  | .conj A B => IsExistAndDisjFree A ∧ IsExistAndDisjFree B
  | .disj _ _ => False
  | .all _ A => IsExistAndDisjFree A
  | .ex _ A => IsExistAndDisjFree A

/-- Assumption variable `u^A` (Section 3.2, p. 12). -/
structure AssumpVar where
  id : Nat
  formula : Formula
  deriving DecidableEq, Repr

/-- Proof contexts `Π, Γ` are finite sets of assumption variables (represented as lists). -/
abbrev ProofContext := List AssumpVar

/-- Conversion equations `r =_ρ r'` corresponding to Definition 2.9, where in the equation
`cons_ρ d^⋄ r l {s} t = s d^⋄ r (l {s} t)` the term `l` can be arbitrary (Axiom 13, p. 15). -/
inductive AxiomConvEq : Ty → Term → Term → Prop where
  | beta (x : Var) (r s : Term) (σ : Ty) :
      WeaklyTyped (.lam x r) (.lolli x.ty σ) →
      WeaklyTyped s x.ty →
      AxiomConvEq σ (.app (.lam x r) s) (substTerm r x s)
  | tensorBeta (ρ σ τ : Ty) (r s t : Term) :
      WeaklyTyped r ρ →
      WeaklyTyped s σ →
      WeaklyTyped t (.lolli ρ (.lolli σ τ)) →
      AxiomConvEq τ
        (.app (.app (.const (.tensorElim ρ σ τ))
          (.app (.app (.const (.tensorIntro ρ σ)) r) s)) t)
        (.app (.app t r) s)
  | fstBeta (ρ σ τ : Ty) (r s t : Term) :
      WeaklyTyped r (.lolli τ ρ) →
      WeaklyTyped s (.lolli τ σ) →
      WeaklyTyped t τ →
      AxiomConvEq ρ
        (.app (.const (.fst ρ σ))
          (.app (.app (.app (.const (.prodIntro ρ σ τ)) r) s) t))
        (.app r t)
  | sndBeta (ρ σ τ : Ty) (r s t : Term) :
      WeaklyTyped r (.lolli τ ρ) →
      WeaklyTyped s (.lolli τ σ) →
      WeaklyTyped t τ →
      AxiomConvEq σ
        (.app (.const (.snd ρ σ))
          (.app (.app (.app (.const (.prodIntro ρ σ τ)) r) s) t))
        (.app s t)
  | inlBeta (ρ σ τ : Ty) (r s : Term) :
      WeaklyTyped r ρ →
      WeaklyTyped s (.prod (.lolli ρ τ) (.lolli σ τ)) →
      AxiomConvEq τ
        (.app (.app (.const (.sumElim ρ σ τ))
          (.app (.const (.inl ρ σ)) r)) s)
        (.app (.app (.const (.fst (.lolli ρ τ) (.lolli σ τ))) s) r)
  | inrBeta (ρ σ τ : Ty) (r s : Term) :
      WeaklyTyped r σ →
      WeaklyTyped s (.prod (.lolli ρ τ) (.lolli σ τ)) →
      AxiomConvEq τ
        (.app (.app (.const (.sumElim ρ σ τ))
          (.app (.const (.inr ρ σ)) r)) s)
        (.app (.app (.const (.snd (.lolli ρ τ) (.lolli σ τ))) s) r)
  | iterNil (ρ τ : Ty) (s t : Term) :
      WeaklyTyped s (.lolli .diamond (.lolli ρ (.lolli τ τ))) →
      WeaklyTyped t τ →
      AxiomConvEq τ (.app (.iter (.const (.nil ρ)) s) t) t
  | iterConsArb (ρ τ : Ty) (d r l s t : Term) :
      WeaklyTyped d .diamond →
      WeaklyTyped r ρ →
      WeaklyTyped l (.list ρ) →
      WeaklyTyped s (.lolli .diamond (.lolli ρ (.lolli τ τ))) →
      WeaklyTyped t τ →
      AxiomConvEq τ
        (.app (.iter (.app (.app (.app (.const (.cons ρ)) d) r) l) s) t)
        (.app (.app (.app s d) r) (.app (.iter l s) t))

/-- Helper building the compatibility chain `x₁ = y₁ → ⋯ → xₙ = yₙ → B`. -/
def eqChainImp : List Ty → List Term → List Term → Formula → Formula
  | ρ :: ρs, x :: xs, y :: ys, B =>
      .imp (Formula.eqForm ρ x y) (eqChainImp ρs xs ys B)
  | _, _, _, B => B

/-- Definition 3.8 (Axioms for the core system, pp. 14–15, equations (3)–(25)).
Each constructor of `CoreAxiom` represents a core axiom instance together with its
canonical formula `CoreAxiom.formula`. -/
inductive CoreAxiom where
  /-- (3) `(C → A) → (C → B) → C → A ∧ B` -/
  | ax3 (A B C : Formula)
  /-- (4) `A₀ ∧ A₁ → A₀` -/
  | ax4_left (A₀ A₁ : Formula)
  /-- (4) `A₀ ∧ A₁ → A₁` -/
  | ax4_right (A₀ A₁ : Formula)
  /-- (5) `A → B → A ⊗ B` -/
  | ax5 (A B : Formula)
  /-- (6) `A ⊗ B → (A → B → C) → C` -/
  | ax6 (A B C : Formula)
  /-- (7) `A₀ → A₀ ∨ A₁` -/
  | ax7_left (A₀ A₁ : Formula)
  /-- (7) `A₁ → A₀ ∨ A₁` -/
  | ax7_right (A₀ A₁ : Formula)
  /-- (8) `(A → C) ∧ (B → C) → A ∨ B → C` -/
  | ax8 (A B C : Formula)
  /-- (9) `∀x.A → ∃x.A` -/
  | ax9 (x : Var) (A : Formula)
  /-- (10) `∃x.A → (∀x.A → B) → B` with `x ∉ FV(B)` -/
  | ax10 (x : Var) (A B : Formula)
  /-- (11) `⊥ → P(r⃗)` -/
  | ax11 (P : PredSym) (rs : List Term)
  /-- (12) Reflexivity `r =_ρ r` -/
  | ax12_refl (ρ : Ty) (r : Term)
  /-- (12) Symmetry `r =_ρ s → s =_ρ r` -/
  | ax12_symm (ρ : Ty) (r s : Term)
  /-- (12) Transitivity `r =_ρ s → s =_ρ t → r =_ρ t` -/
  | ax12_trans (ρ : Ty) (r s t : Term)
  /-- (13) Conversion equation `r =_ρ r'` -/
  | ax13 (ρ : Ty) (r r' : Term)
  /-- (14) `f =_{ρ⊸σ} g → x =_ρ y → f x =_σ g y` -/
  | ax14 (ρ σ : Ty) (f g x y : Term)
  /-- (15) `x₁ = y₁ → ⋯ → xₙ = yₙ → P(x₁,...,xₙ) → P(y₁,...,yₙ)` -/
  | ax15 (P : PredSym) (xs ys : List Term)
  /-- (16) `x =_ρ y → E_ρ(x) → E_ρ(y)` -/
  | ax16 (ρ : Ty) (x y : Term)
  /-- (17) `x =_U ε` -/
  | ax17 (x : Term)
  /-- (18) `(∀x^ρ. f x =_σ g x) → f =_{ρ⊸σ} g` -/
  | ax18 (ρ σ : Ty) (x : Var) (f g : Term)
  /-- (19) `fst z =_ρ fst z' ∧ snd z =_σ snd z' → z =_{ρ×σ} z'` -/
  | ax19 (ρ σ : Ty) (z z' : Term)
  /-- (20→) `E_{ρ⊸σ}(f) → ∀x^ρ. E_ρ(x) → E_σ(f x)` -/
  | ax20_imp (ρ σ : Ty) (x : Var) (f : Term)
  /-- (20←) `(∀x^ρ. E_ρ(x) → E_σ(f x)) → E_{ρ⊸σ}(f)` -/
  | ax20_mpr (ρ σ : Ty) (x : Var) (f : Term)
  /-- (21→) `E_{ρ×σ}(z) → E_ρ(fst z) ∧ E_σ(snd z)` -/
  | ax21_imp (ρ σ : Ty) (z : Term)
  /-- (21←) `E_ρ(fst z) ∧ E_σ(snd z) → E_{ρ×σ}(z)` -/
  | ax21_mpr (ρ σ : Ty) (z : Term)
  /-- (22) `E(c)` for constructor `c ∈ {ε, ⊗⁺, inl, inr, nil, cons}` -/
  | ax22 (c : Const)
  /-- (23) `(∀x^ρ, y^σ. E(x, y) → A[⊗⁺ x y / z]) → ∀z^{ρ⊗σ}. E(z) → A` -/
  | ax23 (ρ σ : Ty) (x y z : Var) (A : Formula)
  /-- (24) `(∀x^ρ. E(x) → A[inl x / z]) ∧ (∀y^σ. E(y) → A[inr y / z]) → ∀z^{ρ+σ}. E(z) → A` -/
  | ax24 (ρ σ : Ty) (x y z : Var) (A : Formula)
  /-- (25) `(E_ρ(x) → A) → A` for c.i. formula `A` -/
  | ax25 (ρ : Ty) (x : Term) (A : Formula)
  deriving DecidableEq, Repr

/-- Side conditions and formula assigned to each `CoreAxiom` (Definition 3.8, pp. 14–15). -/
def CoreAxiom.formula : CoreAxiom → Formula
  | .ax3 A B C => .imp (.imp C A) (.imp (.imp C B) (.imp C (.conj A B)))
  | .ax4_left A₀ A₁ => .imp (.conj A₀ A₁) A₀
  | .ax4_right A₀ A₁ => .imp (.conj A₀ A₁) A₁
  | .ax5 A B => .imp A (.imp B (.tensor A B))
  | .ax6 A B C => .imp (.tensor A B) (.imp (.imp A (.imp B C)) C)
  | .ax7_left A₀ A₁ => .imp A₀ (.disj A₀ A₁)
  | .ax7_right A₀ A₁ => .imp A₁ (.disj A₀ A₁)
  | .ax8 A B C => .imp (.conj (.imp A C) (.imp B C)) (.imp (.disj A B) C)
  | .ax9 x A => .imp (.all x A) (.ex x A)
  | .ax10 x A B => .imp (.ex x A) (.imp (.all x (.imp A B)) B)
  | .ax11 P rs => .imp Formula.bot (.pred P rs)
  | .ax12_refl ρ r => Formula.eqForm ρ r r
  | .ax12_symm ρ r s => .imp (Formula.eqForm ρ r s) (Formula.eqForm ρ s r)
  | .ax12_trans ρ r s t =>
      .imp (Formula.eqForm ρ r s) (.imp (Formula.eqForm ρ s t) (Formula.eqForm ρ r t))
  | .ax13 ρ r r' => Formula.eqForm ρ r r'
  | .ax14 ρ σ f g x y =>
      .imp (Formula.eqForm (.lolli ρ σ) f g)
        (.imp (Formula.eqForm ρ x y) (Formula.eqForm σ (.app f x) (.app g y)))
  | .ax15 P xs ys =>
      eqChainImp P.arity xs ys (.imp (.pred P xs) (.pred P ys))
  | .ax16 ρ x y =>
      .imp (Formula.eqForm ρ x y) (.imp (.existPred ρ x) (.existPred ρ y))
  | .ax17 x => Formula.eqForm .unit x (.const .eps)
  | .ax18 ρ σ x f g =>
      .imp (.all x (Formula.eqForm σ (.app f (.var x)) (.app g (.var x))))
        (Formula.eqForm (.lolli ρ σ) f g)
  | .ax19 ρ σ z z' =>
      .imp
        (.conj
          (Formula.eqForm ρ (.app (.const (.fst ρ σ)) z) (.app (.const (.fst ρ σ)) z'))
          (Formula.eqForm σ (.app (.const (.snd ρ σ)) z) (.app (.const (.snd ρ σ)) z')))
        (Formula.eqForm (.prod ρ σ) z z')
  | .ax20_imp ρ σ x f =>
      .imp (.existPred (.lolli ρ σ) f)
        (.all x (.imp (.existPred ρ (.var x)) (.existPred σ (.app f (.var x)))))
  | .ax20_mpr ρ σ x f =>
      .imp (.all x (.imp (.existPred ρ (.var x)) (.existPred σ (.app f (.var x)))))
        (.existPred (.lolli ρ σ) f)
  | .ax21_imp ρ σ z =>
      .imp (.existPred (.prod ρ σ) z)
        (.conj
          (.existPred ρ (.app (.const (.fst ρ σ)) z))
          (.existPred σ (.app (.const (.snd ρ σ)) z)))
  | .ax21_mpr ρ σ z =>
      .imp
        (.conj
          (.existPred ρ (.app (.const (.fst ρ σ)) z))
          (.existPred σ (.app (.const (.snd ρ σ)) z)))
        (.existPred (.prod ρ σ) z)
  | .ax22 c => .existPred c.ty (.const c)
  | .ax23 ρ σ x y z A =>
      let pairxy := Term.app (.app (.const (.tensorIntro ρ σ)) (.var x)) (.var y)
      .imp
        (.all x (.all y
          (.imp (.existPred ρ (.var x))
            (.imp (.existPred σ (.var y)) (substFormula A z pairxy)))))
        (.all z (.imp (.existPred (.tensor ρ σ) (.var z)) A))
  | .ax24 ρ σ x y z A =>
      let inlx := Term.app (.const (.inl ρ σ)) (.var x)
      let inry := Term.app (.const (.inr ρ σ)) (.var y)
      .imp
        (.conj
          (.all x (.imp (.existPred ρ (.var x)) (substFormula A z inlx)))
          (.all y (.imp (.existPred σ (.var y)) (substFormula A z inry))))
        (.all z (.imp (.existPred (.sum ρ σ) (.var z)) A))
  | .ax25 ρ x A => .imp (.imp (.existPred ρ x) A) A

/-- Side conditions for instances of the schemes of Definition 3.8. -/
def CoreAxiom.SideConditions : CoreAxiom → Prop
  | .ax10 x _ B => x ∉ freeVarsFormula B
  | .ax11 P rs => WeaklyTypedList rs P.arity
  | .ax12_refl ρ r => WeaklyTyped r ρ
  | .ax12_symm ρ r s => WeaklyTyped r ρ ∧ WeaklyTyped s ρ
  | .ax12_trans ρ r s t => WeaklyTyped r ρ ∧ WeaklyTyped s ρ ∧ WeaklyTyped t ρ
  | .ax13 ρ r r' => AxiomConvEq ρ r r'
  | .ax14 ρ σ f g x y =>
      WeaklyTyped f (.lolli ρ σ) ∧ WeaklyTyped g (.lolli ρ σ) ∧
      WeaklyTyped x ρ ∧ WeaklyTyped y ρ
  | .ax15 P xs ys => WeaklyTypedList xs P.arity ∧ WeaklyTypedList ys P.arity
  | .ax16 ρ x y => WeaklyTyped x ρ ∧ WeaklyTyped y ρ
  | .ax17 x => WeaklyTyped x .unit
  | .ax18 ρ σ x f g =>
      x.ty = ρ ∧ x ∉ freeVars f ∧ x ∉ freeVars g ∧
      WeaklyTyped f (.lolli ρ σ) ∧ WeaklyTyped g (.lolli ρ σ)
  | .ax19 ρ σ z z' => WeaklyTyped z (.prod ρ σ) ∧ WeaklyTyped z' (.prod ρ σ)
  | .ax20_imp ρ σ x f => x.ty = ρ ∧ x ∉ freeVars f ∧ WeaklyTyped f (.lolli ρ σ)
  | .ax20_mpr ρ σ x f => x.ty = ρ ∧ x ∉ freeVars f ∧ WeaklyTyped f (.lolli ρ σ)
  | .ax21_imp ρ σ z => WeaklyTyped z (.prod ρ σ)
  | .ax21_mpr ρ σ z => WeaklyTyped z (.prod ρ σ)
  | .ax22 c => c.isConstructor = true
  | .ax23 ρ σ x y z A =>
      x.ty = ρ ∧ y.ty = σ ∧ z.ty = .tensor ρ σ ∧ x ≠ y ∧ x ≠ z ∧ y ≠ z ∧
      x ∉ freeVarsFormula A ∧ y ∉ freeVarsFormula A
  | .ax24 ρ σ x y z A =>
      x.ty = ρ ∧ y.ty = σ ∧ z.ty = .sum ρ σ ∧ x ≠ z ∧ y ≠ z ∧
      x ∉ freeVarsFormula A ∧ y ∉ freeVarsFormula A
  | .ax25 ρ x A => WeaklyTyped x ρ ∧ IsHarrop A
  | _ => True

/-- A valid instance satisfies its scheme's side conditions and the typing
convention of Definition 3.1. -/
def CoreAxiom.IsValid (axiomInstance : CoreAxiom) : Prop :=
  axiomInstance.SideConditions ∧ axiomInstance.formula.WellFormed

/-- Definition 3.6 (Raw proof terms, p. 12):
`M, N, L ::= u^A | c | λu^A M | λx^ρ M | M N | M r | M {N}`. -/
inductive ProofTerm where
  | assump : AssumpVar → ProofTerm
  | ax : CoreAxiom → ProofTerm
  | lamAssump : AssumpVar → ProofTerm → ProofTerm
  | lamTerm : Var → ProofTerm → ProofTerm
  | appProof : ProofTerm → ProofTerm → ProofTerm
  | appTerm : ProofTerm → Term → ProofTerm
  | ind : ProofTerm → ProofTerm → ProofTerm
  deriving DecidableEq, Repr

/-- Substitute assumption variable `v` for `u` in proof term `M` (`M[v^A / u^A]`,
used in the `(Contraction)` rule of Definition 3.7, p. 14). -/
def substAssumpProof (M : ProofTerm) (u v : AssumpVar) : ProofTerm :=
  match M with
  | .assump w => if w == u then .assump v else .assump w
  | .ax c => .ax c
  | .lamAssump w body =>
      if w == u then .lamAssump w body else .lamAssump w (substAssumpProof body u v)
  | .lamTerm x body => .lamTerm x (substAssumpProof body u v)
  | .appProof M₁ M₂ => .appProof (substAssumpProof M₁ u v) (substAssumpProof M₂ u v)
  | .appTerm M₁ r => .appTerm (substAssumpProof M₁ u v) r
  | .ind N M₁ => .ind (substAssumpProof N u v) (substAssumpProof M₁ u v)

/-- Bound assumption variables occurring in a proof term `M`. -/
def boundAssumpVars : ProofTerm → List AssumpVar
  | .assump _ => []
  | .ax _ => []
  | .lamAssump w body => w :: boundAssumpVars body
  | .lamTerm _ body => boundAssumpVars body
  | .appProof M₁ M₂ => boundAssumpVars M₁ ++ boundAssumpVars M₂
  | .appTerm M₁ _ => boundAssumpVars M₁
  | .ind N M₁ => boundAssumpVars N ++ boundAssumpVars M₁

/-- All assumption variables (free or bound) occurring in a proof term `M`. -/
def allAssumpVars : ProofTerm → List AssumpVar
  | .assump w => [w]
  | .ax _ => []
  | .lamAssump w body => w :: allAssumpVars body
  | .lamTerm _ body => allAssumpVars body
  | .appProof M₁ M₂ => allAssumpVars M₁ ++ allAssumpVars M₂
  | .appTerm M₁ _ => allAssumpVars M₁
  | .ind N M₁ => allAssumpVars N ++ allAssumpVars M₁

/-- Disjointness of two proof contexts `Π ∩ Γ = ∅` (by assumption variable id, ensuring
distinct assumption variables in a context have distinct ids). -/
def DisjointProofCtx (Δ Γ : ProofContext) : Prop :=
  ∀ u ∈ Δ, ∀ v ∈ Γ, u.id ≠ v.id

/-- Well-formedness of a proof context: no two distinct assumption variables share an id. -/
def CtxIdsUnique (Δ : ProofContext) : Prop :=
  ∀ u ∈ Δ, ∀ v ∈ Δ, u.id = v.id → u = v

/-- Set-extensional union `Θ = Π ∪ Γ` with `Π ∩ Γ = ∅` (Section 3.2, p. 12:
"We denote proof contexts by `Π, Γ, ...`, and write `Π, Γ` for the union `Π ∪ Γ`,
expressing that `Π` and `Γ` are disjoint."). -/
def IsDisjointCtxUnion (Δ Γ Θ : ProofContext) : Prop :=
  DisjointProofCtx Δ Γ ∧ CtxIdsUnique Θ ∧ ∀ u, u ∈ Θ ↔ (u ∈ Δ ∨ u ∈ Γ)

/-- Variable condition `VarCond` for `(∀⁺)` in Definition 3.7 (pp. 13–14):
"`x` must not be free in the type of any element of `Π ∪ Γ`." -/
def VarCond (x : Var) (Δ Γ : ProofContext) : Prop :=
  (∀ u ∈ Δ, x ∉ freeVarsFormula u.formula) ∧
  (∀ u ∈ Γ, x ∉ freeVarsFormula u.formula)

/-- Step formula in the `(L(τ)-Ind)` rule of Definition 3.7 (p. 14):
`∀ p^⋄, x^τ, l^{L(τ)}. E(p) → E(x) → A → A[cons(p, x, l)/l]`. -/
def indStepFormula (τ : Ty) (p x l : Var) (A : Formula) : Formula :=
  let consTerm := Term.app (.app (.app (.const (.cons τ)) (.var p)) (.var x)) (.var l)
  .all p (.all x (.all l
    (.imp (.existPred .diamond (.var p))
      (.imp (.existPred τ (.var x))
        (.imp A (substFormula A l consTerm))))))

/-- Definition 3.7 (Derivations `Π | Γ ⊢ M : A`, pp. 13–14). -/
inductive Derives : ProofContext → ProofContext → ProofTerm → Formula → Prop where
  /-- `(Assumption)`: `Π | Γ, u^A ⊢ u^A : A` -/
  | assumption (Δ Γ Γ' : ProofContext) (u : AssumpVar) :
      DisjointProofCtx Δ Γ' →
      IsDisjointCtxUnion Γ [u] Γ' →
      (∀ w ∈ Δ ++ Γ', w.formula.WellFormed) →
      Derives Δ Γ' (.assump u) u.formula
  /-- `(Axiom)`: `Π | Γ ⊢ c^A : A` -/
  | axiomRule (Δ Γ : ProofContext) (c : CoreAxiom) :
      DisjointProofCtx Δ Γ →
      (∀ w ∈ Δ ++ Γ, w.formula.WellFormed) →
      c.IsValid →
      Derives Δ Γ (.ax c) c.formula
  /-- `(→⁺)`: from `Π | Γ, u^A ⊢ M : B` infer `Π | Γ ⊢ λu^A M : A → B` -/
  | impIntro {Δ Γ Γ' : ProofContext} {u : AssumpVar} {M : ProofTerm} {B : Formula} :
      IsDisjointCtxUnion Γ [u] Γ' →
      Derives Δ Γ' M B →
      Derives Δ Γ (.lamAssump u M) (.imp u.formula B)
  /-- `(→⁻)`: from `Π | Γ₁ ⊢ M : A → B` and `Π | Γ₂ ⊢ N : A` infer `Π | Γ₁, Γ₂ ⊢ M N : B` -/
  | impElim {Δ Γ₁ Γ₂ Γ : ProofContext} {M N : ProofTerm} {A B : Formula} :
      IsDisjointCtxUnion Γ₁ Γ₂ Γ →
      Derives Δ Γ₁ M (.imp A B) →
      Derives Δ Γ₂ N A →
      Derives Δ Γ (.appProof M N) B
  /-- `(∀⁺)`: from `Π | Γ ⊢ M : A` and `VarCond` infer `Π | Γ ⊢ λx^ρ M : ∀x^ρ A` -/
  | allIntro {Δ Γ : ProofContext} (x : Var) {M : ProofTerm} {A : Formula} :
      Derives Δ Γ M A →
      VarCond x Δ Γ →
      Derives Δ Γ (.lamTerm x M) (.all x A)
  /-- `(∀⁻)`: from `Π | Γ ⊢ M : ∀x^ρ A` and `r` weakly typed by `ρ` infer `Π | Γ ⊢ M r : A[r/x]` -/
  | allElim {Δ Γ : ProofContext} {x : Var} {M : ProofTerm} {A : Formula} (r : Term) :
      Derives Δ Γ M (.all x A) →
      WeaklyTyped r x.ty →
      Derives Δ Γ (.appTerm M r) (substFormula A x r)
  /-- `(Passification)`: from `Π | u^B, Γ ⊢ M : A` and `A` c.i. infer `Π, u^B | Γ ⊢ M : A` -/
  | passification {Δ Δ' Γ Γ' : ProofContext} {u : AssumpVar} {M : ProofTerm} {A : Formula} :
      IsDisjointCtxUnion [u] Γ Γ' →
      IsDisjointCtxUnion Δ [u] Δ' →
      IsHarrop A →
      Derives Δ Γ' M A →
      Derives Δ' Γ M A
  /-- `(Contraction)`: from `u^A, Π | v^A, Γ ⊢ M : B` infer `Π | v^A, Γ ⊢ M[v^A/u^A] : B` -/
  | contraction {Δ Δ' Γ Γ' : ProofContext} {u v : AssumpVar} {M : ProofTerm} {B : Formula} :
      u.formula = v.formula →
      v ∉ boundAssumpVars M →
      IsDisjointCtxUnion [u] Δ Δ' →
      IsDisjointCtxUnion [v] Γ Γ' →
      Derives Δ' Γ' M B →
      Derives Δ Γ' (substAssumpProof M u v) B
  /-- `(L(τ)-Ind)`: list iteration induction rule (p. 14). -/
  | listInd {Δ Γ : ProofContext} {N M : ProofTerm} (τ : Ty) (t : Term)
      (p x l : Var) (A : Formula) :
      p.ty = .diamond →
      x.ty = τ →
      l.ty = .list τ →
      p ≠ x → p ≠ l → x ≠ l →
      p ∉ freeVarsFormula A →
      x ∉ freeVarsFormula A →
      WeaklyTyped t (.list τ) →
      Derives Δ Γ N (.existPred (.list τ) t) →
      Derives Δ [] M (indStepFormula τ p x l A) →
      Derives Δ Γ (.ind N M)
        (.imp (substFormula A l (.const (.nil τ))) (substFormula A l t))

/-- Provability judgment `Π | Γ ⊢ A` (p. 15: "there exists a proof term `M` such that
`Π | Γ ⊢ M : A` is derivable"). -/
def Provable (Δ Γ : ProofContext) (A : Formula) : Prop :=
  ∃ M : ProofTerm, Derives Δ Γ M A

/-- Closed provability `⊢ A` (in empty passive and active contexts). -/
def ClosedProvable (A : Formula) : Prop :=
  Provable [] [] A

end ABHS2004V2
Source
Klaus Aehlig, Ulrich Berger, Martin Hofmann and Helmut Schwichtenberg (2004), An arithmetic for non-size-increasing polynomial-time computation, TCS 318, Section 3, Definitions 3.1–3.8. https://www.mathematik.uni-muenchen.de/~schwicht/papers/abhs01/ICC-TCS/ansipt.pdf
Read-back

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

Formulas

A predicate symbol is equality at a type ρ\rhoρ, of argument types [ρ,ρ][\rho,\rho][ρ,ρ], or a relation with a natural-number identifier and a list of argument types. A formula is a predicate symbol applied to a term list, a typed existence atom Eρ(t)E_\rho(t)Eρ​(t), one of A⊸BA\multimap BA⊸B, A⊗BA\otimes BA⊗B, A∧BA\land BA∧B, A∨BA\lor BA∨B, or ∀x A\forall x\,A∀xA or ∃x A\exists x\,A∃xA. Here ⊸\multimap⊸ is object-language implication, ∧\land∧ is additive conjunction, and a variable records both a natural-number identifier and a type. A predicate application is well formed exactly when the terms and types in its argument lists match by weak typing, including both lists empty. Weak typing gives variables and constants their recorded types and uses function types for abstraction and application, with an iterator of type ν⊸ν\nu\multimap\nuν⊸ν taking a list of type List⁡(ρ)\operatorname{List}(\rho)List(ρ) and a step of type ⋄⊸ρ⊸ν⊸ν\diamond\multimap\rho\multimap\nu\multimap\nu⋄⊸ρ⊸ν⊸ν. An existence atom is well formed when its term has the indicated weak type. Binary formulas require both children well formed, and quantifiers require the body well formed.

Write r=ρsr={}_\rho sr=ρ​s for the equality atom on the list [r,s][r,s][r,s]. Then ⊥\bot⊥ is inl1,1ε=1+1inr1,1ε\mathsf{inl}_{1,1}\varepsilon={}_{1+1}\mathsf{inr}_{1,1}\varepsiloninl1,1​ε=1+1​inr1,1​ε, negation is implication into ⊥\bot⊥, and the biconditional is additive conjunction of the two implications. List-valued implication premises form a right-associated chain. Lists of universally or existentially quantified variables put the first variable outermost. The relativized universal over [x1,…,xn][x_1,\ldots,x_n][x1​,…,xn​] wraps the formula successively with ∀xi (Exi.ty(xi)⊸−)\forall x_i\,(E_{x_i.\mathrm{ty}}(x_i)\multimap-)∀xi​(Exi​.ty​(xi​)⊸−), with x1x_1x1​ outermost. These list operations leave the body alone for an empty list. The formula ◊\lozenge◊ is ∃p E⋄(p)\exists p\,E_\diamond(p)∃pE⋄​(p) at p=(0,⋄)p=(0,\diamond)p=(0,⋄).

The free-variable list deduplicates the combined free variables of an atom's arguments, concatenates and deduplicates across binary nodes, and removes the binder at quantifiers. Maximum identifier scans all argument terms and quantified variables, including bound identifiers, with default 000. Free renaming applies the term renaming to the arguments, traverses binary nodes and stops at a quantifier binding the source variable. Formula size is 111 on either atom, the sum of both child sizes plus 111 on binary nodes and body size plus 111 at either quantifier. For every formula and pair of variables, free renaming preserves this size.

Substitution and types of realizers

Single formula substitution uses single term substitution in each atom and recurses through all binary constructors. At either quantifier with binder vvv, it leaves the quantifier intact if vvv is the target variable xxx. Otherwise if vvv is free in the replacement ttt, it renames the binder to a variable of the same type with identifier 1+max⁡(maxid⁡(body),maxid⁡(t),id(x))1+\max(\operatorname{maxid}(\mathrm{body}),\operatorname{maxid}(t),\mathrm{id}(x))1+max(maxid(body),maxid(t),id(x)) before recurring. Otherwise it recurs with vvv retained. Simultaneous formula substitution applies simultaneous term substitution at all atoms and recurses through the binary constructors. In both formula quantifiers and term abstractions the simultaneous algorithm drops assignments to the binder, then renames it if it is free in a replacement still in the assignment list. Its new identifier is one above the maximum of the old binder identifier, the body identifiers and the identifiers of the remaining keys and values. The variable case picks the first matching replacement, with the variable as default.

The type τ\tauτ is ρ\rhoρ on Eρ(t)E_\rho(t)Eρ​(t) and 111 on any other atom, assigns function, tensor, product and sum type constructors to implication, tensor, additive conjunction and disjunction respectively, and passes through either quantifier. Type cleaning CCC fixes 111 and ⋄\diamond⋄ and cleans element or summand types under lists or sums. At an arrow with recursively cleaned domain and codomain, it gives 111 if the codomain is 111, the codomain if the domain is 111, and the rebuilt arrow otherwise. For tensor and product, it gives the left cleaned factor if the right one is 111, the right one if the left one is 111, and the rebuilt type otherwise. The cleaned associated type is C(τ(A))C(\tau(A))C(τ(A)). The Harrop predicate on AAA is exactly C(τ(A))=1C(\tau(A))=1C(τ(A))=1. The existence-and-disjunction-free predicate accepts ordinary predicate atoms, rejects Eρ(t)E_\rho(t)Eρ​(t) atoms and disjunctions, requires both children to satisfy it at implication, tensor and additive conjunction, and requires the body to satisfy it at either quantifier.

Axiom instances

The directed conversion equality relation at type ν\nuν has eight kinds of root pairs. It includes (λx.r)s(\lambda x.r)s(λx.r)s with r[x:=s]r[x:=s]r[x:=s] when the abstraction has weak type x.ty⊸νx.\mathrm{ty}\multimap\nux.ty⊸ν and sss has weak type x.tyx.\mathrm{ty}x.ty. It pairs telimρ,σ,ν(tinρ,σr s)t\mathsf{telim}_{\rho,\sigma,\nu}(\mathsf{tin}_{\rho,\sigma}r\,s)ttelimρ,σ,ν​(tinρ,σ​rs)t with t r st\,r\,strs at ν\nuν for weak types ρ,σ,ρ⊸σ⊸ν\rho,\sigma,\rho\multimap\sigma\multimap\nuρ,σ,ρ⊸σ⊸ν of r,s,tr,s,tr,s,t. The two projections from pinρ,σ,ηr s t\mathsf{pin}_{\rho,\sigma,\eta}r\,s\,tpinρ,σ,η​rst give r tr\,trt at ρ\rhoρ and s ts\,tst at σ\sigmaσ with weak types η⊸ρ,η⊸σ,η\eta\multimap\rho,\eta\multimap\sigma,\etaη⊸ρ,η⊸σ,η. The sum eliminator selimρ,σ,ν\mathsf{selim}_{\rho,\sigma,\nu}selimρ,σ,ν​ applied to an injection of rrr and a branch product sss gives (fst s) r(\mathsf{fst}\,s)\,r(fsts)r for left or (snd s) r(\mathsf{snd}\,s)\,r(snds)r for right, at ν\nuν. The weak types are the corresponding summand for rrr and the product of ρ⊸ν\rho\multimap\nuρ⊸ν and σ⊸ν\sigma\multimap\nuσ⊸ν for sss. The iterator equations at ν\nuν pair iter(nilρ,s)t\mathsf{iter}(\mathsf{nil}_\rho,s)titer(nilρ​,s)t with ttt and iter(consρ d r l,s)t\mathsf{iter}(\mathsf{cons}_\rho\,d\,r\,l,s)titer(consρ​drl,s)t with s d r (iter(l,s)t)s\,d\,r\,(\mathsf{iter}(l,s)t)sdr(iter(l,s)t). In both cases the weak types of s,ts,ts,t are ⋄⊸ρ⊸ν⊸ν\diamond\multimap\rho\multimap\nu\multimap\nu⋄⊸ρ⊸ν⊸ν and ν\nuν. The cons equation has the additional weak types ⋄,ρ,List⁡(ρ)\diamond,\rho,\operatorname{List}(\rho)⋄,ρ,List(ρ) for d,r,ld,r,ld,r,l, with any weakly typed tail lll.

Each entry below gives the formula of an axiom instance and its extra side conditions. A valid instance must also have a well-formed formula. The notation F⇆GF\leftrightarrows GF⇆G in rows 20 and 21 gives two separate axioms, for F⊸GF\multimap GF⊸G and G⊸FG\multimap FG⊸F. Arrows associate to the right and applications to the left. PPP is a predicate symbol, and π0,π1\pi_0,\pi_1π0​,π1​ in the table are the first and second product projections.

AxiomFormula and extra conditions
3(C⊸A)⊸(C⊸B)⊸C⊸(A∧B)(C\multimap A)\multimap(C\multimap B)\multimap C\multimap(A\land B)(C⊸A)⊸(C⊸B)⊸C⊸(A∧B)
4(A0∧A1)⊸Ai(A_0\land A_1)\multimap A_i(A0​∧A1​)⊸Ai​, one axiom for each i=0,1i=0,1i=0,1
5A⊸B⊸(A⊗B)A\multimap B\multimap(A\otimes B)A⊸B⊸(A⊗B)
6(A⊗B)⊸(A⊸B⊸C)⊸C(A\otimes B)\multimap(A\multimap B\multimap C)\multimap C(A⊗B)⊸(A⊸B⊸C)⊸C
7Ai⊸(A0∨A1)A_i\multimap(A_0\lor A_1)Ai​⊸(A0​∨A1​), one axiom for each i=0,1i=0,1i=0,1
8((A⊸C)∧(B⊸C))⊸(A∨B)⊸C((A\multimap C)\land(B\multimap C))\multimap(A\lor B)\multimap C((A⊸C)∧(B⊸C))⊸(A∨B)⊸C
9(∀x A)⊸(∃x A)(\forall x\,A)\multimap(\exists x\,A)(∀xA)⊸(∃xA)
10(∃x A)⊸(∀x (A⊸B))⊸B(\exists x\,A)\multimap(\forall x\,(A\multimap B))\multimap B(∃xA)⊸(∀x(A⊸B))⊸B, with xxx absent from the free variables of BBB
11⊥⊸P(r⃗)\bot\multimap P(\vec r)⊥⊸P(r), with the term list weakly typed by the arity of PPP
12r=ρrr={}_\rho rr=ρ​r, (r=ρs)⊸(s=ρr)(r={}_\rho s)\multimap(s={}_\rho r)(r=ρ​s)⊸(s=ρ​r), and (r=ρs)⊸(s=ρt)⊸(r=ρt)(r={}_\rho s)\multimap(s={}_\rho t)\multimap(r={}_\rho t)(r=ρ​s)⊸(s=ρ​t)⊸(r=ρ​t), with the displayed terms weakly typed at ρ\rhoρ in each case
13r=ρr′r={}_\rho r'r=ρ​r′, with the directed conversion equality above on r,r′r,r'r,r′ at ρ\rhoρ
14(f=ρ⊸σg)⊸(x=ρy)⊸(fx=σgy)(f={}_{\rho\multimap\sigma}g)\multimap(x={}_\rho y)\multimap(fx={}_\sigma gy)(f=ρ⊸σ​g)⊸(x=ρ​y)⊸(fx=σ​gy), with f,gf,gf,g weakly typed at ρ⊸σ\rho\multimap\sigmaρ⊸σ and x,yx,yx,y at ρ\rhoρ
15The chain of typed argument equalities from x⃗,y⃗\vec x,\vec yx,y​ leading to P(x⃗)⊸P(y⃗)P(\vec x)\multimap P(\vec y)P(x)⊸P(y​), with both lists weakly typed by the arity; the chain takes one head from each of the arity and the two term lists at a time and ends when any list is empty
16(x=ρy)⊸Eρ(x)⊸Eρ(y)(x={}_\rho y)\multimap E_\rho(x)\multimap E_\rho(y)(x=ρ​y)⊸Eρ​(x)⊸Eρ​(y), with x,yx,yx,y weakly typed at ρ\rhoρ
17x=1εx={}_1\varepsilonx=1​ε, with xxx weakly typed at 111
18(∀x (fx=σgx))⊸(f=ρ⊸σg)(\forall x\,(fx={}_\sigma gx))\multimap(f={}_{\rho\multimap\sigma}g)(∀x(fx=σ​gx))⊸(f=ρ⊸σ​g), with x:ρx:\rhox:ρ absent from the free variables of f,gf,gf,g and both f,gf,gf,g weakly typed at ρ⊸σ\rho\multimap\sigmaρ⊸σ
19((π0z=ρπ0z′)∧(π1z=σπ1z′))⊸(z=ρ&σz′)((\pi_0 z={}_\rho\pi_0 z')\land(\pi_1 z={}_\sigma\pi_1 z'))\multimap(z={}_{\rho\mathbin{\&}\sigma}z')((π0​z=ρ​π0​z′)∧(π1​z=σ​π1​z′))⊸(z=ρ&σ​z′), with z,z′z,z'z,z′ weakly typed at the product
20Eρ⊸σ(f)⇆∀x (Eρ(x)⊸Eσ(fx))E_{\rho\multimap\sigma}(f)\leftrightarrows\forall x\,(E_\rho(x)\multimap E_\sigma(fx))Eρ⊸σ​(f)⇆∀x(Eρ​(x)⊸Eσ​(fx)), with x:ρx:\rhox:ρ absent from the free variables of fff and fff weakly typed at ρ⊸σ\rho\multimap\sigmaρ⊸σ
21Eρ&σ(z)⇆(Eρ(π0z)∧Eσ(π1z))E_{\rho\mathbin{\&}\sigma}(z)\leftrightarrows(E_\rho(\pi_0 z)\land E_\sigma(\pi_1 z))Eρ&σ​(z)⇆(Eρ​(π0​z)∧Eσ​(π1​z)), with zzz weakly typed at the product
22Ety(c)(c)E_{\mathrm{ty}(c)}(c)Ety(c)​(c) for a constant ccc flagged as a constructor, namely unit, nil, cons, tensor introduction or either sum injection
23(∀x ∀y (Eρ(x)⊸Eσ(y)⊸A[z:=tinρ,σx y]))⊸∀z (Eρ⊗σ(z)⊸A)(\forall x\,\forall y\,(E_\rho(x)\multimap E_\sigma(y)\multimap A[z:=\mathsf{tin}_{\rho,\sigma}x\,y]))\multimap\forall z\,(E_{\rho\otimes\sigma}(z)\multimap A)(∀x∀y(Eρ​(x)⊸Eσ​(y)⊸A[z:=tinρ,σ​xy]))⊸∀z(Eρ⊗σ​(z)⊸A), with x:ρ,y:σ,z:ρ⊗σx:\rho,y:\sigma,z:\rho\otimes\sigmax:ρ,y:σ,z:ρ⊗σ pairwise distinct and x,yx,yx,y absent from the free variables of AAA
24((∀x (Eρ(x)⊸A[z:=inlρ,σx]))∧(∀y (Eσ(y)⊸A[z:=inrρ,σy])))⊸∀z (Eρ+σ(z)⊸A)((\forall x\,(E_\rho(x)\multimap A[z:=\mathsf{inl}_{\rho,\sigma}x]))\land(\forall y\,(E_\sigma(y)\multimap A[z:=\mathsf{inr}_{\rho,\sigma}y])))\multimap\forall z\,(E_{\rho+\sigma}(z)\multimap A)((∀x(Eρ​(x)⊸A[z:=inlρ,σ​x]))∧(∀y(Eσ​(y)⊸A[z:=inrρ,σ​y])))⊸∀z(Eρ+σ​(z)⊸A), with x:ρ,y:σ,z:ρ+σx:\rho,y:\sigma,z:\rho+\sigmax:ρ,y:σ,z:ρ+σ, x≠zx\ne zx=z and y≠zy\ne zy=z, and x,yx,yx,y absent from the free variables of AAA
25(Eρ(t)⊸A)⊸A(E_\rho(t)\multimap A)\multimap A(Eρ​(t)⊸A)⊸A, with ttt weakly typed at ρ\rhoρ and C(τ(A))=1C(\tau(A))=1C(τ(A))=1

Derivations and contexts

An assumption entry uuu is the pair of a natural-number identifier and formula FuF_uFu​. Contexts are lists of these entries. A context pair is disjoint if the identifiers of any two entries from opposite sides differ. A context satisfies identifier uniqueness if entries with the same identifier are equal. A disjoint context union of X,YX,YX,Y into ZZZ requires disjointness of X,YX,YX,Y, identifier uniqueness in ZZZ, and membership in ZZZ exactly for the entries belonging to XXX or YYY. Identical entries can repeat under the identifier uniqueness test.

Proof terms are assumption occurrences uuu, axiom instances, assumption or term abstractions, proof or term applications, and list induction nodes with two proof children. Substitution M[u:=v]M[u:=v]M[u:=v] replaces equal assumption occurrences, stops under an assumption abstraction binding uuu, and traverses proof children otherwise. It leaves axiom instances and term arguments intact. The bound-assumption list collects binder entries only. The all-assumption list collects those binder entries and assumption leaves. Each preserves the order of traversal, concatenating children in order and listing a binder before its body.

Write (Δ,Γ)⊢MA(\Delta,\Gamma)\vdash_M A(Δ,Γ)⊢M​A for the inductively generated judgment, and X⊎Y=ZX\uplus Y=ZX⊎Y=Z for the disjoint context union relation above. Its clauses are the following.

  • An assumption occurrence uuu gives (Δ,Γ′)⊢uFu(\Delta,\Gamma')\vdash_u F_u(Δ,Γ′)⊢u​Fu​ if Γ⊎[u]=Γ′\Gamma\uplus[u]=\Gamma'Γ⊎[u]=Γ′, the contexts Δ,Γ′\Delta,\Gamma'Δ,Γ′ are disjoint, and every formula in their concatenation is well formed. A valid axiom instance gives its formula in any disjoint pair of contexts whose entry formulas are well formed.
  • Implication introduction from (Δ,Γ′)⊢MB(\Delta,\Gamma')\vdash_M B(Δ,Γ′)⊢M​B requires Γ⊎[u]=Γ′\Gamma\uplus[u]=\Gamma'Γ⊎[u]=Γ′ and concludes Fu⊸BF_u\multimap BFu​⊸B in (Δ,Γ)(\Delta,\Gamma)(Δ,Γ) by assumption abstraction. Elimination uses proofs of A⊸BA\multimap BA⊸B and AAA in (Δ,Γ1)(\Delta,\Gamma_1)(Δ,Γ1​) and (Δ,Γ2)(\Delta,\Gamma_2)(Δ,Γ2​), and concludes BBB by proof application in (Δ,Γ)(\Delta,\Gamma)(Δ,Γ) when Γ1⊎Γ2=Γ\Gamma_1\uplus\Gamma_2=\GammaΓ1​⊎Γ2​=Γ.
  • Universal introduction adds ∀x\forall x∀x and a term abstraction in the same contexts when xxx is absent from the free variables of every assumption formula in both contexts. Elimination applies the proof of ∀x A\forall x\,A∀xA to a term rrr weakly typed at x.tyx.\mathrm{ty}x.ty, with conclusion A[x:=r]A[x:=r]A[x:=r] in the same contexts.
  • Passification takes (Δ,Γ′)⊢MA(\Delta,\Gamma')\vdash_M A(Δ,Γ′)⊢M​A to (Δ′,Γ)⊢MA(\Delta',\Gamma)\vdash_M A(Δ′,Γ)⊢M​A if [u]⊎Γ=Γ′[u]\uplus\Gamma=\Gamma'[u]⊎Γ=Γ′, Δ⊎[u]=Δ′\Delta\uplus[u]=\Delta'Δ⊎[u]=Δ′ and C(τ(A))=1C(\tau(A))=1C(τ(A))=1.
  • Contraction takes (Δ′,Γ′)⊢MB(\Delta',\Gamma')\vdash_M B(Δ′,Γ′)⊢M​B to (Δ,Γ′)⊢M[u:=v]B(\Delta,\Gamma')\vdash_{M[u:=v]} B(Δ,Γ′)⊢M[u:=v]​B if [u]⊎Δ=Δ′[u]\uplus\Delta=\Delta'[u]⊎Δ=Δ′, [v]⊎Γ=Γ′[v]\uplus\Gamma=\Gamma'[v]⊎Γ=Γ′, Fu=FvF_u=F_vFu​=Fv​, and vvv is absent from the bound-assumption list of MMM.
  • List induction uses a type ρ\rhoρ, an arbitrary formula AAA, and distinct variables p:⋄p:\diamondp:⋄, x:ρx:\rhox:ρ, l:List⁡(ρ)l:\operatorname{List}(\rho)l:List(ρ) with p,xp,xp,x absent from the free variables of AAA. It requires ttt weakly typed at List⁡(ρ)\operatorname{List}(\rho)List(ρ), (Δ,Γ)⊢NEList⁡(ρ)(t)(\Delta,\Gamma)\vdash_N E_{\operatorname{List}(\rho)}(t)(Δ,Γ)⊢N​EList(ρ)​(t), and a proof MMM in (Δ,[])(\Delta,[])(Δ,[]) of ∀p ∀x ∀l (E⋄(p)⊸Eρ(x)⊸A⊸A[l:=consρ p x l])\forall p\,\forall x\,\forall l\,(E_\diamond(p)\multimap E_\rho(x)\multimap A\multimap A[l:=\mathsf{cons}_\rho\,p\,x\,l])∀p∀x∀l(E⋄​(p)⊸Eρ​(x)⊸A⊸A[l:=consρ​pxl]). It concludes A[l:=nilρ]⊸A[l:=t]A[l:=\mathsf{nil}_\rho]\multimap A[l:=t]A[l:=nilρ​]⊸A[l:=t] in (Δ,Γ)(\Delta,\Gamma)(Δ,Γ) by induction on N,MN,MN,M.

Provability of AAA in (Δ,Γ)(\Delta,\Gamma)(Δ,Γ) is existence of a proof term MMM in that judgment. Closed provability sets both contexts to empty.

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