最小自然数原理

最小自然数原理是指自然数集的任意非空子集必有最小元, 换言之, 自然数连同其通常序构成良序集.

在初等数论中, 最小自然数原理是无穷递降法的理论基础: 自然数上的方程解集是自然数的子集, 因此方程如有解则有最小解. 如果通过方程的每一组解都能构造出比它更小的解, 则可以证明方程无解.

1陈述与证明

定理 1.1 (最小自然数原理). 每个自然数集的非空子集 $X\subseteq \mathbb{N}$ 有最小元.

证明. 由序数构成的集合在属于关系下必有最小元, 而 $\mathbb{N}$ 中的元素均是序数.

$\square$

推论

第二数学归纳法可以由最小自然数原理推出.

定理 1.2 (第二数学归纳法). 设 $P(n)$ 是关于自然数 $n$ 的命题. 假设

•	$P(0)$ 成立.

•	若对任意 $n<m$ 有 $P(n)$ 成立, 则 $P(m)$ 成立.

那么对任意 $n\in \mathbb{N}$, 有 $P(n)$ 成立.

证明. 反设 $\{n\in \mathbb{N}\mid \neg P(n)\}\ne \varnothing$, 则存在最小元 $m\in \mathbb{N}$ 使得 $P(m)$ 不成立, 但是对任意 $n<m$, 有 $P(n)$ 成立, 与假设矛盾! 因此 $\{n\in \mathbb{N}\mid \neg P(n)\}=\varnothing$.

$\square$

由证明可以看出, 此结论对任何良序集都对, 这即是超限归纳法.

2相关概念

•	数学归纳法
•	无穷递降法