OctoInformBeta

OpenAI preprint, September 2026 · §2. Structural properties

Lemma 8: Conversion distinguishes sort constants and separates products from sorts, while preserving product components

Full β\beta reduction is confluent.

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

Two reduction sequences from one pure type system term raise the question of a common reduct; conversion raises the question of how much of a sort or product’s form is retained.

The pure type system terms over a collection SS of sorts form the least collection generated by the grammar (1), where xx ranges over variables and s∈Ss\in S. M,N,A,B::=x∣s∣MN∣λx:A.M∣Πx:A.B.M,N,A,B ::= x \mid s \mid M\,N \mid \lambda x:A.M \mid \Pi x:A.B.(1)✦ Variables use de Bruijn indices vnv_n, with index 00 referring to the nearest enclosing binder; the bound variable names in (1) are source notation.

A simultaneous substitution σ\sigma for terms over SS is an assignment of terms to variable indices. Its action M[σ]M[\sigma] fixes sort constants and replaces vnv_n by σ(n)\sigma(n). It acts recursively on applications and binder annotations. Within a binder body, it uses the lifted assignment, which fixes v0v_0 and sends n+1n+1 to σ(n)\sigma(n) with all free indices increased by one.

The single-variable substitution σa\sigma_a for a term aa is the assignment in (2); bound-variable instantiation b[a]b[a] is its capture-avoiding action on a term bb. σa(0)=a,σa(n+1)=vn,b[a]=b[σa].\sigma_a(0)=a,\qquad \sigma_a(n+1)=v_n,\qquad b[a]=b[\sigma_a].(2)

One-step β\beta reduction →β\to_\beta on terms over SS is the least relation containing the contraction (3) and closed under every term constructor in (1), including reduction in binder annotations and bodies. (λx:A.b)a→βb[a].(\lambda x:A.b)\,a \to_\beta b[a].(3)✦ Multi-step β\beta reduction →β*\to_\beta^* on terms over SS is the reflexive transitive closure of one-step β\beta reduction →β\to_\beta.✦ The β\beta convertibility relation =β=_\beta on terms over SS is the least equivalence relation containing →β\to_\beta.✦

The Claim

Theorem 1. Let M,U,VM,U,V be terms over SS with M→β*UM\to_\beta^*U and M→β*VM\to_\beta^*V. Confluence gives (4). ∃W(U→β*W∧V→β*W).\exists W\;\bigl(U\to_\beta^*W\ \land\ V\to_\beta^*W\bigr).(4)✦

For sorts s,t∈Ss,t\in S with s=βts=_\beta t, sort injectivity gives (5). s=t.s=t.(5)✦

Product sort inconvertibility for terms A,BA,B and a sort s∈Ss\in S is (6). (Πx:A.B)≠βs.(\Pi x:A.B)\not=_\beta s.(6)✦

For terms A,B,A′,B′A,B,A',B' with (Πx:A.B)=β(Πx:A′.B′)(\Pi x:A.B)=_\beta(\Pi x:A'.B'), product compatibility gives (7). A=βA′andB=βB′.A=_\beta A'\qquad\text{and}\qquad B=_\beta B'.(7)✦

What Is Checked

The claims concern terms over an arbitrary sort collection SS, with full β\beta reduction and its reflexive transitive and equivalence closures. Equality of these terms is decidable whenever equality of sorts in SS is decidable.