数学的帰納法と整列性

同義語：induction and well-ordering

概要

前提知識: 自然数, 集合, 命題, 全順序, 空虚な真

高校での出発点：ドミノ倒しの証明

高校で習う数学的帰納法は、正の整数 $n$ についての主張 $P(n)$ を、次の 2 つを示すことで証明する方法である。

$P(1)$ が成り立つ。
$P(n)$ が成り立つと仮定すると、$P(n+1)$ が成り立つ。

計算 1（和の公式）　$1+2+\cdots+n=\dfrac{n(n+1)}2$ を示す。$n=1$ では両辺とも $1$ である。$n$ で成り立つと仮定すると
$$ 1+2+\cdots+n+(n+1)=\frac{n(n+1)}2+(n+1)=\frac{(n+1)(n+2)}2 $$
なので $n+1$ でも成り立つ。
計算 2（整除性）　$4^n-1$ は $3$ で割り切れる。$n=1$ では $4-1=3$ である。$4^n-1=3m$ と仮定すると $4^{n+1}-1=4(4^n-1)+3=3(4m+1)$ である。
計算 3（2 つ前まで使う）　Fibonacci 数 $F_0=0$、$F_1=1$、$F_{n}=F_{n-1}+F_{n-2}$（$n\ge2$）について $F_n<2^n$ を示す。$n=0,1$ では $0<1$、$1<2$ である。$n\ge2$ で、$n-1$ と $n-2$ のとき成り立つと仮定すると
$$ F_n=F_{n-1}+F_{n-2}<2^{n-1}+2^{n-2}<2^{n-1}+2^{n-1}=2^n $$
である。ここでは「直前の $1$ つ」ではなく「直前の $2$ つ」を仮定しており、出発点も $2$ つ確かめている。
計算 4（最小のものをとる）　「$\sqrt2$ は無理数である」の証明で、$\sqrt2=p/q$（$p,q$ は正の整数）と書けたとして「分母 $q$ が最小になるように選ぶ」という論法がある。これも帰納法と同じ種類の議論であることを、本記事で確かめる（ex-iwo-sqrt2）。
これらの計算は次の疑問を残す。

2 つを示すと「すべての $n$」で正しいと言ってよいのはなぜか。
計算 3 のように前のいくつもの段を仮定してよいのはなぜか。
「最小のものをとる」論法と帰納法はどういう関係にあるか。
答はどれも、自然数の 整列性（空でない部分集合には必ず最小の元がある）に行き着く。本記事では、普通の帰納法・強い帰納法・整列性の 3 つが互いに同値であることを証明し、そこから無限降下法を導く。さらに、帰納法の「誤用」がどの段で破綻しているかを反例で調べ、整列性だけを取り出すと自然数を超えた「超限帰納法」が得られることを紹介する。

取り出す構造：整列性

以下、Mathpedia の流儀に従って $0$ を自然数に含め、$\mathbb{N}=\{0,1,2,\dots\}$ とする。高校の帰納法は $1$ から始まるが、始点をずらすのは番号の付け替えにすぎない（後の節「高校の計算をもう一度見る」で述べる）。
集合 $X$ 上の関係 $<$ が 全順序（狭義の全順序）であるとは、$x< x$ となる $x$ がなく（非反射律）、$x< y$ かつ $y< z$ なら $x< z$ であり（推移律）、任意の $x,y$ について $x< y$、$x=y$、$y< x$ のどれか 1 つだけが成り立つ（三分律）ことをいう。$x\le y$ は「$x< y$ または $x=y$」の略である。部分集合 $S\subset X$ の元 $m$ が $S$ の 最小元 であるとは、すべての $s\in S$ について $m\le s$ であることをいう。最小元はあればただ 1 つである（$m,m'$ がともに最小元なら $m\le m'$ かつ $m'\le m$ なので、三分律から $m=m'$）。

整列順序

全順序集合 $(X,<)$ が 整列している（$<$ が 整列順序 である）とは、$X$ の空でない任意の部分集合が最小元をもつことをいう。

有限個の元からなる全順序集合は整列している（有限集合では、元を $1$ つずつ比べて小さいほうを残していけば最小元が見つかる）。
$\mathbb{N}$ は通常の大小で整列している。これは帰納法から導かれ、逆に帰納法を導く（thm-iwo-equivalence）。
整数全体 $\mathbb{Z}$ は整列していない。負の整数全体 $\{-1,-2,-3,\dots\}$ には最小元がない。
$0$ 以上の有理数全体 $\mathbb{Q}_{\ge0}$ や $0$ 以上の実数全体 $\mathbb{R}_{\ge0}$ も整列していない。正の数全体には最小元がない（$x>0$ なら $x/2$ はもっと小さい正の数である）。$\mathbb{R}_{\ge0}$ 自身の最小元は $0$ なので、「全体に最小元がある」だけでは整列性にならない。
以下で使う $\mathbb{N}$ の性質を明示しておく。$\mathbb{N}$ の大小 $<$ について、次の 4 つを認める。
(N1) $<$ は $\mathbb{N}$ 上の全順序である。
(N2) すべての $n$ について $0\le n$ である（$0$ より小さい自然数はない）。
(N3) すべての $n,k$ について、$k< n+1$ と $k\le n$ は同値である（$n$ と $n+1$ の間に自然数はない）。
(N4) $0$ でない自然数 $n$ は、ある自然数 $m$ を使って $n=m+1$ と書ける。
これらは Peano の公理（あるいは集合論による自然数の構成）から帰納法を使って証明される基本事実であり、本記事では証明しない（自然数の記事を参照）。本記事の関心は、これらを土台にしたとき、次の 3 つの原理がどう関係するかにある。自然数 $n$ ごとに真偽の定まる主張を $P(n)$ と書く。
(I) 普通の帰納法：$P(0)$ が成り立ち、すべての $n$ について「$P(n)$ ならば $P(n+1)$」が成り立つなら、すべての $n$ で $P(n)$ が成り立つ。
(S) 強い帰納法：すべての $n$ について「$k< n$ を満たすすべての $k$ で $P(k)$ が成り立つならば $P(n)$ が成り立つ」なら、すべての $n$ で $P(n)$ が成り立つ。
(W) 整列性：$\mathbb{N}$ の空でない任意の部分集合は最小元をもつ。
(S) には基底段階が書かれていないが、消えたわけではない。$n=0$ のとき前提「$k<0$ のすべての $k$ で $P(k)$」は、(N2) によりそのような $k$ がないので無条件に真である（空虚な真）。したがって (S) の仮定は、$n=0$ については「$P(0)$ を何も仮定せずに示せ」と言っている。

主定理と証明

3 つの原理の同値性

帰納法・強い帰納法・整列性の同値性

(N1)〜(N4) を認めると、(I)・(S)・(W) は互いに同値である。すなわち、どれか 1 つを仮定すれば残りの 2 つが証明できる。

(I)⇒(S)⇒(W)⇒(I) の順に示す

(I)⇒(S)　$P(n)$ が (S) の仮定「$k< n$ のすべての $k$ で $P(k)$ なら $P(n)$」を満たすとする。新しい主張
$$ Q(n):\ \text{$k< n$ を満たすすべての自然数 $k$ で $P(k)$ が成り立つ} $$
を考え、$Q$ に (I) を使う。$Q(0)$ は (N2) により空虚に真である。$Q(n)$ を仮定すると、(S) の仮定から $P(n)$ が成り立つ。$k< n+1$ とすると (N3) により $k\le n$、つまり $k< n$ か $k=n$ であり、前者なら $Q(n)$ から、後者なら今示したことから $P(k)$ が成り立つ。よって $Q(n+1)$ が成り立つ。(I) によりすべての $n$ で $Q(n)$ が成り立ち、$n< n+1$（(N3) で $k=n$ とする）なので $Q(n+1)$ から $P(n)$ が従う。
(S)⇒(W)　対偶を示す。$S\subset\mathbb{N}$ が最小元をもたないとして $S=\emptyset$ を示す。$P(n)$ を「$n\notin S$」とし、(S) の仮定を確かめる。$k< n$ のすべての $k$ で $k\notin S$ とする。もし $n\in S$ なら、任意の $s\in S$ について $s< n$ ではない（$s< n$ なら $s\notin S$ のはずである）から、三分律により $n\le s$ となり、$n$ は $S$ の最小元になってしまう。よって $n\notin S$ である。(S) によりすべての $n$ で $n\notin S$、すなわち $S=\emptyset$ である。
(W)⇒(I)　$P(0)$ と「$P(n)$ ならば $P(n+1)$」を仮定する。$P(n)$ が成り立たない $n$ の集合 $A$ が空でないとすると、(W) により最小元 $m$ がある。$P(0)$ が成り立つので $m\ne0$ であり、(N4) により $m=m'+1$ と書ける。(N3) により $m'< m$ なので、$m$ の最小性から $m'\notin A$、つまり $P(m')$ が成り立つ。仮定により $P(m'+1)=P(m)$ が成り立ち、$m\in A$ に反する。よって $A=\emptyset$ である。$\square$

この証明で (N1)〜(N4) のどれをどこで使ったかは重要である。(W)⇒(I) だけが (N4)「$0$ 以外はどれも何かの次である」を使う。ex-iwo-omega で見るように、(N4) を満たさない整列集合では、整列性があっても普通の帰納法は成り立たない。
(W) から (S) は、上の順路を通らずに直接示すこともできる。$P(n)$ が成り立たない $n$ があるとし、その最小のもの $m$ をとる。$k< m$ ならば $P(k)$ が成り立つので、(S) の仮定から $P(m)$ が成り立ち、矛盾する。この形の議論を 最小反例による証明 という（Ham18 §10.3、p. 191）。「反例があるなら最小の反例がある。最小の反例より小さいところでは主張が正しいので、それを使って最小の反例でも正しいことを示せば矛盾」という論法であり、強い帰納法を背理法の形に書き直したものである。
どれを「公理」とするかは流儀による。Peano の公理系では (I) を公理とし、集合論では $\mathbb{N}$ を「$0$ を含み $n\mapsto n+1$ で閉じた最小の集合」として作ることで (I) が成り立つようにする。どちらの流儀でも、thm-iwo-equivalence により (S) と (W) が従う。逆に KT17 のように整列性を正の整数の基本性質として先に述べ（Principle 3.1、p. 40）、帰納法の原理（Principle 3.11、p. 49）がそれと同値であると注意する教科書もある。強い帰納法は Ham18 §10.2（p. 187）で扱われている。

無限降下法

整列性は「自然数は無限に下がり続けることはできない」とも言い換えられる。

無限降下の不可能性

自然数の列 $n_0>n_1>n_2>\cdots$ で、無限に続くものは存在しない。同じことだが、自然数の集合 $A$ が「どの $a\in A$ に対しても $a'< a$ となる $a'\in A$ がある」を満たすなら、$A=\emptyset$ である。

最小元をとる

後半を示す。$A\ne\emptyset$ なら (W) により $A$ は最小元 $m$ をもつ。仮定により $m'< m$ となる $m'\in A$ があるが、これは $m$ の最小性（$m\le m'$）と三分律に反する。よって $A=\emptyset$ である。前半は、無限に続く列 $n_0>n_1>\cdots$ があったとして $A:=\{n_0,n_1,n_2,\dots\}$ に後半を使えばよい（$n_i\in A$ に対して $n_{i+1}< n_i$ が $A$ に属する）。$\square$

無限降下法で $x^4+y^4=z^2$ に正の整数解がないことを示す例はピタゴラス数と円の有理点で扱う。
cor-iwo-no-descent を使う証明法を 無限降下法 という。「条件を満たす自然数（あるいは解）があれば、もっと小さいものがある」ことを示して、そもそも存在しないと結論する。無限降下法の典型例に「$x^4+y^4=z^2$ は正の整数解をもたない」ことの証明がある（本記事では証明しない）。

$\sqrt{2}$ の無理数性を無限降下で示す

$\sqrt2$ が有理数だとすると、$A:=\{\,q\ge1\mid \text{ある正の整数 $p$ で } p=\sqrt2\,q\,\}$ は空でない。$q\in A$、$p=\sqrt2\,q$ とする。$1<\sqrt2<2$ なので $q< p<2q$ であり、
$$ p':=2q-p,\qquad q':=p-q $$
はどちらも正の整数で、$q'< q$ である（$p<2q$ から $q'=p-q< q$）。さらに $p=\sqrt2\,q$ を代入すると
$$ \frac{p'}{q'}=\frac{(2-\sqrt2)\,q}{(\sqrt2-1)\,q}=\frac{\sqrt2(\sqrt2-1)}{\sqrt2-1}=\sqrt2 $$
なので $q'\in A$ である。どの $q\in A$ にも $A$ のもっと小さい元があるので、cor-iwo-no-descent により $A=\emptyset$ となり、矛盾する。よって $\sqrt2$ は無理数である。
写像 $(p,q)\mapsto(2q-p,\ p-q)$ を $\sqrt2$ の近似分数に使ってみると、
$$ \frac{99}{70}\ \mapsto\ \frac{41}{29}\ \mapsto\ \frac{17}{12}\ \mapsto\ \frac75\ \mapsto\ \frac32\ \mapsto\ \frac11 $$
と分母が下がっていき、$\frac11$ で $1< p/q<2$ が破れて止まる。ちょうど $\sqrt2$ に等しい分数があれば、この降下は永遠に止まらないはずであり、それが不可能だというのが上の証明である。冒頭の計算 4 の「分母が最小のものを選ぶ」は、同じ議論を (W) で書いたものである。

高校の計算をもう一度見る

始点をずらす　高校の帰納法は $n=1$ から始まる。一般に整数 $m$ から始まる主張 $P(n)$（$n\ge m$）は、$Q(j):=P(m+j)$（$j\in\mathbb{N}$）とおけば $\mathbb{N}$ 上の主張になり、「$P(m)$ かつ（$n\ge m$ で $P(n)\Rightarrow P(n+1)$）」は「$Q(0)$ かつ（$Q(j)\Rightarrow Q(j+1)$）」と同じことである。計算 1・2 はこの形の (I) である。
前のいくつもの段を使う　計算 3 は (S) である。(S) の仮定「$k< n$ のすべてで成り立てば $n$ でも成り立つ」を確かめるとき、$n\ge2$ なら $F_n=F_{n-1}+F_{n-2}$ と仮定から結論が出るが、$n=0,1$ では漸化式が使えないので個別に確かめる。一般に、帰納段階の議論が $s$ 段前までさかのぼるなら、最初の $s$ 個を個別に確かめる必要がある。次の例では $3$ 段さかのぼるので、出発点を $3$ つ確かめる。

3 と 5 で作れる数

$8$ 以上のすべての整数 $n$ は、$0$ 以上の整数 $a,b$ を使って $n=3a+5b$ と書ける。

3 段さかのぼる強い帰納法

$8\le k< n$ のすべての $k$ で主張が正しいと仮定して、$n$ で正しいことを示す（始点を $8$ にずらした (S)）。$n=8,9,10$ なら $8=3+5$、$9=3\cdot3$、$10=5\cdot2$ である。$n\ge11$ なら $8\le n-3< n$ なので、仮定により $n-3=3a+5b$ と書け、$n=3(a+1)+5b$ である。$\square$

$7$ は $3a+5b$ の形に書けない（$b=0$ なら $7$ は $3$ の倍数でなく、$b=1$ なら $2$ は $3$ の倍数でなく、$b\ge2$ なら $5b\ge10>7$ である）ので、始点 $8$ は最良である。出発点を $8$ だけにすると何が起きるかは ex-iwo-few-bases で見る。
主張を強めると帰納法が通る　帰納法は、示したい主張そのままでは帰納段階が通らず、より強い主張にすると通ることがある。

平方の逆数の和の評価

すべての正の整数 $n$ について
$$ \sum_{k=1}^n\frac1{k^2}\le2-\frac1n $$
が成り立つ。特に和はつねに $2$ 未満である。

強めた主張に帰納法を使う

$n=1$ では両辺とも $1$ である。$n$ で成り立つと仮定すると
$$ \sum_{k=1}^{n+1}\frac1{k^2}\le2-\frac1n+\frac1{(n+1)^2}\le2-\frac1n+\frac1{n(n+1)}=2-\frac1n+\Bigl(\frac1n-\frac1{n+1}\Bigr)=2-\frac1{n+1} $$
である（$\frac1{(n+1)^2}\le\frac1{n(n+1)}$ を使った）。$\square$

「和 $<2$」をそのまま $P(n)$ にすると、帰納法の仮定から言えるのは「$n+1$ 項の和 $<2+\frac1{(n+1)^2}$」だけで、$2$ 未満には届かない。主張を「$\le2-\frac1n$」に強めると、仮定も強くなり、足される $\frac1{(n+1)^2}$ を吸収する余裕 $\frac1n-\frac1{n+1}$ が生まれる。(S) の証明で $P(n)$ を「$k< n$ のすべてで $P(k)$」という $Q(n)$ に強めたのも同じ発想であり、強い帰納法は「主張を強める」操作を一般的に行ったものと見ることができる。
最小反例の書き方　高校の答案でよく見る「条件を満たさない $n$ が存在したとし、その最小のものを $m$ とする」は、(W) を直接使った証明である（thm-iwo-equivalence の後の注意）。$m$ より小さいところでは主張が正しいという情報が、帰納法の仮定の役割を果たす。
2 点についての不等式から $n$ 点についての不等式を帰納法で導く例は Jensenの不等式（高校数学）で扱う。

例と反例

帰納法の「誤った証明」は、どこかの段で (I) や (S) の仮定が実は示されていない。以下の反例では、どの段が破綻しているかを特定する。

反例：すべての馬は同じ色である

主張 $P(n)$：「$n$ 頭の馬をどう選んでも、それらはすべて同じ色である」（$n\ge1$）。次の「証明」は誤りである。
基底段階：$1$ 頭の馬はそれ自身と同じ色である。
帰納段階：$P(n)$ を仮定し、$n+1$ 頭の馬 $h_1,\dots,h_{n+1}$ をとる。$h_1,\dots,h_n$ は $n$ 頭なので同じ色、$h_2,\dots,h_{n+1}$ も $n$ 頭なので同じ色である。両方に共通の馬がいるので、全体が同じ色である。
破綻しているのは、帰納段階のうち $n=1$ から $n=2$ への段 である。「両方に共通の馬がいる」には共通部分 $h_2,\dots,h_n$ が空でないこと、すなわち $n\ge2$ が要る。$n=1$ では 2 つの組は $\{h_1\}$ と $\{h_2\}$ で、共通の馬はいない。実際 $P(1)$ は真、$P(2)$ は偽（色の違う 2 頭がいれば反例）なので、含意「$P(1)\Rightarrow P(2)$」そのものが偽である。$n\ge2$ での「$P(n)\Rightarrow P(n+1)$」は上の議論で正しく示されている（$P(2)$ が偽なので、そこから先の含意は空虚に真でもある）。この例は「帰納段階が $n\ge2$ でしか示されていなくても $P(1)$ からすべての $n$ が従う」という主張を破っている。(I) の帰納段階は すべての $n$ で示さなければならない。

反例：出発点が足りない強い帰納法

主張「$3$ 以上のすべての整数 $n$ は $n=3a+5b$（$a,b\ge0$）と書ける」を、prf-iwo-three-five をまねて「$n=3$ は $3=3\cdot1$。$n>3$ なら $n-3$ に仮定を使って $3$ を足す」と「証明」したとする。主張は偽である（$4$ は書けない）。
破綻しているのは $n=4$ と $n=5$ の段 である。(S) の仮定「$3\le k< n$ のすべての $k$ で成り立てば $n$ で成り立つ」を $n=4$ で確かめるには $n-3=1$ に仮定を使う必要があるが、$1$ は範囲 $3\le k$ の外なので仮定は使えない。実際 $P(3)$ は真で $P(4)$ は偽なので、$n=4$ での (S) の仮定は偽である。帰納段階が $3$ 段さかのぼる以上、出発点は $3$ つ（$n=3,4,5$）確かめなければならず、そこで $4$ が書けないことが見つかる。

反例：基底段階がない

主張「すべての自然数 $n$ について $n=n+1$」は、両辺に $1$ を足せば $n+1=n+2$ となるので「$P(n)\Rightarrow P(n+1)$」はすべての $n$ で正しい。しかし $P(0)$ は偽であり、主張はどの $n$ でも偽である。この例は「帰納段階だけからすべての $n$ で主張が従う」を破っており、欠けているのは基底段階 $P(0)$ である。

反例：整列していない集合では帰納法も最小反例も使えない

$0$ 以上の有理数全体 $\mathbb{Q}_{\ge0}$ で、$P(x)$ を「$x$ は整数である」とする。$P(0)$ は真で、$P(x)$ なら $P(x+1)$ も真である。しかし $P(\frac12)$ は偽である。$\mathbb{Q}_{\ge0}$ は (N1)・(N2) を満たすが、(N3)（$0<\frac12<1$ なので $n=0$、$k=\frac12$ で破れる）と (N4)（$\frac12$ は $0$ 以上の有理数の「次」ではない）を満たさず、$0$ から $1$ ずつ進んでも届かない元がある。
最小反例の論法も使えない。「すべての正の有理数 $x$ について $x\ge1$」は偽だが、反例全体 $\{x\mid0< x<1\}$ には最小元がないので、「最小の反例 $m$ をとって矛盾を導く」ことは始めからできない。この例は「(N1)・(N2) を満たす全順序集合なら (I) や (W) が成り立つ」という主張を破っている。

反例：整列していても普通の帰納法が成り立たない

$\mathbb{N}$ に新しい元 $\omega$ を 1 つ加え、$X:=\mathbb{N}\cup\{\omega\}$ に、自然数どうしは通常の大小、どの自然数 $n$ についても $n<\omega$ となる順序を入れる。$X$ は整列している。実際、空でない $S\subset X$ について、$S\cap\mathbb{N}\ne\emptyset$ なら $\mathbb{N}$ の整列性によりその最小元が $S$ の最小元であり、そうでなければ $S=\{\omega\}$ で $\omega$ が最小元である。
$X$ 上の主張 $P(x)$ を「$x$ は自然数である」とする。$P(0)$ は真であり、$P(x)$ が真なら $x+1$ も自然数なので、「$P(x)\Rightarrow P(x+1)$」は（$x+1$ が定義される自然数 $x$ について）真である。しかし $P(\omega)$ は偽である。$\omega$ はどの元の「次」でもなく、$X$ は (N4) を満たさない。したがって $X$ では (W) が成り立つのに (I) が成り立たず、thm-iwo-equivalence の (W)⇒(I) に (N4) が欠かせないことが分かる。
一方、$X$ でも強い帰納法 (S) は成り立つ（thm-iwo-equivalence の後の注意の「(W) から (S) を直接示す」議論は (N4) を使わない）。$\omega$ で主張を示すには「すべての自然数で成り立つ」ことを仮定してよいが、「直前の元」は存在しない。この「直前のない元」を扱う段が、次の「さらに先へ」の節の超限帰納法で現れる極限の段である。

数学オリンピックの問題から

最小の解をとる（国際数学オリンピック（1988 年）第 6 問）

問題（第 29 回国際数学オリンピック（1988 年）第 6 問の和訳）　正の整数 $a,b$ について、$ab+1$ が $a^2+b^2$ を割り切るとする。このとき $\dfrac{a^2+b^2}{ab+1}$ は整数の平方であることを示せ。
たとえば $(a,b)=(2,8)$ では $\frac{4+64}{17}=4=2^2$、$(3,27)$ では $\frac{9+729}{82}=9=3^2$ である。
高校数学で解く　$k:=\frac{a^2+b^2}{ab+1}$ は正の整数である。$k$ が平方数でないと仮定して矛盾を導く。整数の組 $(x,y)$ で
$$ x\ge y\ge0,\qquad x^2+y^2=k(xy+1) $$
を満たすもの全体を考える。$a,b$ の大きいほうと小さいほうの組がこれを満たすので、この集合は空でない。そこで $x+y$ が最小になる組 $(x,y)$ を 1 つとる（和 $x+y$ のとる値の集合に (W) を使う）。
$y=0$ なら $x^2=k$ となり、$k$ が平方数でないことに反する。よって $y\ge1$ である。$x$ は $t$ の 2 次方程式
$$ t^2-ky\,t+(y^2-k)=0 $$
の解であり、解と係数の関係から、もう 1 つの解は $x'=ky-x=\dfrac{y^2-k}x$ である。前の式から $x'$ は整数である。

$x'<0$ とすると、$x'\le-1$、$y\ge1$ から $-ky\,x'\ge k$ なので、$x'^2-ky\,x'+y^2-k\ge x'^2+y^2>0$ となり、$x'$ が解であることに反する。
$x'=0$ とすると $y^2=k$ となり、$k$ が平方数でないことに反する。
よって $x'>0$ であり、$x'=\dfrac{y^2-k}x<\dfrac{y^2}x\le y$ である。すると $(y,x')$ も条件を満たす組で（$y>x'\ge1$、方程式は $x$ と $y$ について対称）、和は $y+x'< y+x$ となり、$x+y$ の最小性に反する。
いずれの場合も矛盾するので、$k$ は平方数である。

大学数学で見ると　上の解法は、解の集合の上の写像
$$ (x,y)\ \longmapsto\ (y,\ ky-x)\qquad(x\ge y\ge1) $$
（大きいほうの座標を 2 次方程式のもう 1 つの解に取り替える写像。「Vieta jumping」と呼ばれる）が和 $x+y$ を真に減らすことを示している。$x=y$ の組も定義域に含めておく。上の解法の 3 つめの場合と同じく、$x=y$ でも $0\le ky-x=\frac{y^2-k}x< y$ となるからである（たとえば $k=1$ の解 $(1,1)$ は $(1,0)$ に移る）。cor-iwo-no-descent により、この降下は有限回で止まる。止まるのは $y=0$ の組に達したときだけであり、そこでは $x^2=k$ である。つまり証明の実体は「降下は必ず止まり、止まる場所は $(c,0)$（$k=c^2$）だけ」という無限降下法である。
降下の各段は逆にたどれる（$(y,x')$ から $x=ky-x'$ が復元できる）。したがって $k=c^2$ のときの解は、$(c,0)$ から逆向きの操作 $(x,y)\mapsto(kx-y,\ x)$ をくり返して得られるものに限られる。$c\ge2$ のとき、数列 $x_0=0$、$x_1=c$、$x_{j+1}=c^2x_j-x_{j-1}$ を作ると（$x_{j+1}\ge4x_j-x_j>x_j$ なので狭義に増える）、$x>y\ge1$ の解はちょうど隣り合う 2 項の組 $(x_{j+1},x_j)$（$j\ge1$）である（$c=1$ では $x=y=1$ の解だけになる）。$c=2$ では $0,2,8,30,112,418,\dots$ となり、$(8,2)$、$(30,8)$、$(112,30)$ などが $k=4$ の解である。$x^2-kxy+y^2=k$ の整数解の集合に 2 つの取り替え $(x,y)\mapsto(ky-x,y)$、$(x,y)\mapsto(x,kx-y)$ が作用し、各軌道に「最小の代表」があるという構造は、2 元 2 次形式の簡約理論や Markov 方程式 $x^2+y^2+z^2=3xyz$ の解の木と同じ形をしている。

さらに先へ

超限帰納法　thm-iwo-equivalence の後の注意で見たとおり、「(W) から (S)」の議論は (N1) と整列性しか使わない。したがって次が成り立つ。

整列集合上の帰納法

$(X,<)$ を整列集合とし、$x\in X$ ごとに主張 $P(x)$ があるとする。すべての $x\in X$ について「$y< x$ を満たすすべての $y$ で $P(y)$ が成り立つならば $P(x)$ が成り立つ」なら、すべての $x\in X$ で $P(x)$ が成り立つ。

最小反例をとる

$P(x)$ が成り立たない $x$ の集合 $A$ が空でないとすると、整列性により最小元 $m$ がある。$y< m$ なら $y\notin A$ なので $P(y)$ が成り立ち、仮定から $P(m)$ が成り立つ。これは $m\in A$ に反する。$\square$

これを 超限帰納法 という。整列集合を並べた「長さ」を表すのが順序数であり、$0,1,2,\dots$ の先に $\omega$（ex-iwo-omega の $\omega$）、$\omega+1,\omega+2,\dots,\omega\cdot2,\dots$ と続く。順序数の上の超限帰納法は、実際には次の 3 つの場合に分けて使われることが多い。

$P(0)$ を示す。
$P(\alpha)$ から $P(\alpha+1)$ を示す（後続の段）。
$\alpha$ が $0$ でも何かの次でもない順序数（$\omega$ のような 極限順序数）のとき、$\beta<\alpha$ のすべてで $P(\beta)$ が成り立つことから $P(\alpha)$ を示す（極限の段）。
3 の段が、(N4) の成り立たない整列集合で普通の帰納法を補うものである。順序数の定義と、この 3 つの場合分けが thm-iwo-transfinite と同値であることは、本記事では証明しない。

整列可能定理　どんな集合にも整列順序を入れられる、という主張を整列可能定理という。Zermelo が 1904 年に選択公理を用いて証明し（Zer04）、集合論の他の公理のもとでは選択公理と同値であることが知られている。本記事では証明しない。実数全体 $\mathbb{R}$ にも整列順序が存在するが、具体的に書き下すことはできない（そのような順序の存在は選択公理なしには証明できない）。
整列集合の特徴づけ　cor-iwo-no-descent は任意の整列集合で同じ証明で成り立つ。逆に「無限に下がり続ける列がない全順序集合は整列している」も正しいが、一般の集合で証明するには、列を 1 項ずつ選んでいく議論（従属選択公理と呼ばれる弱い選択公理）が要る。本記事では証明しない。
整礎帰納法と停止性　全順序でなくても、「空でない部分集合に極小元がある」関係（整礎関係）の上では同じ形の帰納法が成り立つ。たとえば $\mathbb{N}\times\mathbb{N}$ に辞書式順序（$(a,b)<(a',b')$ を「$a< a'$、または $a=a'$ かつ $b< b'$」と定める）を入れると整列集合になり、「実行するたびにこの順序で値が下がる手続きは必ず止まる」ことが cor-iwo-no-descent と同じ議論で示せる。計算機科学では、これがプログラムの停止性の証明の基本的な道具である。
帰納法でも届かない主張　Goodstein の定理は、自然数の列についての具体的な主張であり、順序数 $\varepsilon_0$ までの超限帰納法を使うと証明できるが、Peano の公理系の中の帰納法では証明できない（後者は Kirby と Paris による、KP82）。本記事では証明しない。