first principle of finite induction

몇몇 양의 정수의 모임 S가 다음과 같은 성질을 지닌다고 가정하자.

1이 S에 속한다.
정수 k가 S에 속할 때 정수 k+1도 S에 속한다.

그렇다면 S는 모든 양의 정수의 집합이다.

증명)
A를 양의 정수 집합에서 S를 뺀 집합이라고 하자.
그리고 A가 그럼에도 불구하고 공집합이 아니라고 가정하자.
그렇다면 A는 양의 정수의 집합이다.
그렇다면 A는 최솟값을 지닌다.
그 최솟값을 m이라 하자.
그렇다면 m-1은 S에 속할 것이다.
그렇다면 m-1 +1은 S에 속할 것이다.
m - 1 + 1 = m이다.
그렇다면 m은 S에도 속하고 A에도 속한다
그런데 A와 S는 공유하는 원소가 없다.

m이 S에 속하고 A에도 속하지만 A와 S는 공유하는 원소가 없다.
따라서 모순이다.
따라서 양의 정수 집합에서 S를 뺀 집합은 무조건 공집합이 되어야 한다.
따라서 S는 양의 정수의 집합이다.