不動点パズル24：二重不動点原理の導出（１）

（前回はこちら）

機械に、ある記号列を入力すると、ある記号列をもたらす。この機械には規則がある。規則Q と C を再掲しておく。

規則Q　Qx → x
（任意の記号列 x に対して、記号列 Qx は x をもたらす）
規則C　x → y ならば、Cx → yQy
（x が y をもたらすならば、Cx は y の随伴 yQy をもたらす）

この機械（処理系）において、アーニーは、「すべての特殊記号列Θは不動点をもつ」という。これを「アーニーの不動点原理」という。

特殊記号列
記号列Θは、任意の記号列 x に対して、『記号列ΘQx がある記号列 y をもたらすならば、x をもたらす Qx 以外の記号列 z に対しても、Θz はΘQx と同じく y をもたらす』という性質をもつとき、特殊記号列を呼ぶ。

不動点
x がΘ(x) をもたらすならば、x をΘの不動点という。

さらに、アーニーは、二重不動点原理を持ち出した。

二重不動点原理
任意の特殊記号列Θ₁ とΘ₂ に対して、x がΘ₁(y) をもたらし、y がΘ₂(x) をもたらすような記号列 x と y が存在する。

この「アーニーの二重不動点原理」を証明することが目標である。

そのためのガイドとして、以下の問題があった。今回はこの問題について考える。
問27　規則Q と C だけを使い、それぞれが互いにもう一方をもたらすような二つの相異なる記号列を見つけよ。


（解答）
それぞれが互いにもう一方をもたらすような二つの相異なる記号列を x、y とし、

x → y　・・・・・①
y → x　・・・・・②

となるような記号列 x、y を探す。

このとき、記号列 x、y は、どちらかが Q からはじまる記号列で、もう片方は C からはじまる記号列であると考えられる。なぜなら、両方とも同じ記号からはじまる記号列であると、規則の性質上、互いにもう一方をもたらす相異なる記号列は存在しないからである（これにも証明が必要かもしれないがここでは省略する）。

そこで、x = Qx₁、y = Cy₁ と考えると、

Qx₁ → Cy₁　・・・・・①'
Cy₁ → Qx₁　・・・・・②'

となるような記号列を探すことになる。

②'において、CQzC → zCQzC が使えそうである。この z を Q とすると、CQQC → QCQQC がいえる。QCQQC は CQQC をもたらすので、①'も満たす。

よって、規則Q と C だけを使い、それぞれが互いにもう一方をもたらすような二つの相異なる記号列に、QCQQC と CQQC がある。

（つづく）