文献あり

ペアノ算術で加法交換法則の証明図をかく

1013

本記事では，ペアノ算術の加法交換法則の証明図をかいていきたいと思います．

ペアノ算術の各種法則の証明は，等式変形をやっていけばそれほど難しいものではないですが， $\forall$ の付け外しなど，色々とすっ飛ばして書くことになります．
せっかく基礎まで立ち返って証明をやっているのにそれではもったいないので，1段階ずつ推論規則を追って加法交換法則を証明し，証明図にしていこうと思います．

なお，本記事は参考文献にあげた資料および筆者が数年前に受けた記号論理学の講義の記憶をもとに構成されています．
独自の定義を含む可能性がありますので，レポートなどのためにこの記事を見つけられた方はご注意ください．

定義

証明の前にまず必要事項の定義をまとめていきます．

記号

まずは記号の定義です．
ここを厳密に構成するのは筆者の手に余るので自然言語的な説明でお許しください．

記号

$X, Y, Z, \dots$ ：命題変数
真または偽の値を取る変数
$P, Q, R, \dots$ ：述語変数
1つ以上の変数を取って命題となる．
$\land, \lor, \to, \neg, \forall, \exists$ ：論理記号
$\land, \lor, \to$ は2つ， $\neg$ は1つの命題を引数にとり，命題を返す演算子．
$\forall, \exists$ は $\forall x . P (x)$ のかたちで束縛変数を含む命題を作る演算子．
$a, b, c, \dots$ ： (自由)変数
述語の引数となる記号．
$x, y, z, \dots$ ：束縛変数
$\forall, \exists$ によって束縛され証明の外部には出てこない変数．
$f, g, \dots$ ：関数
1つ以上の変数を取って変数となる．

推論規則

古典一階述語論理の推論規則です．
本項は文献[1-4]を元に，(ちょいちょい表記がブレるので)筆者が構成したものです．

～ $I$ ・～ $E$ はそれぞれ～の導入則・除去則を表します．
「 $P ⊢ Q$ 」は $P$ から $Q$ が証明されることを意味するメタ記号で， $\Rightarrow$ と同じような意味です．ただし，論理記号の $\to$ とは区別します．

推論規則

$\land I$ ： $X, Y ⊢ X \land Y$
$\land E$ ： $X \land Y ⊢ X, X \land Y ⊢ Y$
$\lor I$ ： $X ⊢ X \lor Y, Y ⊢ X \lor Y$
$\lor E$ ： $X \lor Y, [X] \dots Z, [Y] \dots Z ⊢ Z$
$\neg I$ ： $[X] \dots ⊥ ⊢ \neg X$
（ $\neg E$ ： $X, \neg X ⊢ ⊥$ ）
$\to I$ ： $[X] \dots Y ⊢ X \to Y$
$\to E$ ： $X \to Y, X ⊢ Y$
$\forall I$ ： $P (x) ⊢ \forall x . P (x)$
$\forall E$ ： $\forall x . P (x) ⊢ P (a)$
$\exists I$ ： $P (a) ⊢ \exists x . P (x)$
$\exists E$ ： $\exists x . P (x), [P (a)] \dots Q ⊢ Q$

$[]$ は推論の際に仮定から外れるという意味で，証明図では
$\frac{\begin{array}{r} \begin{array}{c} [X]^{(n)} & [Y]^{(n)} \\ ⋮^{} & ⋮^{} \\ X \lor Y & Z^{} & Z^{} \end{array} \end{array}}{Z} {\lor E}^{(n)}$
のようにどこの推論に対応する仮定なのかわかるようマークをつけたりします．

排中律（ $\neg E$ ）を含まなければ直観主義論理です．今回の証明では多分使っていないので直観主義論理の範囲でも証明可能ということですね．

等号

「数」を扱うのに必要な等号「 $=$ 」を導入します．
ここで，公理として「 $\to$ 」が入った命題があると式変形がとてつもなくめんどくさくなるので，文献[5]の「相等公理CA」をもとに推論規則を追加する形で定義します．

変数 $x, y$ を取って命題 $x = y$ となる2項演算子 $=$ を以下のように定めます．

=

の推論

反射律： $⊢ x = x$
対称律： $x = y ⊢ y = x$
推移律： $x = y, y = z ⊢ x = z$
代入律1：任意の関数 $f$ について $x = y ⊢ f (\dots, x, \dots) = f (\dots, y, \dots)$
代入律2：任意の述語 $P$ について $x = y, P (\dots, x, \dots) ⊢ P (\dots, y, \dots)$

ペアノ算術

「自然数」における演算を以下の公理系で定義します．(参考：[4,6])

ペアノ算術

記号

$0$ ：定数記号
$s$ ：1変数関数
$+, \times$ ： 2変数関数

公理系（PA）

(PA1)： $\forall n . \neg (s n = 0)$
(PA2)： $\forall m . \forall n . (s m = s n \to m = n)$
(PA3)： $\forall n . (n + 0 = n)$
(PA4)： $\forall m . \forall n . (m + s n = s (m + n))$
(PA5)： $\forall n . (n \times 0 = 0)$
(PA6)： $\forall m . \forall n . (m \times s n = (m \times n) + n)$
数学的帰納法：任意の述語 $P (\dots, n, \dots)$ について， $P (\dots, 0, \dots), \forall n . (P (\dots, n, \dots) \to P (\dots, s n, \dots)) ⊢ \forall n . P (\dots, n, \dots)$

証明

ここまでに定義した推論規則・公理を使って

自然数の加法の交換法則

$\forall x . \forall y . (x + y = y + x)$

を証明します．
全称量化が2つあるので，2重の数学的帰納法で証明していきます．
適宜用いた推論規則や公理を()で付記します．

(I)
(I-i)
$\begin{matrix} (1) & ⊢ 0 + 0 = 0 + 0 (反射律) \end{matrix}$

(I-ii)
$(PA 4) \forall m . \forall n . (m + s n = s (m + n)) ⊢ \forall n . 0 + s n = s (0 + n) (\forall E)$
$\begin{matrix} (2) & ⊢ 0 + s k = s (0 + k) (\forall E) \end{matrix}$
$\begin{matrix} (3) & {[0 + k = k + 0]}^{A} ⊢ s (0 + k) = s (k + 0) (代入律(関数)) \end{matrix}$
$(PA3) \forall n . (n + 0 = n) ⊢ k + 0 = k (\forall E)$
$\begin{matrix} (4) & ⊢ s (k + 0) = s k (代入律(関数)) \end{matrix}$
$\begin{matrix} (5) & (2), (3) ⊢ 0 + s k = s (k + 0) (推移律) \end{matrix}$
$\begin{matrix} (6) & (5), (4) ⊢ 0 + s k = s k (推移律) \end{matrix}$
$(PA3) \forall n . (n + 0 = n) ⊢ s k + 0 = s k (\forall E)$
$\begin{matrix} (7) & ⊢ s k = s k + 0 (対称律) \end{matrix}$
$\begin{matrix} (8) & (6), (7) ⊢ 0 + s k = s k + 0 (推移律) \end{matrix}$
$[]^{A} \dots (8) ⊢ (0 + k = k + 0 \to 0 + s k = s k + 0) (\to I)$
$\begin{matrix} (9) & ⊢ \forall k . (0 + k = k + 0 \to 0 + s k = s k + 0) (\forall I) \end{matrix}$

$\begin{matrix} (10) & (1), (9) ⊢ \forall y . (0 + y = y + 0) (数学的帰納法) \end{matrix}$

(II)
$(PA 4) \forall m . \forall n . (m + s n = s (m + n)) ⊢ s l + s n = s (s l + n) (\forall E)$
$\begin{matrix} (11) & ⊢ s l + s k = s (s l + k) (\forall E) \end{matrix}$
$\begin{matrix} (12) & [s l + k = k + s l]^{B} ⊢ s (s l + k) = s (k + s l) (代入律(関数)) \end{matrix}$
$\begin{matrix} (13) & (11), (12) ⊢ s l + s k = s (k + s l) (推移律) \end{matrix}$
$(PA 4) \forall m . \forall n . (m + s n = s (m + n)) ⊢ \forall n . k + s n = s (k + n) (\forall E)$
$⊢ k + s l = s (k + l) (\forall E)$
$\begin{matrix} (14) & ⊢ s (k + s l) = s s (k + l) (代入律(関数)) \end{matrix}$
$\begin{matrix} (15) & (13), (14) ⊢ s l + s k = s s (k + l) (推移律) \end{matrix}$

$(PA 4) \forall m . \forall n . (m + s n = s (m + n)) ⊢ \forall n . s k + s n = s (s k + n) (\forall E)$
$\begin{matrix} (16) & ⊢ s k + s l = s (s k + l) (\forall E) \end{matrix}$
$[\forall y . l + y = y + l]^{C} ⊢ l + s k = s k + l (\forall E)$
$⊢ s k + l = l + s k (対称律)$
$\begin{matrix} (17) & ⊢ s (s k + l) = s (l + s k) (代入律(関数)) \end{matrix}$
$\begin{matrix} (18) & (16), (17) ⊢ s k + s l = s (l + s k) (推移律) \end{matrix}$
$(PA 4) \forall m . \forall n . (m + s n = s (m + n)) ⊢ \forall n . l + s n = s (l + n) (\forall E)$
$⊢ l + s k = s (l + k) (\forall E)$
$\begin{matrix} (19) & ⊢ s (l + s k) = s s (l + k) (代入律(関数)) \end{matrix}$
$\begin{matrix} (20) & (18), (19) ⊢ s k + s l = s s (l + k) (推移律) \end{matrix}$
$[\forall y . l + y = y + l]^{C} ⊢ l + k = k + l (\forall E)$
$\begin{matrix} (21) & ⊢ s s (l + k) = s s (k + l) (代入律(関数)) \end{matrix}$
$(20), (21) ⊢ s k + s l = s s (k + l) (推移律)$
$\begin{matrix} (22) & ⊢ s s (k + l) = s k + s l (対称律) \end{matrix}$
$\begin{matrix} (23) & (15), (22) ⊢ s l + s k = s k + s l (推移律) \end{matrix}$
$[]^{B} \dots (23) ⊢ (s l + k = k + s l) \to (s l + s k = s k + s l) (\to I)$
$\begin{matrix} (24) & ⊢ \forall k . (s l + k = k + s l) \to (s l + s k = s k + s l) (\forall I) \end{matrix}$

$(10) ⊢ 0 + s l = s l + 0 (\forall E)$
$\begin{matrix} (25) & ⊢ s l + 0 = 0 + s l (対称律) \end{matrix}$
$\begin{matrix} (26) & (25), (24) ⊢ \forall y . s l + y = y + s l (数学的帰納法) \end{matrix}$
$[]^{C}, []^{C} \dots (26) ⊢ (\forall y . l + y = y + l) \to (\forall y . s l + y = y + s l) (\to I)$
$\begin{matrix} (27) & ⊢ \forall l . (\forall y . l + y = y + l) \to (\forall y . s l + y = y + s l) (\forall I) \end{matrix}$

$\begin{matrix} (Q.E.D.) & (10), (27) ⊢ \forall x . \forall y . x + y = y + x (数学的帰納法) \end{matrix}$

この証明を証明図にするとこのようになります．

証明図-全体

いくらなんでも見づらすぎるので前半部分を分割すると，以下のようになります．

証明図-分割

bussproofs パッケージを用いてLaTeXで描画しています．
すぐ紙幅をはみ出すので調整が大変です．

以上です．
今後，機会があれば他の法則の証明もやってみようと思います．
間違いなどありましたらコメントで教えていただけると幸いです．

Appendix-LaTeXソースコード

面倒がってマクロを濫用した汚いコードですが，参考に置いておきます．
※マークダウン記法と干渉しておかしな表示になってるのでソースコードを参照してください．

      \documentclass[a4paper,8pt]{jsarticle}
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{bussproofs}
%\usepackage{proof}
  
\newcommand{\CAA}{(反射律)}
\newcommand{\CAB}{(対称律)}
\newcommand{\CAC}{(推移律)}
\newcommand{\CAD}{ (代入律(関数))}
\newcommand{\CAE}{(代入律(述語))}

\newcommand{\PAA}{$(\mathrm{PA1})\; \forall n. \lnot(sn=0)$}
\newcommand{\PAB}{$(\mathrm{PA2})\;\forall m. \forall n. (sm=sn\to m=n)$}
\newcommand{\PAC}{$(\mathrm{PA3})\; \forall n. (n+0=n)$}
\newcommand{\PAD}{$(\mathrm{PA}4)\; \forall m. \forall n. (m+sn=s(m+n))$}
\newcommand{\MI}{(数学的帰納法)}

\let\A\AxiomC
%\let\R\RightLabel
\newcommand{\R}[1]{\RightLabel{{\footnotesize #1}}}
\let\U\UnaryInfC
\let\B\BinaryInfC
\let\T\TrinaryInfC

\newcommand{\paren}[1]{\left( #1 \right)}
\newcommand{\bracket}[1]{\left[ #1 \right]}
\newcommand{\To}{\vdash}

\begin{document}
\rotatebox{270}{
\scalebox{0.3}{
\parbox{2.7\linewidth}{
\begin{prooftree}
%
\A{}
\R{\CAA}
\U{$0+0=0+0$}%(1)
%
\A{\PAD}
\R{$\forall E$}
\U{$\forall n. 0+sn=s(0+n)$}
\R{$\forall E$}
\U{$0+sk = s(0+k)$}%(2)
%
\A{$\bracket{0+k=k+0}^A$}
\R{\CAD}
\U{$s(0+k)=s(k+0)$}%(3)
\R{\CAC}
\B{$0+sk=s(k+0)$}%(5)
%
\A{\PAC}
\R{$\forall E$}
\U{$k+0=k$}
\R{\CAD}
\U{$s(k+0)=sk$}%(4)
\R{\CAC}
\B{$0+sk=sk$}%(6)
%
\A{\PAC}
\R{$\forall E$}
\U{$sk+0=sk$}
\R{\CAB}
\U{$sk=sk+0$}%(7)
\R{\CAC}
\B{$0+sk=sk+0$}%(8)
\R{$\to I^A$}
\U{$(0+k=k+0\to 0+sk=sk+0)$}
\R{$\forall I$}
\U{$\forall k.(0+k=k+0\to 0+sk=sk+0)$}%(9)
\R{\MI}
\B{$\forall y. (0+y=y+0)$}
%
\A{}
\R{\CAA}
\U{$0+0=0+0$}%(1)
%
\A{\PAD}
\R{$\forall E$}
\U{$\forall n. 0+sn=s(0+n)$}
\R{$\forall E$}
\U{$0+sk = s(0+k)$}%(2)
%
\A{$\bracket{0+k=k+0}^A$}
\R{\CAD}
\U{$s(0+k)=s(k+0)$}%(3)
\R{\CAC}
\B{$0+sk=s(k+0)$}%(5)
%
\A{\PAC}
\R{$\forall E$}
\U{$k+0=k$}
\R{\CAD}
\U{$s(k+0)=sk$}%(4)
\R{\CAC}
\B{$0+sk=sk$}%(6)
%
\A{\PAC}
\R{$\forall E$}
\U{$sk+0=sk$}
\R{\CAB}
\U{$sk=sk+0$}%(7)
\R{\CAC}
\B{$0+sk=sk+0$}%(8)
\R{$\to I^A$}
\U{$(0+k=k+0\to 0+sk=sk+0)$}
\R{$\forall I$}
\U{$\forall k.(0+k=k+0\to 0+sk=sk+0)$}%(9)
\R{\MI}
\B{$\forall y. (0+y=y+0)$}
\R{$\forall E$}
\U{$0+sl=sl+0$}
\R{\CAB}
\U{$sl+0=0+sl$}%(25
%
\A{\PAD}
\R{$\forall E$}
\U{$sl+sn=s(sl+n)$}
\R{$\forall E$}
\U{$sl*sk=s(sl+k)$}%(11)
%
\A{$\bracket{sl+k=k+sl}^B$}
\R{\CAD}
\U{$s(sl+k)=s(k+sl)$}%(12)
\R{\CAC}
\B{$sl+sk=s(k+sl)$}%(13)
%
\A{\PAD}
\R{$\forall E$}
\U{$\forall n. k+sn=s(k+n)$}
\R{$\forall E$}
\U{$k+sl=s(k+l)$}
\R{\CAD}
\U{$s(k+sl)=ss(k+l)$}%(14)
\R{\CAC}
\B{$sl+sk=ss(k+l)$}%(15
%
\A{\PAD}
\R{$\forall E$}
\U{$\forall n. sk+sn=s(sk+n)s$}
\R{$\forall E$}
\U{$sk+sl=s(sk+l)$}%(16
%
\A{$\bracket{\forall y. l+y=y+l}^C$}
\R{$\forall E$}
\U{$l+sk=sk+l$}
\R{\CAB}
\U{$sk+l=l+sk$}
\R{\CAD}
\U{$s(sk+l)=s(l+sk)$}%(17
\R{\CAC}
\B{$sk+sl=s(l+sk)$}%(18
%
\A{\PAD}
\R{$\forall E$}
\U{$\forall n. l+sn=s(l+n)$}
\R{$\forall E$}
\U{$l+sk=s(l+k)$}
\R{\CAD}
\U{$s(l+sk)=ss(l+k)$}%(19
\R{\CAC}
\B{$sk+sl=ss(l+k)$}%(20
%
\A{$\bracket{\forall y. l+y=y+l}^C$}
\R{$\forall E$}
\U{$l+k=k+l$}
\R{\CAD}
\U{$ss(l+k)=ss(k+l)$}%(21
\R{\CAC}
\B{$sk+sl=ss(k+l)$}
\R{\CAB}
\U{$ss(k+l)=sk+sl$}%(22
\R{\CAC}
\B{$sl+sk=sk+sl$}%(23
\R{$\to I^B$}
\U{$(sl+k=k+sl)\to(sl+sk=sk+sl)$}
\R{$\forall I$}
\U{$\forall k. (sl+k=k+sl)\to(sl+sk=sk+sl)$}%(24
\R{\MI}
\B{$\forall y. sl+y = y+sl$}%(25
\R{$\to I$}
\U{$(\forall y.l+y=y+l)\to(\forall y. sl+y=y+sl)$}
\R{$\forall I$}
\U{$\forall l. (\forall y.l+y=y+l)\to(\forall y. sl+y=y+sl)$}%(27
\R{\MI}
\B{$\forall x. \forall y.x+y=y+x$}
\end{prooftree}}}}
\newpage

\scalebox{0.4}{少し見やすいver.}

\fbox{
\scalebox{0.4}{
\parbox{1.4\linewidth}{
\begin{prooftree}
\A{}
\R{\CAA}
\U{$0+0=0+0$}%(1)
%
\A{\PAD}
\R{$\forall E$}
\U{$\forall n. 0+sn=s(0+n)$}
\R{$\forall E$}
\U{$0+sk = s(0+k)$}%(2)
%
\A{$\bracket{0+k=k+0}^A$}
\R{\CAD}
\U{$s(0+k)=s(k+0)$}%(3)
\R{\CAC}
\B{$0+sk=s(k+0)$}%(5)
%
\A{\PAC}
\R{$\forall E$}
\U{$k+0=k$}
\R{\CAD}
\U{$s(k+0)=sk$}%(4)
\R{\CAC}
\B{$0+sk=sk$}%(6)
%
\A{\PAC}
\R{$\forall E$}
\U{$sk+0=sk$}
\R{\CAB}
\U{$sk=sk+0$}%(7)
\R{\CAC}
\B{$0+sk=sk+0$}%(8)
\R{$\to I^A$}
\U{$(0+k=k+0\to 0+sk=sk+0)$}
\R{$\forall I$}
\U{$\forall k.(0+k=k+0\to 0+sk=sk+0)$}%(9)
\R{\MI}
\B{$\forall y. (0+y=y+0)$}
\end{prooftree}
}
}
}\scalebox{0.4}{$\quad\cdots\cdots\quad$\fbox{$\phantom{X}A\phantom{\frac{X}{Y}}$}}

\scalebox{0.4}{
\parbox{2.7\linewidth}{
\begin{prooftree}
%
\A{\fbox{$\phantom{X}A\phantom{\frac{X}{Y}}$}}
%
\A{\fbox{$\phantom{X}A\phantom{\frac{X}{Y}}$}}
\R{$\forall E$}
\U{$0+sl=sl+0$}
\R{\CAB}
\U{$sl+0=0+sl$}%(25
%
\A{\PAD}
\R{$\forall E$}
\U{$sl+sn=s(sl+n)$}
\R{$\forall E$}
\U{$sl*sk=s(sl+k)$}%(11)
%
\A{$\bracket{sl+k=k+sl}^B$}
\R{\CAD}
\U{$s(sl+k)=s(k+sl)$}%(12)
\R{\CAC}
\B{$sl+sk=s(k+sl)$}%(13)
%
\A{\PAD}
\R{$\forall E$}
\U{$\forall n. k+sn=s(k+n)$}
\R{$\forall E$}
\U{$k+sl=s(k+l)$}
\R{\CAD}
\U{$s(k+sl)=ss(k+l)$}%(14)
\R{\CAC}
\B{$sl+sk=ss(k+l)$}%(15
%
\A{\PAD}
\R{$\forall E$}
\U{$\forall n. sk+sn=s(sk+n)s$}
\R{$\forall E$}
\U{$sk+sl=s(sk+l)$}%(16
%
\A{$\bracket{\forall y. l+y=y+l}^C$}
\R{$\forall E$}
\U{$l+sk=sk+l$}
\R{\CAB}
\U{$sk+l=l+sk$}
\R{\CAD}
\U{$s(sk+l)=s(l+sk)$}%(17
\R{\CAC}
\B{$sk+sl=s(l+sk)$}%(18
%
\A{\PAD}
\R{$\forall E$}
\U{$\forall n. l+sn=s(l+n)$}
\R{$\forall E$}
\U{$l+sk=s(l+k)$}
\R{\CAD}
\U{$s(l+sk)=ss(l+k)$}%(19
\R{\CAC}
\B{$sk+sl=ss(l+k)$}%(20
%
\A{$\bracket{\forall y. l+y=y+l}^C$}
\R{$\forall E$}
\U{$l+k=k+l$}
\R{\CAD}
\U{$ss(l+k)=ss(k+l)$}%(21
\R{\CAC}
\B{$sk+sl=ss(k+l)$}
\R{\CAB}
\U{$ss(k+l)=sk+sl$}%(22
\R{\CAC}
\B{$sl+sk=sk+sl$}%(23
\R{$\to I^B$}
\U{$(sl+k=k+sl)\to(sl+sk=sk+sl)$}
\R{$\forall I$}
\U{$\forall k. (sl+k=k+sl)\to(sl+sk=sk+sl)$}%(24
\R{\MI}
\B{$\forall y. sl+y = y+sl$}
\R{$\to I$}
\U{$(\forall y.l+y=y+l)\to(\forall y. sl+y=y+sl)$}
\R{$\forall I$}
\U{$\forall l. (\forall y.l+y=y+l)\to(\forall y. sl+y=y+sl)$}
\R{\MI}
\B{$\forall x. \forall y.x+y=y+x$}
\end{prooftree}
}}

\end{document}