命題
高校数学の知識から大学数学をがんばるための記事なのだ。質問があったらコメント欄でも Twitter で直接でもいいから訊いてほしいのだ
記法
以下集合論に限らず数学をするのに必要な記号なのだ
- $a\colon A$
- 「$a$ は $A$」くらいの意味なのだ。「$x:$ 実数」なら「$x$ は実数」「$x$ が実数」のように捉えるのだ
- $A\coloneqq B$
- 「$A$ を $B$ と定義する」という意味なのだ。例えば「$f(x)\coloneqq x^2$」のように書くのだ。今まで全部 $=$ で書いてきたと思うけれど、これからは等しい意味の $=$ と 定義するという意味の $\coloneqq$ を使い分けるのだ。「$B\eqqcolon A$」とも書くのだ
記法が確認できたところで命題についてやっていくのだ。命題、特に量化は数学をするに当たってとても難しいくせに言葉以前の概念なのだ。昔の数学者もこぞって理解できなかった代物だからすぐに理解できなくても気にしないでゆっくり理解するか、その後の議論を見て雰囲気からつかんでいくといいのだ
真偽をはっきりと定められる文のことを「命題」と呼ぶのだ。例えば「人間はいずれ死ぬ」は真だし、「アライㄜんは小学生である」は偽だからこれらはどちらも命題なのだ。でも「$1$ は小さい」だと真偽は人によるし、「ばなな」はもはや何を言っているかわからないから命題にはなり得ないのだ
「$2$ は偶数である」だとかも命題になるし、「$2$ は奇数である」も偽だけど命題なのだ。気をつけるのだ
また、「$n$ は偶数である」はそのままだと真偽が $n$ に寄ってしまうから命題にはなり得ないのだ。きちんと具体的な状態として読める言明になっている必要があるのだ
「$P: 2$ は偶数である」などのように命題に名前をつけられるようにするのだ
数学の証明で扱う言明は全部命題なのだ。証明とは命題が真であると示すことなのだ
論理記号
数字を $x$ で表現したら $x^2+x+1$ のように記号的に表現できて色々な幅が広がったように、命題を $P$ で表現したら記号的に表現して色々できるようになるのだ。以下 $P, Q, R$ は命題を表す記号なのだ。$P$ が真であることを $P: \T$、偽であることを $P: \F$ と表すのだ
$\heading{P\land Q}$
「$P$ かつ $Q$」と読んで $P$ と $Q$ がどちらも真であることを意味するのだ
以下は真理値表といって $P,Q$ が それぞれ $\T,\F$ であるときに $P\land Q$ が $\T,\F$ どちらになるかを表したものなのだ:
| $P$ | $Q$ | $P\land Q$ |
|---|---|---|
| $\T$ | $\T$ | $\T$ |
| $\T$ | $\F$ | $\F$ |
| $\F$ | $\T$ | $\F$ |
| $\F$ | $\F$ | $\F$ |
命題は真か偽しか取り得ないから逆に真理値表で命題の計算を定義できてしまうのだ。これからそのように定義することがあるのだ
$\heading{P\lor Q}$
「$P$ または $Q$」と読んで $P$ と $Q$ のどちらかが真であることを意味するのだ。$P,Q$ の両方が真だったとしても $P\lor Q$ は真になるから注意なのだ
| $P$ | $Q$ | $P\lor Q$ |
|---|---|---|
| $\T$ | $\T$ | $\T$ |
| $\T$ | $\F$ | $\T$ |
| $\F$ | $\T$ | $\T$ |
| $\F$ | $\F$ | $\F$ |
$\heading{\lnot P}$
「$P$ でない」と読んで $P$ が偽であることを表すのだ
| $P$ | $\lnot P$ |
|---|---|
| $\T$ | $\F$ |
| $\F$ | $\T$ |
これだけ定義すれば命題で困ることはなさそうなのだ。試しに $P:\T, Q:\F, R:\F$ のときに $P\land((Q\lor\lnot R)\lor\lnot P)$ が $\T,\F$ のどちらか計算してみるのだ
$x$ に色々な値が入って $x^2+x+1$ みたいな式に具体的な値を代入できたように、$P,Q,R$ に実際に $P:\T,\ Q:\F,\ R:\F$ を代入してみればいいのだ。正式な表記じゃないけど $\T,\ \F$ を代入して等式で繋いでみるのだ
<$>\begin{aligned} &\quad\ P\land((Q\lor\lnot R)\lor\lnot P)\\ &=\T\land((\F\lor\lnot\F)\lor\lnot\T)\\ &=\T\land((\F\lor\T)\lor\F)\\ &=\T\land(\T\lor\F)\\ &=\T\land\T\\ &=\T \end{aligned}<$>実際に等号の役割をする記号は別に定義されるのだ:
$\heading{P\Rarr Q}$
「$P$ ならば $Q$」と読むのだ。読んで字のごとく $P$ が真であるときに $Q$ も真であることを表すのだ。これは真理値表を見たほうがいいのだ
| $P$ | $Q$ | $P\Rarr Q$ |
|---|---|---|
| $\T$ | $\T$ | $\T$ |
| $\T$ | $\F$ | $\F$ |
| $\F$ | $\T$ | $\T$ |
| $\F$ | $\F$ | $\T$ |
「$P:\T$ なのに $Q:\T$ でない」というとき偽になることがわかるのだ。「カラスは黒い」って言われたときに白いカラスがいればこの命題は偽だとわかるのだ
それに、例えば「地球が爆発したならアライㄜんは死ぬ」という命題ならたぶん正しいけど、現時点で地球は爆発してないのだ。それに「地球が爆発したらこの本を貸してあげる」って言われたらたぶん本を貸して貰えはしないけど嘘は言ってないのだ。以上より真理値表が言えるのだ
さらに $P\Rarr Q$ は $\lnot P\lor Q$ であることと同じだとわかるのだ。真理値表を書くと一致するのだ
| $P$ | $Q$ | $\lnot P$ | $\lnot P\lor Q$ |
|---|---|---|---|
| $\T$ | $\T$ | $\F$ | $\T$ |
| $\T$ | $\F$ | $\F$ | $\F$ |
| $\F$ | $\T$ | $\T$ | $\T$ |
| $\F$ | $\F$ | $\T$ | $\T$ |
よって $P\Rarr Q$ を $\lnot P\lor Q$ で定義し直すのだ。これで演算の種類を少なく保てるのだ。また、この記号は「$P$ から $Q$ が導ける」というメタ的な意味を持ったりもするから、注意するのだ。例えば「$A\land B\Rarr C$」と書いて「『$a\land B$ が真』を仮定すれば $C$ が証明できる」ことを表すのだ
さらに不等式のように $P\Rarr Q\Rarr R$ と書いて $(P\Rarr Q)\land(Q\Rarr R)$ を表したりもするのだ
$\heading{P\Lrarr Q}$
「$P$ は $Q$ と同値」と読むのだ。これは $P$ と $Q$ の真理値が一致することを表すのだ。$=$ のように $P\Lrarr Q\Lrarr R$ と書いたりもするメタ的な記号なのだ:
| $P$ | $Q$ | $P\Lrarr Q$ |
|---|---|---|
| $\T$ | $\T$ | $\T$ |
| $\T$ | $\F$ | $\F$ |
| $\F$ | $\T$ | $\F$ |
| $\F$ | $\F$ | $\T$ |
直感的にこれは $(P\Rarr Q)\land(Q\Rarr P)$ であると思われるけど、まさにその通りなのだ
| $P$ | $Q$ | $P\Rarr Q$ | $Q\Rarr P$ | $(P\Rarr Q)\land(Q\Rarr P)$ | $P\Lrarr Q$ |
|---|---|---|---|---|---|
| $\T$ | $\T$ | $\T$ | $\T$ | $\T$ | $\T$ |
| $\T$ | $\F$ | $\F$ | $\T$ | $\F$ | $\F$ |
| $\F$ | $\T$ | $\T$ | $\F$ | $\F$ | $\F$ |
| $\F$ | $\F$ | $\T$ | $\T$ | $\T$ | $\T$ |
よって $P\Lrarr Q$ を $(P\Rarr Q)\land(Q\Rarr P)$ として定義するのだ
$P\Lrarr Q$ なら $P\land R\Lrarr Q\land R,\ P\lor R\Lrarr Q\lor R$ などの命題が従うのは直感的にわかると思うし、したがって複雑な命題でも $P$ と $Q$ を取り替えてよいとわかるのだ
$\T$ を常に真な命題、$\F$ を常に偽な命題を表す記号として扱えば、$P\Lrarr\T, Q\Lrarr\F, R\Lrarr\F$ として先の解答は正当化されるのだ:
<$>\begin{aligned} &P\land((Q\lor\lnot R)\lor\lnot P)\\ \Lrarr\ &\T\land((\F\lor\lnot\F)\lor\lnot\T)\\ \Lrarr\ &\T\land((\F\lor\T)\lor\F)\\ \Lrarr\ &\T\land(\T\lor\F)\\ \Lrarr\ &\T\land\T\\ \Lrarr\ &\T \end{aligned}<$>ここで $\coloneqq$ と同じように $\colonLrarr$ で命題を定義できるようにするのだ。例えばさっき $P\Rarr Q$ を $\lnot P\lor Q$ で定義したけれど、これを「$P\Rarr Q\colonLrarr\lnot P\lor Q$」と書いてよいのだ
命題の計算
交換則
$P\land Q\Lrarr Q\land P$ だとか $P\lor Q\Lrarr Q\lor P$ だとかはすぐわかると思うのだ
二重否定
$\lnot\lnot P\Lrarr P$ なのだ。これも見ればわかるのだ
結合則
$(P\land Q)\land R\Lrarr P\land(Q\land R)$、さらに $(P\lor Q)\lor R\Lrarr P\lor(Q\lor R)$ がなりたつのだ。これは真理値表を書かなくても明らかだと思うけど、一応 $\land$ について書いておくのだ。$\lor$ でも同様のことがなりたつから暇なら真理値表を書いてみるといいのだ
| $P$ | $Q$ | $R$ | $P\land Q$ | $Q\land R$ | $(P\land Q)\land R$ | $P\land(Q\land R)$ |
|---|---|---|---|---|---|---|
| $\T$ | $\T$ | $\T$ | $\T$ | $\T$ | $\T$ | $\T$ |
| $\T$ | $\T$ | $\F$ | $\T$ | $\F$ | $\F$ | $\F$ |
| $\T$ | $\F$ | $\T$ | $\F$ | $\F$ | $\F$ | $\F$ |
| $\T$ | $\F$ | $\F$ | $\F$ | $\F$ | $\F$ | $\F$ |
| $\F$ | $\T$ | $\T$ | $\F$ | $\T$ | $\F$ | $\F$ |
| $\F$ | $\T$ | $\F$ | $\F$ | $\F$ | $\F$ | $\F$ |
| $\F$ | $\F$ | $\T$ | $\F$ | $\F$ | $\F$ | $\F$ |
| $\F$ | $\F$ | $\F$ | $\F$ | $\F$ | $\F$ | $\F$ |
これによって $P\land Q\land R,\ P\lor Q\lor R$ などと書くことが許されるのだ。逆に $P\land Q\lor R$ などのようには書いちゃいけないのだ。それが以下なのだ
分配法則
$P\land(Q\lor R)\Lrarr (P\land Q)\lor(P\land R)$ なのだ。これも真理値表から左右が一致することを言えばいいのだ:
| $P$ | $Q$ | $R$ | $Q\lor R$ | $P\land(Q\lor R)$ |
|---|---|---|---|---|
| $\T$ | $\T$ | $\T$ | $\T$ | $\T$ |
| $\T$ | $\T$ | $\F$ | $\T$ | $\T$ |
| $\T$ | $\F$ | $\T$ | $\T$ | $\T$ |
| $\T$ | $\F$ | $\F$ | $\F$ | $\F$ |
| $\F$ | $\T$ | $\T$ | $\T$ | $\F$ |
| $\F$ | $\T$ | $\F$ | $\T$ | $\F$ |
| $\F$ | $\F$ | $\T$ | $\T$ | $\F$ |
| $\F$ | $\F$ | $\F$ | $\F$ | $\F$ |
| $P$ | $Q$ | $R$ | $P\land Q$ | $P\land R$ | $(P\land Q)\lor(P\land R)$ |
|---|---|---|---|---|---|
| $\T$ | $\T$ | $\T$ | $\T$ | $\T$ | $\T$ |
| $\T$ | $\T$ | $\F$ | $\T$ | $\F$ | $\T$ |
| $\T$ | $\F$ | $\T$ | $\F$ | $\T$ | $\T$ |
| $\T$ | $\F$ | $\F$ | $\F$ | $\F$ | $\F$ |
| $\F$ | $\T$ | $\T$ | $\F$ | $\F$ | $\F$ |
| $\F$ | $\T$ | $\F$ | $\F$ | $\F$ | $\F$ |
| $\F$ | $\F$ | $\T$ | $\F$ | $\F$ | $\F$ |
| $\F$ | $\F$ | $\F$ | $\F$ | $\F$ | $\F$ |
一致してるから大丈夫なのだ。同様に $P\lor(Q\land R)\Lrarr (P\lor Q)\land(P\lor R)$ もなりたつからみてみるとよいのだ
ド・モルガンの法則
$\lnot(P\land Q)\Lrarr\lnot P\lor\lnot Q$ なのだ:
| $P$ | $Q$ | $P\land Q$ | $\lnot(P\land Q)$ |
|---|---|---|---|
| $\T$ | $\T$ | $\T$ | $\F$ |
| $\T$ | $\F$ | $\F$ | $\T$ |
| $\F$ | $\T$ | $\F$ | $\T$ |
| $\F$ | $\F$ | $\F$ | $\T$ |
| $P$ | $Q$ | $\lnot P$ | $\lnot Q$ | $\lnot P\lor\lnot Q$ |
|---|---|---|---|---|
| $\T$ | $\T$ | $\F$ | $\F$ | $\F$ |
| $\T$ | $\F$ | $\F$ | $\T$ | $\T$ |
| $\F$ | $\T$ | $\T$ | $\F$ | $\T$ |
| $\F$ | $\F$ | $\T$ | $\T$ | $\T$ |
同様に $\lnot(P\lor Q)\Lrarr\lnot P\land\lnot Q$ なのだ
恒真命題
$P\lor\lnot P\Lrarr\T$ なのだ。このような常に $\T$ となる命題を恒真命題というのだ
様々な証明
これらを踏まえると色々な直感的にもなりたつ命題が証明できるのだ。証明とは命題が真であると示すこと、すなわち命題が $\T$ と同値であることを示せばいいのだ
$\heading{(P\Lrarr\T)\Lrarr P}$
ということをまずは示してみるのだ。$\Lrarr$ は等式の代わりだから左右を $\Lrarr$ で繋げばいいのだ
<$>\begin{aligned} &P\Lrarr\T\\ \Lrarr\ &(P\Rarr\T)\land(\T\Rarr P)\\ \Lrarr\ &(\lnot P\lor\T)\land(\lnot\T\lor P)\\ \Lrarr\ &(\lnot P\lor\T)\land(\lnot\T\lor P)\\ \Lrarr\ &(T\land(\F\lor P)\\ \Lrarr\ &\T\land P\\ \Lrarr\ &P \end{aligned}<$>$\F\lor P$ が $P$ と同値になるのは真理値表から従うのだ:
| $P$ | $\F\lor P$ |
|---|---|
| $\T$ | $\T$ |
| $\F$ | $\F$ |
一般に以下が真理値表より従うのだ:
- $\T\land P\Lrarr P$
- $\T\lor P\Lrarr\T$
- $\F\land P\Lrarr\F$
- $\F\lor P\Lrarr P$
$\heading{(\T\Rarr P)\Lrarr P}$
他にも「恒真命題から命題の形を導ければ大丈夫」っていうやり方もあるのだ
<$>\begin{aligned} &\T\Rarr P\\ \Lrarr\ &\lnot\T\lor P\\ \Lrarr\ &\F\lor P\\ \Lrarr\ &P\\ \end{aligned}<$>これもよく使う方法だから覚えておくのだ
$\heading{(P\Rarr Q)\land(Q\Rarr R)\Rarr(P\Rarr R)}$
<$>\begin{aligned} &(P\Rarr Q)\land(Q\Rarr R)\Rarr(P\Rarr R)\\ \Lrarr\ &\lnot\bigl( (P\Rarr Q)\land(Q\Rarr R)\bigr)\lor(P\Rarr R)\\ \Lrarr\ &\lnot\bigl( (P\Rarr Q)\land(Q\Rarr R)\bigr)\lor\lnot P\lor R\\ \Lrarr\ &\lnot(P\Rarr Q)\lor\lnot(Q\Rarr R)\lor\lnot P\lor R\\ \Lrarr\ &\lnot(\lnot P\lor Q)\lor\lnot(\lnot Q\lor R)\lor\lnot P\lor R\\ \Lrarr\ &(P\land\lnot Q)\lor(Q\land\lnot R)\lor\lnot P\lor R\\ \Lrarr\ &\bigl( (P\land\lnot Q)\lor\lnot P\bigr)\lor(Q\land\lnot R)\lor R\\ \Lrarr\ &\bigl( (P\lor\lnot P)\land(\lnot Q\lor\lnot P)\bigr)\lor(Q\land\lnot R)\lor R\\ \Lrarr\ &\bigl(\T\land(\lnot Q\lor\lnot P)\bigr)\lor(Q\land\lnot R)\lor R\\ \Lrarr\ &\lnot Q\lor\lnot P\lor\bigl( (Q\land\lnot R)\lor R\bigr)\\ \Lrarr\ &\lnot Q\lor\lnot P\lor\bigl( (Q\lor R)\land(\lnot R\lor R)\bigr)\\ \Lrarr\ &\lnot Q\lor\lnot P\lor\bigl( (Q\lor R)\land \T\bigr)\\ \Lrarr\ &\lnot Q\lor\lnot P\lor Q\lor R\\ \Lrarr\ &(\lnot Q\lor Q)\lor\lnot P\lor R\\ \Lrarr\ &\T\lor(\lnot P\lor R)\\ \Lrarr\ &\T \end{aligned}<$>これによって $P\Rarr Q\Rarr R\Rarr\ldots\Rarr Z$ から $P\Rarr Z$ のように推論することが正当化されるのだ
$\heading{P\land Q\Rarr P}$
「梅干しは酸っぱくてしょっぱい」から「梅干しは酸っぱい」のだ
<$>\begin{aligned} &P\land Q\Rarr P\\ \Lrarr\ &\lnot(P\land Q)\lor P\\ \Lrarr\ &\lnot P\lor\lnot Q\lor P\\ \Lrarr\ &(P\lor\lnot P)\lor\lnot Q\\ \Lrarr\ &\T\lor\lnot Q\\ \Lrarr\ &\T \end{aligned}<$>$\heading{(P\Rarr Q)\land P\Rarr Q}$
「殴られる($P$)と痛い($Q$)」ときに殴られ($P$)れば当然痛い($Q$)のだ
<$>\begin{aligned} &(P\Rarr Q)\land P\Rarr Q\\ \Lrarr\ &\lnot((P\Rarr Q)\land P)\lor Q\\ \Lrarr\ &\lnot(P\Rarr Q)\lor\lnot P\lor Q\\ \Lrarr\ &\lnot(\lnot P\lor Q)\lor(\lnot P\lor Q)\\ \Lrarr\ &\T \end{aligned}<$>これは
<$>\begin{aligned} &(P\Rarr Q)\land P\\ \Lrarr\ &(\lnot P\lor Q)\land P\\ \Lrarr\ &(\lnot P\land P)\lor(Q\land P)\\ \Lrarr\ &\F\lor(Q\land P)\\ \Lrarr\ &Q\land P\\ \Rarr\ &Q \end{aligned}<$>のように書いても証明になるのだ。これは $P\Rarr Q\Rarr R$ 式のやり方を証明に適用したのだ。こうすることで早く証明できる場合もあるのだ。以後使っていくのだ
$\heading{(P\Rarr Q)\Lrarr(\lnot Q\Rarr\lnot P)}$
<$>\begin{aligned} &P\Rarr Q\\ \Lrarr\ &\lnot P\lor Q\\ \Lrarr\ &\lnot P\lor\lnot\lnot Q\\ \Lrarr\ &\lnot\lnot Q\lor\lnot P\\ \Lrarr\ &\lnot Q\Rarr\lnot P \end{aligned}<$>「$\lnot Q\Rarr\lnot P$」を「$P\Rarr Q$ の対偶」と呼ぶのだ。対偶を証明すれば元の命題が証明できるから便利なのだ
例えば「お客様は神様である」の対偶は「神様じゃなければお客様じゃない」だし、「人間は平家」の対偶は「平家じゃなければ人間じゃない」なのだ。「カラスは黒い」なら「黒くなければカラスでない」が対偶で、合っていそうだなという直感は得られると思うのだ
量化がまだ完全には扱えない
でも、このままだと「$2$ が偶数なら $9$ は奇数である」のような命題は証明できても、「$n$ が偶数なら $(n+1)^2$ は奇数である」のような命題は証明できないのだ……。具体的な $n$ がわからなければ真偽の定まる具体的な命題として得ることができないからなのだ
命題関数
まず、「$2$ は偶数である」「$3$ は偶数である」「$4$ は偶数である」…をいっぺんに扱いたいから「$p(x): x$ は偶数である」のように定めることを認めるのだ
量化
「お好きな自然数 $n$ をとっても $n$ が偶数なら $(n+1)^2$ は奇数である」みたいな状況がちゃんと証明できるか、というのを扱うために量化を使うのだ
全称量化
「$\forall n,\ n:$ 偶数 $\Rarr (n+1)^2:$ 奇数」と書いて上を表すことにするのだ。「任意の $n$ に対して…」「すべての $n$ に対して…」と読むのだ
これは言葉を定義しただけだから、証明のための規則を導入するのだ
「全ての人間に対して、$2$ は偶数である」という命題も正しいのだ。人間関係ないけど。これは $P\Rarr\forall x,\ P$ と一般化してよいのだ。$x$ と全然関係ない真な命題を $\forall x$ の後にくっつけていいのだ
例えば三段論法のような「人間はみんな死ぬ」「ソクラテスは人間である」「ゆえにソクラテスは死ぬ」という推論ができるとうれしいのだ。
$(\forall x,\ p(x))\Rarr p(t)$ という規則を定めることでさっきの三段論法では「$p(x):x$ が人間なら死ぬ$,\ t:$ ソクラテス」の場合として「$p(t):$ ソクラテスが人間なら死ぬ」を得、ソクラテスは死ぬのだ
ほかにも「人間はみんな死ぬ」「死んだものはお墓に入る」「ゆえに人間はみんなお墓に入る」という推論は正しいのだ
これも$\bigl(\forall x,\ p(x)\Rarr q(x)\bigr)\Rarr\Bigl(\bigl(\forall x,\ p(x)\bigr)\Rarr\bigl(\forall x,\ q(x)\bigr)\Bigr)$ を認めると
「$q(x): x$ が死んでいるならお墓に入る」とすることで示せるのだ
というわけで
- $P\Rarr\forall x,\ P$
- $(\forall x,\ p(x))\Rarr p(t)$
- $\bigl(\forall x,\ p(x)\Rarr q(x)\bigr)\Rarr\Bigl(\bigl(\forall x,\ p(x)\bigr)\Rarr\bigl(\forall x,\ q(x)\bigr)\Bigr)$
の 3 つを認めてこれから証明をしていくのだ
暇だったら「みんなみんな丸顔さ*1」を「$p(x): x$ は丸顔である」として命題の言葉に直し、「アライㄜんは丸顔である」を証明してみてほしいのだ
存在量化
偶数、すなわち「$n=2m $ となる $m $ が存在する」も同じようにして「$n:$ 偶数 $\colonLrarr\exists m,\ n=2m $」と表せるのだ
でもこれは全称量化を使って「$\exist x,\ p(x)\colonLrarr\lnot(\forall x,\ \lnot p(x))$」と表せるのだ。よって推論規則は全称量化のそれに従うのだ
$\exist x,\ p(x)$ は「$p(x)$ となる $x$ が存在する」と読んでそのような意味になるのだ。$\forall x,\ p(x)$ は「すべての $x$ にたいして $p(x)$」と読むのだ。これを踏まえると「$p(x):$ $x$ は数学をするアライㄜんである」と置くことで $\lnot(\forall x,\ \lnot p(x))$ は「『すべての $x$ は数学をするアライㄜんではない』なんてことはない」と読み替えられて、定義が正しいことが直感でつかめると思うのだ
一応存在量化の言葉に直したものを書いておくので各自証明してみてほしいのだ。ヒントは対偶なのだ:
- $p(t)\Rarr(\forall x,\ p(x))$
- $\bigl(\forall x,\ p(x)\Rarr q(x)\bigr)\Rarr\Bigl(\bigl(\exist x,\ p(x)\bigr)\Rarr\bigl(\exist x,\ q(x)\bigr)\Bigl)$
また、よくある記法として
- $p(\forall x),\ q(x)\colonLrarr\forall x,\ p(x)\Rarr q(x)$
- $p(\exist x)\st q(x)\colonLrarr\exist x,\ p(x)\land q(x)$
すなわち「$p(x): x$ は自然数」「$q(x): n=2x$」として「$\exists m:$ 自然数 $\st n=2m $」などと書くことがあるので、見ても面食らわないようにしてほしいのだ
$\st$ は such that の略で、「$x\st p(x)$」 と書いて「$p(x)$ をみたすような $x$」を表すのだ
他にも $\forall x,\ \forall y,\ p(x,y)$ を $\forall x,y,\ p(x,y)$ と 1 つにまとめたりすることもあるので気をつけて読んでほしいのだ
唯一存在量化
$\exist ! x,\ p(x)$ と書いて「$p(x)$ をみたす $x$ がただ一つ存在する」と読ませるのだけど、これは $\exist x,\ p(x)\land\forall y,\ p(y)\Rarr y=x$ と同じことなのだ。書き方として覚えておくといいのだ
例えば $\exist ! n,n+2=4$ みたいな感じなのだ
おまけ: 実際の証明
ここはおまけだから疑問に思った人がよめばいいのだ
実際の証明では主に $\forall x,\ p(x)\Rarr q(x)$ を示すことがとても多いのだ。例えば「自然数 $n$ が偶数なら $(n+1)^2$ は奇数である」のような命題を高校生のときにたくさん見てきたと思うのだ
このとき、暗黙に様々な命題が仮定されていることと思うのだ。$1+1=2,\ 2+1=3,\ 3+1=4,\ \ldots$ などもその典型だと思うのだ。$P\Lrarr\T$ と暗黙な命題を組み合わせて $Q$ が導ければ十分なのだ。もちろんそれは普段からの証明と同じものになるのだ
「自然数 $n$ が偶数なら $(n+1)^2$ は奇数である」を例にいつもの証明と命題の言葉での証明をしてみるのだ
まずは普通の証明なのだ:
$\forall n:$ 偶数 をとるのだ。このとき、$\exist m:$ 自然数$\st n=2m $ だからこれをとるのだ
<$>\begin{aligned} (n+1)^2&=(2m+1)^2\\ &=4m^2+4m+1\\ &=2(2m^2+2m)+1 \end{aligned}<$>ここで $2m^2+2m$ は自然数だから $(n+1)^2$ は奇数なのだ
では命題の証明をしていくのだ。証明中に日本語が書けないから $n: \Bbb{N}$ で $n:$ 自然数 を表すことにさせてほしいのだ
「$n:$ 偶数 $\colonLrarr\exists m,\ n=2m $」、「$n:$ 奇数 $\colonLrarr\exists m,\ n=2m+1 $」として文章を数学の命題に直すのだ:
$\forall n: \Bbb{N},\ (\exist m: \Bbb{N},\ n=2m)\Rarr(\exist m: \Bbb{N},\ (n+1)^2=2m+1)$
また $odd(x,y):\ (y:\Bbb{N})\land x=2y+1$ とおくのだ。さらに:
<$>\begin{aligned} &(\forall x,\ p(x)\Rarr q(x))\land(\forall x,\ q(x)\Rarr r(x))\\ \Lrarr\ &(\forall x,\ p(x)\Rarr q(x))\land(\forall y,\ q(y)\Rarr r(y))\\ \Lrarr\ &\forall x,\ (p(x)\Rarr q(x))\land(\forall y,\ q(y)\Rarr r(y))\\ \Rarr\ &\forall x,\ (p(x)\Rarr q(x))\land(q(x)\Rarr r(x))\\ \Rarr\ &\forall x,\ p(x)\Rarr r(x)\\ \end{aligned}<$>より、量化の中でいつも通りの変形をおこなってよいとわかるのだ。そのような変形を $\forall x,\ p(x)\Rarr q(x)\Rarr r(x)$ と書くことにすれば証明がぐっとやりやすくなって:
<$>\begin{aligned} &\forall n: \Bbb{N},\\ &\quad\begin{aligned} &\forall m: \Bbb{N},\\ &\quad\begin{aligned} &n=2m\\ \Rarr\ &n+1=2m+1\\ \Rarr\ &(n+1)^2=(2m+1)^2\\ \Rarr\ &(n+1)^2=4m^2+4m+1\\ \Rarr\ &(n+1)^2=2(2m^2+2m)+1\\ \Rarr\ &odd((n+1)^2, 2m^2+2m)\\ \Rarr\ &\exist m':\Bbb{N},\ (n+1)^2=2m'+1\\ \end{aligned}\\ \Rarr\ &\bigl((\exist m: \Bbb{N},\ n=2m)\Rarr(\exist m: \Bbb{N},\ (n+1)^2=2m+1)\bigr) \end{aligned} \end{aligned}<$>途中で $\forall n: \Bbb{N},\ \forall m: \Bbb{N},\ n=2m\Rarr\exist m': \Bbb{N},\ (n+1)^2=2m'+1$ が恒真命題だとわかるから、最後に $\bigl(\forall x,\ p(x)\Rarr q(x)\bigr)\Rarr\Bigl(\bigl(\exist x,\ p(x)\bigr)\Rarr\bigl(\exist x,\ q(x)\bigr)\Bigl)$ の特殊な形 $\bigl(\forall x,\ p(x)\Rarr Q\bigr)\Rarr\Bigl(\bigl(\exist x,\ p(x)\bigr)\Rarr Q\Bigl)$ を使えば求めていた命題が導けて、さっきの量化を含まない推論とほとんど同じような手順で証明できてしまうのだ
命題の言葉にすれば証明が正確になり、かつ自由度は変わらないことがわかるのだ
次回は命題が準備できたから集合と写像の定義からやっていくのだ
*1:まる顔のうた 大山のぶ代 - 歌詞タイム。一応歌詞は条件付きで丸顔なのだ
