表示 λ 项的 beta 等式类型的正确方法是什么？

Question

我正在寻找在 a : Term、b : Term 上索引的 BetaEq 类型，如果 a 和 b 相同，则可以居住，或者在一系列 beta 归约后它们是否可以变成相同的项。例如，假设 id = (lam (var 0))、a = (app id (app id id)) 和 b = (app (app id id) id)；那么我们应该可以构造一个BetaEq a b类型的term，因为两边都可以化简为(app id id)。我试过这个：

data BetaEq : (a : Term) -> (b : Term) -> Set where
  refl : (a : Term) -> BetaEq a a
  redl : (a : Term) -> (b : Term) -> BetaEq (apply-redex a) b -> BetaEq a b
  redr : (a : Term) -> (b : Term) -> BetaEq a (apply-redex b) -> BetaEq a b

其中 apply-redex 执行一次归约。但这看起来有点虚构，所以我不确定这是否是正确的方法。请注意，这两个术语可能会有所不同，因此我们不能简单地考虑范式。表示 beta 等式的标准方法是什么？

Answer 1

假设范围明确的无类型 lambda 项：

open import Data.Fin
open import Data.Nat

data Tm (n : ℕ) : Set where
  var : Fin n → Tm n
  app : Tm n → Tm n → Tm n
  lam : Tm (suc n) → Tm n

还有最外层变量的单一替换的定义（但请注意，在并行替换方面定义单一替换总是更可取）：

sub : ∀ {n} → Tm n → Tm (suc n) → Tm n

那么 beta 相等是 beta 归约的同余闭包：

data _~_ {n} : Tm n → Tm n → Set where
  β      : ∀ {t u} → app (lam t) u ~ sub u t
  app    : ∀ {t t' u u'} → t ~ t' → u ~ u' → app t u ~ app t' u'
  lam    : ∀ {t t'} → t ~ t' → lam t ~ lam t'
  ~refl  : ∀ {t} → t ~ t
  ~sym   : ∀ {t t'} → t ~ t' → t' ~ t
  ~trans : ∀ {t t' t''} → t ~ t' → t' ~ t'' → t ~ t''

通过同余闭包，我们指的是最小关系：

一种等价关系，即自反、对称和传递的等价关系。
关于术语构造函数的同余，即可以进行归约在任何构造函数中。
通过一步减少 beta 来暗示。

或者，您可以给出一个定向的归约概念，然后将可转换性定义为归约到一个通用术语：

open import Data.Product
open import Relation.Binary.Closure.ReflexiveTransitive

-- one-step reduction
data _~>_ {n} : Tm n → Tm n → Set where
  β    : ∀ {t u} → app (lam t) u ~> sub u t
  app₁ : ∀ {t t' u} → t ~> t' → app t u ~> app t' u
  app₂ : ∀ {t u u'} → u ~> u' → app t u ~> app t u'
  lam  : ∀ {t t'} → t ~> t' → lam t ~> lam t'

-- multi-step reduction as reflexive-transitive closure
_~>*_ : ∀ {n} → Tm n → Tm n → Set
_~>*_ = Star _~>_

_~_ : ∀ {n} → Tm n → Tm n → Set
t ~ u = ∃ λ t' → (t ~>* t') × (u ~>* t')

看情况用哪个版本比较方便。这两个定义是等价的，但 AFAIK 证明这种等价是相当困难的，因为它需要显示 confluence 减少。

表示 λ 项的 beta 等式类型的正确方法是什么？

What is the proper way to represent a beta-equality type for λ-terms?

agda