Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 4.3: Non-Size-Increasing Valuation Under Reduction

Proved
AehligSchwichtenberg2002.lemma_4_3

by kmehltretter82 · Oct 30, 2026 · Mathlib 0df444a (Lean v4.33.1)

implicit-computational-complexitylambda-calculusnormalizationpolynomial-timetype-theory

If r ↦ r' at iteration depth ≤ d, then |r'|_ξ ≤ |r|_ξ for every compatible environment ξ.

Preamble
import Definitions.Def_AehligSchwichtenberg2002_Bounds
Formal statement
namespace AehligSchwichtenberg2002

theorem lemma_4_3 {Γ : Context} {t : Term}
    (ht : HasType Γ t .diamond) :
    Γ ≠ [] ∧ freeVars t ≠ [] := by sorry

end AehligSchwichtenberg2002
Source
Klaus Aehlig and Helmut Schwichtenberg, 'A syntactical analysis of non-size-increasing polynomial time computation', ACM Transactions on Computational Logic 3(3), 2002, pp. 383-401 (LICS 2000, pp. 84-91; doi:10.1145/507382.507386). Lemma 4.3, p. 395.
Read-back

What the Lean code literally says, in plain math · Gemini 3.1 Pro (Independent Blind Auditor)

Read-back: Thm_AehligSchwichtenberg2002_lemma_4_3.lean

Theorem lemma_4_3

Let Γ\GammaΓ be a context (a finite list of typed variables) and let ttt be a raw term. Assume that Γ⊢t:⋄\Gamma \vdash t : \diamondΓ⊢t:⋄ (HasType Γ t .diamond) in the affine linear typing system.

Then both of the following non-emptiness properties hold:

Γ≠[]andFV(t)≠[],\Gamma \neq [] \quad \text{and} \quad \mathrm{FV}(t) \neq [],Γ=[]andFV(t)=[],

where FV(t)\mathrm{FV}(t)FV(t) (freeVars t) is the duplicate-free list of free variables occurring in ttt (with variable occurrences inside λx. r\lambda x.\, rλx.r filtered by v≠xv \neq xv=x, where equality compares both numerical identifier id\mathrm{id}id and type ty\mathrm{ty}ty, and with free variable occurrences inside {r}\{r\}{r} included). In particular, no term ttt of type ⋄\diamond⋄ can be typed in the empty context [][][], and no term ttt of type ⋄\diamond⋄ under any typing context Γ\GammaΓ can be syntactically closed (FV(t)=[]\mathrm{FV}(t) = []FV(t)=[]), even though the typing rules for variables and constants (HasType.var and HasType.const) permit arbitrary unused variables in Γ\GammaΓ.

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