[論理学をつくる] 定理4 : Unique Readability Theorem

「論理学をつくる」の定理４の証明で躓きました。テキストから定理を引用します。

【定理4 : unique readability theorem】A, B, Cはすべて論理式とする。
　また, △, ▲は任意の相異なる２項結合子（→, ∨, ∧）のどれかとする。
　（１） (A △ B) = (C ▲ D)というようなことはない。
　（２） (A △ B) = (¬ C)というようなことはない。
　（３） (A △ B) = (C △ D)ならばA=C, B=Dである。

続けて、（１）の証明の前半を引用します。

（１）仮に(A ∧ B) = (C → D)であるとする。そうするとA ∧ B) = C → D)である。このとき, A=Cでなくてはならない。なぜなら, さもないとA, Cの一方が他方の始切片ということになるが,

「他方の始切片ということになるが」で、議論を追えなくなりました。しばらく悩んだ末に私がたどり着いた考えをここに書いておきます。

まず、=（等号）の定義の確認しておきます。この証明において、等号は左辺と右辺の記号列が等しいことを表しています。論理式の値や意味と別の視点で見ます。

論理式を構成する記号列の話をしているので、両辺の左端から左括弧を取り除いても

A ∧ B) = C → D)

が成り立ちます。

ここで、論理式AとCを構成する記号列について考えます。まず、論理式Aの記号列とCの記号列の長さが異なるとします。仮に、Cの記号列の方が短いとします。模式的に書くと次のようになります。

　　A = ◯◯◯◯◯◯◯
　　C = ◎◎◎◎◎

証明の仮定(A ∧ B) = (C → D)から、論理式Aの記号列の左から５つ目までは、論理式Cの記号列と一致しなくてはなりません。（等号の定義に注意）

つまり、論理式Cの記号列は論理式Aの始切片であるといえます。

定理の仮定で、Cは論理式であるとしています。しかし、定理３によれば、論理式の始切片は論理式ではありません。ここで矛盾が生じました。

矛盾が生じた原因は、論理式AとCの記号列の長さが異なるとしたことによります。これにより、AとCの長さが等しいためA=Cであるといえます。

これ以降の証明については、テキストに書いてある通りに理解できると思います。