§A3.14定義の展開という技法

最終更新

定義の展開は、証明で何を示し、どの仮定を使うのかをどのように明らかにするのでしょうか。本記事では、示すべき結論と利用できる仮定を対象として、それぞれを定義に従って書き下します。両者の間に残る推論を、その場の計算で閉じる部分と、別の定理または公理を必要とする部分とに分けるところまで進みます。

1 結論と仮定の定義への展開

定義の展開では、次の順序を用います。

公式 1.1. 証明する結論を定義で書き換える。利用できる仮定も定義で書き換える。各定義に現れる量化子、対象の範囲、条件をすべて書く。最後に、残った証明の責務を、その場の計算で閉じる部分と既存の定理や公理を必要とする部分とに分ける。

結論を展開すると、何を示せば証明が終わるのかが分かります。仮定を展開すると、証明に使うことができる式や条件が分かります。両方を同じ記号で書くことにより、結論と仮定の間に残る推論を特定することができます。

2 単射の合成と定義の展開

定義 2.1 (単射). 集合X,YX,Yと写像f:X→Yf:X\to Yに対して、ffが単射 (injective map) であるとは、任意のa,b∈Xa,b\in Xについて

f(a)=f(b)⟹a=bf(a)=f(b)\Longrightarrow a=b

が成り立つことをいう。

定理 2.2. 集合X,Y,ZX,Y,Zと写像f:X→Yf:X\to Y、g:Y→Zg:Y\to Zをとる。ffとggが単射ならば、合成写像g∘f:X→Zg\circ f:X\to Zも単射である。

単射の定義を定理の仮定と結論へそれぞれ適用すると、次の条件になります。

役割 定義を展開した条件
ffが単射であるという仮定 すべてのs,t∈Xs,t\in Xに対して、f(s)=f(t)f(s)=f(t)ならばs=ts=tです。
ggが単射であるという仮定 すべてのu,v∈Yu,v\in Yに対して、g(u)=g(v)g(u)=g(v)ならばu=vu=vです。
g∘fg\circ fが単射であるという結論 すべてのa,b∈Xa,b\in Xに対して、g(f(a))=g(f(b))g(f(a))=g(f(b))ならばa=ba=bです。

a,b∈Xa,b\in Xを任意に取ると、f(a),f(b)∈Yf(a),f(b)\in Yです。このため、ggの単射性を先に適用し、続いてffの単射性を適用します。

証明.a,b∈Xa,b\in Xを任意に取り、(g∘f)(a)=(g∘f)(b)(g\circ f)(a)=(g\circ f)(b)と仮定する。この等式は

g(f(a))=g(f(b))g(f(a))=g(f(b))

を意味する。ggは単射であるからf(a)=f(b)f(a)=f(b)であり、ffも単射であるからa=ba=bである。したがって、任意のa,b∈Xa,b\in Xについて(g∘f)(a)=(g∘f)(b)(g\circ f)(a)=(g\circ f)(b)ならばa=ba=bとなるため、g∘fg\circ fは単射である。▨

結論と二つの仮定を定義へ置き換えると、この証明は単射性を二回適用することで閉じます。

3 集合の等式の展開と場合分け

集合の等式についても、仮定と結論を要素の所属条件に書き換えます。

例 3.1. 全体集合UUの部分集合A,B,CA,B,Cが

A∩B=A∩C,A∪B=A∪CA\cap B=A\cap C,\qquad A\cup B=A\cup C

を満たすとする。このときB=CB=Cである。

二つの仮定を要素の条件で書くと、

∀x∈U [(x∈A∧x∈B)⇔(x∈A∧x∈C)],\forall x\in U\,\bigl[(x\in A\land x\in B)\Leftrightarrow(x\in A\land x\in C)\bigr],∀x∈U [(x∈A∨x∈B)⇔(x∈A∨x∈C)]\forall x\in U\,\bigl[(x\in A\lor x\in B)\Leftrightarrow(x\in A\lor x\in C)\bigr]

となる。示すべき結論は∀x∈U (x∈B⇔x∈C)\forall x\in U\,(x\in B\Leftrightarrow x\in C)である。

x∈Ux\in Uを任意に取る。x∈Ax\in Aの場合、共通部分の等式からx∈B⇔x∈Cx\in B\Leftrightarrow x\in Cが従う。x∉Ax\notin Aの場合、和集合の等式から同じ同値が従う。二つの場合はUUのすべての要素を尽くすので、B=CB=Cである。

一方の仮定だけでは結論は成り立たない。U={1,2}U=\{1,2\}、A={1}A=\{1\}、B=∅B=\varnothing、C={2}C=\{2\}とすると、A∩B=A∩C=∅A\cap B=A\cap C=\varnothingであるがB≠CB\ne Cである。同じU,A,BU,A,BとC={1}C=\{1\}ならば、A∪B=A∪C={1}A\cup B=A\cup C=\{1\}であるがB≠CB\ne Cである。

4 上限公理を要する収束の例

定義を展開すると、計算だけでは閉じない依存を特定することもできます。次の定理はその例です。

定理 4.1. 上に有界な広義単調増加数列は収束する。

実数列(an)n≥1(a_n)_{n\ge1}について仮定を展開すると、すべてのn≥1n\ge1に対する不等式an≤an+1a_n\le a_{n+1}と、ある実数MMが存在して、すべてのn≥1n\ge1に対してan≤Ma_n\le Mが成り立つことが現れます。一方、結論を展開すると、極限の候補となる実数α\alphaが存在し、任意のε>0\varepsilon>0に対して番号NNを選ぶことができ、n≥Nn\ge Nを満たすすべてのnnに対して∣an−α∣<ε|a_n-\alpha|<\varepsilonが成り立つという量化が現れます。仮定の不等式だけから、実数α\alphaの存在を得ることはできません。

数列の値の集合{an∣n≥1}\{a_n\mid n\ge1\}は空でなく、上に有界です。極限候補を得る段階では、§D1.4 定義 1.2から得られる上限の存在を用います。ただし、上限が存在することだけでは収束の証明は終わりません。上限の性質から、任意のε>0\varepsilon>0に対応する番号NNを得る推論も必要です。その推論を含む完全な証明は§D1.7 定理 1.1に委ねます。

閑話休題:証明を機械に行わせる試みと、その限界 定義に従う書き換えを繰り返せば、証明を機械的な記号操作として記述することができるのではないか、という問いが生じます。2020世紀初頭、ヒルベルトは、数学を公理から形式的に導き、その体系の無矛盾性を有限的な方法で保証する計画を掲げました。この計画をヒルベルト・プログラムといいます。

19311931年、ゲーデルは不完全性定理によって、この計画に限界があることを示しました。自然数の算術を表すことができ、無矛盾で、公理と証明を機械的に検査することができる十分に強い形式体系には、その体系内で証明も反証もできない文が存在します。さらにチューリングは、任意に与えられたプログラムと入力について、そのプログラムが停止するかどうかを常に判定する手続きが存在しないことを示しました。この停止性問題を定式化する過程で、計算を表す理論上の機械としてチューリング機械が導入されました。

今日、Lean や Coq などの証明支援系は、形式化された定義、公理、推論規則に基づいて証明を検査します。証明支援系は不完全性定理や停止性問題の制約を取り除くものではありませんが、公理から結論までの各推論を機械的に確認することができます。定義を展開して必要な推論を特定するという本記事の手順は、この形式化の入口にあたります。形式体系そのものを数学の対象として扱う理論は§F39 モデル理論が扱います。

例題

条件と何を求めるかを確認してから、式と答えの対応を見比べてください。

次の言明を定義に従って論理式に展開し、さらにその否定(否定記号を内側へ押し込んだ形)を書け。

次の言明を定義に従って論理式に展開し、その否定も書け。

解法の型証明に詰まったら定義を展開する。展開すれば「示すべきこと」「使えること」が式になり、残りは計算。否定は ∀\forall↔∃\exists を反転し、A ⇒\Rightarrow B は A ∧\land¬B\neg B に

  1. 例題 1

    数列 (an) は L に収束する\text{数列 } (a_n) \ \text{は } L \ \text{に収束する}
  2. 例題 2

    f は偶関数であるf \ \text{は偶関数である}
  3. 例題 3

    ベクトルの組 v1,…,vn は一次独立である\text{ベクトルの組 } v_1, \ldots, v_n \ \text{は一次独立である}
  4. 例題 4

    f:X→Y は全射であるf : X \to Y \ \text{は全射である}
  5. 例題 5

    f は単射であるf \ \text{は単射である}
  6. 例題 6

    M は S の上限(最小の上界)であるM \ \text{は } S \ \text{の上限(最小の上界)である}
  7. 例題 7

    f は単調増加である(広義)f \ \text{は単調増加である(広義)}
  8. 例題 8

    f は(実数全体で)有界であるf \ \text{は(実数全体で)有界である}
  9. 例題 9

    H は群 G の部分群であるH \ \text{は群 } G \ \text{の部分群である}
  10. 例題 10

    n は偶数であるn \ \text{は偶数である}

演習

問題を解いてから「解答・解説」を開けます。

次の言明を定義に従って論理式に展開し、さらにその否定(否定記号を内側へ押し込んだ形)を書け。

演習を読み込み中…

前提記事