tnomuraのブログ

束と論理

「論理とは何か」という問いに一言で答えることができるだろうか。束論についていろいろと散策していたらそれができることに気が付いた。すなわち、論理とは、

「束という数学的構造の代数である。」

ということだ。束の定義は次のようになる。（Wikipedia より引用）

半順序集合 (L, ≤) が束であるとは、以下の二条件が満足されるときに言う。

二元の結びの存在
    L の任意の二元 a, b に対して、二元集合 {a, b} が結び（上限、最小上界、和） a ∨ b を持つ。
二元の交わりの存在
    L の任意の二元 a, b に対して、二元集合 {a, b} が交わり（下限、最大下界、積） a ∧ b を持つ。

これは抽象的な概念だが、幸い直感的に理解できる例がある。それは領域 D の冪集合 P(D) だ。P(D) では和集合と、共通部分という演算について閉じており、また、包含関係という半順序が定義できる。さらに、それらの分配法則や補元の定義もできる。これらは、論理の性質そのものだ。

つまり、数学的対象が束であれば、それは論理で余すところなく記述することができるのだ。

しかし、集合も個体も対象として考え、集合の外延を個体間の所属関係から求める構造は、束の要件を満たしていない。これらの構造は「自分自身を要素として含まない集合」などの自己言及が可能だが、束ではないので論理をこの構造の代数として用いることができないのだ。

ラッセルのパラドックスが明らかにしたのは、束という構造をとらないシステムには論理が適用できないということだ。

ところで、数学的対象のなかで最も重要な自然数は束である。自然数はすべての代数の基礎であるので、ほとんどの数学的対象に論理が適用できるのも理解できる。

また、集合と論理の演算の類似は、どちらも束としてとらえることができるからなのだろう。「論理とは何か」、「どうして論理と集合は似ているのか」、「論理で扱える集合とはどのような集合か」、「どうして論理は普遍的なのか」などの頭を悩ませる問いは、「論理は束の代数である」という観点からすっきりと理解できる。

束論は教科書を買って勉強し始めたばかりなので、上の議論は論証を含まない直感的なものだが、おそらく正当なものだろうと思う。

論理は万能か

集合とは物の集まりであるという素朴集合論の定義では、ラッセルのパラドックスという矛盾が発生してしまう。したがって、公理によって集合の定義を制限することによって論理と整合性のあるものを集合と考えようというのが公理的集合論なのだろう。

この発想のもとになっているのは、論理はどのような場合にも正当性があるので、集合の定義をそれに合わせなければならないという暗黙の了解である。したがって、物の集まりが集合であるという定義は本当の集合を定義できていないという表現も生まれてくるのだろう。しかし、その場合、公理的集合論で定義される集合とはどのようなものかという疑問に答えてくれる記述が見あたらない。公理的集合論の公理に適合するものが集合だというのは答えにはなっていない。正当な集合につての直感的なイメージが作れないのだ。

状況を整理するために、一度、論理は万能だという考えを疑ってみる必要があるのではないだろうか。論理は多様なシステムの記述に効果を表すが、論理が効果を表せないシステムも実際に存在する。それはラッセルのパラドックスから明らかだ。集合も個体も等しく対象と考え、集合の定義は対象間の所属関係を表す特性関数で決定するというシステムでは、自分自身を要素として含まない集合の集合は定義できず、論理演算が行えなくなるからだ。

論理は論理演算が適用できるシステムしか記述できないと考えるべきだ。それでは、論理が適用できるシステムとはどのようなものだろうか。

束論では束の代表例として領域集合の冪集合を挙げている。冪集合は和集合、共通部分の演算について閉じており、集合の包含関係による大小関係も存在する。このようなシステムの要素には、集合演算が矛盾なく適用できる。この場合、冪集合の要素は物の集まり、すなわち、領域の要素の集まりと考えても全く矛盾はない。つまり、束は集合の定義と集合演算を矛盾なく適用できる構造を持っているのだ。

同様の事情が論理についてもいえるような気がする。論理にもそれが適用できる特定の構造があるということだ。論理は万能ではなく、論理が適用できる構造を必要としているのではないだろうか。

証明の発見

前回 ￢￢A -> A を発見的に証明する方法について考えてみたが、その際 ￢A -> (A -> B) と A -> A という定理を使用したので、これらを証明してみる。使用する変換規則は次のようになる。

Tr1: A => B -> A

Tr2: A -> (B -> C) => ((A -> B) -> (A -> C))

Tr3: ￢B -> ￢A => A -> B

まず ￢A -> (A -> B) を証明してみる。最初にこの論理式を含む公理を作らなければならないが、論理式全体に対偶の公理を使うと ￢(A -> B) という扱いづらい論理式ができてしまうので、A -> B に注目して対偶の公理を使う。

(￢B -> ￢A) -> (A -> B)

これに変換規則 Tr1 を適用して、

￢A -> ((￢B -> ￢A) -> (A -> B))

Tr2 を適用

(￢A -> (￢B -> ￢A)) -> (￢A -> (A -> B))

前項が公理なので後項は定理

￢A -> (A -> B)

次に A -> A の証明をしてみる。最初に A -> A を後項とする次のような論理式を考える。B は未定である。

(A -> B) -> (A -> A)

この論理式が定理で、A -> B が定理ならば A -> A は証明できる。この論理式を含む公理は、

(A -> (B -> A)) -> (A -> B) -> (A -> A)

A -> (B -> A) は公理なので、後項は定理。

(A -> B) -> (A -> A)

これは B の値によらず定理である。B は任意なので B -> A と置き換えると、

(A -> (B -> A))  -> (A -> A)

前項は定理だから後項は定理。

A -> A

どちらの証明も最終的な結論を出発点として証明を探すことができる。また、公理の適用を行う意味が分かりやすい。

変換規則による命題論理の証明の発見

命題論理の証明を論理式に変換規則を適用することと考えると、定理の証明の発見が楽になる。最初に変換規則を再掲する。

Tr1: A => B -> A

Tr2: A -> (B -> C) => (A -> B) -> (A -> C)

Tr3: ￢B -> ￢A => A -> B

そこで、例として ￢￢A -> A の証明を発見的に解決してみよう。

まず、￢￢A -> A は定理の前項の論理式を B とすると、B -> (￢￢A -> A) という形の論理式(定理）から導入されるはずだ。そこで証明の出発となる定理を仮定する。最初に思いつくのは Tr3 の対偶の公理だ。すなわち、次のようになる。これは公理である。

(￢A -> ￢￢￢A) -> (￢￢A -> A)

これを元に ￢￢A -> A への変換を考えることになる。上の公理から、変換規則 Tr1 によって次の定理が得られる。

￢￢A -> ((￢A -> ￢￢￢A) -> (￢￢A -> A))

これは定理だから、これから変換規則 Tr2 によって次の定理が得られる。

(￢￢A -> (￢A -> ￢￢￢A)) -> (￢￢A -> (￢￢A -> A))

上の論理式で前項は定理だから、後項も定理である。

￢￢A -> (￢￢A -> A)

この論理式にさらに Tr2 を適用して、

(￢￢A -> ￢￢A) -> (￢￢A -> A)

これは前項が定理だから、後項は定理である。すなわち、

￢￢A -> A

以上の証明の過程について見てみると、最初に、証明したい論理式を元に公理（または定理）を作り、それを変換規則で新しい定理に変換していくという一連の操作で証明が完成している。格段の工夫もなく自然に証明が行われる。

変換規則を元にした命題の証明は、証明の意図が明確になり証明の発見がたやすくなるという特徴がある。

前件肯定 (modus ponens) と変換規則

命題論理の推論規則のうち、ウカシェビッチの公理はすべて、論理式の変換規則としてとらえることができる。ウカシェビッチの公理は次の3つだ。

Ax1： A -> (B -> A)

Ax2: (A -> (B -> C)) -> ((A -> B) -> (A -> C))

Ax3: (￢B -> ￢A) -> (A -> B)

これは、定理の変換規則として考えることができる。定理の論理式があった場合、それを変換規則によって変換することで新しい定理を作ることができる。上の3つの公理に対する変換規則は次の3つだ。

Tr1: A => B -> A

Tr2: A -> (B -> C) => (A -> B) -> (A -> C)

Tr3: ￢B -> ￢A => A -> B

これらの変換規則は => の前項が定理なら、後項が定理になるという関係を表している。例えば、命題 A が定理ならば、任意の命題 B について変換規則 Tr1 によって、B -> A は定理である。

公理を変換規則としてとらえる利点は、議論の焦点を定理の論理式に絞ることができるからだ。証明は論理式に変換規則を適用することによって新たな論理式を導き出すという操作になる。

しかし推論規則の前件肯定 (modus ponens) についてはそうはいかない。前件肯定では二つの定理 A と A -> B から新しい定理 B を導かなくてはならず、常に2つの定理に注意を払う必要があるからだ。しかし、前件肯定の議論を論理式の変換規則としてとらえることができれば、命題論理の議論が見通しの良いものになる。

そこで、前件肯定の規則を変換規則に変える方法を考えてみた。つまり、定理 A と定理 A -> B から定理 B を推論するに際しては、A と A -> B は定理である。したがって、A => B という変換規則を新たに採用すると、その変換規則 A => B は定理 A を定理 B に変換する新しい変換規則になる。したがって、公理由来の変換規則以外に A => B を定理を定理に変換する新しい変換規則として採用してよいということになる。

新しい定理が作られるたびに新しい変換規則が採用されるので、変換規則の数は証明が進むたびに増えていくが、証明の操作は、常に定理を変換して新しい定理を作るという一貫した操作になる。

この方法で A -> A が定理であることを証明してみよう

A -> ((A -> A) -> A) ..... 公理 Ax1

(A -> (A -> A)) -> (A -> A) ..... 変換規則 Tr2 の適用

A -> (A -> A) => A -> A ..... 定理から導入した新しい変換規則 Tr-a

A -> (A -> A) ..... 公理 Ax1

A -> A .... 変換規則 Tr-a の適用

この証明の特徴は、証明が常に定理の変換規則で行われるということだ。分岐などはないので、証明の意図が非常にわかりやすくなる。やっていることは通常の命題論理の証明とかわらないが、どこに証明の意図があるかに焦点を当てることができる。

定理から新しい変換規則を導入するという方法で、命題論理の証明を、常に定理に変換規則を適用して新しい定理を作るという操作に統一することができる。