部分组合代数

部分组合代数是对单一类型 $\lambda$ 演算的推广, 它允许函数应用仅对部分情况定义. 这也可以看作一种代数化的组合子逻辑.

1定义

记 $A\rightharpoonup B$ 为从 $A$ 到 $B$ 的部分函数的集合. 这可以看作 $A\to (\{\perp \}\bigsqcup B)$ 的函数集.

定义 1.1 (部分应用结构). 对于集合 $A$, 其上的部分应用结构为对部分输入有定义的二元运算符$$m:A\times A\rightharpoonup A$$并且一般 $m(a,b)$ 在有定义的情况下 (即 $(a,b)\in \mathrm{dom}m$) 会记作 $ab$ 或者 $ab$.

定义 1.2 (同态). 对于集合 $A,B$ 及其各自的部分应用结构, 其上的同态定义为满足如下条件的函数 $f:A\to B$: $$f(ab)=f(a)f(b)$$这个公式隐含了对于有定义的 $ab$, 必定存在有定义的 $f(a)f(b)$. 注意 $f$ 必须是全函数, 也就是说它对全部输入都有定义.

定义 1.3 (部分组合代数). 在满足如下条件时, 集合 $A$ 及其上的部分应用结构 $m$ 是一个部分组合代数:

•	存在 $k\in A$ 使得对于任意 $a,b\in A$ 都有: ∘ $ka$ 和 $kab$ 有定义, 且 ∘ $kab=a$

•	存在 $s\in A$ 使得对于任意 $a,b\in A$ 都有: ∘ $sa$ 和 $sab$ 有定义, 且 ∘ 对于任意 $c\in A$, $sabc$ 有定义当且仅当 $(ac)(bc)$ 有定义, 且两者相等.

部分组合代数之间的同态就是它们之上的部分应用结构的同态.

定义 1.4. 部分组合代数中, 若其上的部分应用结构 $m:A\times A\rightharpoonup A$ 是全函数, 那么这是一个完全组合代数.

2例子

•

Kleene 第一代数是定义在自然数集上的部分组合代数. 考虑所有一般递归函数组成的集合 $S\subseteq \mathbb{N}\rightharpoonup \mathbb{N}$. 它的 Gödel 编码给出一个单射 $e:S\hookrightarrow \mathbb{N}$, 使得求值映射$$\mathrm{ev}(f,n)=\{\begin{array}{ll}{e}^{-1}(f)(n)& (f\in e(S))\\ \perp & (\text{其他情况})\end{array}$$是 $\mathbb{N}\times \mathbb{N}\rightharpoonup \mathbb{N}$ 的一般递归函数. 令求值映射给出部分应用结构, 则由 Gödel 编码的定义容易验证这构成部分组合代数.

3性质

引理 3.1. 任意部分组合代数 $A$ 都存在恒同映射, 即存在 $i\in A$ 使得对于任意 $a\in A$ 都有$$ia有定义且ia=a$$

证明. 令 $i=skk$.

$\square$

引理 3.2. 任意部分组合代数 $A$ 都存在不动点组合子, 即存在 $y\in A$ 使得对于任意 $a\in A$ 都有$$a(ya)和ya有定义且a(ya)=ya$$

证明. 令 $y=s(k(sii))(s(s(ks)k)(k(sii)))$.

$\square$

术语翻译

部分组合代数 • 英文 partial combinatory algebra