# 33주차 — 강한 귀납법과 최소원리

:::{admonition} 이 주의 길잡이
:class: keybox

**핵심 문장**: 직전 하나만 필요하면 귀납, 과거 전부가 필요하면 강한 귀납, 반례를 상대하려면 최소원리다.

**이 주의 위치**: 50주 과정의 33주차. 31~32주차의 귀납법을 가정의 크기 쪽으로 넓히고, 17$\cdot$21$\cdot$22$\cdot$25주차에서 "인정하고 쓴다"고 적어 둔 사실들을 증명해 회수한다.

**원서 대응**: BoP(Book of Proof) 10.1 (Strong Induction), 10.2 (Proof by Smallest Counterexample). 원서 없이 읽을 수 있다.
:::

## 이번 주 목표

1. 강한 귀납법(strong induction)의 원리를 백지에 쓰고, "언제 필요한가"의 신호 두 가지(분해형$\cdot$고정 보폭)로 도구를 고를 수 있다.
1. 최소원리(well-ordering principle)를 백지에 쓰고, 최소 반례법의 서식을 재현할 수 있다.
1. 빚 청산 3건을 직접 증명한다: **소인수분해의 존재**($\to$ 소수 약수의 존재), **나눗셈 정리**, **기약분수의 존재**.
1. 귀납$\cdot$강한 귀납$\cdot$최소원리가 한 가족(동치)임을 문제 11과 14의 구조로 설명할 수 있다.

본문 곳곳의 **확인** 상자는 연필로 먼저 답하는 자리다. 바로 아래의 **답** 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다.

## 준비 운동 (32주차 복습)

1. 부등식 귀납의 2단 구조를 쓰시오.
1. 우표 문제(32주차 문제 15)의 귀납 단계 아이디어(교체 2케이스)를 말로 재현하시오.
1. 21주차에서 "사실로 인정"하고 썼던 두 가지가 무엇이었는지 쓰시오 (√2 증명과 소수 무한 증명에서).

### 자주 나오는 세 가지 답 — 3번 문항

방금 쓴 답은 대개 다음 세 유형 중 하나다. 셋 다 옳은 부분이 있고, 셋 다 이번 주에 메울 정확한 간격이 있다.

- **유형 1 — 도구 이름으로 답하기.** "최소원리와 강한 귀납법"이라고 적는다. 21주차가 그

둘에 기대고 있었다는 판단은 옳고 이번 주의 도구가 정확히 그 둘이다. 다만 질문이 묻는 것은 도구가 아니라 **인정하고 쓴 명제**다 — 기약분수 표현의 존재와 소수 약수의 존재다.

- **유형 2 — 하나만 적기.** "기약분수"만 적는다. 21주차 √2 증명이 실제로 빌려 쓴 것이

그것이므로 옳다. 빠진 것은 같은 주 소수 무한 증명이 첫 줄에서 쓴 "$N \ge 2$는 소수인 약수를 가진다"이다 — 두 증명이 각각 하나씩 빌렸다.

- **유형 3 — 백지.** 인정하고 쓴 사실은 본문 곳곳에 흩어져 있어 되짚기 어렵다.

21주차 §1.8이 그 둘을 "빌려 쓰는 사실"로 못 박았고, §1.9가 근거 목록 옆에 그 항목들을 "33주차에서 회수할 것"으로 적어 두었다. 이번 주는 그 표시를 지우는 주다.

## 개념 — 가정을 넓히는 길과, 반례를 붙잡는 길

### 1 보통 귀납으로 밀어붙이면 어디서 막히는가

이번 주의 대표 명제를 31주차의 서식 그대로 밀어붙여 보자.

:::{admonition} 시도 — 보통 귀납으로 밀어붙이기
:class: quotebox

명제: 2 이상의 모든 정수는 소수이거나 소수들의 곱이다.

"**[기초]** $n = 2$: 2는 소수. ✓

**[귀납]** $P(k)$가 참이라 가정하자 — 즉 $k$는 소수이거나 소수들의 곱이다.

$k+1$을 생각한다. $k+1$이 소수이면 그것으로 끝난다. 소수가 아니면

$k+1 = ab$ ($1 < a, b < k+1$)로 쪼개진다. 그런데 $a$와 $b$는 … "
:::

여기서 멈춘다. 손에 있는 정보는 $k$ 하나에 대한 것인데, 지금 정보가 필요한 대상은 $a$와 $b$다. $k+1 = 12$라면 $12 = 3 \times 4$이므로 $a = 3$, $b = 4$ — 어느 쪽도 $k = 11$이 아니다. **보통 귀납이 주는 가정은 직전 하나($P(k)$)뿐이고, 필요한 과거의 위치를 미리 지정할 수 없으면 가정을 구간 전체로 넓혀야 증명이 이어진다.**

:::{container} quotebox
**확인 1.** 멈춘 자리에서 다음 줄이 나오려면 어떤 대상에 대한 정보가 필요한가.

그 대상의 위치를 $k$만 알고 미리 지정할 수 있는가.
:::

:::{admonition} 답
:class: quotebox dropdown

$a$와 $b$ 각각에 대한 정보가 필요하고, 위치는 미리 지정할 수 없다. 합성수의

정의가 보장하는 것은 "$1 < a, b < k+1$"이라는 **구간**뿐이고, 구간 안 어디인지는

$k+1$이 무엇이냐에 따라 매번 달라진다.
:::

### 2 필요한 과거를 재어 보기

$k+1$이 합성수일 때 실제로 어느 과거가 쓰이는지 몇 개만 채워 보자(마지막 열은 그 과거가 직전 $k$와 같은지를 묻는다).

| **$k+1$** | **분해 한 가지** | **필요한 과거** | **직전($k$)인가** |
|---|---|---|---|
| $12$ | $3 \times 4$ | $P(3),\ P(4)$ | 아니다 ($k = 11$) |
| $30$ | $5 \times 6$ | $\underline{\quad(1)\quad}$ | $\underline{\quad}$ |
| $25$ | $5 \times 5$ | $\underline{\quad(2)\quad}$ | $\underline{\quad}$ |
| $9$ | $3 \times 3$ | $P(3)$ | 아니다 ($k = 8$) |

:::{container} quotebox
**확인 2.** 빈칸 (1)(2)를 채우고, 네 행의 "필요한 과거"가 공통으로 갖는 성질을

한 문장으로 적어 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

(1) $P(5),\ P(6)$ (2) $P(5)$ — 둘 다 직전이 아니다.

공통 성질: 필요한 과거는 매번 다른 자리에 있지만 **언제나 2 이상 $k$ 이하**다.

그러므로 구간 전체를 가정해 두면 어느 자리가 필요해지든 손에 있다.
:::

이 관찰에 정식 이름과 형식을 붙인다. 원리 자체에 새로운 것은 없다 — 방금 표에서 필요하다고 확인한 것을 가정 자리에 옮겨 적었을 뿐이다.

### 강한 귀납법의 원리 (strong induction) [백지 암기 대상]

:::{container} quotebox
**(기초)** $P(1)$이 참이다. (필요하면 $P(1), P(2), \dots, P(n_0)$ 여러 개)

**(귀납)** 모든 $k$에 대해, **$P(1), P(2), \dots, P(k)$가 전부 참이면** $P(k+1)$도 참이다.

그러면 모든 자연수 $n$에 대해 $P(n)$이 참이다.
:::

"$P(1), P(2), \dots, P(k)$가 전부 참이면"은 "피 원부터 피 케이까지 모두 참이면"으로 읽고, 이 가정을 **강한 귀납 가정**(strong inductive hypothesis)이라 부른다. 무대가 $n \ge n_0$인 명제에서는 기초와 구간을 $n_0$부터 세어 읽는다(32주차의 일반화된 귀납 원리와 같은 조정 — 예제 2.1은 $n_0 = 2$다).

### 3 원리 해부 — 조각마다 하는 일

| **조각** | **하는 일** | **증명에서의 역할** |
|---|---|---|
| "$P(1)$이 참이다" | 출발점 확보 | 전달 장치가 물어 올 첫 참을 마련한다 |
| "모든 $k$에 대해" | 전달 장치의 적용 범위 | 어느 $k$에서도 다음 칸으로 넘어갈 수 있음을 요구한다 |
| "$P(1), \dots, P(k)$가 전부 참이면" | **가정의 크기** | 보통 귀납과 다른 유일한 조각. 필요한 과거의 위치를 몰라도 되게 만든다 |
| "$P(k+1)$도 참이다" | 전달의 도착점 | 증명해야 할 조건문의 결론 |
| "모든 자연수 $n$에서 참" | 결론 | 위 둘을 확보하면 따라 나오는 것 |

**조각 삭제 실험 1 — 가정을 줄여 보기.** 셋째 조각을 "$P(k)$가 참이면"으로 되돌리면 §1.1의 막힘이 그대로 재연된다: $12 = 3 \times 4$ 앞에서 $P(11)$은 쓸 데가 없다.

**조각 삭제 실험 2 — 기초를 지워 보기.** 첫 조각을 지우면 전달 장치만 남는다. "$P(1)$부터 $P(k)$까지 참이면 $P(k+1)$도 참"은 $P$가 전부 거짓이어도 공허하게 참일 수 있다(8주차 — 앞부분이 거짓인 조건문은 참). 31주차 문제 17이 이 붕괴를 다뤘다.

### 4 언제 필요한가 — 신호 두 가지와 기초의 개수

$k+1$의 성질이 **직전($k$)이 아니라 더 먼 과거, 또는 어느 과거인지 미리 알 수 없는 지점**에서 올 때 강한 귀납법이 필요하다. 이 상황은 두 가지 얼굴로 온다.

| **신호** | **생김새** | **이번 주의 무대** |
|---|---|---|
| 분해형 | $k+1 = ab$처럼 쪼개지는데 $a, b$의 위치를 모른다 | 예제 2.1, 훈련 1, 문제 15 |
| 고정 보폭 | $k+1$의 성질이 $k-2$나 $k-1$처럼 **정해진 칸수 뒤**에서 온다 | 문제 8$\cdot$12$\cdot$19, 34주차 피보나치 |

고정 보폭에는 규칙이 하나 붙는다. 귀납 단계가 $d$칸 뒤를 참조하면 시작 부분의 $d$개는 전달 장치로 덮이지 않으므로 **기초를 $d$개** 확인해야 한다. 문제 8은 보폭 3이라 기초가 세 개다.

반대로, 보통 귀납으로 충분한 명제에 강한 귀납법을 선언해도 하자는 없다 — 강한 가정은 보통 가정을 포함하므로 넉넉히 받아 두고 $P(k)$만 쓰면 된다. 하자는 반대 방향에서 생긴다: $P(k-2)$를 쓰면서 "$P(k)$를 가정하자"라고만 적으면 가정한 적 없는 것을 근거로 삼은 것이다.

:::{container} quotebox
**확인 3.** 수열이 $c_n = c_{n-2} + 2$로 정의되어 있다. 귀납 단계가 $P(k-1)$을

쓰는데 기초를 $P(1)$ 하나만 확인했다면, 확보되지 않은 첫 항은 무엇인가.
:::

:::{admonition} 답
:class: quotebox dropdown

$P(2)$다. 귀납 단계는 $k+1 \ge 3$에서만 뜻이 있으므로($c_n$의 정의가 $n \ge 3$),

$k+1 = 2$를 만들어 낼 방법이 없다. 기초에서도 귀납에서도 $P(2)$가 확보되지

않는다 — 보폭이 2이므로 기초도 두 개여야 한다. 문제 17에서 이 참사를 해부한다.
:::

### 5 반례 쪽에서 접근하기 — 최소원리

방향을 바꿔 본다. "모든 $n$에서 $P(n)$"을 귀류법으로 증명하려면 거짓인 $n$이 있다고 가정하고 모순을 만들어야 한다.

:::{admonition} 시도 — 아무 반례나 잡아 보기
:class: quotebox

"$P(n)$이 거짓인 자연수 $n$이 있다고 가정하자. 그런 $n$을 하나 잡는다.

그러면 $P(n)$이 거짓이고, $n - 1$에 대해서는 … "
:::

여기서 멈춘다. 잡은 $n$에 대해 아는 것은 "$P(n)$이 거짓"이라는 사실 하나뿐이고, $n-1$ 이하에 대해서는 아무 정보가 없다. 귀납법이 늘 손에 쥐고 있던 "이전 것은 참"이라는 정보가 여기에는 없다.

:::{container} quotebox
**확인 4.** 잡은 반례에 조건을 하나 더 붙여 $n$보다 작은 곳에 대한 정보를 얻고

싶다. 어떤 조건을 붙이면 되는가.
:::

:::{admonition} 답
:class: quotebox dropdown

"**가장 작은** 반례"라는 조건이다. $m$이 가장 작은 반례이면 $m$보다 작은 모든 자연수에서

$P$가 참이다 — 그 자리에는 반례가 없기 때문이다. 이 한 마디가 강한 귀납 가정과 같은

정보를 만든다. 남은 문제는 그런 반례가 정말 있는가이고, 그것을 보장하는 것이 다음 원리다.
:::

### 최소원리 (well-ordering principle) [백지 암기 대상]

:::{container} quotebox
공집합이 아닌 자연수의 부분집합은 반드시 **최소원소**를 가진다.

(음이 아닌 정수의 부분집합에 대해서도 동일하게 성립한다.)
:::

집합 $S$의 **최소원소**란 $m \in S$이면서 모든 $x \in S$에 대해 $m \le x$인 $m$을 말하고, 기호로는 $\min S$로 쓰고 "에스의 최솟값"으로 읽는다. 자기 자신이 $S$의 원소여야 한다 — 아래를 막아 주기만 하는 수는 최소원소가 아니다.

| **조각** | **하는 일** | **증명에서의 역할** |
|---|---|---|
| "공집합이 아닌" | 적용 전제 | 인용하기 전에 원소 하나를 실제로 제시해야 한다 |
| "자연수의 부분집합" | 무대 제한 | 실수$\cdot$유리수로 넓히면 거짓이 된다 |
| "반드시 최소원소를 가진다" | 존재 보장 | "가장 작은 것을 잡자"고 쓸 자격을 준다 |

**조각 삭제 실험 1 — "공집합이 아닌"을 지우면.** 공집합에도 최소원소가 있어야 하는데, 최소원소는 그 집합의 원소여야 하므로 원소가 없는 집합에는 있을 수 없다. 실전에서 $S \neq \varnothing$의 확인이 필수 단계인 이유다.

**조각 삭제 실험 2 — "자연수의"를 지우면.** 실수 구간 $(0, 1)$은 비어 있지 않지만 최솟값이 없다 — 후보 $m$을 무엇으로 잡든 $\frac{m}{2}$이 그 구간 안에 있으면서 더 작다(22주차 문제 10). 최소원리는 자연수가 듬성듬성 놓여 있기에 성립한다.

:::{container} quotebox
**확인 5.** 집합 $S = \{x \in \mathbb{Q} : x > 0\}$(양의 유리수 전체)에 최소원리를

적용해 "가장 작은 양의 유리수"를 잡아도 되는가.
:::

:::{admonition} 답
:class: quotebox dropdown

안 된다. $S$는 비어 있지 않지만 자연수의 부분집합이 아니다. 실제로 어떤 $m > 0$을

잡아도 $\frac{m}{2}$이 더 작은 양의 유리수이므로 최소원소가 존재하지 않는다.

최소원리를 인용할 때는 무대가 자연수(또는 음이 아닌 정수)인지 먼저 확인한다.
:::

최소원리를 음이 아닌 정수까지 넓혀 적용하면, 22$\cdot$25주차에서 인정하고 써 온 사실 하나가 함께 회수된다.

:::{admonition} 보조 명제 33.A — 0과 1 사이에는 정수가 없다
:class: quotebox

$0 < x < 1$인 정수 $x$는 존재하지 않는다.
:::

무대를 자연수가 아니라 **정수**로 잡는 것이 요점이다. 자연수 쪽에서 "$n \ge 1$"을 증명하려 들면 3주차가 $\mathbb{N} = \{1, 2, 3, \dots\}$로 못 박은 정의를 되풀이하는 공회전이 된다. 실제로 22$\cdot$25주차가 빌려 쓴 것은 정수 쪽 진술이다.

**증명.** 모순을 위해 $T = \{x \in \mathbb{Z} : 0 < x < 1\}$이 공집합이 아니라고 가정하자. $T$의 원소는 모두 $0$보다 크므로 $T$는 음이 아닌 정수의 부분집합이고, 최소원리(음이 아닌 정수 판)에 의해 최소원소 $m$을 가진다. $m \in T$이므로 $0 < m < 1$이다. 부등식 $m < 1$의 양변에 $m > 0$을 곱하면 $m^2 < m$이고, $m > 0$인 두 수의 곱이므로 $m^2 > 0$이다(근거 ③). 곧 $0 < m^2 < m < 1$이고 정수의 곱은 정수이므로(근거 ②) $m^2 \in T$인데 $m^2 < m$ — $m$의 최소성과 모순이다. $\blacksquare$

:::{admonition} 따름정리 (22$\cdot$25주차의 빚 청산)
:class: quotebox

0이 아닌 정수의 절댓값은 1 이상이다.
:::

$a$를 0이 아닌 정수라 하면 $|a|$도 정수이고 $|a| > 0$이다. 만약 $|a| < 1$이면 $0 < |a| < 1$이므로 $|a| \in T$가 되어 33.A와 모순이다. 따라서 $|a| \ge 1$이다. 22주차 §1.9의 인정 항목이 이것이고, 25주차 예제 2.2의 보조정리가 그 위에 서 있었다.

### 6 최소 반례법 — 서식

:::{admonition} 백지 암기 대상
:class: keybox

**최소 반례법 (proof by smallest counterexample)**

**명제.** 모든 자연수 $n$에 대해 $P(n)$이다.

**증명.** 모순을 위해 $P(n)$이 거짓인 자연수가 있다고 가정하자.

반례들의 집합 $S = \{n \in \mathbb{N} : P(n)$이 거짓$\}$은 공집합이 아니므로,

최소원리에 의해 최소원소 $m$이 존재한다.

($m$의 최소성에 의해, $m$보다 작은 모든 자연수에서 $P$는 참이다.)

$\quad\vdots\quad$ $m$에서 모순을 이끌어낸다.

따라서 반례는 존재하지 않고, 모든 자연수 $n$에서 $P(n)$이다. $\blacksquare$
:::

:::{container} quotebox
**확인 6.** 이 서식에서 "최소"라는 낱말을 지우고 "반례 $m$이 존재한다"로만

적으면 무엇을 잃는가.
:::

:::{admonition} 답
:class: quotebox dropdown

$m$보다 작은 곳에서 $P$가 참이라는 정보를 잃는다. 그 정보가 이 논법이 쥐는 유일한

재료이므로 잃고 나면 §1.5에서 멈춘 자리로 되돌아간다 — 실제 일을 하는 낱말은

"반례"가 아니라 "최소"다.
:::

최소원리는 반례 집합에만 쓰는 것이 아니다. 이번 주의 세 가지 쓰임은 다음과 같다.

| **쓰임** | **최소원리를 적용하는 집합** | **최소원소가 뜻하는 것** | **무대** |
|---|---|---|---|
| 최소 반례 | 반례들의 집합 | 가장 작은 반례 | 문제 11, 14 |
| 최소 잔여 | $a$에서 $n$을 뺀 값 중 음이 아닌 것 | 나머지 $r$ | 예제 2.2 |
| 최소 후보 | 같은 수를 나타내는 표현들의 분모 | 기약분수의 분모 | 예제 2.3, 문제 13 |

세 쓰임은 최소원소 $m$을 잡는 데까지가 같고, 모순을 만드는 마지막 한 걸음에서 두 갈래로 갈린다. **첫째 갈래 — $m$보다 작은 원소를 실제로 만들어 최소성과 충돌시킨다**(최소 잔여$\cdot$최소 후보 — 예제 2.2, 2.3, 문제 13). **둘째 갈래 — 최소성이 주는 "$m$보다 작은 곳은 전부 참"을 써서 $m$에서도 명제가 참임을 보이고 $m \in S$와 충돌시킨다**(최소 반례 — 문제 11, 14). 충돌 상대가 각각 최소성과 소속으로 다르지만, 어느 쪽이든 일을 하는 낱말은 "최소"다. 이 골격을 §2 관찰에서 대응표로 다시 확인하고 거기서 ④-a$\cdot$④-b로 이름 붙인다.

### 7 근거 목록 갱신 — 칸은 그대로 네 개

증명에서 쓸 수 있는 것은 여전히 네 칸이다. 늘어나는 것은 칸이 아니라 ④의 내용물이다.

| **근거** | **내용** | **이번 주에는 이렇게 쓴다** |
|---|---|---|
| ① 정의 | 1~32주차의 정의 전부(특히 정의 15.2 소수, 15.3 합성수, 21.2 기약분수) | "합성수"를 $k+1 = ab$ ($1 < a, b < k+1$)로 푼다 |
| ② 닫힘성 | 정수의 합$\cdot$차$\cdot$곱은 정수, 자연수의 합$\cdot$곱은 자연수(차는 자연수가 아닐 수 있다) | 정수 쪽: "$a - n(q_0+1)$은 정수이므로"를 별도 설명 없이 쓴다 / 자연수 쪽: "$d b_1$은 자연수이므로"는 되지만 "$a_0 - b_0$은 자연수이므로"는 안 된다 |
| ③ 등식$\cdot$부등식의 성질 | 대입 / 전개 / 묶기 / 양변 연산 | $r \ge n$의 양변에서 $n$을 뺀다 |
| ④ 이미 증명한 명제 | 1~32주차 전부 + **이번 주에 승격되는 항목**(아래) | "예제 2.1에 의해 $a$는 소수들의 곱이므로" |

**강한 귀납법과 최소원리는 칸을 늘리지 않는다.** 21주차의 귀류법이 그랬듯 이 둘이 바꾸는 것은 증명의 뼈대이지 각 줄의 근거가 아니다 — 뼈대 안쪽의 계산은 1주차의 직접 증명과 다르지 않다.

이번 주가 끝나면 근거 ④에 여섯 항목이 등록된다 — 소인수분해의 존재(예제 2.1), 소수 약수의 존재(문제 6, 훈련 3), 나눗셈 정리의 존재(예제 2.2와 그 확장 — 모든 정수 $a$)와 유일(문제 10), 기약분수 표현의 존재(예제 2.3과 그 확장 — 모든 유리수), "0이 아닌 정수의 절댓값은 1 이상"(보조 명제 33.A의 따름정리), 그리고 "모든 정수는 짝수이거나 홀수"(예제 2.2의 따름정리). 전부 1$\cdot$9$\cdot$11$\cdot$17$\cdot$19$\cdot$21$\cdot$22$\cdot$25주차에서 "인정하고 쓴다"고 적어 둔 항목이며, 증명이 붙어 인용 가능한 정리가 된다. 각 항목의 무대가 인정하고 쓴 범위와 같은지까지 맞춰야 회수가 끝난다 — 예제 2.2와 2.3에 확장 단계를 따로 붙이는 이유가 그것이다.

:::{container} quotebox
**확인 7.** 어떤 답안에 다음 세 문장이 나왔다. 각각 허용되는가. 허용된다면 몇 번 근거인가.

(가) "$k+1$이 합성수이므로 $k+1 = ab$인 정수 $a, b$ ($1 < a, b < k+1$)가 존재한다."

(나) "$q_0 + 1$은 정수이므로 $a - n(q_0 + 1)$도 정수이다."

(다) "$a_0 - b_0$은 자연수이므로 1 이상이다."
:::

:::{admonition} 답
:class: quotebox dropdown

(가) 허용된다 — 근거 ①. 정의 15.3을 그대로 풀어쓴 줄이므로 별도 설명이 필요 없다.

(나) 허용된다 — 근거 ②. 정수의 합$\cdot$차$\cdot$곱은 정수이고 $q_0, n, a$가 모두 정수다.

(다) 허용되지 않는다. 근거 ②가 주는 것은 "정수의 차는 **정수**"까지이고, 자연수는

차에 대해 닫혀 있지 않다($1 - 2 = -1$은 자연수가 아니다). $a_0 - b_0$이 자연수라고

쓰려면 $a_0 > b_0$을 따로 보여야 한다 — 문제 13(a)가 정확히 그 준비다. 그것이

확보된 뒤라야 "1 이상"이 33.A의 따름정리(근거 ④)로 따라 나온다.
:::