to mock a mockingbirdを読む(32)13章

A Gallery of Sage Birds

order 1の鳥とは鳥Aについて、Axがxのみで表せることをいう。
mockingbirdMx = xxやidentity bird I x = xなどがこれに当たる。
これまでに出てきたコンビネータの中では、この2つだけがorder 1に該当する。
もちろんorder1の鳥は無数にあり、例えばAx = x(xx)やAx=(x(xx))((xxx)x)といったものを考えることができる。

order 2の鳥とは鳥Aについて、Axyがxとyのみから表せることをいう。
order 2の鳥としては、Thrush, Lark, Warblerなどが挙げられる。

同様にorder 3の鳥とは鳥AについてAxyzがx,y,zのみで表せることを言う。
ここまでに遭遇した鳥の多くはorder 3である。
B,C,R,F,Vに加えてQ,Q1,Q2,Q3,Q4はorder 3となる。

同様に考えてorder 4,5,6,7,8などを考えることができる。
Doveはorder 4,Bald Eagleはorder 7である。

オーダーを持たない鳥もいる。例えばTIx=xIでIを消すことができないのでTIはオーダーを持たない。
TIxy=xIy TIxyz=xIyzと変数を増やしてもIが消せないため、オーダーを持てない。
何らかのオーダーを持つ鳥はproper combinatorial bird,またはもっと短くproper birdと呼ぶ。

combinatorial birdとは、proper birdを用いて表現できる鳥を言う。
combinatorial birdはproperとは限らない。
TIはcombinatorial birdだがproperではない。
一方ITはproperである。IT = Tであるため。

SOME SAGE BIRDS

賢人鳥(sage bird)Θとは、任意の鳥xについて以下を満たす鳥を言う。

x(Θx)=Θx
(xはΘxが好き)

賢人鳥はproper birdではない。
しかしproper birdを使って賢人鳥を表すことはできる。
10章では具体的な賢人鳥は求めずにその存在を示したが、
ここからはあるproper birdの元で賢人鳥を求めていく