Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 3.6 — Canonical forms of normal almost closed terms

Open
AehligSchwichtenberg2002V2.proposition_3_6

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

implicit-complexitylambda-calculustype-theory

A normal term whose free variables all have token type has a canonical outer form at each of the following types. A list-typed term is a list spine, a Boolean is tt\mathsf{tt}tt or ff\mathsf{ff}ff, and a term of token type is a variable of token type.

Preamble
import Definitions.Def_AehligSchwichtenberg2002V2_Syntax
Formal statement
namespace AehligSchwichtenberg2002V2

theorem proposition_3_6 {Γ : Context} {t : Term}
    (hac : IsAlmostClosed t) (hnorm : IsNormal t) :
    (∀ τ : Ty, HasType Γ t (.list τ) → IsListTerm t) ∧
    (HasType Γ t .bool → t = .const .tt ∨ t = .const .ff) ∧
    (HasType Γ t .diamond → ∃ x : Var, x.ty = .diamond ∧ t = .var x) := by sorry

end AehligSchwichtenberg2002V2
Source
Klaus Aehlig and Helmut Schwichtenberg (2002), A syntactical analysis of non-size-increasing polynomial time computation, Proposition 3.6. https://arxiv.org/abs/cs/0011037
Read-back

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

For every context Γ\GammaΓ and raw term ttt, assume every free variable of ttt has type ◊\Diamond◊ and ttt is normal. The three conclusions hold together. For every type AAA, if Γ⊢t:L(A)\Gamma\vdash t:\mathsf L(A)Γ⊢t:L(A), there exists n∈Nn\in\mathbb Nn∈N such that C(t)C(t)C(t) returns nnn. If Γ⊢t:Bool\Gamma\vdash t:\mathsf{Bool}Γ⊢t:Bool, ttt is literally one of the constants tt\mathsf{tt}tt and ff\mathsf{ff}ff. If Γ⊢t:◊\Gamma\vdash t:\DiamondΓ⊢t:◊, there is a variable xxx of type ◊\Diamond◊ such that ttt is literally the variable term xxx. The free-variable premise includes terms with no free variables, and context entries may have any type. The typing premises of the three implications can all be false, as with t={tt}t=\{\mathsf{tt}\}t={tt}. The types are generated by ◊\Diamond◊, Bool\mathsf{Bool}Bool, arrows A⊸BA\multimap BA⊸B, tensors A⊗BA\otimes BA⊗B, products A×BA\times BA×B, and lists L(A)\mathsf L(A)L(A). A variable is a pair of a natural-number identifier and a type. Equality of variables compares both entries. The terms are variables, constants, abstractions λx.r\lambda x.rλx.r, pairs ⟨r,s⟩\langle r,s\rangle⟨r,s⟩, applications rsrsrs, and braces {r}\{r\}{r}. Successive applications associate to the left and arrow chains associate to the right. The constants tt\mathsf{tt}tt and ff\mathsf{ff}ff have declared type Bool\mathsf{Bool}Bool. For every type AAA, the constants nilA\mathsf{nil}_AnilA​ and consA\mathsf{cons}_AconsA​ have declared types L(A)\mathsf L(A)L(A) and ◊⊸A⊸L(A)⊸L(A)\Diamond\multimap A\multimap\mathsf L(A)\multimap\mathsf L(A)◊⊸A⊸L(A)⊸L(A). For all types A,BA,BA,B, tpA,B\mathsf{tp}_{A,B}tpA,B​ has declared type A⊸B⊸(A⊗B)A\multimap B\multimap(A\otimes B)A⊸B⊸(A⊗B). Contexts are lists of variables. A context is a union of two operand contexts if each variable belongs to the result exactly when it belongs to at least one operand. A disjoint union additionally requires that the operands have no common variable. These relations permit arbitrary ordering and repetitions within a context. The typing relation Γ⊢r:A\Gamma\vdash r:AΓ⊢r:A is generated by the variable rule in any context containing that variable, and the constant rule in any context with the declared constant type. An abstraction λx.r\lambda x.rλx.r has type A⊸BA\multimap BA⊸B in Γ\GammaΓ if xxx has declared type AAA and rrr has type BBB in a union of Γ\GammaΓ and the singleton list [x][x][x]. An application rsrsrs has type BBB in a disjoint union of contexts typing rrr at A⊸BA\multimap BA⊸B and sss at AAA. The pair ⟨r,s⟩\langle r,s\rangle⟨r,s⟩ has type A×BA\times BA×B if rrr has type AAA and sss has type BBB in the same context. A term rrr of product type A×BA\times BA×B gives applications r ttr\,\mathsf{tt}rtt and r ffr\,\mathsf{ff}rff of types AAA and BBB in its context. If rrr has Boolean type and both sss and uuu have type AAA in a shared context disjoint from the context of rrr, then r⟨s,u⟩r\langle s,u\rangler⟨s,u⟩ has type AAA in their disjoint union. For distinct variables x,yx,yx,y of types A,BA,BA,B, respectively, r(λx.λy.s)r(\lambda x.\lambda y.s)r(λx.λy.s) has type CCC in a disjoint union of a context typing rrr at A⊗BA\otimes BA⊗B and a context Δ\DeltaΔ disjoint from [x,y][x,y][x,y], provided sss has type CCC in a union of Δ\DeltaΔ and [x,y][x,y][x,y]. If rrr has type L(A)\mathsf L(A)L(A) and hhh has type ◊⊸A⊸R⊸R\Diamond\multimap A\multimap R\multimap R◊⊸A⊸R⊸R in the empty context, r{h}r\{h\}r{h} has type R⊸RR\multimap RR⊸R in the context of rrr. The free occurrences of a variable term are its singleton list and a constant contributes none. An abstraction filters the occurrences of its binder from those of its body, a pair or application concatenates the two occurrence lists from left to right, and braces use the occurrence list of their contents. The list FV⁡(r)\operatorname{FV}(r)FV(r) retains the first occurrence of each distinct variable in the resulting list. The optional list entry count CCC returns 000 on any nilA\mathsf{nil}_AnilA​, returns 1+C(l)1+C(l)1+C(l) on consA d a l\mathsf{cons}_A\,d\,a\,lconsA​dal if C(l)C(l)C(l) returns a number, and is undefined otherwise. It looks at the rightmost tail argument of each fully applied cons\mathsf{cons}cons, permits any parameters AAA on the constructors along that chain, and ignores the contents of the other two arguments. A term is normal when none of the nodes reached from its root through only application nodes, including the root itself, has any of these forms. The forms are an applied abstraction, a pair applied to tt\mathsf{tt}tt or ff\mathsf{ff}ff, tt\mathsf{tt}tt or ff\mathsf{ff}ff applied to a pair, tpA,B\mathsf{tp}_{A,B}tpA,B​ applied to two terms and a double abstraction whose distinct binders have types A,BA,BA,B, nilA\mathsf{nil}_AnilA​ applied to a brace and another term, and a fully applied consA\mathsf{cons}_AconsA​ with a countable tail further applied to a brace and another term. Abstractions, pairs and braces are normal at the root regardless of their contents.

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