ホーム >> 集合・論理 >> 無限降下法

整数に関する証明問題等で威力を発揮する,無限降下法について解説します.



無限降下法とは

無限降下法(むげんこうかほう)とは,自然数あるいは自然数の部分集合には必ず最小の元が存在するという性質を用いた証明法です.背理法の一種であり,数学的帰納法の派生とみなすこともできます.代表的には,不定方程式の自然数解の不存在性を証明するときに用いられます.17世紀の数学者ピエール・ド・フェルマーが好んでよく用いたとされています.

非常に単純なアイデアに基づいた証明法ですが,その応用範囲は大きいです.無限降下法の基本的なアイデアと使い方をみていきましょう.

無限降下法のアイデア

無限降下法の最も重要なアイデアは, 自然数あるいは自然数の部分集合には必ず最小の元が存在するという事実です.
たとえば,自然数全体の集合の最小の元は $1$ です.また,集合 $\{5,10,15,20,25\}$ の最小の元は $5$ です.また,集合 $\{p\ |\ p \ \text{は素数}\}$ の最小の元は $2$ です.このように,有限集合であっても無限集合であっても,それが自然数全体の集合の部分集合であるならば,必ず最小の元をもちます.

ちなみに,自然数全体の集合の部分集合でない集合は最小の元をもつとは限りません,たとえば,集合 $\{\frac{1}{n}\ |\ n \ \text{は自然数}\}$ は最小の元をもちません.

さて,無限降下法の一般的な証明のプロセスはつぎのようになっています.
自然数 $n$ に関する命題 $P(n)$ を考えます. 『任意の自然数 $n$ に対して,命題 $P(n)$ は偽』という主張を示したいとしましょう.

無限降下法の手順:
Step 1: ある自然数 $n_1$ に対して,命題 $P(n_1)$ が真であると仮定します.(背理法)
Step 2: 『ある自然数 $n_1$ に対して,$P(n_1)$ が真 $\Rightarrow$ $n_1$ より小さい自然数 $n_2$ が存在して,$P(n_2)$ が真』であることを示します.
Step 3: Step 2 の主張を繰り返し用いると,命題 $P(n)$ を満たす自然数の無限列 $n_1>n_2>n_3> \cdots$ が得られます.ところが自然数の部分集合 $\{n_1,n_2,...\}$ は必ず最小の元をもつので,これは矛盾です.

つまり,もし,命題を真とするような自然数があったとすると,それよりも小さい自然数で命題を真とするものがとれてしまい矛盾するという論法です.

例題

具体的な例題を通して,無限降下法の使い方に慣れましょう.

例題 $\sqrt[3]{2}$ は無理数であることを証明せよ.

背理法で示します.$\sqrt[3]{2}$ が有理数であると仮定すると,自然数 $x_1,y_1$ を用いて, $$\sqrt[3]{2}=\frac{x_1}{y_1}$$ とかけます.両辺 $3$ 乗すると, $$x_1^3=2y_1^3$$ となります.右辺は偶数なので,左辺も偶数でなければなりません.特に $x_1$ は偶数です.したがって,自然数 $x_2$ を用いて,$x_1=2x_2$ とかけます.これを代入すると, $$4x_2^3=y_1^3$$ となります.今度は左辺が偶数なので,右辺は偶数でなければなりません.特に $y_1$ は偶数です.したがって,自然数 $y_2$ を用いて,$y_1=2y_2$ とかけます.これを代入すると, $$x_2^3=2y_2^3$$ となります.この議論を繰り返していくと,方程式 $x^3=2y^3$ の自然数の解 $(x_1,y_1),(x_2,y_2),(x_3,y_3)...$ が無限に得られることになります.ところがつくりかたから,$x_1>x_2>x_3>\cdots$ であるので,これは自然数の部分集合が必ず最小元をもつことに矛盾します.

例題 方程式 $x^2+y^2=3z^2$ を満たす自然数解 $(x,y,z)$ は存在しないことを示せ.

存在するとして矛盾を導きます.$(x_1,y_1,z_1)$ を方程式 $x^2+y^2=3z^2$ のある自然数解とします.したがって, $$x_1^2+y_1^2=3z_1^2$$ が成り立ちます. 右辺は $3$ の倍数なので,左辺も $3$ の倍数です.ところで,平方数を $3$ で割ったあまりは $0$ または $1$ なので,$x_1^2,y_1^2$ はともに $3$ の倍数でなければなりません.つまり,$x_1,y_1$ はともに $3$ の倍数です.したがって,ある自然数 $x_2,y_2$ を用いて $x_1=3x_2,y_1=3y_2$ とおけます.これらを代入すると, $$3x_2^2+3y_2^2=z_1^2$$ となります.左辺は $3$ の倍数なので,右辺も $3$ の倍数です.したがって,ある自然数 $z_2$ を用いて,$z_1=3z_2$ とおけます.これを代入すると, $$x_2^2+y_2^2=3z_2^2$$ となります.この議論を繰り返していくと,方程式 $x^2+y^2=3z^2$ の自然数の解 $(x_1,y_1,z_1),(x_2,y_2,z_2),(x_3,y_3,z_3)...$ が無限に得られることになります.ところが,$x_1>x_2>x_3>\cdots$ であるので,これは自然数の集合が必ず最小元をもつことに矛盾します.

練習問題

 $△ABC$ を鋭角三角形とする.$A$ から辺 $BC$ へ下ろした垂線の足を $A_1$ とする.$A_1$ から辺 $CA$ へ下ろした垂線の足を $A_2$ とする.$A_2$ から辺 $AB$ へ下ろした垂線の足を $A_3$ とする.以下同様にして $△ABC$ の辺上の点 $A_1,A_2,A_3,A_4,...$ を得る.このとき,$A_1,A_2,A_3,A_4,...$ はすべて相異なる点であることを示せ.
無限降下法

→solution

$△ABC$ は鋭角三角形なので,$A_1,A_2,...$ はすべて辺 $AB$ または辺 $BC$ または辺 $CA$ 上にあり,さらに,$A,B,C$ とは異なる点であることに注意する.

$2$ 点 $A_i,A_j\ (i< j)$ が一致しているとする.このとき,点列のつくりかたから $A_{i-1},A_{j-1}$ も一致していなければならない.この議論を繰り返すと結局 $2$ 点 $A_1,A_{j-i+1}$ が一致していなければならない.つまり,$A,A_{j-i}$ が一致していなければならないが,これは冒頭にのべたことに反する.したがって,$A_1,A_2...$ はすべて相異なる.

 $n$ を $3$ 以上の自然数とする.このとき,方程式 $$x^n+2y^n=4z^n$$ を満たす自然数 $(x,y,z)$ は存在しないことを示せ.

→solution

自然数の組 $(x_1,y_1,z_1)$ が $x_1^n+2y_1^n=4z_1^n$ を満たすと仮定する.
$2y_1^n,4z_1^n$ はともに偶数なので,$x_1^n$ も偶数である.したがって,$x_1$ は偶数.したがって,ある自然数 $x_2$ を用いて $x_1=2x_2$ とかける.これを方程式に代入すると, $$2^nx_2^n+2y_1^n=4z_1^n$$ すなわち $$2^{n-1}x_2^n+y_1^n=2z_1^n$$ さきほどの議論と同様にして,$y_1$ は偶数でなければならない.したがって,ある自然数 $y_2$ を用いて $y_1=2y_2$ とかける.これを方程式に代入すると, $$2^{n-1}x_2^n+2^ny_1^n=2z_1^n$$ すなわち $$2^{n-2}x_2^n+2^{n-1}y_1^n=z_1^n$$ さきほどの議論と同様にして,$z_1$ は偶数でなければならない ($n\ge 3$ に注意).したがって,ある自然数 $z_2$ を用いて $z_1=2z_2$ とかける.これを方程式に代入すると, $$2^{n-2}x_2^n+2^{n-1}y_1^n=2^nz_2^n$$ 両辺 $2^{n-2}$ で割ると, $$x_2^n+2y_2=4z_2^n$$ を得る.つまり,自然数の組 $(x_1,y_1,z_1)$ が方程式 $x^n+2y^n=4z^n$ の解であるとき,$(x_2,y_2,z_2)$ も解となる.この議論を繰り返すと,方程式 $x^n+2y^n=4z^n$ の自然数解の列 $(x_1,y_1,z_1),(x_2,y_2,z_2),...$ を得ることができる.ところが,$x_1>x_2>\cdots $ であるから,これは自然数の集合に最小元が存在することに矛盾する.
よって,方程式 $x^n+2y^n=4z^n$ の自然数解は存在しない.