PART I — 증명
자연수의 가장 평범해 보이는 성질 하나, "공집합이 아닌 자연수의 부분집합엔 반드시 가장 작은 원소가 있다"는 사실이 사실은 강력한 증명 도구가 됩니다. 이 원리를 정렬 원리(Well Ordering Principle, WOP)라고 부르고, 이번 장에서는 이걸로 \( \sqrt{2} \)가 무리수임을 보이고, 모든 자연수가 소수의 곱이라는 사실까지 증명해 봅니다. 미리 귀띔하자면, 정렬 원리는 5장에서 배울 수학적 귀납법과 사실상 동치(서로를 증명할 수 있는 관계)입니다. 같은 도구를 다른 모자를 쓰고 만나는 셈이에요.
먼저 원리부터 정확히 적어 봅시다. 자연수 집합을 \( \mathbb{N} = \{0, 1, 2, 3, \ldots\} \)로 쓰겠습니다. (0을 자연수에 포함시키느냐 마느냐는 책마다 다르지만, 이 노트에서는 0을 포함합니다. 한국 교과서 관습과 다를 수 있으니 헷갈리면 \( \mathbb{N} \)을 "음수가 아닌 정수"라고 읽어 주세요.)
정의 2.1.1 (정렬 원리, Well Ordering Principle)
\( \mathbb{N} \)의 공집합이 아닌 모든 부분집합 \( S \subseteq \mathbb{N} \)은 최소 원소(minimum element)를 갖는다. 즉, 어떤 \( m \in S \)가 존재해서 모든 \( n \in S \)에 대해 \( m \le n \)이다.
너무 당연해 보이죠? 자연수 몇 개를 한 줌 집어 놓고 보면 그중 가장 작은 게 있을 수밖에 없잖아요. 그런데 이 "당연함"이 증명에 동원되면 의외로 강력합니다. 핵심 트릭은 이렇습니다. 어떤 명제가 모든 자연수에서 성립한다고 주장하고 싶을 때, 우리는 반례들의 집합을 잡습니다. 그 반례 집합이 비어 있지 않다고 가정하면, 정렬 원리에 의해 가장 작은 반례가 존재합니다. 그런데 그 "가장 작은 반례"의 성질을 자세히 들여다보면 보통 모순이 튀어나와요. 그러면 반례 집합은 처음부터 공집합이었다는 결론에 도달하고, 명제는 참이 됩니다.
노트 — 다이아몬드 광부의 비유
최소 반례를 잡는 전략은 마치 다이아몬드 광맥에서 "여기 진짜 다이아가 있다면, 가장 작은 다이아가 어딘가에 박혀 있을 거야"하고 캐 들어가는 것과 비슷합니다. 그런데 "가장 작은 다이아"라고 잡은 그 돌을 깨 보면 그 안에 더 작은 다이아가 들어 있어요. 그러면 우리가 "가장 작다"고 한 가정이 틀린 거고, 결국 처음부터 다이아 같은 건 없었다는 결론이 납니다. 좀 짓궂은 광부죠.
이 전략을 가장 고전적인 결과 하나로 시연해 봅시다. 그리스 수학자들이 발견했을 때 충격을 받았다는 그 사실, 바로 \( \sqrt{2} \)가 유리수가 아니라는 정리입니다.
정리 2.1.2 (\( \sqrt{2} \)의 무리수성)
\( \sqrt{2} \)는 유리수가 아니다. 즉, 어떤 자연수 \( a, b \)에 대해서도 \( \sqrt{2} = a/b \)가 성립하지 않는다.
증명 (정렬 원리 사용)
모순을 위해 \( \sqrt{2} \)가 유리수라고 가정합시다. 그러면 어떤 양의 자연수 \( a, b \)가 있어서 \( \sqrt{2} = a/b \)입니다. 이제 다음 집합을 정의합니다.
\[ C = \{\, n \in \mathbb{N} \;:\; n > 0 \text{ 이고 } n\sqrt{2} \text{가 자연수}\,\}. \]
가정에 의해 \( b\sqrt{2} = a \in \mathbb{N} \)이고 \( b > 0 \)이므로 \( b \in C \)입니다. 따라서 \( C \)는 공집합이 아닙니다. 정렬 원리에 의해 \( C \)에는 최소 원소가 존재하는데, 그것을 \( n_0 \)라 부릅시다.
이제 새로운 수 \( n_1 = n_0\sqrt{2} - n_0 = n_0(\sqrt{2} - 1) \)을 생각해 봅시다. 이 수는 두 자연수의 차 (\( n_0 \sqrt{2} \in \mathbb{N} \)이고 \( n_0 \in \mathbb{N} \)) 이므로 정수입니다. 그리고 \( 1 < \sqrt{2} < 2 \)이므로 \( 0 < \sqrt{2} - 1 < 1 \), 따라서 \( 0 < n_1 < n_0 \). 자연수네요.
그런데
\[ n_1 \sqrt{2} = n_0(\sqrt{2} - 1)\sqrt{2} = n_0(2 - \sqrt{2}) = 2n_0 - n_0\sqrt{2}. \]
\( 2n_0 \)도 자연수, \( n_0 \sqrt{2} \)도 자연수이므로 \( n_1 \sqrt{2} \)도 자연수입니다. 그러면 \( n_1 \in C \)이고 \( n_1 < n_0 \). 이는 \( n_0 \)가 \( C \)의 최소 원소라는 사실에 모순입니다. 따라서 \( \sqrt{2} \)는 유리수일 수 없습니다.
∎
흔히 알려진 증명("\( a, b \)를 서로소로 잡으면 둘 다 짝수가 되어 모순")과는 사뭇 다른 분위기죠? 사실 두 증명은 정신은 같습니다. 둘 다 "유리수 표현이 있다면 더 단순한 표현이 또 있다"는 무한강하법(infinite descent)의 변주예요. 정렬 원리 버전은 그 무한 내려가기를 "가장 작은 반례"라는 한 번의 모순으로 깔끔하게 묶어 줍니다.
노트 — \( \mathbb{N} \) 안에서만 통한다
정렬 원리는 \( \mathbb{N} \)의 부분집합에 대해서만 보장됩니다. 정수 집합 \( \mathbb{Z} \)에는 \( \{\ldots, -3, -2, -1\} \)처럼 최소 원소가 없는 부분집합이 잔뜩 있고, 실수 \( \mathbb{R} \)에서는 열린 구간 \( (0, 1) \)이 비어 있지 않으면서도 최소 원소가 없죠. 그래서 정렬 원리를 쓰는 증명은 항상 "자연수 안에서만 비교한다"는 점을 분명히 해야 합니다.
앞 절의 증명을 들여다보면, 정렬 원리를 쓰는 증명은 거의 같은 골격을 따릅니다. 이걸 한 번 정리해 두면, 비슷한 문제를 만났을 때 빈칸 채우기 게임처럼 풀 수 있어요.
WOP 증명 템플릿
"모든 자연수 \( n \)에 대해 명제 \( P(n) \)이 참이다"를 보이고 싶을 때:
1. 반례 집합 정의: \( C = \{\, n \in \mathbb{N} : P(n)\text{이 거짓}\,\} \)으로 둔다.
2. 목표 선언: \( C = \emptyset \)임을 보이는 것이 목표이다.
3. 모순을 위한 가정: \( C \neq \emptyset \)이라고 가정한다.
4. 최소 원소 호출: 정렬 원리에 의해 \( C \)에는 최소 원소 \( n_0 \)가 존재한다.
5. 모순 도출: \( n_0 \)의 성질을 분석해서, 더 작은 반례 \( n_1 \in C \)를 만들거나, \( n_0 \) 자체가 \( P(n_0) \)을 만족함을 보여 모순을 이끈다.
6. 결론: 따라서 \( C = \emptyset \), 즉 모든 \( n \)에 대해 \( P(n) \)이 참이다.
여기서 가장 까다로운 단계는 5번이에요. "더 작은 반례를 어떻게 만드느냐"는 명제마다 다르고, 그게 사실상 증명의 본체입니다. \( \sqrt{2} \) 증명에서는 \( n_1 = n_0(\sqrt{2} - 1) \)이라는 영리한 한 수를 둬서 \( n_1 \)이 \( n_0 \)보다 작은데도 여전히 \( C \)에 속하게 만들었죠.
한 가지만 더. 모순을 이끄는 방법은 두 가지 결이 있습니다.
실전에서는 둘 중 어느 쪽이든 자연스러운 쪽으로 가면 됩니다. 다음 절에서 보여줄 소인수분해 증명은 하강의 변형으로 풀어 보겠습니다.
예제 2.2.1 — 작은 워밍업
"모든 자연수 \( n \)에 대해 \( n^2 \ge n \)이다"를 정렬 원리로 보여 봅시다. 반례 집합 \( C = \{n \in \mathbb{N} : n^2 < n\} \). 가정상 \( C \neq \emptyset \)이면 최소 원소 \( n_0 \)가 있고, \( n_0^2 < n_0 \)입니다. \( n_0 = 0 \)이면 \( 0 < 0 \)이라는 모순. \( n_0 \ge 1 \)이면 양변을 \( n_0 \)로 나눠 \( n_0 < 1 \), 즉 \( n_0 = 0 \)이라는 모순. 어느 쪽이든 막힙니다. 따라서 \( C = \emptyset \). 이 정도는 그냥 \( n(n-1) \ge 0 \)으로도 풀리지만, 템플릿에 익숙해지는 연습으로는 좋습니다.
이번엔 좀 더 묵직한 결과로 가 봅시다. 학교에서부터 익숙한 사실 — "모든 1보다 큰 자연수는 소수들의 곱으로 쓸 수 있다" — 을 정렬 원리로 정확하게 증명해 보겠습니다. 정확한 진술은 이렇습니다.
정의 2.3.1 (소수)
\( p \in \mathbb{N} \)이 소수(prime)라는 것은, \( p \ge 2 \)이면서 \( p \)의 양의 약수가 \( 1 \)과 \( p \)뿐인 경우를 말한다. 그렇지 않은 \( n \ge 2 \)는 합성수(composite)라고 한다.
정리 2.3.2 (소인수분해의 존재성)
모든 자연수 \( n \ge 2 \)에 대해, \( n \)을 소수들의 곱으로 표현할 수 있다. 즉, 어떤 소수들 \( p_1, p_2, \ldots, p_k \) (반드시 서로 다를 필요는 없음)가 존재해서 \( n = p_1 p_2 \cdots p_k \)이다. (한 개짜리 곱, 즉 \( n \)이 그 자체로 소수인 경우 \( k = 1 \)도 허용한다.)
증명 (정렬 원리)
반례 집합을 다음처럼 잡습니다.
\[ C = \{\, n \in \mathbb{N} : n \ge 2 \text{ 이고 } n\text{을 소수의 곱으로 쓸 수 없다}\,\}. \]
주장은 \( C = \emptyset \)입니다. 모순을 위해 \( C \neq \emptyset \)이라 가정하고, 정렬 원리에 의해 최소 원소 \( n_0 \in C \)를 잡습니다.
\( n_0 \)는 두 가지 가능성을 가집니다.
경우 1: \( n_0 \)가 소수. 그러면 \( n_0 = n_0 \) 자체가 소수 한 개의 곱이고, 이는 정의 2.3.1에 따라 정리 2.3.2의 표현에 해당합니다. 즉 \( n_0 \notin C \). 가정에 모순.
경우 2: \( n_0 \)가 합성수. 그러면 \( n_0 = a \cdot b \)인 자연수 \( a, b \)가 존재하고, \( 1 < a, b < n_0 \)입니다. 두 인수 모두 \( 2 \) 이상이고 \( n_0 \) 미만이죠. 그런데 \( n_0 \)는 \( C \)의 최소 원소입니다. 즉 \( a, b < n_0 \)인 \( 2 \) 이상의 자연수는 모두 \( C \)에 속하지 않습니다. 그러므로 \( a, b \) 각각은 소수의 곱으로 표현됩니다.
\[ a = p_1 p_2 \cdots p_r, \qquad b = q_1 q_2 \cdots q_s. \]
그렇다면 두 표현을 그대로 이어 붙이면
\[ n_0 = a \cdot b = p_1 p_2 \cdots p_r \, q_1 q_2 \cdots q_s, \]
역시 소수들의 곱입니다. 그러면 \( n_0 \notin C \). 가정에 모순.
두 경우 모두 모순이므로 처음의 \( C \neq \emptyset \) 가정이 틀렸고, \( C = \emptyset \)입니다. 따라서 \( 2 \) 이상의 모든 자연수는 소수들의 곱으로 표현됩니다.
∎
노트 — "유일성"은 또 다른 이야기
이 정리는 소인수분해의 존재성만 보장합니다. \( 12 = 2 \cdot 2 \cdot 3 \) 같은 표현이 본질적으로 유일하다는 사실(산술의 기본 정리, fundamental theorem of arithmetic)은 별도의 증명이 필요해요. 그건 보통 약수 보조정리(\( p \mid ab \implies p \mid a \) 또는 \( p \mid b \))를 거쳐 증명하고, 이 노트의 뒤쪽 정수론 장에서 다룰 예정입니다. 즉 지금은 "소수 부품으로 분해할 수 있다"까지만 안전하게 챙겨 두는 거예요.
잠깐 컴퓨터과학 사이드로 빠지자면, 이 증명은 사실상 재귀적 분해 알고리즘의 정당성을 그대로 보여줍니다. 어떤 \( n \)이 들어왔을 때 (1) 소수면 그대로 반환, (2) 합성수면 \( n = ab \)인 \( a, b \)를 찾아 각각 재귀적으로 분해, 처럼 짠 함수가 항상 종료한다는 것 — 이게 정렬 원리가 보장해 주는 것이에요. 매번 더 작은 자연수에서 호출되니까, 무한히 내려갈 수가 없는 거죠. 5장의 강한 귀납법(strong induction)도 같은 사실을 다른 각도에서 말합니다.
예제 2.3.3 — 손으로 한 번
\( 84 \)를 분해해 봅시다. \( 84 = 2 \cdot 42 \). \( 42 = 2 \cdot 21 \). \( 21 = 3 \cdot 7 \). 이어 붙이면 \( 84 = 2 \cdot 2 \cdot 3 \cdot 7 \). 위 증명의 "두 인수 각각을 재귀적으로 분해해서 이어 붙인다"가 그대로 작동하는 모습입니다.
정렬 원리는 \( \mathbb{N} \)의 특별한 성질이지만, 같은 아이디어를 다른 순서집합에도 일반화할 수 있습니다. 일반화된 개념의 이름은 정렬집합(well ordered set)이에요.
정의 2.4.1 (정렬집합)
전순서(total order) \( \le \)가 부여된 집합 \( (S, \le) \)이 정렬집합이라는 것은, \( S \)의 공집합이 아닌 모든 부분집합에 \( \le \) 기준 최소 원소가 존재한다는 의미이다.
"전순서"라는 단서는, 임의의 두 원소 \( x, y \in S \)에 대해 항상 \( x \le y \)이거나 \( y \le x \)가 성립한다는 뜻입니다. (둘 다 성립하면 \( x = y \).) 이게 보장돼야 "최소"라는 말이 의미를 가지죠.
몇 가지 예를 봅시다.
예제 2.4.2 — 정렬집합 / 정렬 아닌 집합
(a) \( \mathbb{N} \) with \( \le \): 정렬집합이다. 이게 정렬 원리.
(b) \( \mathbb{Z} \) with \( \le \): 정렬집합이 아니다. 예컨대 \( S = \{n \in \mathbb{Z} : n < 0\} \)은 비어 있지 않으면서도 최소 원소가 없다. (\( -1, -2, -3, \ldots \)이 끝없이 작아진다.)
(c) \( \mathbb{R} \) with \( \le \): 정렬집합이 아니다. 열린 구간 \( (0, 1) \)에는 최소 원소가 없다. 어떤 후보를 잡아도 그것의 절반이 더 작으니까.
(d) 음수 아닌 유리수 \( \mathbb{Q}_{\ge 0} \) with \( \le \): 정렬집합이 아니다. \( \{1/n : n \ge 1\} \)에 최소 원소가 없다(0보다 큰 어떤 \( 1/n \)을 잡아도 \( 1/(n+1) \)이 더 작다). 게다가 \( \{q \in \mathbb{Q} : q > 0\} \) 자체에도 "양의 가장 작은 유리수"는 존재하지 않는다.
노트 — 표준 순서가 아닌 다른 순서를 주면?
흥미롭게도 어떤 집합은 평소의 순서로는 정렬집합이 아니지만, 순서를 다시 줘서 정렬집합으로 만들 수 있습니다. 예를 들어 양의 유리수 \( \mathbb{Q}_{> 0} \)을 "기약분수 \( a/b \)에서 \( a + b \) 작은 순, 같으면 \( a \) 작은 순"처럼 사전식 비슷한 순서로 다시 정렬하면, 그 순서로는 모든 부분집합이 최소 원소를 갖게 만들 수 있어요. 그러나 이런 인위적 재정렬이 통하는 것은 어디까지나 가산집합(셀 수 있는 집합)에서이고, 일반적으로 임의의 집합을 정렬할 수 있다는 주장(정렬 정리, well-ordering theorem)은 선택공리(Axiom of Choice)와 동치인 강한 명제입니다. 이 노트의 범위를 좀 벗어나니 호기심으로만 남겨 두세요.
일반화의 한 좋은 예로 사전식 순서(lexicographic order)를 봅시다. 두 자연수 쌍 \( (a, b), (c, d) \in \mathbb{N} \times \mathbb{N} \)에 대해
\[ (a, b) \le_{\text{lex}} (c, d) \iff a < c \;\;\text{또는}\;\; (a = c \text{ 이고 } b \le d). \]
로 정의합시다. 사전에서 단어를 정렬하는 방식과 정확히 같죠. 이 순서로 \( \mathbb{N}^2 \)는 정렬집합이 됩니다.
정리 2.4.3
\( (\mathbb{N} \times \mathbb{N}, \le_{\text{lex}}) \)은 정렬집합이다.
증명 스케치
\( T \subseteq \mathbb{N} \times \mathbb{N} \)이 비어 있지 않다고 하자. \( T \)에 등장하는 첫째 좌표들의 집합 \( A = \{ a : \exists b,\, (a, b) \in T \} \subseteq \mathbb{N} \)을 보면, \( A \)는 비어 있지 않으므로 정렬 원리에 의해 최소 원소 \( a_0 \)가 있다. 이제 \( B = \{ b : (a_0, b) \in T \} \)을 보면 이것도 비어 있지 않은 \( \mathbb{N} \)의 부분집합이고, 따라서 최소 원소 \( b_0 \)를 갖는다. 그러면 \( (a_0, b_0) \in T \)이고 \( \le_{\text{lex}} \) 정의상 이는 \( T \)의 최소 원소이다.
∎
이 결과는 단순히 추상적 호기심이 아닙니다. 알고리즘에서 종료성을 증명할 때 단일 자연수 카운터로는 안 되는 경우, "사전식 순으로 줄어드는 (a, b) 쌍"을 잡아 종료를 보이는 기법이 자주 등장합니다. 예를 들어 두 카운터 중 하나가 가끔 늘어나도, 사전식 순서로는 전체가 줄어든다면 알고리즘은 반드시 종료하죠. 이 사실의 정당화가 정확히 정리 2.4.3이에요.
노트 — 정렬 원리와 귀납법의 동치성, 살짝 맛보기
장 도입에서 예고한 대로, 정렬 원리는 수학적 귀납법(특히 강한 귀납법)과 동치입니다. 직관은 이렇습니다. 만약 \( P(0) \)이 참이고 "\( k < n \)에서 \( P \)가 참이면 \( P(n) \)도 참"이라는 점화 단계가 성립한다면, 반례 집합 \( C = \{n : \neg P(n)\} \)에 최소 원소가 있다고 해 봐야 그 최소 원소 자체가 점화 단계에 의해 \( P \)를 만족하게 되어 모순. 즉 강한 귀납법은 정렬 원리로 환원됩니다. 반대 방향도 가능합니다. 자세한 형식 증명은 5장에서 다시 만나요. 지금은 "두 도구가 같은 도구의 두 얼굴"이라는 그림만 머리에 남겨 두면 충분합니다.
예제 2.4.4 — 종료성 한 컷
두 자연수 \( m, n \)에 대해 다음 절차를 생각해 보자. (1) \( m = 0 \)이면 멈춤. (2) \( n > 0 \)이면 \( n \)을 \( 1 \) 줄이고 다시 (1)로. (3) \( n = 0 \)이면 \( m \)을 \( 1 \) 줄이고 \( n \)을 임의의 자연수로 재설정한 뒤 다시 (1)로. 단계 (3) 때문에 \( n \)은 마구 커질 수 있어 단순 카운터로는 종료를 못 보이지만, 매 단계마다 쌍 \( (m, n) \)이 \( \le_{\text{lex}} \) 기준으로 엄격히 줄어든다. \( \mathbb{N} \times \mathbb{N} \)이 정렬집합이므로 무한 하강 수열은 존재할 수 없고, 따라서 절차는 반드시 종료한다.
여기까지가 정렬 원리의 첫 만남입니다. 핵심을 다시 한 줄로 추리면 이렇습니다. "가장 작은 반례"는 종종 자기 자신을 부정한다 — 그러므로 처음부터 반례는 없었다. 이 한 문장이 \( \sqrt{2} \)의 무리수성에서부터 소인수분해 존재성, 알고리즘 종료성에 이르기까지 폭넓게 작동합니다. 다음 장부터는 같은 정신을 또 다른 모습으로 — 명제논리의 추론 규칙들로, 그리고 5장에서는 귀납법의 옷으로 — 다시 만나게 될 거예요.