17주차 — 경우 나누기 (Proof by Cases)

17주차 — 경우 나누기 (Proof by Cases)#

이 주의 길잡이

핵심 문장: 경우는 겹쳐도 되지만, 빠뜨리면 증명이 아니다.

이 주의 위치: 50주 과정의 17주차. 4부(직접 증명)의 마지막 기술 — 가정이 정보를 하나로 주지 않을 때 무대를 쪼개 각각을 직접 증명으로 처리한다.

원서 대응: BoP(Book of Proof) 4.4 (Using Cases), 4.5 (Treating Similar Cases). 원서 없이 읽을 수 있다.

이번 주 목표#

  1. 경우 나누기의 논리적 근거와 채점 기준 두 가지(빠짐없음 + 각 경우 완결)를 백지에 쓰고, 각 조각이 왜 필요한지 설명할 수 있다.

  2. 표준 분할 3종(짝/홀, 부호, mod \(d\) 나머지)을 명제에 맞게 골라 쓸 수 있다.

  3. 절댓값의 케이스 정의로 절댓값 명제를 증명한다 — 삼각부등식까지 포함한다.

  4. WLOG(일반성을 잃지 않고)로 대칭인 경우를 압축하고, 그 선언이 정당한지 판정할 수 있다.

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

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

  1. 차–제곱 전략 3단계를 쓰시오.

  2. AM–GM 부등식을 등호 조건까지 진술하시오.

  3. 1주차 문제 16(연속한 두 정수의 곱 \(a(a+1)\)은 짝수)을 안 보고 증명하시오.

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

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

  • 유형 1 — 한쪽만 처리. “\(a = 2k\)인 정수 \(k\)가 존재한다”로 시작해

\(a(a+1) = 2\big(k(a+1)\big)\)까지 간다. 이 계산은 한 줄도 틀리지 않았다. 문제는 첫 문장이다 — 가정에는 “\(a\)는 정수”만 있는데 “\(a\)는 짝수”를 몰래 얹었다. \(a\)가 홀수인 상황이 통째로 남는다.

  • 유형 2 — 예시 확인. \(3 \times 4 = 12\), \(7 \times 8 = 56\), \(10 \times 11 = 110\)을

적고 “항상 짝수”라 결론짓는다. 확인한 사례에 대해서는 옳다. 남는 것은 1주차 문제 18에서 이미 확인한 간격이다 — 확인하지 않은 무한히 많은 정수는 무엇이 보장하는가.

  • 유형 3 — 두 경우를 나눴으나 한 줄이 없다. “경우 1: \(a\)가 짝수 … 경우 2:

\(a\)가 홀수 …”로 양쪽을 각각 완결했다. 계산도 구조도 옳다. 빠진 것은 “모든 정수는 짝수이거나 홀수이다”라는 한 줄이다. 이번 주 채점 기준의 절반이 정확히 그 한 줄에 걸려 있다(§1.3).

개념 — 무대를 쪼개는 기술#

1 정의를 풀 수 없을 때 어디서 막히는가#

이번 주의 대표 명제를 15~16주차까지의 도구만으로 밀어붙여 보자.

시도 — 정의 풀기와 대수 변형만으로

명제: 모든 정수 \(n\)에 대해 \(3 \mid (n^3 - n)\).

“\(n\)을 임의의 정수라 하자. \(n^3 - n = n(n-1)(n+1)\)로 인수분해된다.

목표는 \(n^3 - n = 3 \times (\text{정수})\) 꼴을 만드는 것이다(정의 2.1).

그런데 \(n\)에 대해 주어진 것은 ‘정수’뿐이므로 풀어 쓸 정의가 없다.

따라서 \(n^3 - n = \ \dots\) “

여기서 멈춘다. 1~2주차의 증명은 언제나 가정의 낱말(“짝수”, “\(a \mid b\)”)을 정의로 풀어 등식을 얻는 데서 시작했는데, 이 명제의 가정에는 풀 낱말이 없다.

확인 1. 멈춘 자리에서 다음 줄이 나오려면 \(n\)에 대해 어떤 종류의 정보가

필요한가. “\(n\)은 ~다” 꼴로 한 구절 적어 보자.

답

“\(n\)은 (무엇) 꼴이다” — 곧 \(n\)의 생김새를 주는 등식이다. 1주차 §1.1과 같은

자리이되, 그때는 가정이 등식을 줄 낱말을 갖고 있었고 지금은 없다. 가정이 주지

않으면 스스로 만들어야 하고, 하나로 정할 수 없다면 가능한 꼴을 전부 나열해

각각에서 증명하는 길이 남는다.

이 주 전체의 기준

가정이 정보를 하나로 주지 않으면, 가능한 상황 전체를 빠짐없이 나눠

각 상황에서 결론을 따로 증명한다. 그 전체가 하나의 증명이 된다.

2 나눠 보기 — 표에서 관찰로#

\(n^3 - n = n(n-1)(n+1)\)은 연속한 세 정수의 곱이다. 세 인수 중 어느 것이 3의 배수가 되는지 몇 개 채워 보자.

\(n\)

세 인수

3의 배수인 인수

\(n\)을 3으로 나눈 나머지

\(6\)

\(5,\ 6,\ 7\)

\(n = 6\)

\(0\)

\(7\)

\(6,\ 7,\ 8\)

\(\underline{\quad(1)\quad}\)

\(\underline{\quad(2)\quad}\)

\(8\)

\(7,\ 8,\ 9\)

\(\underline{\quad(3)\quad}\)

\(\underline{\quad(4)\quad}\)

\(11\)

\(10,\ 11,\ 12\)

\(\underline{\quad(5)\quad}\)

\(\underline{\quad(6)\quad}\)

확인 2. 빈칸 (1)~(6)을 채우고, “3의 배수인 인수”가 무엇에 의해 결정되는지

한 문장으로 적어 보자.

답

(1) \(n - 1 = 6\) (2) \(1\) (3) \(n + 1 = 9\) (4) \(2\) (5) \(n + 1 = 12\) (6) \(2\).

결정하는 것은 \(n\)을 3으로 나눈 나머지다. 나머지가 0이면 \(n\)이, 1이면

\(n-1\)이, 2이면 \(n+1\)이 3의 배수다. 결정적인 사실은 그 나머지가 0, 1, 2

세 가지뿐이라는 것이다 — 세 경우를 각각 처리하면 모든 정수를 다룬 것이 된다.

이 관찰에 정식 형식과 이름을 붙인다. 식 자체에 새로운 것은 없다 — 방금 한 판정을 논리 기호로 굳혔을 뿐이다.

경우 나누기의 논리적 근거 [백지 암기 대상]#

\[ (P_1 \lor P_2) \Rightarrow Q \quad\equiv\quad (P_1 \Rightarrow Q) \land (P_2 \Rightarrow Q) \]

“\(P_1\) 또는 \(P_2\)이면 \(Q\)”는 “\(P_1\)이면 \(Q\)”와 “\(P_2\)이면 \(Q\)”를 모두 주장하는 것과 같은 명제다, 로 읽는다. 기호 \(\lor\)는 “또는”, \(\land\)는 “그리고”(정의 7.3), \(\equiv\)는 논리적 동치(정의 9.1)로 읽는다. 경우가 셋 이상이어도 같은 꼴이다:

\[ (P_1 \lor P_2 \lor P_3) \Rightarrow Q \quad\equiv\quad (P_1 \Rightarrow Q) \land (P_2 \Rightarrow Q) \land (P_3 \Rightarrow Q) \]

확인 3. 우변의 세 조각은 \(\land\)(그리고)로 이어져 있다. 만약 \(\lor\)(또는)로

이어졌다면 증명 절차가 어떻게 달라지는가.

답

“경우 중 하나에서만 \(Q\)를 보이면 된다”가 되어, 나머지 경우는 증명되지 않은 채

남는다. 실제 동치는 \(\land\)이므로 모든 경우에서 \(Q\)에 도달해야 하고,

좌변의 \(\lor\)가 경우들이 가정 전체를 덮는다고 말하고 있다. 이 두 요구가 곧

§1.3의 채점 기준 두 가지다. (이 동치의 진리표 증명은 문제 20에서 한다.)

3 채점 기준 — 동치식에서 읽어 내기#

§1.2의 동치식은 답안이 갖춰야 할 것 두 가지를 지정한다. 하나는 동치식의 우변에 그대로 적혀 있고, 다른 하나는 그 동치를 쓰기 위해 먼저 갚아야 하는 빚이다. 둘을 뽑아 이번 주 내내 쓰는 채점 기준으로 세운다.

채점 기준 두 가지 [백지 암기 대상]#

① 빠짐없음 (exhaustive): 나눈 경우들이 가능한 상황 전체를 덮어야 한다.

② 각 경우 완결: 각 경우 안에서 결론까지 도달해야 한다.

기준 ②는 §1.2 동치식의 우변에서 그대로 읽힌다. 기준 ①은 동치식이 말해 주는 것이 아니라 동치식을 쓰기 위해 별도로 갚아야 하는 빚이다 — 좌변의 가정 \(P_1 \lor P_2\)가 실제로 성립함을 보여야 우변에서 얻은 결론을 회수할 수 있다. 조각마다 하는 일이 다르다.

조각

하는 일

증명에서의 역할

좌변의 “\(P_1 \lor P_2\)”

가정이 그 갈래 전부임을 별도로 증명해야 함

기준 ① — “모든 정수는 셋 중 하나의 꼴이다” 같은 한 줄이 이 조각이다

우변의 각 “\(P_i \Rightarrow Q\)”

경우 하나짜리 작은 증명

기준 ② — 경우마다 결론을 처음부터 다시 만든다

우변을 잇는 “\(\land\)”

모든 경우가 동시에 필요

경우를 하나라도 증명하지 않으면 우변 전체를 얻지 못한다 — 연언은 조각이 전부 갖춰져야 손에 들어온다

세 조각에 공통인 “\(Q\)”

도착점의 일치

경우마다 결론이 다르면 종합할 수 없다

조각 삭제 실험. 기준 ①을 지우면 무엇이 무너지는지 실제 답안으로 본다.

가짜 증명 — 빠짐없음을 지우면

명제: 모든 정수 \(n\)에 대해 \(n^2 + 2\)는 짝수이다.

“경우 1: \(n = 2k\). 그러면 \(n^2 + 2 = 4k^2 + 2 = 2(2k^2 + 1)\)이므로 짝수이다.

경우 2: \(n = 4k\). 그러면 \(n^2 + 2 = 16k^2 + 2 = 2(8k^2 + 1)\)이므로 짝수이다.

따라서 \(n^2 + 2\)는 언제나 짝수이다.”

확인 4. 두 경우의 계산은 각각 옳다. 그런데 결론은 거짓이다

(\(n = 3\)이면 \(n^2 + 2 = 11\)). 정확히 무엇이 빠졌는가.

답

두 경우가 정수 전체를 덮지 않는다 — 홀수가 통째로 새어 나갔다(경우 2는

경우 1의 일부일 뿐이라 새로 덮는 것이 없다). 덮지 못한 구간에서는 결론이

한 번도 증명되지 않았고, 그 구간에 반례(\(n = 3\))가 살고 있어도 이 답안은

알아채지 못한다. 각 경우의 계산이 옳은 것과 증명이 완성된 것은 다른 일이다.

이 답안도 §1.2 동치식의 정당한 인스턴스라는 점을 확인해 둔다 — \(P_1\)을

“\(n = 2k\)”, \(P_2\)를 “\(n = 4k\)”로 두면 우변의 두 조건문이 각각 증명됐다.

동치식은 \(P_1, P_2\)가 무엇이든 성립하므로 빠짐없음을 대신 보장해 주지 않는다.

그 자리를 메우는 것이 기준 ①이다.

확인 5. 위 답안에서 경우 2는 경우 1에 완전히 포함된다. 겹침 자체가

증명을 무너뜨리는가.

이 주의 길잡이

답

무너뜨리지 않는다. 겹치는 상황은 두 경우에서 각각 결론이 증명되므로 두 번

증명한 셈이고, 낭비일 뿐 논리적 결함은 아니다. 이 답안이 무너진 이유는

겹침이 아니라 빠짐이다. 이번 주의 핵심 문장이 이것을 한 줄로 압축한다 —

경우는 겹쳐도 되지만, 빠뜨리면 증명이 아니다.

4 표준 분할 3종#

실전에서 쓰는 분할은 대개 다음 셋 중 하나다. 셋째 열이 기준 ①을 담당한다.

분할

경우

빠짐없음의 근거

짝/홀

\(n = 2k\) 또는 \(n = 2k + 1\)

나눗셈 정리(나누는 수 2)

부호

\(x \ge 0\) 또는 \(x < 0\) (필요하면 \(>,\ =,\ <\) 셋)

실수의 삼분법

mod \(d\) (나누는 수 \(d\))

나누는 수가 3이면 \(3q,\ 3q+1,\ 3q+2\)

나눗셈 정리(나누는 수 3)

지금은 인정하고 쓰는 두 사실

나눗셈 정리 (Division Algorithm). 정수 \(a\)와 자연수 \(d\)에 대해

\(a = dq + r\), \(0 \le r < d\)인 정수 \(q, r\)이 유일하게 존재한다.

증명 없이 인정하고 쓴다(33주차 최소원리에서 증명한다). 나누는 수를 \(d\)로

적는 것은 이번 주의 명제들이 나뉘는 수 쪽을 \(n\)으로 쓰기 때문이다 —

예제 2.1의 \(n\)은 여기의 \(a\) 자리에 들어간다.

실수의 삼분법 (trichotomy). 임의의 실수 \(x\)에 대해 \(x > 0\), \(x = 0\),

\(x < 0\) 중 정확히 하나가 성립한다. 실수의 순서에 관한 기본 성질로 인정하고 쓴다.

두 사실이 하는 일은 같다 — 분할이 전체를 덮는다는 근거 문장을 제공한다.

“mod \(d\)”는 “모듈로 디”로 읽고 “\(d\)로 나눈 나머지로 분류한 것”을 뜻한다. 합동 기호 자체는 20주차에서 다루고, 이번 주에는 나머지에 따라 \(3q\), \(3q+1\), \(3q+2\)로 적는 표기만 쓴다.

확인 6. 다음 분할은 정수 전체에 대해 빠짐없는가.

(가) \(n \ge 1\) / \(n \le -1\) (나) \(n\)이 3의 배수 / \(n\)이 3의 배수가 아님

답

(가) 빠짐이 있다 — \(n = 0\)이 어느 쪽에도 속하지 않는다.

(나) 빠짐이 없다 — 어떤 명제 \(P\)에 대해서든 “\(P\) 또는 \(\neg P\)”는 참이다

(7주차 진리표에서 확인한 사실). 분할이 반드시 나눗셈 정리에서만 나오는 것은

아니고, “그렇다 / 그렇지 않다”의 이분법도 빠짐없음을 만족하는 정당한 분할이다.

5 절댓값 — 정의가 이미 케이스인 개념#

절댓값을 “부호를 뗀 값”이라는 말로만 두면 §1.1과 같은 자리에서 막힌다. 말은 계산이 되지 않는다. 절댓값의 정의는 처음부터 두 경우로 갈려 있다.

정의 17.1 — 절댓값 (absolute value) [백지 암기 대상]#

실수 \(x\)에 대해

\[\begin{split} \begin{aligned}|x| = \begin{cases} x & (x \ge 0) \\ -x & (x < 0) \end{cases}\end{aligned} \end{split}\]

\(|x|\)는 “엑스의 절댓값”으로 읽는다. 중괄호로 묶은 두 줄은 “조건에 따라 값이 갈린다”는 표기이고, “\(x\)가 0 이상이면 \(|x|\)는 \(x\), \(x\)가 0보다 작으면 \(|x|\)는 \(-x\)”로 읽는다. 읽는 법까지가 정의다.

이 정의는 네 조각으로 되어 있고, 조각마다 판정에서 맡는 역할이 다르다.

조각

하는 일

판정에서의 역할

두 줄로 갈린 형태

값을 경우별로 지정

\(\lvert x \rvert\)를 만나면 먼저 \(x\)의 부호를 판정한다 — 절댓값 증명이 경우 나누기가 되는 이유

첫 줄의 조건 “\(x \ge 0\)”

첫 가지의 적용 범위

등호가 이 줄에 붙어 있어 \(x = 0\)이 첫 가지에서 처리된다

둘째 줄의 조건 “\(x < 0\)”

둘째 가지의 적용 범위

첫 줄과 겹치지 않고, 둘을 합치면 실수 전체 — 빠짐없음이 정의 안에 들어 있다

둘째 줄의 값 “\(-x\)”

부호 반전

“마이너스를 붙인다”가 아니라 반대 부호를 취한다 — \(x < 0\)이므로 \(-x > 0\)이다

조각 삭제 실험. 둘째 줄의 조건을 “\(x \le 0\)”으로 바꾸면 \(x = 0\)이 두 줄에 동시에 걸린다. 그런데 값은 \(0\)과 \(-0 = 0\)으로 같으므로 아무 일도 일어나지 않는다 — 겹침은 무해하다. 반대로 첫 줄을 “\(x > 0\)”으로 바꾸고 둘째 줄을 “\(x < 0\)”으로 두면 \(x = 0\)에서 값이 정의되지 않는다. \(|0|\)이 등장하는 순간 증명이 멈춘다. 정의에서도 겹침은 무해하고 빠짐은 치명적이다.

확인 7. \(|-3|\)과 \(|0|\)을 정의의 어느 가지로 계산하는지 밝히고 값을 적어 보자.

답

\(-3 < 0\)이므로 둘째 가지다: \(|-3| = -(-3) = 3\).

\(0 \ge 0\)이므로 첫 가지다: \(|0| = 0\).

어느 가지인지 먼저 밝히는 것이 답안의 필수 부분이다 — 부호 판정 없이 값만

적으면 근거가 비어 있다. 애매하면 정의로 돌아간다는 1주차 §1.5의 습관이

여기서도 그대로 작동한다.

정의에서 곧바로 따라 나오는 파생 사실 세 개는 이번 주 내내 재료로 쓰인다.

\[ |x| \ge 0, \qquad x \le |x|, \qquad -x \le |x| \]

확인 8. 셋째 사실 \(-x \le |x|\)는 문제 5에서 둘째 사실과 같은 분할로 함께

증명한다(§6 문제 5의 복기). 이것과 둘째 사실을 합치면 왜

\(-|x| \le x \le |x|\)가 되는가.

답

\(-x \le |x|\)의 양변에 \(-1\)을 곱하면 부등호 방향이 뒤집혀(16주차 (W3))

\(x \ge -|x|\), 곧 \(-|x| \le x\)가 된다. 이것을 \(x \le |x|\)와 이어 쓰면

\(-|x| \le x \le |x|\)이다. 이 두 줄짜리 사실이 문제 12(삼각부등식)의 재료다.

6 WLOG — 반복을 생략하는 장치#

백지 암기 대상

WLOG — 일반성을 잃지 않고 (Without Loss Of Generality)

남은 경우가 다룬 경우와 문자의 역할 교환만으로 같은 증명이 될 때,

“일반성을 잃지 않고 (조건)이라 하자”라고 선언하고 한 경우만 쓴다.

WLOG는 경우를 없애는 장치가 아니라 같은 글을 두 번 쓰지 않기 위한 장치다. 생략의 대가로 반드시 남겨야 하는 것이 있다 — 두 경우가 실제로 이름 교환으로 서로 옮겨진다는 근거 한 줄이다. 그 줄이 없으면, 경우 하나를 정당하게 생략한 답안과 그냥 빠뜨린 답안을 구별할 방법이 없다.

확인 9. 다음 두 선언 중 WLOG가 정당한 것은 어느 쪽인가.

(가) 명제 “정수 \(x, y\) 중 적어도 하나가 짝수이면 \(xy\)는 짝수” —

“일반성을 잃지 않고 \(x\)가 짝수라 하자”

(나) 명제 “모든 정수 \(x, y\)에 대해 \(x^2 + y^2 \ge 2xy\)” —

“일반성을 잃지 않고 \(x = y\)라 하자”

답

(가)만 정당하다. (가)에서 남은 경우(”\(y\)가 짝수”)는 \(x\)와 \(y\)의 이름을 맞바꾸면

다룬 경우와 글자 그대로 같은 증명이 된다. (나)에서 남은 경우(”\(x \neq y\)”)는

이름을 어떻게 바꿔도 “\(x = y\)”로 옮겨지지 않는다 — 다룬 것은 전체 중 한

특수한 상황이고, 나머지가 통째로 남는다. (나)의 오류는 문제 19에서 정식으로

진단한다.

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

1~2주차에서 세운 근거 목록의 칸은 이번 주에도 네 개다. 이번 주가 채우는 것은 ①과 ④다.

근거

이번 주에 추가되는 것

이번 주에는 이렇게 쓴다

① 정의

정의 17.1(절댓값)

절댓값을 만나면 \(x\)의 부호로 갈라 값을 확정한다

② 닫힘성

변화 없음 — 16주차에서 등록한 (W4)(양수의 합\(\cdot\)곱은 양수)를 계속 쓴다

“\(3q^2 + 2q\)는 정수이므로”를 별도 설명 없이 쓴다

③ 등식\(\cdot\)부등식의 성질

변화 없음 (부등식의 양변 연산은 16주차 (W2)(W3))

양변에 같은 값 더하기\(\cdot\)빼기(W2), 두 부등식의 변끼리 덧셈(16주차 문제 2(c) — (W2) 두 번 + 추이성), 음수를 곱할 때의 방향 반전(W3)

④ 이미 증명한 명제

16주차 (W1)(\(x^2 \ge 0\))이 여기 있고, 나눗셈 정리\(\cdot\)삼분법(인정하고 사용), 경우 나누기의 동치(문제 20에서 증명)가 더해진다

분할이 전체를 덮는다는 근거를 한 줄로 인용한다

경우 나누기의 동치는 9주차 §1.6의 동치 목록 여덟 개에 들어 있지 않다. 문제 20에서 진리표로 증명하는 순간 근거 ④에 등록된다. 그 전까지 이번 주의 증명들은 동치를 인용하는 대신, 동치가 요구하는 두 조건(빠짐없음\(\cdot\)각 경우 완결)을 답안 안에서 직접 지키는 방식으로 정당화된다.

확인 10. 다음 두 문장은 각각 몇 번 근거인가.

(가) “나눗셈 정리에 의해 \(n\)은 \(3q\), \(3q+1\), \(3q+2\) 중 정확히 하나의 꼴이다.”

(나) “\(x < 0\)이므로 정의에 의해 \(|x| = -x\)이다.”

답

(가) 근거 ④ — 인정하고 쓰는 기존 사실의 인용이다. 이 한 줄이 분할의

빠짐없음을 담당하므로, 생략하면 채점 기준 ①이 비게 된다.

(나) 근거 ① — 정의 17.1의 둘째 가지를 적용했다. 어느 가지인지 정하려면 그

앞에 부호 판정(”\(x < 0\)이므로”)이 반드시 있어야 한다. 부호 판정과 가지 적용은

한 몸이다.