「スマリヤンのゲーデル・パズル」Q70の証明 3
[ ]→x
ならば
C[ ]→xQx
なので、
[ ]→y
yが[ ]よりも長い記号列ならば、
C[ ]→yQy
の右辺は、[ ]よりも長い記号列になります。ここで、
C[ ]とyQyが異なることが示されました。(ただしCQCの場合を除く)
C[C・・C[ ]]→[C・・C[ ]]Q[C・・C[ ]]
この場合、両辺は異なると仮定します(数学的帰納法)。さて、Cをもうひとつ増やすと
C[C[C・・C[ ]]]→[C[C・・C[ ]]]Q[C[C・・C[ ]]]
となり、この両辺も異なります。ゆえに、CとQのみを使った記号列で、自らをもたらす記号列はCQCのみであることが証明できました。
いやあ、長くて非エレガントですね。もっと簡潔に書けるといいのですが、僕にはこれが限界です。