OctoInformBeta

OpenAI preprint, September 2026 · §2. Structural properties

Lemma 7: Application types are always sorted in the same context

Assigned types are sorts or have sorts.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Typing assigns terms to types, which are themselves terms of the same language. Regularity concerns the typing judgements available for an assigned type.

A pure type system specification is a triple P=(S,𝒜,ℛ)P=(S,\mathcal A,\mathcal R), where SS is a collection of sorts, 𝒜⊆S×S\mathcal A\subseteq S\times S is an axiom relation, and ℛ⊆S×S×S\mathcal R\subseteq S\times S\times S is a product-rule relation.✦ Terms over SS, with variables written xx, form the smallest collection generated by the grammar (1). M,N,A,B::=x∣s∣MN∣λx:A.M∣Πx:A.B,s∈S.M,N,A,B ::= x \mid s \mid M\,N \mid \lambda x:A.M \mid \Pi x:A.B, \qquad s\in S.(1)✦ Here xx is named source notation for a variable. In de Bruijn notation, vnv_n denotes the variable with index nn, and index zero refers to the nearest enclosing binder. A context Γ\Gamma is a finite list of terms in newest-first order; the extension by x:Ax:A is written x:A,Γx:A,\Gamma.

Variable renaming by a map ρ:ℕ→ℕ\rho:\mathbb N\to\mathbb N is the operation on terms that replaces vnv_n by vρ(n)v_{\rho(n)}, fixes sorts, and acts recursively on applications and binder domains. Under a binder it uses the lifted map that fixes zero and sends n+1n+1 to ρ(n)+1\rho(n)+1. Simultaneous substitution by an assignment σ\sigma of terms to indices is the operation on terms that replaces vnv_n by σ(n)\sigma(n), fixes sorts, and acts recursively on applications and binder domains. Under a binder its lift sends zero to v0v_0 and sends n+1n+1 to σ(n)\sigma(n) with every free index increased by one.

The single-variable substitution determined by a term aa is the assignment that sends zero to aa and n+1n+1 to vnv_n.✦ Bound-variable instantiation b[a/x]b[a/x] of a binder body bb is simultaneous substitution by the single-variable substitution determined by the term aa; substitution avoids capture.✦

One-step β\beta reduction →β\to_\beta is the least relation containing the contraction (2) and closed under reduction in either application position, in an abstraction’s annotation and body, and in a product’s domain and codomain. (λx:A.b)a→βb[a/x].(\lambda x:A.b)\,a \to_\beta b[a/x].(2)✦ The β\beta convertibility relation =β=_\beta is the smallest equivalence relation containing →β\to_\beta.✦

Typing

The typing judgement Γ⊢M:A\Gamma\vdash M:A is the least relation generated by the axiom, variable, weakening, product, abstraction, application, and conversion rules.✦ An axiom (s,t)∈𝒜(s,t)\in\mathcal A gives []⊢s:t[]\vdash s:t. When Γ⊢A:s\Gamma\vdash A:s, the variable rule gives x:A,Γ⊢x:Ax:A,\Gamma\vdash x:A, and weakening extends any judgement Γ⊢M:B\Gamma\vdash M:B to x:A,Γ⊢M:Bx:A,\Gamma\vdash M:B, with xx fresh. In de Bruijn notation, context extension shifts the variable rule’s assigned type and both the subject and assigned type of the weakened judgement by successor on indices.

When Γ⊢A:s1\Gamma\vdash A:s_1, x:A,Γ⊢B:s2x:A,\Gamma\vdash B:s_2, and (s1,s2,s3)∈ℛ(s_1,s_2,s_3)\in\mathcal R, the product rule gives Γ⊢Πx:A.B:s3\Gamma\vdash\Pi x:A.B:s_3. The abstraction rule applies when x:A,Γ⊢b:Bx:A,\Gamma\vdash b:B and Γ⊢Πx:A.B:s\Gamma\vdash\Pi x:A.B:s for some sort ss; it gives Γ⊢λx:A.b:Πx:A.B\Gamma\vdash\lambda x:A.b:\Pi x:A.B. When Γ⊢f:Πx:A.B\Gamma\vdash f:\Pi x:A.B and Γ⊢a:A\Gamma\vdash a:A, application gives Γ⊢fa:B[a/x]\Gamma\vdash f\,a:B[a/x]. From Γ⊢M:A\Gamma\vdash M:A, A=βBA=_\beta B, and Γ⊢B:s\Gamma\vdash B:s for some sort ss, conversion gives Γ⊢M:B\Gamma\vdash M:B.

The Claim

Theorem 1. Let Γ⊢M:A\Gamma\vdash M:A. Then (∃s∈S,A=s)or(∃s∈S,Γ⊢A:s).\bigl(\exists s\in S,\ A=s\bigr) \quad\text{or}\quad \bigl(\exists s\in S,\ \Gamma\vdash A:s\bigr).(3)✦ Let Γ⊢fa:T\Gamma\vdash f\,a:T. Then ∃s∈S,Γ⊢T:s.\exists s\in S,\quad \Gamma\vdash T:s.(4)✦

What Is Checked

The regularity statement (3) and the application statement (4) concern arbitrary pure type system specifications and derivable typing judgements over their terms and contexts.

When equality of sorts is decidable, equality of terms is decidable.