# 21주차 — 귀류법 1 (Proof by Contradiction) :::{admonition} 이 주의 길잡이 :class: keybox **핵심 문장**: 결론을 부정해 가정 자리에 놓으면, 만들 목표 꼴이 없던 자리에 전개할 등식이 생긴다. **이 주의 위치**: 50주 과정의 21주차. 18주차에서 진단만 하고 넘긴 "부정형 결론의 막힘"을 뚫는 세 번째 증명 기법을 세운다. **원서 대응**: BoP(Book of Proof) 6.1 (Proving Statements with Contradiction). 원서 없이 읽을 수 있다. ::: ## 이번 주 목표 1. 귀류법의 3단계 구조와 서식을 백지에 쓰고, 각 단계가 하는 일을 설명할 수 있다. 1. "$\sqrt{2}$는 무리수이다"와 "소수는 무한히 많다"를 백지에서 증명할 수 있다. 1. "가장 큰/가장 작은 ~는 없다", "정수 해가 없다" 유형을 귀류법으로 처리할 수 있다. 1. 모순이 나오지 않는 상황($\sqrt{4}$)에서 무엇을 읽어야 하는지 판단할 수 있다. 본문 곳곳의 **확인** 상자는 연필로 먼저 답하는 자리다. 바로 아래의 **답** 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다. ## 준비 운동 (20주차 복습) 1. $a \equiv b \pmod n$의 정의를 쓰시오. 1. "$n^2$이 짝수이면 $n$은 짝수이다"의 증명 구조를 말로 재현하시오 (19주차 예제 2.1 — 이번 주의 핵심 부품이다). 1. 11주차 문제 20에서 써 둔 "$\sqrt{2}$ 귀류법의 첫 두 줄"을 다시 쓰시오. 답을 노트에 적어 둔다. 이번 주 끝(§5 재현 뒤)에 이 기록을 다시 본다. ### 자주 나오는 세 가지 답 — 3번 문항 방금 쓴 답은 대개 다음 세 유형 중 하나다. 셋 다 옳은 부분이 있고, 셋 다 이번 주에 메울 정확한 간격이 있다. - **유형 1 — 부정을 말로만 다시 적기.** "$\sqrt{2}$는 무리수가 아니다"라고 적고 멈춘다. 부정 자체는 옳다. 문제는 "무리수가 아니다"가 아직 전개할 수 없는 말이라는 것이다 — 정의 15.1로 "$\sqrt{2}$는 유리수이다"로 바꾸고, 다시 3주차 $\mathbb{Q}$의 정의로 "$\sqrt{2} = \frac{a}{b}$인 정수 $a, b$($b \neq 0$)가 존재한다"까지 풀어야 등식이 손에 들어온다. 그 두 단계가 §1.1의 초점이다. - **유형 2 — 등식까지 풀었지만 조건은 없이.** "$\sqrt{2} = \frac{a}{b}$인 정수 $a, b$가 존재한다"까지 정확히 적었다. 11주차 문제 20이 요구한 것은 여기까지이므로 그 자체로 완결이다. 이번 주의 증명은 이 줄에 조각 하나를 더 붙인다 — "기약분수로 잡을 수 있다". 그 조각이 왜 필요한지가 §1.8과 예제 2.2의 초점이다. - **유형 3 — 백지.** 첫 줄을 무엇으로 시작할지 몰라 적지 못했다. 귀류법의 첫 두 줄은 창작이 아니라 두 규칙의 기계적 적용이다 — 11주차 §1.3(부정 제작)과 정의 15.1(유리수의 정의). 이번 주는 그 기계적 절차를 서식으로 고정한다. ## 개념 — 귀류법의 구조 ### 1 부정형 결론에서 직접 증명이 어디서 막히는가 이번 주의 대표 명제는 "$\sqrt{2}$는 무리수이다"이다. 18주차까지 세운 도구 — 직접 증명과 대우 증명 — 만으로 밀어붙여 보자. :::{admonition} 시도 1 — 직접 증명으로 밀어붙이기 :class: quotebox 명제: $\sqrt{2}$는 무리수이다. "$\sqrt{2}$를 생각하자. 무리수의 정의(정의 15.1)에 의해 보여야 할 것은 $\sqrt{2}$가 유리수가 **아니라는** 것, 곧 $\sqrt{2} = \frac{a}{b}$인 정수 $a, b$($b \neq 0$)가 존재하지 **않는다**는 것이다. 따라서 … " ::: 여기서 멈춘다. 직접 증명의 몸통은 결론의 정의 꼴을 실제로 만들어 제시하는 과정인데, 만들라는 것이 "존재하지 않음"이다. 제시할 대상이 없으므로 다음 줄이 나오지 않는다. :::{admonition} 시도 2 — 대우로 갈아타기 :class: quotebox 대우 증명(19주차)은 "$P \Rightarrow Q$"의 $P$와 $Q$를 뒤집는 기법이다. 그런데 "$\sqrt{2}$는 무리수이다"에는 뒤집을 $P$도 $Q$도 없다 — 조건문이 아니기 때문이다. ::: :::{container} quotebox **확인 1.** 두 시도가 막힌 자리를 각각 한 문장으로 적어 보자. 두 막힘은 같은 것인가 다른 것인가. ::: :::{admonition} 답 :class: quotebox dropdown 직접 증명은 결론이 부정형이라 **만들 목표 꼴이 없어서** 막혔고, 대우 증명은 **뒤집을 조건문 구조 자체가 없어서** 막혔다. 두 막힘은 다르다. 18주차 §1의 진단 표가 이 중 앞의 것을 "부정형 결론의 막힘"이라 부르고 21주차의 소재로 넘긴 그 자리다. ::: :::{admonition} 이 주 전체의 기준 :class: quotebox 부정형 결론은 만들 목표 꼴이 없다. 그렇다면 결론을 부정해 **가정 쪽으로** 옮긴다. 부정형의 부정은 긍정형이고, 긍정형은 정의로 풀려 등식이 된다. ::: ### 2 부정을 가정으로 옮기면 무엇이 손에 들어오는가 기준을 세 명제에 실제로 적용해 보자. 각 행에서 부정을 만들고, 그 부정을 가정했을 때 손에 들어오는 것을 적는다. | **증명하려는 명제 $P$** | **부정 $\neg P$** | **$\neg P$를 가정하면 손에 들어오는 것** | |---|---|---| | $\sqrt{2}$는 무리수이다 | $\sqrt{2}$는 유리수이다 | $\sqrt{2} = \frac{a}{b}$인 정수 $a, b$ ($b \neq 0$) | | 가장 큰 정수는 존재하지 않는다 | $\underline{\quad(1)\quad}$ | 가장 큰 정수 — 이름을 $N$이라 붙일 수 있다 | | 소수는 무한히 많다 | 소수는 유한 개뿐이다 | $\underline{\quad(2)\quad}$ | | $x^2 = 4y+3$인 정수 $x, y$는 존재하지 않는다 | $\underline{\quad(3)\quad}$ | $\underline{\quad(4)\quad}$ | :::{container} quotebox **확인 2.** 빈칸 (1)(2)(3)(4)를 채우고, 셋째 열 전체에 공통으로 일어난 일을 한 문장으로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) 가장 큰 정수가 존재한다 (2) 소수 전체의 유한한 목록 $p_1, p_2, \dots, p_n$ (3) $x^2 = 4y+3$인 정수 $x, y$가 존재한다 (4) 그 등식을 만족하는 정수 $x, y$와 등식 $x^2 = 4y+3$. 공통으로 일어난 일: 부정하기 전에는 "없다$\cdot$아니다"여서 붙잡을 것이 없었는데, 부정한 뒤에는 **이름을 붙일 수 있는 대상과 전개할 수 있는 등식**이 되었다. 셋째 열에 해당하는 것이 곧 증명의 재료다. ::: 이 절차에 정식 이름과 형식을 붙인다. 절차 자체에 새로운 것은 없다 — 방금 표에서 한 일(결론을 부정해 가정 자리에 놓기)을 문장으로 굳혔을 뿐이다. ### 정의 21.1 — 귀류법 (proof by contradiction) [백지 암기 대상] :::{container} quotebox 명제 $P$를 **귀류법**으로 증명한다는 것은 다음 세 단계를 밟는다는 뜻이다. ① $\neg P$를 가정한다. ② 논리를 전개해, 어떤 명제 $C$에 대해 $C \land \neg C$를 얻는다. ③ $C \land \neg C$는 항상 거짓이므로 그것을 유도한 가정 $\neg P$가 거짓이다. 따라서 $P$가 참이다. ::: $C \land \neg C$처럼 어떤 상황에서도 거짓인 명제를 **모순**(contradiction)이라 한다 — 7주차 §3에서 두 행짜리 진리표로 확인한 그 명제다. $C \land \neg C$는 "씨 그리고 씨가 아니다"로 읽는다. 읽는 법까지가 정의다. 라틴어 이름 reductio ad absurdum도 같은 절차를 가리킨다. ### 3 정의 해부 — 조각마다 하는 일 정의 21.1은 네 조각으로 되어 있고, 조각마다 증명에서 맡는 역할이 다르다. | **조각** | **하는 일** | **증명에서의 역할** | |---|---|---| | "$\neg P$를 가정한다" | 출발점 제공 | 부정형 결론이 긍정형 가정으로 바뀌어 정의로 풀린다 — §1.1의 막힘이 풀리는 자리 | | "논리를 전개해" | 몸통 | 직접 증명과 한 줄도 다르지 않다. 각 줄의 근거는 여전히 ①~④뿐이다 | | "$C \land \neg C$를 얻는다" | 도착점 지정 | 도착할 곳이 **아무 모순이나**이므로 방향이 하나로 정해지지 않는다 | | "따라서 $P$가 참이다" | 원명제 회수 | ①~③을 원래 주장으로 되돌린다. 근거는 §1.4의 진리표 | **조각 삭제 실험.** 셋째 조각의 "$C \land \neg C$"를 "어딘가 어색한 결과"로 완화해 보자. 예제 2.2의 전개를 따라가면 "$a$와 $b$가 둘 다 짝수"라는 문장이 나오는데, 여기서 멈추고 "이상하다"고 적으면 증명이 끝나는가. 끝나지 않는다 — $\frac{4}{2}$처럼 분자와 분모가 둘 다 짝수인 표현은 유리수의 정당한 표현이므로 그 자체로는 거짓이 아니다. 무너지는 것은 도착점의 자격이다. 모순은 "이상함"이 아니라 **한 명제와 그 부정이 동시에 성립함**이다. :::{container} quotebox **확인 3.** 위 실험에서 "$a$와 $b$가 둘 다 짝수"가 모순이 되려면, 증명이 미리 무엇을 선언해 두어야 하는가. ::: :::{admonition} 답 :class: quotebox dropdown 첫머리에 "$\frac{a}{b}$를 기약분수로 잡는다"를 선언해 두어야 한다. 그러면 $C$ = "2는 $a$와 $b$의 공통 약수가 아니다"(공통 약수가 $\pm 1$뿐이고 $2 \neq \pm 1$이므로 따라온다), $\neg C$ = "2는 $a$와 $b$의 공통 약수이다"(전개에서 얻은 것)가 되어 $C \land \neg C$가 문자 그대로 완성된다. 모순은 저절로 생기지 않는다 — 충돌할 상대를 미리 설치해 두는 것이 귀류법 설계의 절반이다. 문제 3(c)가 이 조각의 하중을 다시 확인한다. ::: **조각 변형 실험.** 첫째 조각의 $\neg P$를 부정확하게 만들어 보자. "$\sqrt{2}$는 무리수이다"의 부정을 "$\sqrt{2}$는 정수이다"로 적고 시작하면 어떻게 되는가 (유리수를 정수로 좁혀 부정한 전형적 오류다). :::{container} quotebox **확인 4.** 부정을 $\neg P$가 아닌 다른 명제 $R$로 잘못 만들면, 모순을 이끌어낸 뒤 실제로 증명되는 것은 무엇인가. ::: :::{admonition} 답 :class: quotebox dropdown $\neg R$이다 — $P$가 아니다. 위 예에서 증명되는 것은 "$\sqrt{2}$는 정수가 아니다"뿐이고, 그것은 무리수라는 결론과 다른 주장이다($\frac{3}{2}$은 정수가 아니지만 유리수다). 11주차의 부정 제작이 귀류법의 **첫 줄에서** 소비되는 이유가 이것이다. 첫 줄이 틀리면 뒤의 모든 줄이 옳아도 다른 명제를 증명한 답안이 된다. ::: ### 4 왜 이것이 증명이 되는가 ②가 실제로 증명한 것은 조건문 "$\neg P \Rightarrow (C \land \neg C)$"이다. $C \land \neg C$는 어떤 상황에서도 거짓이므로 이 조건문의 결론 자리는 항상 F다. 조건문은 가정이 T이고 결론이 F인 경우에만 F이므로(8주차 정의 8.1), 결론이 F인 조건문이 참이려면 가정이 F여야 한다. | **$P$** | **$\neg P$** | **$C \land \neg C$** | **$\neg P \Rightarrow (C \land \neg C)$** | |---|---|---|---| | T | F | F | T | | F | T | F | F | :::{container} quotebox **확인 5.** 위 표의 마지막 열과 첫 열을 비교해 보자. 두 열이 같다는 것은 무엇을 뜻하는가. ::: :::{admonition} 답 :class: quotebox dropdown "$\neg P$에서 모순이 유도된다"는 명제와 "$P$이다"는 명제가 모든 행에서 진리값이 같다 — 9주차의 뜻으로 **동치**다. 그러므로 앞의 것을 보이면 뒤의 것을 보인 것이다. 귀류법이 새로운 논리를 도입하는 것이 아니라 이미 세운 동치 하나를 쓰는 것임이 이 두 행에 전부 들어 있다. 문제 2가 이 표를 직접 작성하는 자리다. ::: ### 5 서식 :::{admonition} 백지 암기 대상 :class: keybox **귀류법의 서식** **명제.** $P$이다. **증명.** 모순을 이끌어내기 위해, $P$가 거짓이라고 가정하자. (이 자리에서 $\neg P$를 11주차 부정 규칙으로 정확히 서술한다.) $\quad\vdots$ 이는 ~와 모순이다. 따라서 $P$이다. $\blacksquare$ ::: 서식 포인트 두 가지. - **첫 문장에서 기법을 선언한다.** "모순을 이끌어내기 위해"가 없으면, 뒤따르는 $\neg P$가 저자가 참이라고 믿는 문장으로 읽힌다 — 증명하려는 것과 정반대다. - **마지막 줄에서 충돌한 두 문장을 지목한다.** "모순이다"만 적고 무엇과 무엇이 충돌했는지 적지 않으면 도착점이 확인되지 않는다. 지목할 두 문장이 $C$와 $\neg C$다. :::{container} quotebox **확인 6.** 어떤 답안이 "$\sqrt{2} = \frac{a}{b}$라 하자"로 시작한다. 서식상 무엇이 빠졌고, 그 결과 이 줄은 어떻게 읽히는가. ::: :::{admonition} 답 :class: quotebox dropdown "모순을 이끌어내기 위해 $\sqrt{2}$가 유리수라고 가정하자"라는 선언이 빠졌다. 그 문장이 없으면 "$\sqrt{2} = \frac{a}{b}$"는 저자가 참으로 주장하는 등식으로 읽힌다. 기법 선언은 장식이 아니라 뒤에 오는 모든 줄의 지위를 정하는 문장이다. ::: ### 6 언제 귀류법을 고르는가 — 신호 [백지 암기 대상] | **신호** | **이유** | |---|---| | 결론이 "~는 무리수" 등 부정형 개념 | 부정을 가정하면 "유리수 $= \frac{a}{b}$"라는 전개 가능한 등식이 생긴다 | | "**존재하지 않는다** / ~일 수 없다" | 부정("존재한다")을 가정하면 그 대상이 손에 들어온다 — 그 대상을 재료로 모순을 만든다 | | "가장 큰/작은 ~는 **없다**" | 부정하면 최대$\cdot$최소인 대상 $M$이 생긴다 — 그보다 크거나 작은 것을 만들어 최대$\cdot$최소성과 충돌시킨다 | | "**무한히 많다**" | 부정("유한 개뿐")하면 전체 목록을 손에 쥔다 — 목록 밖의 대상을 만들어 목록의 완전성과 충돌시킨다 | 공통 원리: **부정형$\cdot$비존재형 결론은 목표 꼴이 없어 직접 증명이 막히지만 (18주차 문제 20), 부정을 가정으로 돌리면 그 자리가 재료가 된다.** :::{container} quotebox **확인 7.** 다음 셋 중 귀류법의 신호가 있는 것은 어느 것인가. (가) 짝수와 짝수의 합은 짝수이다 (나) $\sqrt{3}$은 무리수이다 (다) 가장 작은 양의 유리수는 존재하지 않는다. ::: :::{admonition} 답 :class: quotebox dropdown (나)와 (다). (가)는 결론이 긍정형이고 목표 꼴 $2 \times (\text{정수})$이 그대로 만들어지므로 직접 증명이 최단이다(1주차 예제 2.1). 신호가 없는 명제에 귀류법을 쓰는 것이 틀린 증명이 되지는 않지만, 첫 줄과 마지막 줄만 늘고 몸통은 직접 증명과 같아진다. 기법 선택의 우선순위는 22주차에서 정한다. ::: ### 7 대우 증명과 무엇이 다른가 — 도착점 두 기법은 모두 "결론의 부정을 재료로 삼는다"는 점이 같다. 다른 것은 도착점이다. | | **대우 증명 (19주차)** | **귀류법 (이번 주)** | |---|---|---| | 적용 대상 | 조건문 $P \Rightarrow Q$만 | 아무 명제나 | | 가정하는 것 | $\neg Q$ | $\neg P$ (증명하려는 명제 전체의 부정) | | 도착점 | $\neg P$ 하나로 고정 | 아무 모순이나 | | 방향 | 시작 전에 정해진다 | 시작 전에 정해지지 않는다 | :::{container} quotebox **확인 8.** 도착점이 정해져 있지 않다는 성질이 장점인 이유와 단점인 이유를 각각 한 문장으로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown 장점 — 어느 방향의 충돌이든 이용할 수 있으므로 적용 범위가 가장 넓다 (예제 2.1은 부등식 충돌, 예제 2.2는 약분 가능성 충돌, 예제 2.3은 나누어떨어짐 충돌로 서로 다르다). 단점 — 목표가 없으므로 전개가 어디로 가는지 모른 채 밀고 나가야 하고, 모순이 나오지 않는 길로 오래 갈 수 있다. 문제 18과 문제 20이 이 단점을 정면으로 다룬다. ::: ### 8 부품 준비 — 기약분수와 소수 약수 이번 주의 두 대표 증명은 이번 주에 증명하지 않는 사실 두 개를 쓴다. 어느 것이 빌려 쓰는 것인지 미리 못 박아 둔다. ### 정의 21.2 — 기약분수 (reduced fraction) [백지 암기 대상] :::{container} quotebox 정수 $a, b$($b \neq 0$)에 대해, 분수 $\dfrac{a}{b}$가 **기약분수**라는 것은 $a$와 $b$의 공통 약수가 $\pm 1$뿐이라는 뜻이다. ::: :::{admonition} 빌려 쓰는 사실 1 :class: quotebox 모든 유리수는 기약분수로 나타낼 수 있다. ::: 직관은 이렇다. 공약수가 남아 있으면 약분하면 되고, 약분할 때마다 분모의 절댓값이 줄어드므로 언젠가 끝난다. "언젠가 끝난다"를 엄밀하게 말하려면 33주차의 최소원리가 필요하다 — 지금은 사실로 인정하고 쓴다(33주차에서 증명한다). :::{admonition} 빌려 쓰는 사실 2 :class: quotebox 2 이상의 모든 정수는 소수인 약수를 가진다. ::: 이것도 33주차의 강한 귀납법에서 증명한다 — 지금은 인정하고 쓴다. :::{container} quotebox **확인 9.** $\frac{12}{18}$은 기약분수인가. 정의 21.2로 판정하고, 같은 유리수의 기약분수 표현을 하나 제시해 보자. ::: :::{admonition} 답 :class: quotebox dropdown 기약분수가 아니다. $12 = 6 \times 2$, $18 = 6 \times 3$이므로 6이 공통 약수이고, $\pm 1$ 말고도 $\pm 2, \pm 3, \pm 6$이 공통 약수다. 분자와 분모를 6으로 나누면 $\frac{12}{18} = \frac{2}{3}$이고, 2와 3의 공통 약수는 $\pm 1$뿐이므로 $\frac{2}{3}$이 기약분수 표현이다. 같은 유리수에 표현이 여러 개 있고 그중 기약인 것을 **골라 쓸 수 있다**는 것이 빌려 쓰는 사실 1의 내용이다. ::: ### 9 근거 목록 갱신 — 칸은 그대로 네 개 | **근거** | **이번 주의 내용** | **이번 주에는 이렇게 쓴다** | |---|---|---| | ① 정의 | 정의 15.1(유리수$\cdot$무리수), 정의 20.1(합동), **정의 21.2(기약분수)** | "유리수" $\leftrightarrow$ "$\frac{a}{b}$ 꼴" 사이를 번역한다 | | ② 닫힘성 | 정수의 합$\cdot$차$\cdot$곱은 정수 | "$N + 1$은 정수이므로"를 별도 설명 없이 쓴다 | | ③ 등식$\cdot$부등식의 성질 | 양변 제곱 / 대입 / 양변을 같은 수로 더하기$\cdot$나누기, 부등호의 부정($\le$의 부정은 $>$, 11주차 §1.3) | $\sqrt{2} = \frac{a}{b}$의 양변을 제곱한다 | | ④ 이미 증명한 명제 | 19주차 예제 2.1($2 \mid n^2 \Rightarrow 2 \mid n$)$\cdot$예제 2.2($3 \mid n^2 \Rightarrow 3 \mid n$)$\cdot$문제 15($5 \mid n^2 \Rightarrow 5 \mid n$)$\cdot$문제 8($n^3$ 짝수 $\Rightarrow n$ 짝수), 20주차 문제 13($2 \mid x$이고 $3 \mid x$이면 $6 \mid x$), 15주차 유리수 닫힘성 다섯 개, 2주차 문제 17, 17주차 문제 9, 1주차 문제 16 | "19주차 예제 2.1에 의해 $a$는 짝수이다" | 여기에 빌려 쓰는 사실 두 개(기약분수 표현, 소수 약수의 존재)를 목록 옆에 따로 적어 둔다 — 지금은 인정하고 쓰되 33주차에서 증명해 회수할 항목이라는 표시다. 17주차부터 같은 자격으로 써 온 나눗셈 정리(몫과 나머지의 존재와 유일성)도 이 옆자리에 둔다 — 문제 19가 그 나머지의 유일성을 근거로 쓴다. **귀류법은 목록에 칸을 늘리지 않는다.** 귀류법이 바꾸는 것은 증명의 뼈대 (어디서 출발해 어디로 가는가)이지 각 줄의 근거가 아니다. $\neg P$를 가정한 뒤의 몸통은 직접 증명과 한 줄도 다르지 않다. :::{container} quotebox **확인 10.** "$\sqrt{2} = \frac{a}{b}$의 양변을 제곱해 $2 = \frac{a^2}{b^2}$을 얻는다"는 줄의 근거는 몇 번인가. ::: :::{admonition} 답 :class: quotebox dropdown 근거 ③ 등식의 성질(양변에 같은 연산). 이어서 $2b^2 = a^2$으로 정리하는 것도 같은 ③이다. 귀류법을 쓰는 중이어도 각 줄의 근거는 평소와 같다 — 달라진 것은 첫 줄에 무엇을 놓았는가뿐이다. ::: 정의 21.1과 21.2, 서식(§1.5), 신호 표(§1.6)가 [백지 암기 대상]이다. 문장을 통째로만 외우면 일부를 잊었을 때 복구할 길이 없으므로, §1.3의 조각별 이유와 함께 외운다. 조각을 잊어도 이유에서 재구성할 수 있다.