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

내용

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

이 주의 길잡이

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

이 주의 위치: 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). 원서 없이 읽을 수 있다.

이번 주 목표#

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

시도 — 보통 귀납으로 밀어붙이기

명제: 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)\))뿐이고, 필요한 과거의 위치를 미리 지정할 수 없으면 가정을 구간 전체로 넓혀야 증명이 이어진다.

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

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

답

\(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\))

확인 2. 빈칸 (1)(2)를 채우고, 네 행의 “필요한 과거”가 공통으로 갖는 성질을

한 문장으로 적어 보자.

답

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

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

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

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

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

(기초) \(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)\)를 가정하자”라고만 적으면 가정한 적 없는 것을 근거로 삼은 것이다.

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

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

답

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

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

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

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

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

시도 — 아무 반례나 잡아 보기

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

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

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

확인 4. 잡은 반례에 조건을 하나 더 붙여 \(n\)보다 작은 곳에 대한 정보를 얻고

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

답

“가장 작은 반례”라는 조건이다. \(m\)이 가장 작은 반례이면 \(m\)보다 작은 모든 자연수에서

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

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

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

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

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

집합 \(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). 최소원리는 자연수가 듬성듬성 놓여 있기에 성립한다.

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

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

답

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

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

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

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

보조 명제 33.A — 0과 1 사이에는 정수가 없다

\(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\)

따름정리 (22\(\cdot\)25주차의 빚 청산)

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 최소 반례법 — 서식#

백지 암기 대상

최소 반례법 (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\)

확인 6. 이 서식에서 “최소”라는 낱말을 지우고 “반례 \(m\)이 존재한다”로만

적으면 무엇을 잃는가.

답

\(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에 확장 단계를 따로 붙이는 이유가 그것이다.

확인 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 이상이다.”

답

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

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

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

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

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

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