Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 2.13 — Canonical forms of normal almost closed terms

Open
ABHS2004V2.proposition_2_13

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

implicit-complexityprogram-extractionrealizability

The outer constructors of a normal affinely typed term with only token variables free are those prescribed by its type.

Preamble
import Definitions.Def_ABHS2004V2_TermSystem
Formal statement
namespace ABHS2004V2

/-- Proposition 2.13. A normal term with only diamond variables free has a
canonical outer form determined by its type. -/
theorem proposition_2_13 {w : Term} {τ : Ty}
    (ht : HasType w τ) (hac : IsAlmostClosed w) (hnorm : IsNormal w) :
    HasCanonicalNormalForm τ w := by sorry

end ABHS2004V2
Source
Klaus Aehlig, Ulrich Berger, Martin Hofmann and Helmut Schwichtenberg (2004), An arithmetic for non-size-increasing polynomial-time computation, TCS 318, Proposition 2.13. https://www.mathematik.uni-muenchen.de/~schwicht/papers/abhs01/ICC-TCS/ansipt.pdf
Read-back

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

For every term www and type τ\tauτ, assume www has type τ\tauτ, every free variable occurrence of www has type ⋄\diamond⋄, and there is no one-step reduct of www. The free-variable condition includes the empty list of free occurrences. The step used for normality contracts a beta redex, tensor elimination on tensor introduction, a product projection on product introduction, sum elimination on an injection, or an iterator applied to a seed on a nil or cons list. The cons case requires a syntactic list tail. These contractions can occur at the root or through descendants reached by going into either child of applications and iterators.

The conclusion gives these syntactic shapes for www, by case on τ\tauτ.

  • For the unit type 111, w=εw=\varepsilonw=ε, the unit constant.
  • For ⋄\diamond⋄, www is a variable xxx with recorded type ⋄\diamond⋄.
  • For List⁡(ρ)\operatorname{List}(\rho)List(ρ), www is a nil constant, or a chain of fully applied cons constants consσ d u l\mathsf{cons}_{\sigma}\,d\,u\,lconsσ​dul with the same shape required recursively of the tail lll. The list-shape test accepts any nil tag and any cons tag at each node.
  • For ρ⊗σ\rho\otimes\sigmaρ⊗σ, there are terms u,vu,vu,v with w=tinρ,σ u vw=\mathsf{tin}_{\rho,\sigma}\,u\,vw=tinρ,σ​uv, where tin\mathsf{tin}tin is tensor introduction.
  • For the product ρ&σ\rho\mathbin{\&}\sigmaρ&σ, there are a type ν\nuν and terms u,v,tu,v,tu,v,t with w=pinρ,σ,ν u v tw=\mathsf{pin}_{\rho,\sigma,\nu}\,u\,v\,tw=pinρ,σ,ν​uvt, where pin\mathsf{pin}pin is product introduction.
  • For the sum ρ+σ\rho+\sigmaρ+σ, either w=inlρ,σ uw=\mathsf{inl}_{\rho,\sigma}\,uw=inlρ,σ​u for some uuu or w=inrρ,σ vw=\mathsf{inr}_{\rho,\sigma}\,vw=inrρ,σ​v for some vvv.
  • For a function type ρ⊸σ\rho\multimap\sigmaρ⊸σ, www is some abstraction λx.u\lambda x.uλx.u, some constant applied on the left to a list of arguments, or some iter(u,v)\mathsf{iter}(u,v)iter(u,v). The argument list in the constant case can be empty.

The typing judgment gives a variable its recorded type, a constant its declared type, and λx.u\lambda x.uλx.u the type x.ty⊸σx.\mathrm{ty}\multimap\sigmax.ty⊸σ when uuu has type σ\sigmaσ. To type u vu\,vuv at σ\sigmaσ, the rules require uuu at ρ⊸σ\rho\multimap\sigmaρ⊸σ, vvv at ρ\rhoρ, and disjoint free-variable lists in the sense of no shared member. To type iter(u,v)\mathsf{iter}(u,v)iter(u,v) at ν⊸ν\nu\multimap\nuν⊸ν, they require uuu at List⁡(ρ)\operatorname{List}(\rho)List(ρ) and a closed vvv at ⋄⊸ρ⊸ν⊸ν\diamond\multimap\rho\multimap\nu\multimap\nu⋄⊸ρ⊸ν⊸ν, with arrows associated to the right. A variable is a pair of a natural-number identifier and a type. Its sole occurrence is free as a variable term. Constants contribute no occurrences, abstractions remove all occurrences of the binder, and applications and iterators concatenate their children's free-occurrence lists.

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