是否存在两个外延相等但范式不同的 lambda 项？

Question

考虑无类型 lambda 演算。 "normal form" 仅表示 "beta-eta-nf"。 "different/same" lambda 项比较 mod alpha 转换。

这个问题和"Is there a counterexample of the following proposition?"

一样

∀ t1 : term, ∀ t2 : term, (∃ t1'= nf t1  ∧  ∃ t2' = nf t2) →  (t1' = t2' ↔  ex_eq  t1  t2)

或者，有证据吗？

Answer 1

(以下将=读作\equiv_{\beta\eta})

我想你想要的是伯姆定理的直接应用。定理指出：

Theorem (Böhm, 1968) Let f, g be two closed lambda terms in beta-eta normal form which are not equivalent up to alpha-conversion. Then there exist closed terms a_1, ..., a_n in beta-eta normal form such that for all x, y it holds:
  f a_1 ... a_n x y = x
  g a_1 ... a_n x y = y

一个直接的推论是：

推论： 如果 f 和 g 是 beta-eta 范式中的两个闭项，不等于 alpha 转换，则它们在外延上并不等价。

证明：为了自相矛盾，假设fg在NF中并且不同，但是他们是外延等效。选择 a_1, ..., a_n，如 Böhm 定理。由于 f、g 被假定为外延等价，因此 f a_1 必须等于 g a_1。但这与任意不相等的 x 和 y 相矛盾 f a_1 ... a_n x y = x != y = g a_1 ... a_n x y。因此假设一定是错误的，f 和 g 毕竟不能外延等价。

现在：

推论： 假设 f、g 是两个闭 lambda 项，分别具有现有范式 nf 和 ng .它认为：当且仅当 f 和 g 在扩展上等效时，nf 等效于 ng 直到 alpha 转换。

证明： 一个方向：如果 nf 等价于 ng 直到 alpha 转换，则 f 和 g 由于合流（Church-Rosser 定理）而扩展等价。相反方向：根据前面推论的对立，如果 nf 和 ng 在外延上等价，那么它们必须等于 alpha 转换。

因此，您问题的答案是“不，没有两个外延相等但范式不同的项”。但这对你没有多大帮助，因为正常形式的存在是不可判定的。因此，例如，它不会突然使两个任意程序的等价性变得可判定。

是否存在两个外延相等但范式不同的 lambda 项？

Is there two lambda terms which are extensional equal but have different normal forms?

lambda

functional-programming

lambda-calculus