用反证法证明（最小数原理）正整数集 N* 的非空子集必有最小数

756199795

（最小数原理）正整数集N*的非空子集必有最小数，即N＊的非空子集S，存在a∈S，对任意c∈S，使得a≤c。

证：用反证法，假设存在N＊的一个子集M没有最小数，全体小于这个集合任何元素的正整数集N’，因为M没有最小数，知1∉M，所以1∈N＇。
对于m∈N＇，现在证明m＋∈N＇，事实上，假设m＋∉N＇，则在M中有a1，使m＋≥a1，又由M中没有最小数，知有a2∈M，使a1＞a2，这就有a2≤m，此与m∈M矛盾，于是m＋∈M，因此，N＇＝N＊（归纳公理）。
由M非空，知有正整数t∈M，又因为t∈N＇，于是t＜t，这不可能，最小数原理得证。

elim

设\(E\subset \mathbb{N}^*\) 没有最小元，\(U=\mathbb{N}^*-E\), 则\(1\not\in E\),所以\(\,1\in U\).
假定\(1,\ldots,k\in U,\)，因为比\(\,k+1\,\)小的正整数都不在\(\,E\,\)中，\(\,E\,\)没有
最小元，所以\(\,k+1\not\in E\) 即\(\,k+1\in U\). 据归纳原理，\(U=\mathbb{N}^*\).
可见没有最小元的正整数子集必是空集．非空正整数子集必有最小元．