Cslib.SKI.Polynomial.elimVar
defimported Lean
Inductively define a polynomial Γ' so that (up to the fact that we haven't defined reduction on polynomials) Γ' ⬝ t ↠ Γ[xₙ ← t].
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in open Relation in def Cslib.SKI.Polynomial.elimVar {n : Nat} : SKI.Polynomial (n+1) → SKI.Polynomial n /- The K-combinator leaves plain terms unchanged by substitution `K ⬝ x ⬝ t ⇒ x` -/
- Defined in
- CSLib, `Cslib.SKI.Polynomial.elimVar`
- Lean proof
- By Thomas Waring, from github.com/leanprover/cslib at
3951377e5a3f(Copyright (c) 2025 Thomas Waring. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.33.0.Cslib.SKI.Polynomial.elimVar← Cslib.SKI.Polynomial.elimVar (Cslib/Languages/CombinatoryLogic/Basic.lean:72): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Built on 3
- Cslib.SKI.PolynomialA polynomial is an SKI terms with free variables.
- Cslib.SKIAn SKI expression is built from the primitive combinators
S,KandI, and application. - Cslib.SKI.CoeTermPolynomialCslib.SKI.CoeTermPolynomial
- Used by 1
- Cslib.SKI.Polynomial.toSKIBracket abstraction, by induction using
SKI.Polynomial.elimVar
- Cslib.SKI.Polynomial.toSKIBracket abstraction, by induction using
Lean source view module on GitHub
set_option quotPrecheck false open Cslib Cslib.SKI local infixl:100 " ⬝' " => SKI.Polynomial.app local prefix:101 "&" => SKI.Polynomial.var open Cslib Cslib.SKI @[inherit_doc] local infixl:100 " ⬝ " => app set_option autoImplicit true in set_option relaxedAutoImplicit true in open Relation in /-- Inductively define a polynomial `Γ'` so that (up to the fact that we haven't defined reduction on polynomials) `Γ' ⬝ t ↠ Γ[xₙ ← t]`. -/ def Cslib.SKI.Polynomial.elimVar {n : Nat} : SKI.Polynomial (n+1) → SKI.Polynomial n /- The K-combinator leaves plain terms unchanged by substitution `K ⬝ x ⬝ t ⇒ x` -/ | .term x => K ⬝' x /- Variables other than `xₙ` use the K-combinator as above, for `xₙ` we use `I`. -/ | .var i => by by_cases i<n case pos h => exact K ⬝' (.var <| @Fin.ofNat n ⟨Nat.ne_zero_of_lt h⟩ i) case neg h => exact ↑I /- The S-combinator inductively applies the substitution to the subterms of an application. -/ | .app Γ Δ => S ⬝' Γ.elimVar ⬝' Δ.elimVar