定義の展開は、証明で何を示し、どの仮定を使うのかをどのように明らかにするのでしょうか。本記事では、示すべき結論と利用できる仮定を対象として、それぞれを定義に従って書き下します。両者の間に残る推論を、その場の計算で閉じる部分と、別の定理または公理を必要とする部分とに分けるところまで進みます。
1 示すことも、使うことも、定義に戻す
定義の展開では、次の順序を用います。
公式 1.1. 証明する結論を定義で書き換える。利用できる仮定も定義で書き換える。各定義に現れる量化子、対象の範囲、条件をすべて書く。最後に、残った証明の責務を、その場の計算で閉じる部分と既存の定理や公理を必要とする部分とに分ける。
結論を展開すると、何を示せば証明が終わるのかが分かります。仮定を展開すると、証明に使うことができる式や条件が分かります。両方を同じ記号で書くことにより、結論と仮定の間に残る推論を特定することができます。
2 例:計算で埋めることができる場合
定義 2.1 (単射). 集合と写像に対して、が単射であるとは、任意のについて
が成り立つことをいう。
結論と仮定の両方へ、この定義を適用します。
定理 2.2. 集合と写像、をとる。とが単射ならば、合成写像も単射である。
証明.を任意に取り、と仮定する。この等式は
を意味する。は単射であるからであり、も単射であるからである。したがって、任意のについてならばとなるため、は単射である。▨
結論と二つの仮定を定義へ置き換えると、この証明は単射性を二回適用することで閉じます。
3 例:別の定理を必要とする場合
定義を展開すると、計算だけでは閉じない依存を特定することもできます。次の定理はその例です。
定理 3.1 (有界な広義単調数列の収束). 上に有界な広義単調増加数列は収束する。
実数列について仮定を展開すると、すべてのに対する不等式と、ある実数が存在して、すべてのに対してが成り立つことが現れます。一方、結論を展開すると、極限の候補となる実数が存在し、任意のに対して番号を選ぶことができ、を満たすすべてのに対してが成り立つという量化が現れます。仮定の不等式だけから、実数の存在を得ることはできません。
数列の値の集合は空でなく、上に有界です。極限候補を得る段階では、§D1.4 定義 1.2が与える上限の存在を用います。ただし、上限が存在することだけでは収束の証明は終わりません。上限の性質から、任意のに対応する番号を得る推論も必要です。その推論を含む完全な証明は§D1.7 定理 1.1に委ねます。
定義の展開は、局所的な計算で閉じる部分と、既存の定理や公理を必要とする部分とを分けます。定義に戻れば必ず初等的な計算だけになるとは限りません。
閑話休題:証明を機械に行わせる試みと、その限界 定義に従う書き換えを繰り返せば、証明を機械的な記号操作として記述することができるのではないか、という問いが生じます。世紀初頭、ヒルベルトは、数学を公理から形式的に導き、その体系の無矛盾性を有限的な方法で保証する計画を掲げました。この計画をヒルベルト・プログラムといいます。
年、ゲーデルは不完全性定理によって、この計画に限界があることを示しました。自然数の算術を表すことができ、無矛盾で、公理と証明を機械的に検査することができる十分に強い形式体系には、その体系内で証明も反証もできない文が存在します。さらにチューリングは、任意に与えられたプログラムと入力について、そのプログラムが停止するかどうかを常に判定する手続きが存在しないことを示しました。この停止性問題を定式化する過程で、計算を表す理論上の機械としてチューリング機械が導入されました。
今日、Lean や Coq などの証明支援系は、形式化された定義、公理、推論規則に基づいて証明を検査します。証明支援系は不完全性定理や停止性問題の制約を取り除くものではありませんが、公理から結論までの各推論を機械的に確認することができます。定義を展開して必要な推論を特定するという本記事の手順は、この形式化の入口にあたります。形式体系そのものを数学の対象として扱う理論は「数理論理・モデル理論」が扱います。