3.5

证明二元不动点定理：对于任何 F,G∈ΛF,G\in \Lambda，存在 X,Y∈ΛX,Y \in \Lambda，满足：

FXY=XFXY=X 和 GXY=YGXY=Y

证明

由标准组合子 K≡λxy.xK\equiv \lambda xy.x 和 K∗≡λxy.yK^* \equiv \lambda xy.y，定义一种有序对关系：

[M,N]=λz.zMN[M, N] = \lambda z. zMN，从而 [M,N]K=KMN=M[M,N]K = KMN = M，[M,N]=K∗MN=N[M,N] = K^*MN=N

要证：∃X1,X2\exists X_1, X_2， X1=FX1X2,X2=GX1X2X_1=FX_1X_2, X_2=GX_1X_2，从二元化归到一元，构造：

[F1(XK)(XK∗),F2(XK)(XK∗)]⋯(∗)[F_1(XK)(XK*), F_2(XK)(XK^*)] \cdots(*)

∃\exists fixed point XX，X=(∗)X = (*)，定义 X1=XK,X2=XK∗X_1 = XK, X_2 = XK^*，从而有

X1=F1X1X2X_1=F_1X_1X_2，X2=F2X1X2X_2=F_2X_1X_2