証明_(数学) - 暇つぶしWikipedia

証明_(数学)

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方）
出典検索?: "証明" 数学 ? ニュース・書籍・スカラー・ CiNii ・ J-STAGE ・ NDL ・ dlib.jp ・ジャパンサーチ・ TWL（2021年7月）
原論における最初の命題と証明（オリヴァー・バーン編纂による英語版）。ただし原論では二円が交わることが保証されていないため [1]、厳密には適当な連続性公理が必要となる。

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

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

証明の代表的なテクニックを以下に示す。
対偶法
命題 P⇒Q を証明する代わりに、これと同値な￢Q⇒￢P を証明する方法（￢は否定）。[2]
背理法（帰謬法）
命題 P を証明する代わりに、￢P が偽であることを証明する方法（￢P が偽であることを証明するには、￢P を仮定して矛盾を導けばよい）。[3]
反例
命題「全てのxがP(x)を満たす」が偽であることを示すには、 P(x) を満たさない x を一つあげればよいというもの。￢∀x, P(x) と ∃x, ￢P(x) が同値であることを利用する（∀は「全ての」、∃は「存在する」）。[4]
転換法
全ての状況が 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個以上のボールが入っている。[5]
数学的帰納法
 自然数に関する命題 P(n) が全ての n に対して成立することを示す論法。まず P(1) が成立することを示し、次に P(n) が成立すれば P(n+1) が成立することを示す。[6]
背理法による例

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

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

存在証明 - 解が存在することを示す行為

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

 証明の形式的定義

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

有限集合を1つ固定し、その有限集合の元をアルファベットという。

アルファベットの有限列を語という。

語の集合を言語という。

言語を1つ固定し、その言語に属する語を命題という。

命題の集合を1つ固定し、その集合に属する命題を事前に認められた仮定として採用し、それを公理と呼ぶ。

命題の有限個の組がどのような条件を満たせば、それらの命題から別の命題が導けるのかを決めたルールの組を決め、それらのルールを推論規則という。

公理の集合と推論規則の集合の組を公理系と呼ぶ。