수학적 귀납법 기반
편의상 $\{ 1, 2, \cdots , n \}$ 라는 표기는 $1$ 이상 $n$ 이하의 모든 자연수들의 집합으로 표기한다.
먼저, 다음과 같은 보조정리가 성립한다.

보조정리 1
$n \in \mathbb{N}$인 $n$에 대해 $\{ 1, 2, \cdots , n \}$ 의 공집합이 아닌 부분집합이 항상 최소 원소를 가진다.

보조정리 증명

$\{ 1 \}$ 의 공집합이 아닌 부분집합은 $\{ 1 \}$ 밖에 없으므로 당연히 최소 원소 $1$을 가진다.
$\{ 1, 2, \cdots , n \}$ 의 공집합이 아닌 부분집합이 최소 원소를 가진다고 가정한다.
$\{ 1, 2, \cdots , n + 1 \}$의 공집합이 아닌 부분집합 $S$에 대하여, $S$가 $n + 1$을 포함하지 않으면 $S$는 $\{ 1, 2, \cdots , n \}$ 의 부분집합이기도 하므로, $S$의 최소 원소가 존재한다.
$S$가 $n + 1$만 원소를 가진다면, $S$의 최소 원소는 $n + 1$이다.
이제 $S$가 $n + 1$도 원소를 가지면서 $n + 1$만을 원소로 가지지는 않는 (즉, $S$의 크기 $\mid S \mid$ 가 $2$ 이상) 경우만 따지면 된다.
$T = S \cap \{ 1, 2, \cdots , n \}$, 즉, $T$를 $S$와 $\{ 1, 2, \cdots , n \}$의 교집합이라 하면, $T$는 $\{ 1, 2, \cdots , n \}$ 의 공집합이 아닌 부분집합이다.

$T$의 성질 증명

$S$가 $n + 1$도 원소를 가지면서 $n + 1$만을 원소로 가지지는 않는 경우이므로, $S$는 $1 \leq s \leq n$인 어떤 원소 $s$를 가지고 있다. (그렇지 않다면 원소는 $n + 1$뿐이다.)
동시에 $\{ 1, 2, \cdots , n \}$은 $n + 1$을 원소로 가지지 않으므로, $S$와 $\{ 1, 2, \cdots , n \}$의 교집합인 $T$는 $n + 1$을 원소로 가지지 않는다.
$T$가 $n + 1$을 원소로 가지지 않고, $1 \leq s \leq n$인 어떤 원소 $s$를 가지고 있으므로 $T$는 $\{ 1, 2, \cdots , n \}$ 의 공집합이 아닌 부분집합이라 할 수 있다.

따라서 $T$에는 최소 원소 $t$가 존재한다. ($\{ 1, 2, \cdots , n \}$ 의 공집합이 아닌 부분집합이 최소 원소를 가진다고 가정했으므로)
$S$의 원소 중 $\{ 1, 2, \cdots , n \}$ 에 속하지 않는 것은 $n + 1$뿐이고, $T$가 $\{ 1, 2, \cdots , n \}$ 의 공집합이 아닌 부분 집합이므로 $1 \leq t \leq n$이다. 따라서 $t < n + 1$이다.
$S$의 원소 중 $\{ 1, 2, \cdots , n \}$ 에 속하는 $s$에 대하여, $s \in T$이므로 $t \leq s$이다. ($t > s$ 라면 $s$가 $T$의 원소인데 $T$의 최소 원소 $t$보다 작은 값이 $T$에 있다는 것은 모순)
따라서, $S$에는 최소 원소 $t$가 존재하게 되고, $\{ 1, 2, \cdots , n \}$ 의 공집합이 아닌 부분집합이 최소 원소를 가진다고 가정했을 때 $\{ 1, 2, \cdots , n + 1 \}$ 의 공집합이 아닌 부분집합이 최소 원소를 가지므로, 수학적 귀납법 에 따라 모든 $n \in \mathbb{N}$ 에 대해 $\{ 1, 2, \cdots , n + 1 \}$ 의 공집합이 아닌 부분집합이 최소 원소를 가진다.