コンビネータ論理►to mock a mockingbird

to mock a mockingbirdを読む(6)9章

Compatible birds

同じでも異なっていてもよい2つの鳥A,Bが互換性がある(compatible)とは
次の条件を満たすときをいう

1
A x = y　かつ B y = x

Problem 6

Problem1のC1とC2の元で
任意の2つの鳥A,Bは互換性があることを示せ

解

1
2
3
ABは不動点yを持つ
x = B yとおくと
A x = A B y = y

Happy birds

鳥Aが幸せ(happoy)であるとは、それ自身と互換性があることを言う
つまり

1
A x = y かつ A y = x

Problem 7

少なくとも1つの鳥を好きな任意の鳥はhappyであることを示せ

つまりコンビネータが不動点を持つ時happyであるということを証明せよという問いである

解

1
2
3
4
AがBを好きであるとき
AB = Bであるので
x=B y=Bとおけば
Ax = y かつ Ay = x

normal birds

ある鳥が正規(normal)であるとは、少なくとも1つの鳥を好きなことを言う
Problem 7で示したとおり各normalな鳥はhappyである
この逆は必ずしも成り立たず、happyな鳥がnormalであるとは限らない

Problem 8

Problem1のC1の元で
森に少なくとも1つのhappyな鳥がいるとき
少なくとも1つのnormalな鳥がいることを証明せよ

解

1
2
3
4
5
6
7
8
Hがhappy birdだと仮定すると
Hx = y Hy = xなるxとyが存在する
xをHyで置き換えると
H(Hy) = y
条件C1の元でHとHを合成した鳥Bが存在する。
By = H(Hy) = y
つまりBy = y
Bはyが好き、よってBはnormalである