背理法を組み合わせたもの
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/05/21 22:48 UTC 版)
「数学的帰納法」の記事における「背理法を組み合わせたもの」の解説
詳細は「無限降下法」を参照 無限降下法とは、背理法を用いて ∀ n ∈ N . P ( n ) {\displaystyle \forall n\in \mathbb {N} .\,P(n)} を証明する、次のようなパターンのことである。 P ( n ) {\displaystyle P(n)} が成立しないような自然数 n {\displaystyle n} が存在すると仮定し、その中で最小のものを k {\displaystyle k} とする。次に、 P ( k ) {\displaystyle P(k)} を仮定すると、「ある自然数 k ′ < k {\displaystyle k'<k} が存在して P ( k ′ ) {\displaystyle P(k')} ではないこと」を導けることを示す。これは k {\displaystyle k} の最小性に矛盾するから、背理法により、 P ( n ) {\displaystyle P(n)} が成立しないような自然数 n {\displaystyle n} は存在しない。すなわち、すべての自然数 n {\displaystyle n} に対して P ( n ) {\displaystyle P(n)} が成り立つ。 この議論と前に述べた「先立つすべての結果を用いる」形の数学的帰納法の正しさは自然数全体の集合 N {\displaystyle \mathbb {N} } が通常の大小関係 < {\displaystyle <} によって整列されていることによる。 < {\displaystyle <} が N {\displaystyle \mathbb {N} } 上の整列順序であることは、最初に述べた標準的な形の数学的帰納法を用いることで証明される。
※この「背理法を組み合わせたもの」の解説は、「数学的帰納法」の解説の一部です。
「背理法を組み合わせたもの」を含む「数学的帰納法」の記事については、「数学的帰納法」の概要を参照ください。
- 背理法を組み合わせたもののページへのリンク