突然想起来一个关于lambda演算的问题

Question

考虑所有的lambda函数的等价类(因为有许多形式上不一样的函数表达同一个东西)的集合,能否给这个集合一个代数结构?
如果我们把一个lambda函数以另一个为参数作用,看作是一个非交换的运算,那么这个集合已经接近构成一个群或者半群((lambda (x) x)是幺元,并且任何两个函数的结合还是函数),但是这似乎还不够,我觉得我无法说明一个lambda函数有逆,也无法否定它.
哦,还有,lambda演算是否满足结合率?似乎是满足的:f(g(h)) = (f(g))(h)?
各位大牛能否给出一个比较简洁的说法,或者推荐一些参考资料呢?谢谢!

[ 本帖最后由 PeterGhostWolf 于 2010-1-5 21:56 编辑 ]

Answer 1

((lambda (x) x)是幺元，那零元如何表示呢？

Answer 2

本帖最后由 luochen1990 于 2015-03-03 14:41 编辑

lambda演算确实可以看做是一个代数结构，其元素是lambda算子，相关的二元运算是apply（apply f x ，就是我们通常写的 f(x)）。
但是，这个代数结构，既不是群，也不是半群，而是比他们都更一般。
因为群比半群更特殊，所以我直接说为什么它不是半群了：因为半群要求相关的二元运算满足结合律，而apply是不满足结合律的。

(apply f (apply g x))  = (apply (combine f g) x)
         !=  (apply (apply f g) x)
where:
  apply = lambda f. lambda a. f a    = lambda f. lambda g. lambda x. (f g) x  （这里逆用了eta规约，为了与下面更好对比）
  combine = lambda f. lambda g. lambda x. f (g x)

后来又想了一下，如果不取apply，而是用combine作为定义半群的二元运算，那么应该可以构成一个幺半群

后续讨论可以见我在知乎的提问：www DOT zhihu DOT com/question/28481538

Answer 3

domain和codomain是所有lambda函数等价类构成的集合,因为每一个lambda函数作用在另一个lambda函数上还是得到一个lambda函数.
我纠结在"逆"这里,我不能确定一个lambda函数可以成为一个这个集合的变换,也没有什么思路.这样看起来它似乎已经是一个含幺半群了,我觉得还有再向前走的能力....
范畴学我一无所知,要过一段时间才有机会学到(现在知识还不足以接触T T)

Answer 4

楼主应该把问题陈述得更精确一些。至少把  domain 和  codomain 明确下来，否则 f g 有意义， g f 就不一定有意义了。由于一个映射不必是单的，所以不一定有逆。在代数中，有如下结论：

1、一个集合到自身的变换构成一个幺半群；
2、一个集合到自身的一一变换构成一个群。

如果要求 domain 和 codomain 不同，可以参考范畴方面的材料。

[ 本帖最后由 win_hate 于 2010-1-6 13:57 编辑 ]

Answer 5

你说的有点category theory的意思。函数确实组成一个monoid：
(f . g) . h = f . (g . h)
id . f = f
f . id = f

[ 本帖最后由 roy_hu 于 2010-1-6 15:28 编辑 ]