Typing and ideal definitional equality of the proof-split core (thesis §2, §6.1)
Definitionltt3_judgmentsThe two mutually inductive judgments at the heart of the thesis's metatheory, for the proof-split core calculus. The typing judgment has the variable, universe, split application and lambda, split forall/Pi, let, conversion, and empty-type rules. The ideal definitional equality is the equivalence relation generated by the congruences, the beta rules for proof and type application, the eta rule for the non-propositional Pi, zeta reduction of let, and definitional proof irrelevance (any two proofs of a proposition are equal). The conversion rule makes typing depend on definitional equality and the reflexivity/beta/eta/irrelevance rules make definitional equality depend on typing, so the two are defined simultaneously, exactly as in the thesis. Formalization Note. Contexts use de Bruijn indices; lookup returns the type of an index lifted past the intervening binders. This core layer is the foundation on which the menagerie judgment rules and the set-theoretic interpretation are built.
import Mathlib import Definitions.Def_ltt3_syntax /-! # The Type Theory of Lean, part III: the core judgments The typing judgment and the ideal definitional equality of the proof-split core calculus (Carneiro 2019, sections 2.1-2.2 and 6.1): variables, concrete-number universes, the split propositional forall and non-propositional Pi with their proof/type lambdas and applications, let binders, the conversion rule, the empty type and its recursor, and the beta, eta, zeta and proof-irrelevance rules. The two judgments are mutually inductive, reflecting the mutual dependence of typing and definitional equality in the thesis. -/ namespace LeanTT3 /-- Context lookup: the type of de Bruijn index `i` in `Γ`, where the head of the list is the innermost binder. The returned type is lifted to account for the binders between the variable's binding site and its use. -/ def lookup : Ctx → Nat → Option E | [], _ => none | α :: Γ, 0 => some (E.lift 0 1 α) | α :: Γ, i+1 => (lookup Γ i).map (E.lift 0 1) set_option autoImplicit true in mutual /-- The typing judgment `Γ ⊢ e : α` of the proof-split core calculus (thesis §6.1). -/ inductive Ty : Ctx → E → E → Prop where | var : lookup Γ i = some α → Ty Γ (.bvar i) α | sort : Ty Γ (.sort n) (.sort (n+1)) | appP : Ty Γ f (.piP α β) → Ty Γ a α → Ty Γ (.appP f a) (E.inst β a) | appT : Ty Γ f (.piT α β) → Ty Γ a α → Ty Γ (.appT f a) (E.inst β a) | lamP : Ty (α::Γ) e β → Ty (α::Γ) β (.sort 0) → Ty Γ (.lamP α e) (.piP α β) | lamT : Ty (α::Γ) e β → Ty (α::Γ) β (.sort n) → 1 ≤ n → Ty Γ (.lamT α e) (.piT α β) | piP : Ty Γ α (.sort n) → Ty (α::Γ) β (.sort 0) → Ty Γ (.piP α β) (.sort 0) | piT : Ty Γ α (.sort n1) → Ty (α::Γ) β (.sort n2) → 1 ≤ n2 → Ty Γ (.piT α β) (.sort (max n1 n2)) | letE : Ty Γ v α → Ty Γ (E.inst b v) β → Ty Γ (.letE α v b) β | conv : Ty Γ e α → Deq Γ α β → Ty Γ e β | empty : Ty Γ .empty (.sort 0) | recEmpty : Ty Γ C (.piT .empty (.sort n)) → Ty Γ (.recEmpty C) (.piT .empty (.appT (E.lift 0 1 C) (.bvar 0))) /-- The ideal definitional equality `Γ ⊢ e ≡ e'` of the proof-split core calculus (thesis §2.2, §6.1): an equivalence relation closed under the congruences, beta, eta, zeta, and definitional proof irrelevance. -/ inductive Deq : Ctx → E → E → Prop where | refl : Ty Γ e α → Deq Γ e e | sym : Deq Γ e e' → Deq Γ e' e | trans : Deq Γ e1 e2 → Deq Γ e2 e3 → Deq Γ e1 e3 | sort : Deq Γ (.sort n) (.sort n) | appP : Deq Γ f f' → Deq Γ a a' → Deq Γ (.appP f a) (.appP f' a') | appT : Deq Γ f f' → Deq Γ a a' → Deq Γ (.appT f a) (.appT f' a') | lamP : Deq Γ α α' → Deq (α::Γ) e e' → Deq Γ (.lamP α e) (.lamP α' e') | lamT : Deq Γ α α' → Deq (α::Γ) e e' → Deq Γ (.lamT α e) (.lamT α' e') | piP : Deq Γ α α' → Deq (α::Γ) β β' → Deq Γ (.piP α β) (.piP α' β') | piT : Deq Γ α α' → Deq (α::Γ) β β' → Deq Γ (.piT α β) (.piT α' β') | betaP : Ty (α::Γ) e β → Ty Γ a α → Deq Γ (.appP (.lamP α e) a) (E.inst e a) | betaT : Ty (α::Γ) e β → Ty Γ a α → Deq Γ (.appT (.lamT α e) a) (E.inst e a) | etaT : Ty Γ f (.piT α β) → Deq Γ (.lamT α (.appT (E.lift 0 1 f) (.bvar 0))) f | zeta : Ty Γ v α → Ty Γ (E.inst b v) β → Deq Γ (.letE α v b) (E.inst b v) | proofIrr : Ty Γ p (.sort 0) → Ty Γ h p → Ty Γ h' p → Deq Γ h h' end end LeanTT3
Read-back
What the Lean code literally says, in plain math · drafting-agent (non-blind self-readback)
Note: This read-back is non-blind: it was written by the same agent that drafted the Lean code, not by an independent auditor. It is a reading aid only, not independent testimony.
The code defines lookup Γ i, returning the type of de Bruijn index i in context Γ (lifted past intervening binders), or none. It then defines two mutually inductive relations. Ty Γ e α (typing) has rules: variable (via lookup); universe (sort n : sort (n+1)); proof/type application (against a piP/piT type, instantiating the codomain); proof/type lambda (body typed, with the codomain a proposition for lamP or a universe ≥ 1 for lamT); propositional forall / non-propositional Pi formation; let (value typed and instantiated body typed); conversion (change the type along Deq); the empty type (empty : sort 0); and the empty recursor. Deq Γ e e' (ideal definitional equality) has rules: reflexivity (from typing), symmetry, transitivity; universe reflexivity; proof/type application congruence; proof/type lambda and forall/Pi congruence; proof and type beta; type eta; let zeta; and proof irrelevance (two proofs of a proposition are equal). The two relations are defined simultaneously.