2020年2月4日火曜日

「パースの法則」は「少しも変」ではない。:「自然演繹」による「パースの法則」の「5(3)通りの証明」。

(01)
排中律や二重否定の除去と等価な命題のひとつで、変なものとして、パースの法則があります。
任意の命題P, Qについて、
((P→Q)→P)→P
が成り立つ
『「PならばQ」ならばP』ならばP
なんか、パズルのような命題ですね。
排中律、二重否定の除去、パースの法則 - Qiita)
(02)
5 原始的規則あるい導出された規則を、既に証明されたどのような連式あるいは定理とでも、ともに用いて、証明せよ。
5 Using primitive or derived rules, together with any sequents or theorems already proved, prove;
(c)├((P→Q)→P)→P 
(E.J.レモン、論理学初歩、竹尾治一郎・浅野楢英 訳、1973年、80頁と、原文)
cf.
ただし、「E.J.レモン、論理学初歩」には、「練習問題の解答」は、載ってゐません。
然るに、
(03)
(ⅰ)
1   (1)  (P→ Q)→P   A
1   (2) ~(P→ Q)∨P   1含意の定義
 3  (3) ~(P→ Q)     A
  4 (4)  ~P∨ Q      A
  4 (5)   P→ Q      3含意の定義
 34 (6) ~(P→ Q)&
         (P→ Q)     5&I
 3  (7)~(~P∨ Q)     46RAA
 3  (8)   P&~Q      7ド・モルガンの法則
 3  (9)   P         8&I
   ア(ア)         P   A
1   (イ)   P         239アア∨E
    (ウ) ((P→Q)→P)→P 1イCP
    (〃)((PならばQ)ならばP)ならばP。
(ⅱ)
   (1)   ~P∨P        TI(排中律
2  (2)   ~P          A
2  (3)   ~P∨Q        2∨I
2  (4)    P→Q        2含意の定義
2  (5)   (P→Q)&~P    24&I
2  (6)~(~(P→Q)∨ P)   5ド・モルガンの法則
 9 (7)   (P→Q)→ P    A
 9 (8)  ~(P→Q)∨ P    7含意の定義
49 (9)~(~(P→Q)∨ P)&
       (~(P→Q)∨ P)   68&I
4  (ア) ~((P→Q)→ P)   79RAA
4  (イ) ~((P→Q)→ P)∨P ア∨I
  ウ(ウ)      P        A
  ウ(エ) ~((P→Q)→ P)∨P ウ∨I
   (オ) ~((P→Q)→ P)∨P 12イウエ∨E
   (カ)  ((P→Q)→ P)→P オ含意の定義
   (〃)  ((PならばQ)ならばPならば)Pである。
(ⅲ)
1       (1)  (P→ Q)→P     A
 2      (2) ~(P&~Q)       A
  3     (3)   P           A
   4    (4)     ~Q        A
  34    (5)   P&~Q        34&I
 234    (6) ~(P&~Q)&
             (P&~Q)       25&I
 23     (7)    ~~Q        46RAA
 23     (8)      Q        7DN
 2      (9)   P→ Q        38CP
        (ア) ~(P&~Q)→(P→Q) 29CP
    イ   (イ) ~(P&~Q)       A
1   イ   (ウ)         (P→Q) アイMPP
1   イ   (エ)          P    1ウMPP
1       (オ) ~(P&~Q)→ P    イエCP
1       (カ)~~(P&~Q)∨ P    含意の定義
     キ  (キ)~~(P&~Q)       A
     キ  (ク)   P&~Q        キDN
     キ  (ケ)   P           ク&I
      コ (コ)          P    A
1       (サ)            P  カキケココ∨E
        (シ) ((P→Q)→ P)→P  1サCP
        (〃) ((PならばQ)ならばP)ならばP。
従って、
(02)(03)により、
(04)
5 原始的規則あるい導出された規則を、既に証明されたどのような連式あるいは定理とでも、ともに用いて、証明せよ。
5 Using primitive or derived rules, together with any sequents or theorems already proved, prove;
兎に角、証明せよ。
(c)├((P→Q)→P)→P
といふ「問題」に対する「解答」は、少なくとも、
(ⅰ)     
(ⅰ)12行の「計算」
(ⅱ)15行の「計算」
(ⅲ)21行の「計算」
による、少なくとも、「3通りの証明」が有ることになる。
然るに、
(05)
① 仮定(A)
② 前件肯定(MPP)
③ 後件否定(MTT)
④ 二重否定(DN)
⑤ 条件法的証明(CP)
⑥ 連言導入(&I)
⑦ 連言除去(&E)
⑧ 選言導入(∨I)
⑨ 選言除去(∨E)
⑩ 背理法(RAA)  
といふ「10個の規則」を、「原始的規則(primitive rules)」といふ。
従って、
(03)(04)(05)により、
(06)
5 次の連式を、原始的規則のみによって証明せよ
5 Prove the following sequent by primitive rules alone:
(c)├((P→Q)→P)→P
といふ「問題」であるならば、
(ⅰ)12行の「計算」
(ⅱ)15行の「計算」
(ⅲ)21行の「計算」
に於いて、
(ⅰ)からは、「含意の定義+含意の定義+ド・モルガンの法則」          を除く「必要」が有り、
(ⅱ)からは、「排中律+含意の定義+ド・モルガンの法則+含意の定義+含意の定義」を除く「必要」が有り、
(ⅲ)からは、「含意の定義」                          を除く「必要」が有る。
然るに、
(07)
(ⅰ)
1   (1)  (P→ Q)→P   A
1   (2) ~(P→ Q)∨P   1含意の定義
 3  (3) ~(P→ Q)     A
  4 (4)  ~P∨ Q      A
  4 (5)   P→ Q      3含意の定義
 34 (6) ~(P→ Q)&
         (P→ Q)     5&I
 3  (7)~(~P∨ Q)     46RAA
 3  (8)   P&~Q      7ド・モルガンの法則
 3  (9)   P         8&I
   ア(ア)         P   A
1   (イ)   P         239アア∨E
    (ウ) ((P→Q)→P)→P 1イCP
    (〃) ((PならばQ)ならばP)ならばP。
から、「含意の定義+含意の定義+ド・モルガンの法則」を除くのであれば、
(ⅳ)
1           (1)    (P→ Q)→P   A
 2          (2) ~(~(P→ Q)∨P)  A
  3         (3)   ~(P→ Q)     A
  3         (4)   ~(P→ Q)∨P   3∨I
 23         (5) ~(~(P→ Q)∨P)&
                 (~(P→ Q)∨P)  24&I
 2          (6)  ~~(P→ Q)     35RAA
 2          (7)    (P→ Q)     6DN
12          (8)           P   17MPP
12          (9)   ~(P→ Q)∨P   8∨I
12          (ア) ~(~(P→ Q)∨P)&
                 (~(P→ Q)∨P)  29&I
1           (イ)~~(~(P→ Q)∨P)  2アRAA
1           (ウ)   ~(P→ Q)∨P   イDN(2)
   エ        (エ)   ~(P→ Q)     A(選言支左)
    オ       (オ)    ~P∨ Q      A
     カ      (カ)     P&~Q      A
      キ     (キ)    ~P         A
     カ      (ク)     P         カ&E
     カキ     (ケ)    ~P&P       キク&I
      キ     (コ)   ~(P&~Q)     カケRAA
       サ    (サ)        Q      A
     カ      (シ)       ~Q      カ&E
     カ サ    (ス)     Q&~Q      サシ&I
       サ    (セ)   ~(P&~Q)     カスRAA
    オ       (ソ)   ~(P&~Q)     オキコシセ∨E
        タ   (タ)     P         A
         チ  (チ)       ~Q      A
        タチ  (ツ)     P&~Q      タチ&I
    オ   タチ  (テ)   ~(P&~Q)&
                   (P&~Q)     コツ&I
    オ    タ  (ト)      ~~Q      チテRAA
    オ    タ  (ナ)        Q      トDN
    オ       (ニ)     P→ Q      タナ
   エオ       (ヌ)   ~(P→ Q)&
                   (P→ Q)      エニ&I
   エ        (ネ)  ~(~P∨ Q)     オヌRAA
          ノ (ノ)    ~P         A
          ノ (ハ)    ~P∨ Q      ノ∨I
   エ      ノ (ヒ)  ~(~P∨ Q)&
                  (~P∨ Q)     ネハ&I
   エ        (フ)   ~~P         ノヒRAA
   エ        (ヘ)     P         フDN
           ホ(ホ)           P   A(選言支右)
1           (マ)           P   ウエヘホホ∨E
            (ミ) ((P→Q)→P)→P   1マCP
            (〃) ((PならばQ)ならばP)ならばP。
従って、
(06)(07)により、
(08)
(ⅰ)12行の「計算」
(ⅱ)15行の「計算」
(ⅲ)21行の「計算」
に於いて、
(ⅰ)からは、「含意の定義+含意の定義+ド・モルガンの法則」を除くならば、
(ⅰ)12行の「計算」は、「30行」増へて、「42行」になる。
従って、
(06)(08)により、
(09)
(ⅰ)12行の「計算」
(ⅱ)15行の「計算」
(ⅲ)21行の「計算」
に於いて、
(ⅱ)からは、「排中律+含意の定義+ド・モルガンの法則+含意の定義+含意の定義」を除くならば、
(ⅱ)15行の「計算」は、恐らく、「90行」近くになる。
然るに、
(06)により、
(10)
(ⅲ)21行の「計算」に対しては、
(ⅴ)
1       (1)  (P→ Q)→P     A
 2      (2) ~(P&~Q)       A
  3     (3)   P           A
   4    (4)     ~Q        A
  34    (5)   P&~Q        34&I
 234    (6) ~(P&~Q)&
             (P&~Q)       25&I
 23     (7)    ~~Q        46RAA
 23     (8)      Q        7DN
 2      (9)   P→ Q        38CP
        (ア) ~(P&~Q)→(P→Q) 29CP
    イ   (イ) ~(P&~Q)       A
1   イ   (ウ)         (P→Q) アイMPP
1   イ   (エ)          P    1ウMPP
1       (オ) ~(P&~Q)→ P    イエCP
     カ  (カ) ~(P&~Q)&~P    A
     カ  (キ) ~(P&~Q)       カ&E
1    カ  (ク)          P    オキMPP
     カ  (ケ)         ~P    カ&E
1    カ  (コ)       P&~P    クケ&I
1       (サ)~~(P&~Q)       カコDN
1       (シ)  (P&~Q)       サDN
1       (ス)  (P&~Q)∨ P    サ∨I
      セ (セ)   P&~Q        A
      セ (ソ)   P           ス&E
       タ(タ)          P    A
1       (チ)          P    スセソタツ∨E
        (ツ)((P→Q)→P)→P    1タCP
        (〃)((PならばQ)ならばPならば)Pである。
であるため、
(ⅲ)21行の「計算」に対しては、
(ⅴ)27行の「計算」に変へることによって、
(ⅲ)からは、「含意の定義」を除くことが、出来る。
従って、
(06)~(10)により、
(11)
5 原始的規則あるい導出された規則を、既に証明されたどのような連式あるいは定理とでも、ともに用いて、証明せよ。
5 Using primitive or derived rules, together with any sequents or theorems already proved, prove;
5 兎に角、証明せよ。
(c)├((P→Q)→P)→P
といふ「問題」ではなく、
5 次の連式を、原始的規則のみによって証明せよ
5 Prove the following sequent by primitive rules alone:
(c)├((P→Q)→P)→P
といふ「問題」であるならば、
(ⅰ)12行の「計算」は、「42行」になり、
(ⅱ)15行の「計算」は、「90行」近くになり、
(ⅲ)21行の「計算」は、「27行」になる。
cf.
こうしてその証明を、最初の基本的規則からのより長い証明に変形できる。この場合に必要なのは、ある番号の付けかえのみである。
and thus transform the proof into a lengtheir proof form first principles: only a certain renumbering of lines is involved.
(E.J.レモン、論理学初歩、竹尾治一郎・浅野楢英 訳、1973年、72頁と、原文)
従って、
(11)により、
(12)
5 原始的規則あるい導出された規則を、既に証明されたどのような連式あるいは定理とでも、ともに用いて、証明せよ。
5 Using primitive or derived rules, together with any sequents or theorems already proved, prove;
(c)├((P→Q)→P)→P 
(E.J.レモン、論理学初歩、竹尾治一郎・浅野楢英 訳、1973年、80頁と、原文)
といふ「問題」になってゐる。といふことからも分かるやうに、いづれにせよ
   ├((P→Q)→P)→P≡((PならばQ)ならばP)ならばPである。
といふ「パースの法則」は、「自然演繹」で、「証明出来る
といふ、ことになる。
然るに、
(13)
 ├((P→Q)→P)→P
といふ「定理(Theorem)」を「証明」するといふことは、
(1)((P→Q)→P) から、
(2)         が「演繹出来ることを、「証明」することに「等しい」。
然るに、
(14)
「含意の定義」により、
(1) ((P→Q)→P) は、
(2)~(~P∨Q)∨P  に「等しい」。
然るに、
(15)
「ド・モルガンの法則」により、
(2)~(~P∨Q)∨P は、
(3) (P&~Q)∨P に「等しい」。
然るに、
(16)
(3) (P&~Q)∨P からは、
(4)  P    ∨P が「演繹」出来る。
然るに、
(17)
(4)  P    ∨P からは、
(5)        P が「演繹」出来る。
従って、
(14)~(17)により、
(18)
(1) ((P→Q)→P)
(2)~(~P∨Q)∨P :含意の定義
(3) (P&~Q)∨P :ド・モルガンの法則
(4)  P    ∨P
(5)        P
(6)((P→ Q)→P)→P
となるものの、このことは、「含意の定義・ド・モルガンの法則」を、理解してゐる人間にとっては、「当然」である。
従って、
(19)
 ├ ((PならばQ)ならばP)ならばPである。
といふ風に、「言葉」で言ふと、「パースの法則」は、「不思議な感じ」がするものの、
(1) ((P→Q)→P)
(2)~(~P∨Q)∨P 
(3) (P&~Q)∨P
(4)  P    ∨P
(5)        P
(6)((P→ Q)→P)→P
といふ「計算」を見てしまふと、「そんなことは、当然」である。
といふことに、なる。
従って、
(20)
「含意の定義」と「ド・モルガンの法則」を、理解してゐるのであれば、
(ⅰ)
1   (1)  (P→ Q)→P   A
1   (2) ~(P→ Q)∨P   1含意の定義
 3  (3) ~(P→ Q)     A
  4 (4)  ~P∨ Q      A
  4 (5)   P→ Q      3含意の定義
 34 (6) ~(P→ Q)&
         (P→ Q)     5&I
 3  (7)~(~P∨ Q)     46RAA
 3  (8)   P&~Q      7ド・モルガンの法則
 3  (9)   P         8&I
   ア(ア)         P   A
1   (イ)   P         239アア∨E
    (ウ) ((P→Q)→P)→P 1イCP
    (〃)((PならばQ)ならばP)ならばP。
といふ「計算」は、「当然」であって、それ故、
 ├ ((PならばQ)ならばP)ならばPである。
といふ「パースの法則」は、「当然」である。
(21)
5 原始的規則あるい導出された規則を、既に証明されたどのような連式あるいは定理とでも、ともに用いて、証明せよ。
5 Using primitive or derived rules, together with any sequents or theorems already proved, prove;
兎に角、証明せよ。
(c)├((P→Q)→P)→P
といふ「問題」を、解いた際には、「特に、不思議な定理である」とは思はないまま、多分、
(1) ((P→Q)→P)
(2)~(~P∨Q)∨P 
(3) (P&~Q)∨P
(4)  P    ∨P
(5)        P
(6)((P→ Q)→P)→P
といふ「計算」をして、「そのやうな計算」をしたことを、忘れてゐた
然るに、
(22)
排中律や二重否定の除去と等価な命題のひとつで、変なものとして、パースの法則があります。
任意の命題P, Qについて、
((P→Q)→P)→P
が成り立つ。
といふ「記事」に接して、「それならば、排中律を使って、証明しよう。」と思って、
(ⅱ)
   (1)   ~P∨P        TI(排中律)
2  (2)   ~P          A
2  (3)   ~P∨Q        2∨I
2  (4)    P→Q        2含意の定義
2  (5)   (P→Q)&~P    24&I
2  (6)~(~(P→Q)∨ P)   5ド・モルガンの法則
 9 (7)   (P→Q)→ P    A
 9 (8)  ~(P→Q)∨ P    7含意の定義
49 (9)~(~(P→Q)∨ P)&
       (~(P→Q)∨ P)   68&I
4  (ア) ~((P→Q)→ P)   79RAA
4  (イ) ~((P→Q)→ P)∨P ア∨I
  ウ(ウ)      P        A
  ウ(エ) ~((P→Q)→ P)∨P ウ∨I
   (オ) ~((P→Q)→ P)∨P 12イウエ∨E
   (カ)  ((P→Q)→ P)→P オ含意の定義
   (〃)  ((PならばQ)ならばPならば)Pである。
といふ「計算」をした。
然るに、
(23)
(ⅰ)
1   (1)  (P→ Q)→P   A
1   (2) ~(P→ Q)∨P   1含意の定義
 3  (3) ~(P→ Q)     A
  4 (4)  ~P∨ Q      A
  4 (5)   P→ Q      3含意の定義
 34 (6) ~(P→ Q)&
         (P→ Q)     5&I
 3  (7)~(~P∨ Q)     46RAA
 3  (8)   P&~Q      7ド・モルガンの法則
 3  (9)   P         8&I
   ア(ア)         P   A
1   (イ)   P         239アア∨E
    (ウ) ((P→Q)→P)→P 1イCP
    (〃)((PならばQ)ならばP)ならばP。
といふ「計算」があるのだから、固より、
(ⅱ)
   (1)   ~P∨P        TI(排中律
から始まる「計算」をする「必要」などは、無かった
といふことが、分かった
然るに、
(24)
(ⅰ)
1(1)     P A
1(2)  ~Q∨P 1∨I
1(3)   Q→P 2含意の定義
 (4)P→(Q→P) 13CP
 (〃)Pならば(QならばPである)。
といふ「計算」であっても、
(ⅱ)
 (1)   P∨~P  TI(排中律
 (2)   P     A
 (3)   ~Q∨P  1∨I
 (4)    Q→P  2含意の定義
 (5) P→(Q→P) 13CP
6(6)     ~P  A
6(7)~P∨(Q→P) 6∨I
6(8) P→(Q→P) 7含意の定義
 (9) P→(Q→P) 12567∨E
 (〃) Pならば(QならばPである)。
といふ風に、「排中律」から始めて、「ワザワザ、無駄な計算」をすることが、出来る。
cf.
「ルカジェヴィッツの公理1」。
従って、
(01)~(24)により、
(25)
排中律や二重否定の除去と等価な命題のひとつで、変なものとして、パースの法則があります。
とは、言はれてはゐる(?)ものの、今は、
パースの法則」と「排中律」が、「等価」であるならば、例へば、
「ルカジェヴィッツの公理1」等々も、そうである。
といふことを、知ってゐる。
従って、
(26)
パースの法則は、排中律等価である。」と、敢へて、言ふ「必要」はない
と、私自身は、思ってゐる。
令和02年02月04日、毛利太。

0 件のコメント:

コメントを投稿