정렬순서원리(Well-ordering principle)은 다음과 같이 서술되는 공리이다.
Axiom — N {\displaystyle \mathbb {N} } 의 공집합이 아닌 임의의 부분집합은 최소원을 가진다.
즉, 정렬순서원리는 양의 정수들의 집합이 정렬집합이라고 선언한다.
정렬순서원리에서 수학적 귀납법을 이끌어낼 수 있다.
정리 1. 집합 E ⊂ N {\displaystyle E\subset \mathbb {N} } 이 조건
을 만족하면 E = N {\displaystyle E=\mathbb {N} } 이다.
N {\displaystyle \mathbb {N} } 에 포함되지 않은 E {\displaystyle E} 의 원소가 있다고 가정하자. 그러면 N ∖ E ≠ ∅ {\displaystyle \mathbb {N} \setminus E\neq \emptyset } 이다. 정렬순서원리에 의해 N ∖ E {\displaystyle \mathbb {N} \setminus E} 는 최소원 m {\displaystyle m} 을 가진다. m ≠ 1 {\displaystyle m\neq 1} 이므로 m > 1 {\displaystyle m>1} 이며, 따라서 m − 1 ∈ N {\displaystyle m-1\in \mathbb {N} } 이다. m {\displaystyle m} 이 N ∖ E {\displaystyle \mathbb {N} \setminus E} 의 최소원이므로 m − 1 ∉ N ∖ E {\displaystyle m-1\notin \mathbb {N} \setminus E} , 즉 m − 1 ∈ E {\displaystyle m-1\in E} 이다. 그러면 m ∈ E {\displaystyle m\in E} 가 되어 모순이 발생한다.