2002年 5月15日 作成 反射性の証明 >> 目次 (テーマごと)
2007年 7月16日 補遺  


 
 さて、今回は、「反射性」 の証明を扱ってみましょう。反射性は、対称性と移行性から導出できます
 記号の操作に慣れるには都合の良い例題ですから、ゆっくりと取り組んでみてください。

 反射性・対称性・移行性については、前々回 (4月14日、116ページ)、説明しました。
 反射性・対称性・移行性は、以下のように記述されます。

 (1) 反射性 ∀x R (x, x).
 (2) 対称性 ∀x ∀y [ R (x, y) ⇒ R (y, x) ].
 (3) 移行性 ∀x ∀y ∀z{ [ R (x, y) ∧ R (y, z) ] ⇒ R (x, z)}.

 まず、以下の「全称の存在化」 を思い出してください

 (1) ∀x P (x) ⇒ P (x).
 (2) P (x) ⇒ ∃x P (x).

 (1) を証明のなかで使いますので、覚えておきましょう。
 では、反射性を導出するための前提になっている対称性と移行性を変形しましょう。

 1.対称性の置換:

 ∀x ∀y{ [ R (x, y) ⇒ R (y, x) ] は、以下のように置換できます (全称の x を単称の u に置換する)。

   ∀y{ [ R (u, y) ⇒ R (y, u) ]. (A)

 ∀y{ [ R (u, y) ⇒ R (y, u) ] は、以下のように置換できます (全称の y を単称の v に置換する)。

    [ R (u, v) ⇒ R (y, v) ]. (B)

 
 2.移行性の置換:

 ∀x ∀y ∀z{ [ R (x, y) ∧ R (y, z) ⇒ R (x, z) ] は、以下のように置換できます (全称の x を単称の u に置換する)。

   ∀y ∀z { [ R (u, y) ∧ R (y, z) ⇒ R (u, z) ].

 ∀y ∀z { [ R (u, y) ∧ R (y, z) ⇒ R (u, z) ] は、以下のように置換できます(全称の y を単称の v に置換する)。

   ∀z { [ R (u, v) ∧ R (v, z) ⇒ R (u, z) ].

 ∀z{ [ R (u, v) ∧ R (v, z) ⇒ R (u, z) ] は、以下のように置換できます(全称の z を単称の u に置換する)。

   { [ R (u, v) ∧ R (v, u) ⇒ R (u, u) ]. (C)

 ∀x ∀y ∀z { [ R (x, y) ∧ R (y, z) ⇒ R (x, z) ] は、以下のように置換できます(全称の x を単称の v に置換する)。

   ∀y ∀z { [ R (v, y) ∧ R (y, z) ⇒ R (v, z) ].

 ∀y ∀z{ [ R (v, y) ∧ R (y, z) ⇒ R (v, z) ] は、以下のように置換できます(全称の y を単称の u に置換する)。

   ∀z { [ R (v, u) ∧ R (u, z) ⇒ R (v, z) ].

 ∀z{ [ R (v, u) ∧ R (u, z) ⇒ R (v, z) ] は、以下のように置換できます(全称の z を単称の v に置換する)。

   { [ R (v, u) ∧ R (u, v) ⇒ R (v, v) ]. (D)

 
 3.反射性の証明:

 以上の置換の結果 (A、B、C、D) を、それぞれ、以下のように置換します。

 (1) X = R (u, v).
 (2) Y = R (v, u).
 (3) U = R (u, u).
 (4) V = R (v, v).

 では、証明しましょう。

 (1) X ⇒ Y.      (対称性)
 (2) Y ⇒ X.      (対称性)
 (3)(X ∧ Y) ⇒ U. (移行性)
 (4)(X ∧ Y) ⇒ V. (移行性)

 したがって、X ⇒ (U ∧ V).
 したがって、R (u, v) ⇒ [ R (u, u) ∧ R (v, v) ]. (反射性)

 さて、この証明が、いったい、なんの役に立つのか、といえば--反射性が、対称性や移行性から導出されるということは--、「抽象化」 を定義しているのです。つまり、「論理的な同一性」 を保証する概念なのです。たとえば、集合の対等とか作図の合同とか価値の等価とかの概念を保証するのです。

[ 補筆 ]
 以上に述べた置換のやりかたを習得しておいてください。
 置換のやりかたがわからないと、(以前の 「読書案内」 のなかで記載した) ヒルベルト・アッケルマン 共著の 「数学の基礎」 を読むことができない。「数学の基礎」 では、冠頭量化記号の外しかたや置換のやりかたが多用されています。

 次回は、「広義の述語論理」 について説明します。 □

 



[ 補遺 ] (2007年 7月16日)

 この証明例題は、われながら、なかなか良い例題を選んだなと思っています。というのは、2つ集合が対等である 「論理的な同一性」 が反射性・対称性・移行性を前提にして証明できるし、その証明が、私のような数学の シロート であっても、追跡できる簡単な証明だから。この証明のなかで、シロート が思い浮かばない着想は、全称を単称で置換するという手続きでしょう。われわれ シロート が、実際に--仕事のなかで--、こういう証明をすることは、まず、ないと思うのですが、この証明を追跡して、置換の手続きが証明のなかで大切な役割をはたしていることを認識すれば良いでしょうね。そうすれば、数学基礎論の他の書物を読んでいて、証明がいくつも出てきて、それらの証明のなかで置換が使われていても、納得することができるでしょう。「補遺」 として綴ったように、私は、「数学の基礎」 (ヒルベルト・アッケルマン) を読んだときに、それを切に感じました。




  << もどる ベーシックス すすむ >>
  数学基礎論