証明 (数学)

数学、記号論理学における証明

ある命題が正しいことを主張するための一連の演繹を証明 (英: Mathematical proof) と呼ぶ。証明の各段階においては、前提（公理、定理等の認められた事実）や仮定から推論規則によって新たな命題を導くという形態をとる。ある証明の中で導入された仮定は、証明の別の部分で証明されるか、その証明の中で否定され（背理法）なければならない。

命題 P を証明したいとき、P を直に証明することを直接証明と言う。それに対して P が真であることを直接証明する代わりに、P と同値な別の命題が真であることを証明する方法を間接証明と言う（これらはあくまで直観的な分類に過ぎず、数学的な定義があるわけではない）。

代表的な証明方法

証明の代表的なテクニックを以下に示す。

• 対偶法 - 命題 P⇒Q を証明する代わりに、これと同値な ￢Q⇒￢P を証明する方法（￢は否定）。
• 背理法 - 命題 P を証明する代わりに、￢P が偽であることを証明する方法（￢P が偽であることを証明するには、￢P を仮定して矛盾を導けばよい）。
• 反例 - 命題「全てのxがP(x)を満たす」 が偽であることを示すには、 P(x) を満たさない x を一つあげればよい（￢∀xPx と ∃x￢Px が同値であることを利用する）。
• 転換法 - 全ての状況が P, Q, R のいずれかに分類でき、A, B, C が独立であるとする。今「P⇒A」「Q⇒B」「R⇒C」が証明できていたとする。このとき、それらの逆「A⇒P」「B⇒Q」「C⇒R」も成立する。
• 同一法 - A ⇒ B が成り立ち、B を満たすものがただひとつであれば、B ⇒ A が成り立つ。
• ディリクレの箱入れ論法 - n+1 個以上のボールのそれぞれが n 個の箱のいずれかに入っているとする。このとき、少なくとも1個の箱には2個以上のボールが入っている。
• 数学的帰納法 - 自然数に関する命題 P(n) が全ての n に対して成立することを示す論法。まず P(1) が成立することを示し、次に P(n) が成立すれば P(n+1) が成立することを示す。

その他の用語

• 存在証明 - 解が存在することを示す行為
• 一意性証明 - （解がもし存在すれば）解の数は1つであることを示す行為

証明の形式的定義

数学における命題の証明においては、通常、その正しさの確認は証明の作成者と読者に委ねられている。証明の概念を形式化することによって、その正しさを機械的に判定したり、証明そのものを数学の研究対象とすることもできる。

• 有限集合を1つ固定し、その有限集合の元をアルファベットという。
• アルファベットの有限列を語という。
• 語の集合を言語という。
• 言語を1つ固定し、その言語に属する語を命題という。
• 命題の集合を1つ固定し、その集合に属する命題を事前に認められた仮定として採用し、それを公理と呼ぶ。
• 命題の有限個の組がどのような条件を満たせば、それらの命題から別の命題が導けるのかを決めたルールの組を決め、それらのルールを推論規則という。
• 公理の集合と推論規則の集合の組を公理系と呼ぶ。

Aを公理系とし、(P₁,...,P_n) を命題の列とする。

任意の i≦n に対し P_i が

• P_i は公理である
• P_i は、P₁,..., P_i-1 から、許された推論規則によって導くことができる

のいずれかを満たすとき、(P₁,...,P_n) を P_n の（公理系 A における）証明と言う。

ある (P₁,...,P_n) があって、(P₁,...,P_n) が P_n の証明であるとき、P_n は（公理系 A において）証明可能である、もしくは P_n は定理であると言う。

記述の習慣

証明を記述する際には、証明とそれ以外の部分をはっきりわけて可読性をあげるため、証明の始めと終わりを明確に示す習慣があり、特に高等学校などで初めて証明の記述を学ぶ者に対しては厳しく指導される。始めや終わりを示す記号は書く人の好みによりさまざまであるが、始めには「proof」「prf.」「pf.」「（証明）」「（証）」、丸で囲んだ「∵」などが、終わりには「Q.E.D.」「（証明終わり）」「（証明終）」「（証終）」「（終）」「□」「■」「//」などが用いられる。

証明の例（背理法）

「素数は無限個存在する」という命題の証明は以下のようになされる。

pf. 素数の個数は有限であると仮定する。すべての素数を掛け合わせた数に1を足したものはどの素数で割っても1余り、割り切れない。すなわちそれ自体が素数であるか、ここで想定した最大の素数よりも大きい素数でしか割り切れないことを意味する。いずれにしても、すべての素数以外に素数が存在することになり仮定と矛盾する。よって仮定は間違っており、素数は無限に存在することが示された。Q.E.D.