Lemma 2.21 and Corollary 2.22 — Bound on reduction sequences
OpenABHS2004V2.corollary_2_22Each bounded reduction of a typed term strictly decreases . The step count of a reduction sequence is at most the initial measure with parameter the number of free variables.
import Definitions.Def_ABHS2004V2_TermSystem
namespace ABHS2004V2
/-- Lemma 2.21 and Corollary 2.22. A bounded reduction strictly decreases `theta`,
which bounds the length of a reduction sequence. -/
theorem corollary_2_22 {r : Term} {ρ : Ty} (ht : HasType r ρ) :
(∀ (n : Nat) (r' : Term), RedStepBounded n r r' → theta n r' < theta n r) ∧
(∀ (k : Nat) (r' : Term), RedSteps k r r' → k ≤ theta (freeVarCount r) r) := by sorry
end ABHS2004V2Read-back
What the Lean code literally says, in plain math · OpenAI Codex (GPT-6)
For every term and type , assume has type . For every natural number and term , a one-step reduction from to that contracts a redex with at most free variable occurrences implies . The occurrence test is on the source of the contracted conversion. It is inherited through application and iterator contexts without an additional count test on the surrounding term. In addition, for every natural number and term , if reaches in exactly ordinary steps, then , where is the number of free variable occurrences of , with repetitions. Both natural numbers may be zero. A chain of length zero goes from to itself.
The measure is on a variable or constant, increases by through an abstraction, adds the children's measures at an application, and at an iterator satisfies
Here if is syntactically a chain of fully applied cons constants ending in a nil constant, and otherwise. Nil alone has count . The cons count depends on the shape of the tail at each node.
The typing judgment gives a variable its recorded type, a constant its declared type, and the type when has type . To type at , the rules require at , at , and disjoint free-variable lists in the sense of no shared member. To type at , they require at and a closed at , 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.
A step contracts one of the following syntactic conversions at the root or inside either child of an application or iterator. With application associating to the left, denotes the iterator with list term and step term . Write for the tensor introduction, tensor elimination, product introduction, two product projections, two sum injections, and sum elimination constants. For any type parameters , the conversions are with capture-avoiding substitution, , , , and , with and in the right-branch rule. The list conversions are and , the latter when is a chain of fully applied cons constants ending in a nil constant. The step contexts consist exactly of the root and descendants reached by those application and iterator rules.