[Number Theory] Well-Ordering Principle

이 증명은 다른 증명을 위해서 많이 쓰이는 증명이기에 짚고 넘어간다.

 

Well-Ordering Principle(정렬 정리)

$ \forall S ( \subsetneq ℕ) \neq ∅ , ∃ min S $

𝑝𝑓) S가 최소원을 갖지 않는다고 하자. P(n) ≔ ∀ S ⊂ ℕ, n ∈ S ⇒ ∃ min S
n=1 일때 1을 원소로 가지는 S 에 대해 S는 ℕ 의 부분집합이므로 1보다 작은 원소를 가지지 않는다. 따라서 S는 최소원 1을 가지기 때문에 S가 1을 원소로 가질 때 S는 최소원을 가져야 할 것이다.
n=1, 2, 3, ..., k 일때 k를 원소로 가지는 S 에 대해 min S 가 존재함을 가정하고,
n=k+1 인 경우에서 S의 최소원이 존재함을 보이자. S가 1, ..., k을 가진다면 P(1), P(2), ..., P(k)이 성립한다고 가정했으므로 가정에 모순이다. 따라서 S가 k+1 이상의 원소를 가져야 할 터이다. 이때 k+1이 최소원이 되어야 하지만 k+1 ∈ S이므로 가정에 모순이다. 따라서 P(k)가 성립하면 P(k+1)도 성립해야 한다.
Mathematical Induction에 의해 모든 자연수 n에 대해 P(n) ≔ ∀ S ⊂ ℕ, n ∈ S ⇒ ∃ min S 이다.