AFTD Auto-Formalizing Theoretical Domains

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.
Verified
08 Oct 2026
Axioms
none listed
Built on 3
Used by 1

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
See it in the graphDiscuss this resultChallenge it