OctoInformBeta

OpenAI preprint, September 2026 · §6. A typed calculus for the forbidden configuration

Lemma 34: Structural laws and reduction lifting for data and proof modes

Labelled typing supports reduction and erasure.

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

Labels on applications, abstractions and dependent products distinguish the modes of an argument and a result. Erasure removes these labels from a typed term and its expected type. The structural metatheory concerns typing before erasure and the relation between labelled reduction and ordinary β\beta reduction.

A pure type specification P=(S,𝒜,ℛ)P=(S,\mathcal A,\mathcal R) consists of a collection of sorts, an axiom relation 𝒜⊆S×S\mathcal A\subseteq S\times S, and a product-rule relation ℛ⊆S3\mathcal R\subseteq S^3.✦ The two modes are 𝖽𝖺𝗍𝖺\mathsf{data} and 𝗉𝗋𝗈𝗈𝖿\mathsf{proof}.✦ A label ll is one of 𝖽𝖽,𝖽𝗉,𝗉𝗉\mathsf{dd},\mathsf{dp},\mathsf{pp}, with argument and result modes given by (1). l𝖽𝖽𝖽𝗉𝗉𝗉dom⁡(l)𝖽𝖺𝗍𝖺𝖽𝖺𝗍𝖺𝗉𝗋𝗈𝗈𝖿res⁡(l)𝖽𝖺𝗍𝖺𝗉𝗋𝗈𝗈𝖿𝗉𝗋𝗈𝗈𝖿\begin{array}{c|ccc} l&\mathsf{dd}&\mathsf{dp}&\mathsf{pp}\\ \hline \operatorname{dom}(l)&\mathsf{data}&\mathsf{data}&\mathsf{proof}\\ \operatorname{res}(l)&\mathsf{data}&\mathsf{proof}&\mathsf{proof} \end{array}(1)

A labelled term over SS is a variable, a sort, an application M@lNM\mathbin{@_l}N, an annotated abstraction λlx:A.b\lambda^l x:A.b, or a dependent product Πlx:A.B\Pi^l x:A.B.✦ Binder names denote capture-avoiding syntax; indexed notation uses de Bruijn variables xnx_n, with x0x_0 nearest its binder, and newest-first contexts. For a renaming ρ\rho of variable indices, the renamed term M[ρ]M[\rho] is obtained from MM by replacing each free index nn by ρ(n)\rho(n) and preserving labels; under a binder, the lift of ρ\rho fixes zero and sends n+1n+1 to ρ(n)+1\rho(n)+1.✦

A simultaneous substitution σ\sigma is an assignment of a term to each variable index. The term M[σ]M[\sigma] substitutes these images throughout MM, preserving labels and avoiding capture.✦ Write ↑M\uparrow M for successor renaming. The lift under a binder and the single substitution used for instantiation are given by (2); the same operations apply to ordinary terms. σ+(0)=x0,σ+(n+1)=↑σ(n),σa(0)=a,σa(n+1)=xn,b[a]=b[σa].\begin{aligned} \sigma^+(0)&=x_0,&\sigma^+(n+1)&=\uparrow\sigma(n),\\ \sigma_a(0)&=a,&\sigma_a(n+1)&=x_n,&b[a]&=b[\sigma_a]. \end{aligned}(2)

Write |M||M| for the erasure of a labelled term MM, as in (3). The erasure |Γ||\Gamma| of a labelled context Γ\Gamma is the ordinary context obtained by erasing each entry of Γ\Gamma. |xn|=xn,|s|=s,|M@lN|=|M||N|,|λlx:A.b|=λx:|A|.|b|,|Πlx:A.B|=Πx:|A|.|B|.\begin{aligned} |x_n|&=x_n,&|s|&=s,&|M\mathbin{@_l}N|&=|M|\,|N|,\\ |\lambda^l x:A.b|&=\lambda x:|A|.|b|,& |\Pi^l x:A.B|&=\Pi x:|A|.|B|. \end{aligned}(3)✦

Labelled one-step reduction →L\to_L is the compatible closure of (4), including every annotation and binder body.✦ Write →L*\to_L^* for its reflexive transitive closure and ≡L\equiv_L for its equivalence closure. Ordinary reduction →β\to_\beta, its closure →β*\to_\beta^*, and ordinary convertibility use the corresponding unlabelled head contraction and compatible closure. (λlx:A.b)@la→Lb[a].(\lambda^l x:A.b)\mathbin{@_l}a\ \to_L\ b[a].(4)

An ordinary term QQ is β\beta normal, written NF⁡(Q)\operatorname{NF}(Q), if it has no one-step reduct.✦ An ordinary term QQ is weakly normalizing, written WN⁡(Q)\operatorname{WN}(Q), if a β\beta normal term Q#Q^\# is reachable from QQ by →β*\to_\beta^*.✦

Typing and Modes

Labelled typing Γ⊢LM:T\Gamma\vdash_L M:T is the judgment generated by the axiom, variable, weakening, product, abstraction, application and conversion rules.✦ In newest-first notation, [][] is the empty context and A::ΓA::\Gamma is the extension of Γ\Gamma by AA. An axiom (s,t)∈𝒜(s,t)\in\mathcal A gives []⊢Ls:t[]\vdash_L s:t. If Γ⊢LA:s\Gamma\vdash_L A:s, the variable rule gives A::Γ⊢Lx0:↑AA::\Gamma\vdash_L x_0:\uparrow A; weakening shifts both the subject and its expected type when extending by AA. If Γ⊢LA:s1\Gamma\vdash_L A:s_1, A::Γ⊢LB:s2A::\Gamma\vdash_L B:s_2, and (s1,s2,s3)∈ℛ(s_1,s_2,s_3)\in\mathcal R, the product Πlx:A.B\Pi^l x:A.B has sort s3s_3. If A::Γ⊢Lb:BA::\Gamma\vdash_L b:B and the product Πlx:A.B\Pi^l x:A.B has a sort in Γ\Gamma, the abstraction λlx:A.b\lambda^l x:A.b has type Πlx:A.B\Pi^l x:A.B. If Γ⊢Lf:Πlx:A.B\Gamma\vdash_L f:\Pi^l x:A.B and Γ⊢La:A\Gamma\vdash_L a:A, the application f@laf\mathbin{@_l}a has type B[a]B[a] in Γ\Gamma. Conversion replaces an expected type by a ≡L\equiv_L-convertible type that has a sort in Γ\Gamma. Ordinary typing Γ⊢M:T\Gamma\vdash M:T uses these rules without labels.✦

A valid context Δ\Delta is either the empty context or an extension A::ΓA::\Gamma of a valid context Γ\Gamma by a term AA with a sort in Γ\Gamma; write Valid⁡(Δ)\operatorname{Valid}(\Delta) for this condition.✦ Context lookup Γ(n)=T\Gamma(n)=T gives the type of index nn in the whole context: its rules are (A::Γ)(0)=↑A(A::\Gamma)(0)=\uparrow A and (B::Γ)(n+1)=↑T(B::\Gamma)(n+1)=\uparrow T whenever Γ(n)=T\Gamma(n)=T.✦ A typed substitution σ:Γ⇒Δ\sigma:\Gamma\Rightarrow\Delta is an assignment satisfying (5). Γ(n)=A⇒Δ⊢Lσ(n):A[σ].\Gamma(n)=A\quad\Longrightarrow\quad \Delta\vdash_L\sigma(n):A[\sigma].(5)✦

A mode context γ\gamma is an assignment of a mode to each variable index. The extension m::γm::\gamma of a mode context γ\gamma by a mode mm is the mode context that sends zero to mm and n+1n+1 to γ(n)\gamma(n).✦ A term MM has mode mm under a mode context γ\gamma, written γ⊢M::m\gamma\vdash M::m, according to the rules in (6). γ⊢xn::γ(n),γ⊢s::𝖽𝖺𝗍𝖺,γ⊢f::res⁡(l)γ⊢a::dom⁡(l)γ⊢f@la::res⁡(l),γ⊢A::𝖽𝖺𝗍𝖺dom⁡(l)::γ⊢b::res⁡(l)γ⊢λlx:A.b::res⁡(l),γ⊢A::𝖽𝖺𝗍𝖺dom⁡(l)::γ⊢B::𝖽𝖺𝗍𝖺γ⊢Πlx:A.B::𝖽𝖺𝗍𝖺.\begin{gathered} \gamma\vdash x_n::\gamma(n),\qquad \gamma\vdash s::\mathsf{data},\\ \frac{\gamma\vdash f::\operatorname{res}(l)\quad \gamma\vdash a::\operatorname{dom}(l)} {\gamma\vdash f\mathbin{@_l}a::\operatorname{res}(l)},\\ \frac{\gamma\vdash A::\mathsf{data}\quad \operatorname{dom}(l)::\gamma\vdash b::\operatorname{res}(l)} {\gamma\vdash\lambda^l x:A.b::\operatorname{res}(l)},\\ \frac{\gamma\vdash A::\mathsf{data}\quad \operatorname{dom}(l)::\gamma\vdash B::\mathsf{data}} {\gamma\vdash\Pi^l x:A.B::\mathsf{data}}. \end{gathered}(6)✦

The generation condition Gen⁡(Γ,M,T)\operatorname{Gen}(\Gamma,M,T) describes the immediate typing data for the outer constructor of MM. For M=xnM=x_n, it requires a lookup Γ(n)=A\Gamma(n)=A with T≡LAT\equiv_L A. For M=sM=s, it requires an axiom (s,t)∈𝒜(s,t)\in\mathcal A with T≡LtT\equiv_L t. For M=f@laM=f\mathbin{@_l}a, it requires Γ⊢Lf:Πlx:A.B\Gamma\vdash_L f:\Pi^l x:A.B, Γ⊢La:A\Gamma\vdash_L a:A, and T≡LB[a]T\equiv_L B[a]. For M=λlx:A.bM=\lambda^l x:A.b, it requires A::Γ⊢Lb:BA::\Gamma\vdash_L b:B, Γ⊢LΠlx:A.B:s\Gamma\vdash_L\Pi^l x:A.B:s, and T≡LΠlx:A.BT\equiv_L\Pi^l x:A.B. For M=Πlx:A.BM=\Pi^l x:A.B, it requires Γ⊢LA:s1\Gamma\vdash_L A:s_1, A::Γ⊢LB:s2A::\Gamma\vdash_L B:s_2, (s1,s2,s3)∈ℛ(s_1,s_2,s_3)\in\mathcal R, and T≡Ls3T\equiv_L s_3. All the types and sorts mentioned in each case are existentially chosen.

The Claim

Theorem 1 (Structural metatheory and erasure). Let P=(S,𝒜,ℛ)P=(S,\mathcal A,\mathcal R) be a pure type specification. For any labelled judgment Γ⊢LM:T\Gamma\vdash_L M:T, context validity and regularity are expressed by (7) and (8). Valid⁡(Γ).\operatorname{Valid}(\Gamma).(7)✦ (∃s∈S,T=s)∨(∃s∈S,Γ⊢LT:s).(\exists s\in S,\ T=s)\quad\lor\quad (\exists s\in S,\ \Gamma\vdash_L T:s).(8)✦

For this judgment, let Δ\Delta be valid and let σ:Γ⇒Δ\sigma:\Gamma\Rightarrow\Delta be a typed substitution. Substitution has the conclusion (9). Δ⊢LM[σ]:T[σ].\Delta\vdash_L M[\sigma]:T[\sigma].(9)✦

Suppose A::Γ⊢Lb:BA::\Gamma\vdash_L b:B, Γ⊢LA:s\Gamma\vdash_L A:s, Γ⊢LA′:t\Gamma\vdash_L A':t, and A≡LA′A\equiv_L A'. Context head conversion gives (10). A′::Γ⊢Lb:B.A'::\Gamma\vdash_L b:B.(10)✦

Every judgment Γ⊢LM:T\Gamma\vdash_L M:T has the generation property (11). Gen⁡(Γ,M,T).\operatorname{Gen}(\Gamma,M,T).(11)✦

Suppose Γ⊢LM:T\Gamma\vdash_L M:T and M→L*NM\to_L^*N. Subject reduction gives (12). Γ⊢LN:T.\Gamma\vdash_L N:T.(12)✦

For arbitrary labelled terms with a→L*ba\to_L^*b and a→L*ca\to_L^*c, confluence is (13). ∃d,b→L*d∧c→L*d.\exists d,\quad b\to_L^*d\ \land\ c\to_L^*d.(13)✦

Suppose Πlx:A.B≡LΠkx:A′.B′\Pi^l x:A.B\equiv_L\Pi^k x:A'.B'. Product compatibility has the conclusion (14). l=k,A≡LA′,B≡LB′.l=k,\qquad A\equiv_L A',\qquad B\equiv_L B'.(14)✦

For Γ⊢LM:T\Gamma\vdash_L M:T, erasure preserves typing as in (15). If |M|→βN|M|\to_\beta N, a labelled step lifting that reduction exists as in (16). |Γ|⊢|M|:|T|.|\Gamma|\vdash |M|:|T|.(15)✦ ∃M′,M→LM′∧|M′|=N.\exists M',\quad M\to_L M'\ \land\ |M'|=N.(16)✦

Suppose Γ⊢LM:T\Gamma\vdash_L M:T, γ⊢M::m\gamma\vdash M::m, and WN⁡(|M|)\operatorname{WN}(|M|). A reduct with normal erasure satisfies (17). ∃M′,M→L*M′∧Γ⊢LM′:T∧γ⊢M′::m∧NF⁡(|M′|).\exists M',\quad M\to_L^*M'\ \land\ \Gamma\vdash_L M':T\ \land\ \gamma\vdash M'::m\ \land\ \operatorname{NF}(|M'|).(17)✦

What Is Checked

The claims concern labelled terms and typing over arbitrary axiom and product-rule relations, capture-avoiding substitution, and full compatible reduction; the normal erasure statement additionally assumes the mode judgment and weak normalization of the erased subject.