# 21주차 · 강의 — 예제 · 연습 · 해설 ## 예제 — 귀류법 증명을 함께 만들기 완성된 증명을 먼저 보이지 않는다. 예제 2.1은 설계부터 한 줄씩 함께 만들고, 예제 2.2는 설계만 함께 하고, 예제 2.3은 설계부터 스스로 한다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다. ### 예제 2.1 — 가장 큰 정수는 존재하지 않는다 **명제.** 가장 큰 정수는 존재하지 않는다. **설계 — 쓰기 전에 정하는 세 가지.** 직접 증명에서는 출발점과 도착점 두 가지를 정했다(1주차 예제 2.1의 번역표). 귀류법에서는 세 가지다 — 무엇을 부정할 것인가, 그 부정이 주는 출발점은 무엇인가, 도착점은 어디인가. | | **말** | **번역** | |---|---|---| | 원래 목표 $P$ | 가장 큰 정수는 존재하지 않는다 | 만들 목표 꼴이 없다 — 직접 증명이 막힌다 | | 가정할 것 $\neg P$ | $\underline{\quad(1)\quad}$ | 그 대상에 이름을 붙여 $N$이라 놓는다 | | 출발점 | $N$이 가장 크다는 것 | 모든 정수 $n$에 대해 $n \le N$ | | 도착점 | 아무 모순이나 | 어떤 $C$에 대해 $C \land \neg C$ | :::{container} quotebox **확인 11.** 표의 빈칸 (1)을 채워 보자. "존재하지 않는다"의 부정은 11주차 총목록의 어느 줄에서 나오는가. ::: :::{admonition} 답 :class: quotebox dropdown (1) "가장 큰 정수가 존재한다." 11주차 §1.3 총목록의 $\exists$ 줄을 거꾸로 읽은 것이다 — 원문이 "존재하지 않는다"($\neg \exists$)이므로 그것을 다시 부정하면 이중부정이 풀려 "존재한다"가 된다. ::: **1단계 — 부정을 선언하고 대상에 이름을 붙인다.** 부정을 가정하는 순간 "가장 큰 정수"라는 대상이 생긴다. 이름이 없으면 그 대상으로 계산할 수 없다. :::{container} quotebox **확인 12.** 첫 문장을 완성해 보자: "모순을 이끌어내기 위해, $\underline{\qquad}$고 가정하고 그것을 $N$이라 하자." ::: :::{admonition} 답 :class: quotebox dropdown "가장 큰 정수가 존재한다"고 가정하고 그것을 $N$이라 하자. 존재 가정에서 대상을 받아 문자로 놓는 이 동작은, 정의에서 "정수 $k$가 존재한다"를 풀어 $k$를 받아 오던 것(1주차 §1.3의 '존재한다' 표)과 같은 동작이다. ::: **2단계 — 가정이 준 것을 문장으로 적는다.** "$N$이 가장 큰 정수"라는 말이 무슨 뜻인지 풀어 둔다. 말로만 두면 계산이 시작되지 않는다. :::{container} quotebox **확인 13.** "$N$은 가장 큰 정수이다"를 부등식으로 풀어 보자: "모든 정수 $n$에 대해 $\underline{\qquad}$이다." ::: :::{admonition} 답 :class: quotebox dropdown $n \le N$. 이 부등식이 이 증명에서 충돌시킬 상대다. 최대$\cdot$최소를 가정하는 유형에서는 이 줄을 반드시 명시적으로 적는다 — 충돌할 상대를 미리 설치하는 것이 §1.3 확인 3에서 확인한 설계다. ::: **3단계 — 모순 후보를 만든다.** 도착점은 아무 모순이나이지만, 지금 손에 있는 문장이 "모든 정수 $n$에 대해 $n \le N$"이므로 그것을 깨는 정수 하나를 만들면 된다. :::{container} quotebox **확인 14.** $N$보다 큰 정수를 하나 만들어 보자. 그것이 **정수**임의 근거는 몇 번인가. ::: :::{admonition} 답 :class: quotebox dropdown $N + 1$. $N$과 1이 정수이므로 합 $N + 1$도 정수다 — 근거 ② 닫힘성. 그리고 $N + 1 > N$이다. 만든 대상이 정수라는 확인이 빠지면 2단계의 문장("모든 **정수** $n$에 대해")과 맞물리지 않아 충돌이 성립하지 않는다. 만드는 대상이 가정이 말하는 범위에 속하는지 확인하는 줄은 이 유형에서 늘 필요하다(문제 4, 문제 9에서 반복된다). ::: **4단계 — 충돌한 두 문장을 지목한다.** :::{container} quotebox **확인 15.** 이 증명에서 $C$와 $\neg C$에 해당하는 문장을 각각 지목해 보자. ::: :::{admonition} 답 :class: quotebox dropdown $C$ = "$N + 1 \le N$" (2단계의 문장을 $n = N + 1$에 적용한 것), $\neg C$ = "$N + 1 > N$" (3단계에서 만든 것). 두 문장이 동시에 성립하므로 $C \land \neg C$가 완성됐다. 답안에 적을 때는 "이는 $N$이 가장 크다는 가정과 모순이다"로 줄여도 되지만, 줄이더라도 무엇과 무엇이 충돌했는지는 남겨 둔다. ::: **5단계 — 원명제를 회수한다.** :::{container} quotebox **확인 16.** 마지막 문장을 완성해 보자: "따라서 가정이 거짓이므로, $\underline{\qquad}$. $\blacksquare$" ::: :::{admonition} 답 :class: quotebox dropdown "가장 큰 정수는 존재하지 않는다." 이 한 줄의 근거는 §1.4의 진리표다 — $\neg P$에서 모순이 나왔으므로 $P$가 참이다. ::: **완성본.** 방금 만든 다섯 문장을 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 "왜?"에 스스로 답해 본다. | 증명의 한 줄 | 왜 이 줄을 쓰는가? | |---|---| | 모순을 이끌어내기 위해, 가장 큰 정수가 존재한다고 가정하고 그것을 $N$이라 하자. | 기법 선언 + 부정 제작 + 이름 붙이기. 이름이 없으면 다음 줄에서 계산할 대상이 없다. | | 그러면 모든 정수 $n$에 대해 $n \le N$이다. | 가정이 준 것을 부등식으로 풀어 둔다. 이 줄이 뒤에서 충돌할 상대다. | | $N$과 1은 정수이므로 $N + 1$도 정수이고(근거 ②), $N + 1 > N$이다. | 도착점을 향해 모순 후보를 만든다. 정수임의 확인이 빠지면 앞 줄과 맞물리지 않는다. | | 둘째 줄을 $n = N + 1$에 적용하면 $N + 1 \le N$인데, 이는 $N + 1 > N$과 동시에 성립할 수 없다. 모순이다. | 충돌한 두 문장을 지목한다 — $C \land \neg C$의 완성. | | 따라서 가정이 거짓이므로, 가장 큰 정수는 존재하지 않는다. $\blacksquare$ | §1.4의 진리표로 원명제를 회수한다. | **이 다섯 줄이 특정한 $N$에 의존하지 않는 이유.** 완성본의 $N$에 구체적인 값을 넣어 읽어 보자. :::{container} quotebox **확인 17.** $N = 100$일 때 셋째 줄과 넷째 줄은 각각 어떤 문장이 되는가. $N = -3$이면 어떤가. ::: :::{admonition} 답 :class: quotebox dropdown $N = 100$: "101은 정수이고 $101 > 100$이다", "$101 \le 100$인데 $101 > 100$이다". $N = -3$: "$-2$는 정수이고 $-2 > -3$이다", "$-2 \le -3$인데 $-2 > -3$이다". 어느 값을 넣어도 모든 줄이 그대로 성립한다 — 증명의 어느 줄도 $N$이 특정 정수라는 사실을 쓰지 않았고, 쓴 것은 "정수"라는 자격뿐이기 때문이다. 다만 $N$은 결론적으로 **존재하지 않는** 대상이다. 존재하지 않는 것에 이름을 붙여도 되는 이유는, 이 증명이 하는 일이 정확히 "그런 이름을 붙일 수 있다고 치면 무너진다"를 보이는 것이기 때문이다. ::: ### 예제 2.2 — $\sqrt{2}$는 무리수이다 **명제.** $\sqrt{2}$는 무리수이다. 이번에는 설계만 함께 하고, 본문은 완성본으로 본다. :::{container} quotebox **확인 18.** 번역표를 채워 보자. 가정할 것 $\neg P$: $\sqrt{2}$는 $\underline{\quad(1)\quad}$이다. 출발점: $\sqrt{2} = \underline{\quad(2)\quad}$인 정수 $a, b$($b \neq 0$)가 존재하며, 게다가 $\underline{\quad(3)\quad}$로 잡을 수 있다. 도착점: 아무 모순이나. ::: :::{admonition} 답 :class: quotebox dropdown (1) 유리수 (2) $\frac{a}{b}$ (3) 기약분수. 셋째 칸이 이 증명의 설계다. §1.3 확인 3에서 본 대로, 충돌할 상대를 첫머리에 설치해 두지 않으면 마지막 줄에서 충돌시킬 것이 없다. 그 상대를 공급하는 것이 빌려 쓰는 사실 1(모든 유리수는 기약분수로 나타낼 수 있다)이다. ::: :::{container} quotebox **확인 19.** 출발점의 등식 $\sqrt{2} = \frac{a}{b}$에는 근호가 있다. 정수의 언어로 계산하려면 먼저 무엇을 하는가. ::: :::{admonition} 답 :class: quotebox dropdown 양변을 제곱한다(근거 ③). $2 = \frac{a^2}{b^2}$, 곧 $a^2 = 2b^2$. 근호가 사라지고 정수만 남는 등식이 되었다 — 이제부터는 1주차와 2주차의 도구가 그대로 통한다. 근호를 없애는 이 한 걸음이 무리수 논증의 표준 절차다 (문제 7, 15, 17이 각각 제곱과 세제곱으로 이 걸음을 반복한다). ::: **완성본.** | 증명의 한 줄 | 왜 이 줄을 쓰는가? | |---|---| | 모순을 이끌어내기 위해, $\sqrt{2}$가 유리수라고 가정하자. | 기법 선언 + 부정 제작. "무리수"의 부정은 "유리수"다(정의 15.1). 11주차 문제 20이 이 한 줄이었다. | | 그러면 $\sqrt{2} = \frac{a}{b}$인 정수 $a, b$($b \neq 0$)가 존재하며, 기약분수로 잡을 수 있다 — 곧 $a$와 $b$의 공통 약수는 $\pm 1$뿐이다. | 유리수의 정의를 풀고(근거 ①), 빌려 쓰는 사실 1로 기약 조건을 붙인다. 이 조건이 마지막 줄에서 충돌할 상대다. | | 양변을 제곱하면 $2 = \frac{a^2}{b^2}$, 곧 $a^2 = 2b^2$이다. | 근호를 없애고 정수 세계의 등식으로 옮긴다(근거 ③). | | $a^2 = 2b^2$은 $2 \times (\text{정수})$ 꼴이므로 짝수이고, 따라서 $a$는 짝수이다 (19주차 예제 2.1). | 대우로 증명해 둔 명제를 부품으로 쓴다(근거 ④). "$a^2$이 짝수이면 $a$가 짝수"는 정의만으로는 나오지 않는다. | | $a = 2c$인 정수 $c$가 존재한다. 대입하면 $4c^2 = 2b^2$, 곧 $b^2 = 2c^2$이다. | 짝수의 정의를 풀고(근거 ①) 대입한 뒤 양변을 2로 나눈다(근거 ③). | | $b^2 = 2c^2$도 짝수이므로 $b$도 짝수이다 (같은 부품). | 같은 명제를 $b$에 한 번 더 적용한다. 이제 $a$와 $b$가 둘 다 짝수다. | | $a$와 $b$가 모두 짝수이면 2가 공통 약수인데, 이는 공통 약수가 $\pm 1$뿐이라는 것과 동시에 성립할 수 없다. 모순이다. 따라서 $\sqrt{2}$는 무리수이다. $\blacksquare$ | 둘째 줄과 충돌 — $C$ = "2는 공통 약수가 아니다"(기약 조건에서 따라온다), $\neg C$ = "2는 공통 약수이다". 원명제 회수. | **구조 읽기.** 이 증명에서 "기약"은 장식이 아니다. 그 조각이 없으면 마지막 줄에 남는 것은 "$a$와 $b$가 둘 다 짝수"라는 문장 하나뿐이고, 그 문장은 그 자체로 거짓이 아니다. 그리고 19주차 예제 2.1은 두 번 소비된다 — $a$에 한 번, $b$에 한 번. 두 곳 모두 근거를 적어야 한다. ### 예제 2.3 — 소수는 무한히 많다 **명제.** 소수는 무한히 많다. 이번에는 설계부터 스스로 해 보자. :::{container} quotebox **확인 20.** 가정할 것 $\neg P$는 무엇이고, 그 가정이 손에 쥐여 주는 것은 무엇인가. ::: :::{admonition} 답 :class: quotebox dropdown $\neg P$ = "소수는 유한 개뿐이다". 손에 들어오는 것은 소수 **전체의 목록** $p_1, p_2, \dots, p_n$이다. 유한 개라는 가정이 없으면 "전부를 나열했다"고 적을 수 없다 — 이 목록이 이 증명의 재료 전부이고, 도착점은 목록의 완전성과의 충돌이 된다. ::: :::{container} quotebox **확인 21.** 목록 $p_1, \dots, p_n$의 어느 소수로도 나누어떨어지지 않는 수를 만들려 한다. 곱 $p_1 p_2 \cdots p_n$에 무엇을 더하면 되는가. 그렇게 만든 수를 $p_i$로 나눈 나머지는 얼마인가. ::: :::{admonition} 답 :class: quotebox dropdown 1을 더한다. $N = p_1 p_2 \cdots p_n + 1$을 $p_i$로 나누면 앞의 곱은 $p_i$의 배수이므로 나머지는 1이다. "목록의 어느 것으로도 나누어떨어지지 않는 수"를 만드는 것이 이 증명의 설계이고, 그 수의 소수 약수가 목록 밖에 있을 수밖에 없다는 것이 충돌의 내용이다. ::: **증명.** 모순을 이끌어내기 위해, 소수가 유한 개뿐이라고 가정하고 그 전부를 $p_1, p_2, \dots, p_n$이라 하자. 수 $$ N = p_1 p_2 \cdots p_n + 1 $$ 을 생각하자. $N \ge 2$이므로 $N$은 소수인 약수 $p$를 가진다(빌려 쓰는 사실 2). $p$는 소수이고 목록이 소수 전부이므로, 어떤 $i$에 대해 $p = p_i$이다. 그러면 $p \mid N$이고, 또 $p$는 곱 $p_1 p_2 \cdots p_n$의 인수 중 하나이므로 $p \mid p_1 p_2 \cdots p_n$이다(2주차 훈련 1). 따라서 2주차 문제 17 ($a \mid (b + c)$이고 $a \mid b$이면 $a \mid c$)에 의해 $$ p \mid \big(N - p_1 p_2 \cdots p_n\big) = 1 $$ 이다. 그러나 $p$는 소수이므로 $p \ge 2$이고, $p \mid 1$이려면 $1 = pc$인 정수 $c$가 있어야 하는데 그러면 $|p| \cdot |c| = 1$이고 $|c| \ge 1$이므로 $|p| \le 1$이 되어 $p \ge 2$와 어긋난다. 모순이다. 따라서 소수는 무한히 많다. $\blacksquare$ 이번 증명은 표 없이 **산문**으로 적었다. 표는 연습 단계의 장치이고, 실전의 증명은 처음부터 끝까지 이런 산문이다. **흔한 오해 교정.** 이 증명은 $N$ 자체가 소수라고 주장하지 **않는다**. 실제로 $$ 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \times 509 $$ 로 $N$이 합성수인 사례가 있다. 논증이 말하는 것은 "$N$의 소수 약수가 목록 안에 있을 수 없다"는 것 — 곧 목록이 완전할 수 없다는 것이다. 위 사례에서도 소수 약수 59와 509는 둘 다 목록 $2, 3, 5, 7, 11, 13$ 밖에 있다. 문제 13의 채점 기준에 이 구분이 들어간다. ### 관찰 — 세 증명의 같은 뼈대 예제 2.1, 2.2, 2.3은 소재가 각각 순서$\cdot$분수$\cdot$소수로 전혀 다르다. 대응표의 빈칸을 채워 뼈대를 비교해 보자. | **단계** | **예제 2.1** | **예제 2.2** | **예제 2.3** | |---|---|---|---| | ① 부정 가정 + 이름 붙이기 | 가장 큰 정수가 존재한다 — 그것을 $N$이라 하자 | $\underline{\quad(1)\quad}$ | 소수가 유한 개뿐이다 — 전부를 $p_1, \dots, p_n$이라 하자 | | ② 재료 전개 + 모순 후보 제작 | 모든 정수 $n$에 대해 $n \le N$; $N + 1$을 만든다 | $a^2 = 2b^2$에서 $a$와 $b$가 모두 짝수임을 유도 | $\underline{\quad(2)\quad}$ | | ③ 충돌 지목 + 원명제 회수 | $\underline{\quad(3)\quad}$ | 공통 약수 2 vs 공통 약수는 $\pm 1$뿐 | $p \mid 1$ vs $p \ge 2$ | :::{container} quotebox **확인 22.** 표의 빈칸 (1)(2)(3)을 채워 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) $\sqrt{2}$가 유리수이다 — $\sqrt{2} = \frac{a}{b}$(기약)로 놓자. (2) $N = p_1 \cdots p_n + 1$을 만들고 그 소수 약수 $p$를 잡아 $p \mid 1$을 유도한다. (3) $N + 1 \le N$ vs $N + 1 > N$. 세 증명 모두 정확히 이 세 걸음이다. ::: 방금 확인한 뼈대에 이름을 붙인다. :::{admonition} 백지 암기 대상 :class: keybox **귀류법의 3단계 틀** ① $\neg P$를 가정하고, 그 가정이 주는 대상에 이름을 붙인다 $\to$ ② 가정이 준 재료로 전개해 모순 후보를 만든다 $\to$ ③ 충돌한 두 문장을 지목하고 원명제를 회수한다 ::: 22주차에서는 이 틀이 조건문 $P \Rightarrow Q$에 적용될 때 ①이 어떻게 바뀌는지를 본다. ## 빈칸 사다리 — 지지대를 하나씩 빼며 필사에서 자립으로 넘어가는 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 해설(§6)에 있다 — 다 채운 뒤에 대조한다. ### 훈련 1 ●○○ — 수식 빈칸 **명제.** 유리수와 무리수의 합은 무리수이다. **증명.** 모순을 이끌어내기 위해, 유리수 $x$와 무리수 $y$에 대해 $x + y$가 $\underline{\quad(1)\quad}$라고 가정하자. 그러면 $$ y = (x + y) - x $$ 는 유리수에서 유리수를 뺀 것이므로 $\underline{\quad(2)\quad}$이다 (15주차 문제 9: 두 유리수의 차는 유리수). 이는 $y$가 $\underline{\quad(3)\quad}$라는 가정과 모순이다. 따라서 $x + y$는 무리수이다. $\blacksquare$ ### 훈련 2 ●●○ — 수식과 근거를 함께 이번에는 구조 낱말과 근거 문장도 빈칸이다. **명제.** 유리수 $r$과 무리수 $y$에 대해 $y - r$은 무리수이다. **증명.** 모순을 이끌어내기 위해, $y - r$이 $\underline{\quad(1)\quad}$라고 가정하고 그것을 $q$라 하자. 그러면 $$ y = q + \underline{\quad(2)\quad} $$ 이고, $\underline{\quad(3)\quad}$이므로 $y$는 유리수이다. 이는 $\underline{\quad(4)\quad}$과 모순이다. 따라서 $\underline{\quad(5)\quad}$. $\blacksquare$ ### 훈련 3 ●●● — 뼈대만 남기고 이번에는 3단계 틀(§2 관찰)의 각 칸을 통째로 채운다. **명제.** $6n + 3 = 2m$을 만족하는 정수 $n, m$은 존재하지 않는다. **증명의 뼈대.** - ① 부정 가정과 이름 붙이기: $\underline{\quad(1)\quad}$ - ② 재료 전개와 모순 후보 제작: $\underline{\quad(2)\quad}$ - ③ 충돌 지목과 원명제 회수: $\underline{\quad(3)\quad}$ (좌변과 우변의 홀짝을 각각 판정하면 된다. "어떤 정수도 짝수이면서 동시에 홀수일 수는 없다"는 지금은 인정하고 쓴다 — 22주차 문제 5에서 증명한다. 이 훈련이 문제 12의 예행연습이다.) ## 연습문제 (20문항) 해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 '접근'까지만 읽고 다시 시도한다 $\to$ 그래도 안 되면 풀이를 읽는다. :::{admonition} 이번 주의 채점 기준 :class: quotebox 답이 아니라 **근거**가 점수다. "$\sqrt{3}$은 무리수다(맞음)"는 0점이고, 첫 줄에 정확한 부정을 선언하고 마지막 줄에 충돌한 두 문장을 지목한 증명이 만점이다. 귀류법 답안에서 가장 자주 비는 칸이 정확히 그 두 군데다 — 첫 줄의 "모순을 이끌어내기 위해 ~라고 가정하자"와 마지막 줄의 "무엇과 무엇이 모순인지". 난이도와 무관하게, 힌트 상자는 5분 이상 막힌 뒤에만 연다. ::: ### 기본 ●○○ **1.** 다음 명제를 귀류법으로 증명한다면 첫 문장에 가정할 내용을 정확히 쓰시오 (증명 불필요). (a) $\sqrt{3}$은 무리수이다. (b) 가장 작은 양의 유리수는 존재하지 않는다. (c) $x^2 = 4y + 3$을 만족하는 정수 $x, y$는 존재하지 않는다. :::{admonition} 힌트 :class: quotebox dropdown 세 항목 모두 §1.5 서식의 첫 문장을 채우는 일이다. (b)(c)의 "존재하지 않는다"는 11주차 총목록의 $\exists$ 줄을 거꾸로 읽는다 — 부정하면 "존재한다"가 되고, 존재한다고 가정하는 순간 그 대상에 이름을 붙일 수 있다. ::: **2.** 진리표로 확인하시오: $\neg P \Rightarrow F$ ($F$는 항상 거짓인 명제)의 진리값 열이 $P$의 열과 일치한다. (2행이면 충분 — §1.4의 표를 직접 작성하는 자리다) :::{admonition} 힌트 :class: quotebox dropdown $F$ 열은 두 행 모두 F로 채워 놓고 시작한다. 남은 것은 조건문 한 열뿐이고, 조건문은 가정이 T이고 결론이 F인 행에서만 F다(8주차). ::: **3.** (a) "기약분수"의 뜻을 쓰시오. (b) $\frac{12}{18}$을 기약분수로 나타내시오. (c) $\sqrt{2}$ 증명에서 "기약으로 잡을 수 있다"는 가정이 없으면 마지막 모순이 왜 안 터지는지 한 문장으로 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown (c)는 예제 2.2의 마지막 줄에서 "기약"을 지우는 삭제 실험이다. 그 줄이 충돌시키는 두 문장 중 하나가 사라지면, 남는 문장 하나는 그 자체로 거짓인가. ::: **4.** 가장 큰 짝수는 존재하지 않음을 귀류법으로 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 예제 2.1의 $N + 1$ 자리에 무엇을 놓아야 하는가. $M + 1$은 $M$보다 크지만 짝수가 아니므로 "가장 큰 **짝수**"의 최대성과 충돌하지 않는다. 만든 수가 ① 짝수임 ② $M$보다 큼 — 두 가지를 모두 확인한다. ::: **5.** 빈칸 사다리 훈련 1(유리수 + 무리수 = 무리수)을 백지에서 완성하시오. :::{admonition} 힌트 :class: quotebox dropdown 첫 줄에서 부정할 것은 "$x + y$가 무리수이다"이고 그 부정은 "$x + y$가 유리수이다"이다. 몸통은 $y$를 $x + y$와 $x$만으로 표현하는 등식 한 줄이 전부다. ::: **6.** 예제 2.1(가장 큰 정수 없음)을 백지에 재현하시오. :::{admonition} 힌트 :class: quotebox dropdown 세 걸음만 확인하면 된다 — ① 부정 선언과 이름 붙이기 ② $N + 1$ 제작과 정수임의 확인 ③ 충돌한 두 문장의 지목. 셋 중 하나라도 빠졌으면 다시 쓴다. ::: ### 표준 ●●○ :::{admonition} 부품 갈아 끼우기 — "$\sqrt{p}$는 무리수" 유형 :class: quotebox 예제 2.2의 몸통에서 2 **고유의 성질**(짝수 부품)에 의존하는 줄은 넷째$\cdot$여섯째 두 곳이다 — "$a^2$이 짝수이면 $a$는 짝수"(19주차 예제 2.1)를 쓴 자리다. 그 밖에 숫자 2가 그대로 갈리는 자리는 셋째$\cdot$다섯째 줄의 등식과 마지막 줄의 공통 약수값이고, 이쪽은 부품이 필요 없는 계산이다. 소수 $p$를 바꾸려면 앞의 두 자리에 "$p \mid n^2$이면 $p \mid n$"의 $p$ 버전을 끼워 넣어야 한다. 3 버전은 19주차 예제 2.2에, 5 버전은 19주차 문제 15에 있다. 이 부품이 준비되지 않은 수에 대해서는 예제 2.2의 복사가 통하지 않는다 — 문제 18이 그 경계를 보여 준다. ::: **7.** $\sqrt{3}$은 무리수임을 증명하시오. (부품: "$3 \mid n^2$이면 $3 \mid n$" — 19주차 예제 2.2) :::{admonition} 힌트 :class: quotebox dropdown 예제 2.2를 그대로 옮기되 2를 3으로 바꾼다. 양변을 제곱해 $a^2 = 3b^2$을 얻은 뒤, 짝수 부품이 아니라 3 버전 부품을 인용한다. $a = 3c$를 대입하면 처음과 같은 꼴의 등식이 $b$에 대해 다시 나온다. ::: **8.** $x$가 0이 아닌 유리수이고 $y$가 무리수이면 $xy$는 무리수임을 귀류법으로 증명하시오. (부품: 15주차 문제 15 — 유리수 나눗셈 닫힘) :::{admonition} 힌트 :class: quotebox dropdown 목표를 부정하면 $xy$가 유리수 — 이름을 붙여 $xy = q$로 둔다. $y$를 $q$와 $x$만으로 표현하려면 나누어야 하고, 나눗셈에는 조건이 하나 붙는다. 문제의 가정 중 그 조건을 공급하는 것은 무엇인가. ::: **9.** 가장 작은 양의 유리수는 존재하지 않음을 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 그런 $q$가 있다면 $\frac{q}{2}$는 무엇인가. ::: **10.** [백지 재현] $\sqrt{2}$는 무리수 — 예제 2.2를 재현하시오. :::{admonition} 힌트 :class: quotebox dropdown 일곱 줄 중 세 곳이 자주 빈다 — 둘째 줄의 "기약분수로 잡을 수 있다", 넷째$\cdot$여섯째 줄의 부품 인용(19주차 예제 2.1), 마지막 줄의 충돌 지목. 그 세 곳부터 확인한다. ::: **11.** 다음이 무리수임을 증명하시오 ($\sqrt{2}$가 무리수라는 사실은 이제 자유롭게 인용). (a) $1 + \sqrt{2}$ (b) $\dfrac{\sqrt{2}}{2}$ :::{admonition} 힌트 :class: quotebox dropdown (a)는 $\sqrt{2}$를 $1 + \sqrt{2}$와 1만으로 표현하는 등식 한 줄이 몸통이다. (b)는 귀류를 새로 쓸 필요가 없다 — $\frac{\sqrt{2}}{2} = \frac{1}{2} \cdot \sqrt{2}$로 보면 이미 증명한 문제가 그대로 적용된다. 어느 문제인가. ::: :::{admonition} 새 유형 — "정수 해가 없다" :class: quotebox 방정식에 정수 해가 없음을 보이려면, 해가 있다고 가정한 뒤 그 해가 반드시 만족해야 할 성질 두 가지를 각각 계산해 충돌시킨다. 가장 자주 쓰는 충돌은 홀짝이다 — 같은 수가 짝수이면서 동시에 홀수라는 결론이 나오면 모순이다. "어떤 정수도 짝수이면서 동시에 홀수일 수는 없다"는 지금은 인정하고 쓴다 (22주차 문제 5에서 증명한다). 빈칸 사다리 훈련 3이 이 유형의 예행연습이었다. ::: **12.** $a^2 - 4b = 2$를 만족하는 정수 $a, b$는 존재하지 않음을 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 존재한다면 $a^2 = 2(2b+1)$이다. $a$의 홀짝을 추적해 홀수 = 짝수 충돌을 만든다. ::: **13.** [백지 재현] 소수는 무한히 많다 — 예제 2.3을 재현하시오. :::{admonition} 힌트 :class: quotebox dropdown 세 곳이 자주 빈다 — ① "유한 개뿐"이라는 부정의 정확한 서술과 목록에 이름 붙이기 ② $N$의 소수 약수를 빌려 쓰는 사실 2로 확보하기 ③ $N$이 소수라고 주장하지 않기. ::: **14.** 방정식 $x^2 + x - 1 = 0$은 정수 해를 갖지 않음을 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 정수 해 $x$가 있다면 $x^2 + x$는 무엇인가 — 1주차 문제 16. ::: ### 도전 ●●● **15.** $\sqrt{6}$은 무리수임을 증명하시오. (안내: $a^2 = 6b^2$에서 ① $a^2$이 짝수 $\to$ $a$ 짝수(19주차 예제 2.1) ② $3 \mid a^2$ $\to$ $3 \mid a$(19주차 예제 2.2) ③ 따라서 $6 \mid a$(20주차 문제 13) $\to$ $a = 6c$ 대입 $\to$ $b$도 같은 운명 $\to$ 기약 모순) :::{admonition} 힌트 :class: quotebox dropdown 안내의 ①②③을 $a$에 대해 끝낸 뒤 그대로 $b$에 반복한다. $a = 6c$를 대입해 얻는 등식이 처음 등식과 **같은 꼴**($b^2 = 6c^2$)이라는 것이 반복의 근거다. 같은 꼴이 아니면 반복은 정당하지 않다. ::: **16.** $\sqrt{2} + \sqrt{3}$은 무리수임을 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 유리수 $r$과 같다고 가정하고 양변을 제곱하면 $r^2 = 5 + 2\sqrt{6}$이다. $\sqrt{6}$을 유리수들로 표현할 수 있게 되어 문제 15와 충돌한다. ::: **17.** $\sqrt[3]{2}$(세제곱해서 2가 되는 수)는 무리수임을 증명하시오. (부품: "$n^3$이 짝수이면 $n$은 짝수" — 19주차 문제 8) :::{admonition} 힌트 :class: quotebox dropdown 예제 2.2의 제곱을 세제곱으로 바꾼다. $a^3 = 2b^3$에서 $a$가 짝수임을 끌어내는 부품은 19주차 문제 8이다. $a = 2c$를 대입해 정리하면 $b^3$이 짝수임이 나오는지 확인한다. ::: :::{admonition} 모순이 나오지 않을 때 무엇을 읽는가 :class: quotebox 지금까지의 증명은 전부 모순이 나왔다. 나오지 않는 경우도 있다. 그 경험을 해부하는 것이 다음 문제이고, 여기서 얻는 결론이 이번 주 목표의 4번이다. 풀기 전에 예제 2.2의 각 줄을 종이 왼쪽에 적고 오른쪽에 $\sqrt{4}$ 버전을 나란히 적어, 어느 줄에서 갈라지는지 눈으로 비교한다. ::: **18.** (진단) 어떤 학생이 예제 2.2를 흉내 내어 "$\sqrt{4}$는 무리수"를 증명하려 했다: "$\sqrt{4} = \frac{a}{b}$ 기약, $4b^2 = a^2$, $a^2$이 짝수이므로 $a = 2c$, 대입하면 $4b^2 = 4c^2$, 즉 $b^2 = c^2$…" — 여기서 멈췄다. (a) $\sqrt{2}$ 증명과 달리 왜 $b$가 짝수라는 결론이 안 나오는지 지적하시오. (b) 모순이 안 나오는 것이 당연한 이유는? (c) 이 경험이 말해 주는 "귀류법의 성질"을 한 문장으로 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown $\sqrt{2}$ 증명의 대응하는 줄은 $b^2 = 2c^2$이었고 이 시도의 줄은 $b^2 = c^2$이다. 두 등식이 $b$의 홀짝에 대해 각각 무엇을 강제하는지 비교한다. (b)는 $\sqrt{4}$의 값을 실제로 계산해 보면 나온다. ::: **19.** $n^2 \equiv 3 \pmod 4$인 정수 $n$은 존재하지 않음을 귀류법으로 증명하시오. (부품: 17주차 문제 9 — $n^2$의 mod 4 나머지는 0 또는 1) :::{admonition} 힌트 :class: quotebox dropdown 17주차 문제 9가 $n^2$을 4로 나눈 나머지의 후보를 0과 1로 좁혀 놓았다. 가정이 말하는 나머지는 3이다. 한 수를 4로 나눈 나머지가 두 값을 동시에 가질 수 없는 근거는 나눗셈 정리의 나머지 유일성이다. ::: **20.** (서술) (a) 대우 증명과 귀류법의 공통점과 차이(도착점의 관점에서)를 두 문장으로 쓰시오. (b) "귀류법은 도착점을 미리 모른다"는 특징이 장점이자 단점인 이유를 각각 한 문장으로 쓰시오. ## 백지 재현 — 복습 프로토콜 권장 일정 — 1~3일차: §0~§4 학습과 연습문제 / 4일차: 1차 재현 / 5일차: 완전 백지 재현. 재현은 두 번으로 나눈다. 한 번에 완전 백지로 가지 않는다. **1차 시도 (4일차) — 틀 카드 허용.** 귀류법의 3단계 틀(§2 관찰)$\cdot$서식(§1.5)$\cdot$ 근거 목록(§1.9)만 펴 놓고, 예제 2.2($\sqrt{2}$)를 처음부터 끝까지 적는다. 본문과 19주차 부품 문장은 보지 않는다. **2차 시도 (5일차) — 완전 백지.** 아무것도 보지 않고 수행한다. - [ ] 귀류법의 3단계 구조(정의 21.1)와 서식(§1.5)을 조각 그대로 썼다. - [ ] "$\neg P$에서 모순이 유도되면 $P$"가 왜 정당한지 두 행짜리 진리표로 설명했다. - [ ] 예제 2.2($\sqrt{2}$)를 처음부터 끝까지 재현했다 — "기약"의 역할과 19주차 부품이 소비되는 두 지점을 짚으면서. - [ ] 예제 2.3(소수 무한)을 재현했다 — "$N$이 소수라는 주장이 아님"을 설명하면서. - [ ] 귀류법의 신호 네 가지(부정형 개념 / 비존재 / 최대$\cdot$최소 없음 / 무한)를 썼다. - [ ] 이번 주에 빌려 쓴 두 사실이 무엇이고 언제 회수되는지 말할 수 있다. - [ ] 유리수 + 무리수, 0이 아닌 유리수 $\times$ 무리수의 결과를 증명과 함께 기억한다. - [ ] 모순이 끝까지 나오지 않을 때 무엇을 읽어야 하는지 말할 수 있다 — 전개 부족인지 명제가 거짓인지의 갈림길(문제 18). **막힌 지점별 처방.** 막힌 지점이 무엇을 다시 볼지 알려 준다. | **막힌 지점** | **처방** | |---|---| | 첫 줄에 무엇을 가정할지 모르겠다 | §1.5 서식 + 11주차 §1.3 부정 총목록 — 부정 제작은 규칙의 적용이다 | | 부정은 썼는데 다음 줄이 없다 | §1.2의 표 — 부정을 정의로 풀어 등식이나 대상 이름을 손에 넣는다 | | 전개는 되는데 모순이 안 보인다 | §1.3 확인 3 — 충돌할 상대를 첫머리에 설치했는지 확인한다 | | "이상하다"까지 갔는데 끝내지 못한다 | §1.3 조각 삭제 실험 — 모순은 $C \land \neg C$ 꼴이어야 한다 | | 최대$\cdot$최소 유형에서 막힌다 | 예제 2.1의 2~3단계 — 최대성을 부등식으로 적고, 그 범위에 속하는 대상을 만든다 | | 무리수 유형에서 부품이 기억나지 않는다 | §1.9 근거 목록의 ④ 칸 — 2$\cdot$3$\cdot$5 각각의 부품 위치가 적혀 있다 | | 모순이 끝까지 나오지 않는다 | 문제 18 — 전개가 부족한 것인지 명제가 거짓인 것인지 갈림길을 확인한다 | 하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다. ## 해설 각 해설은 **접근**(문제 앞에서 무엇을 생각하는가)과 **풀이**로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다. ### 빈칸 사다리 — 훈련 1 (1) 유리수 (2) 유리수 (3) 무리수 ※ (2)의 근거는 15주차 문제 9(두 유리수의 차는 유리수)다. 부정 가정이 $x + y$를 유리수로 만들어 주었으므로 $y = (x+y) - x$의 우변은 유리수 두 개의 차이고, 따라서 $y$가 유리수가 된다 — 무리수라는 가정과 충돌한다. 이 훈련의 설계는 "무리수 $y$를 유리수들만으로 표현하는 등식 한 줄"을 만드는 것이고, 문제 8$\cdot$11$\cdot$16이 전부 같은 설계의 변형이다. ### 빈칸 사다리 — 훈련 2 (1) 유리수 (2) $r$ (3) 두 유리수의 합은 유리수이므로 (15주차 예제 2.2, 근거 ④) (4) $y$가 무리수라는 가정 (5) $y - r$은 무리수이다 ※ 훈련 1과 다른 점은 부정한 대상에 **이름을 붙인** 것뿐이다. "$y - r$이 유리수라고 가정하고 그것을 $q$라 하자"로 이름을 붙였기 때문에 $y = q + r$처럼 등식으로 옮겨 적을 수 있다. 이름 붙이기가 없으면 이 등식이 나오지 않는다. ### 빈칸 사다리 — 훈련 3 (1) 모순을 이끌어내기 위해, $6n + 3 = 2m$인 정수 $n, m$이 존재한다고 가정하자. (2) 좌변은 $6n + 3 = 2(3n + 1) + 1$이고 $3n + 1$은 정수이므로(근거 ②) 홀수이다. 우변은 $2m$이고 $m$은 정수이므로 짝수이다. 두 변은 같은 수이므로, 그 수는 짝수이면서 동시에 홀수이다. (3) 어떤 정수도 짝수이면서 동시에 홀수일 수는 없으므로(인정하고 쓰는 사실, 22주차 문제 5) 모순이다. 따라서 $6n + 3 = 2m$인 정수 $n, m$은 존재하지 않는다. $\blacksquare$ ※ 이 유형의 요령은 하나다 — 같은 수를 두 가지 방식으로 읽어 서로 다른 판정을 얻는 것. 문제 12와 문제 14가 같은 요령을 쓴다. ### 문제 1 **접근.** 세 항목 모두 §1.5 서식의 첫 문장을 만드는 일이고, 재료는 11주차 §1.3의 부정 총목록과 정의 15.1뿐이다. (a)는 "무리수"의 부정이 "유리수"라는 것, (b)(c)는 "존재하지 않는다"($\neg \exists$)를 다시 부정하면 이중부정이 풀려 "존재한다"가 된다는 것. 존재 가정에서는 그 대상에 이름을 붙이는 데까지가 첫 문장의 임무다 — 이름이 없으면 둘째 줄에서 계산할 것이 없다. **풀이.** (a) "모순을 이끌어내기 위해, $\sqrt{3}$이 유리수라고 가정하자." (이어지는 둘째 줄은 "그러면 $\sqrt{3} = \frac{a}{b}$인 정수 $a, b$($b \neq 0$)가 존재하고 기약분수로 잡을 수 있다"가 된다.) (b) "모순을 이끌어내기 위해, 가장 작은 양의 유리수가 존재한다고 가정하고 그것을 $q$라 하자." (c) "모순을 이끌어내기 위해, $x^2 = 4y + 3$을 만족하는 정수 $x, y$가 존재한다고 가정하자." **복기.** (b)와 (c)의 차이도 짚어 둔다. (b)는 대상이 하나이므로 이름 하나($q$)를 붙이고, (c)는 문제가 이미 $x, y$라는 이름을 주었으므로 새로 붙일 이름이 없다. 이름이 필요한지 아닌지는 부정한 문장이 무엇을 존재한다고 말하는지가 정한다. ### 문제 2 **접근.** $F$는 항상 거짓인 명제이므로 그 열은 두 행 모두 F로 미리 채워 놓는다. 남은 것은 조건문 $\neg P \Rightarrow F$ 한 열을 행마다 계산하는 것뿐이고, 조건문은 가정이 T이고 결론이 F인 행에서만 F다(8주차). **풀이.** | **$P$** | **$\neg P$** | **$F$** | **$\neg P \Rightarrow F$** | |---|---|---|---| | T | F | F | T | | F | T | F | F | 첫 행: $\neg P$ = F이고 $F$ = F이므로 가정이 거짓인 조건문 — 진리값은 T. 둘째 행: $\neg P$ = T이고 $F$ = F이므로 T $\Rightarrow$ F — 진리값은 F. 마지막 열 (T, F)는 첫 열 $P$의 (T, F)와 완전히 일치한다. 두 명제의 진리값이 모든 행에서 같으므로 둘은 동치다(9주차). 곧 "$\neg P$에서 거짓이 유도됨"을 보이는 것은 "$P$이다"를 보이는 것과 논리적으로 같은 일이다. $\blacksquare$ **복기.** 귀류법이 정당한 이유가 이 두 행에 전부 들어 있다. 모순 $C \land \neg C$는 어떤 상황에서도 거짓인 명제(7주차)이므로 $F$ 자리에 그대로 들어간다 — 그래서 §1.4의 표와 이 표는 같은 표다. ### 문제 3 **접근.** (a)(b)는 정의 21.2의 적용이다. (c)는 예제 2.2의 마지막 줄에서 "기약"을 지우는 삭제 실험이고, 물을 것은 하나다 — 충돌시키는 두 문장 중 하나가 사라지면 남는 문장은 그 자체로 거짓인가. **풀이.** (a) 분자와 분모의 공통 약수가 $\pm 1$뿐인 분수. 정확히는, 정수 $a, b$($b \neq 0$)에 대해 $\frac{a}{b}$가 기약분수라는 것은 $a$와 $b$의 공통 약수가 $\pm 1$뿐이라는 뜻이다(정의 21.2). (b) $12 = 6 \times 2$, $18 = 6 \times 3$이므로 6이 공통 약수이고 $\frac{12}{18}$은 기약분수가 아니다. 분자와 분모를 6으로 나누면 $\frac{12}{18} = \frac{2}{3}$이고, 2와 3의 공통 약수는 $\pm 1$뿐이므로 $\frac{2}{3}$이 기약분수 표현이다. (c) 기약 가정이 없으면 마지막 줄에서 손에 남는 것은 "$a$와 $b$가 모두 짝수"라는 문장 하나뿐인데, 그 문장은 그 자체로 거짓이 아니다 — $\frac{4}{2}$처럼 분자와 분모가 모두 짝수인 유리수 표현은 얼마든지 있기 때문이다. 모순은 $C \land \neg C$ 꼴이어야 하는데 충돌할 상대 $C$("공통 약수는 $\pm 1$뿐")를 첫머리에 설치하지 않았으므로 $\neg C$ 하나만 남고, 그 하나로는 아무것도 무너지지 않는다. **복기.** 귀류법 설계의 절반은 "무엇과 충돌시킬지"를 미리 정해 첫머리에 적어 두는 것이다. 문제 18이 같은 조각을 반대 방향에서 확인한다 — 거기서는 상대를 설치했는데도 충돌이 나오지 않는다. ### 문제 4 **접근.** 예제 2.1의 구조를 그대로 쓰되 조건이 하나 붙는다. 만드는 수가 **짝수** 여야 한다. $M + 1$은 $M$보다 크지만 짝수가 아니므로 "가장 큰 짝수"의 최대성과 충돌하지 않는다 — 그 최대성은 짝수들 사이에서만 주장되기 때문이다. $M + 2$를 쓰고, 그것이 짝수임을 정의로 확인한다. **풀이.** 모순을 이끌어내기 위해, 가장 큰 짝수가 존재한다고 가정하고 그것을 $M$이라 하자. 그러면 모든 짝수 $n$에 대해 $n \le M$이다. $M$은 짝수이므로 정의에 의해 $M = 2k$인 정수 $k$가 존재한다. 이제 $M + 2$를 생각하면 $$ M + 2 = 2k + 2 = 2(k + 1) $$ 이고 $k + 1$은 정수이므로(근거 ②) $M + 2$는 짝수이다. 또 $M + 2 > M$이다. $M + 2$가 짝수이므로 둘째 문장을 $n = M + 2$에 적용할 수 있고, 그러면 $M + 2 \le M$인데 이는 $M + 2 > M$과 동시에 성립할 수 없다. 모순이다. 따라서 가장 큰 짝수는 존재하지 않는다. $\blacksquare$ **복기.** 최대$\cdot$최소 유형에서 만든 대상이 **가정이 말하는 범위에 속하는지**를 확인하는 줄이 반드시 필요하다. 여기서는 "$M + 2$가 짝수임"이 그 줄이고, 문제 9에서는 "$\frac{q}{2}$가 양의 유리수임"이 그 줄이다. **검산.** $M = 100$이면 $M + 2 = 102 = 2 \times 51$ — 짝수이고 100보다 크다 ✓. ### 문제 5 **접근.** 훈련 1의 세 빈칸을 채운 뒤 통째로 재현한다. 설계의 핵심은 "무리수 $y$를 유리수들만으로 표현하는 등식"을 한 줄 만드는 것이다: $y = (x + y) - x$. 부정 가정이 $x + y$를 유리수로 만들어 주었으므로 우변은 유리수 두 개의 차다. **풀이.** 모순을 이끌어내기 위해, 유리수 $x$와 무리수 $y$에 대해 $x + y$가 유리수라고 가정하자. 그러면 $$ y = (x + y) - x $$ 이고, 우변은 유리수에서 유리수를 뺀 것이므로 유리수이다(15주차 문제 9). 곧 $y$가 유리수인데, 이는 $y$가 무리수라는 가정과 모순이다. 따라서 $x + y$는 무리수이다. $\blacksquare$ **복기.** 이 세 줄이 이번 주 무리수 논증의 표준형이다 — 무리수를 유리수들의 사칙연산으로 표현하는 등식을 한 줄 만들고, 15주차 닫힘성 정리로 그것이 유리수임을 선언한 뒤, 무리수라는 가정과 충돌시킨다. 문제 8$\cdot$11$\cdot$16이 각각 곱$\cdot$차$\cdot$제곱으로 같은 설계를 반복한다. **검산.** $x = 1$, $y = \sqrt{2}$로 두면 $x + y = 1 + \sqrt{2}$ — 문제 11(a)가 이 명제의 특수한 경우다 ✓. ### 문제 6 **접근.** 재현 문제이므로 채점 기준을 미리 정해 놓고 쓴다 — ① 부정 선언과 이름 붙이기 ② $N + 1$의 정수임 확인 ③ 충돌한 두 문장의 지목. 셋 중 하나라도 빠지면 재현이 아니다. **풀이.** 모순을 이끌어내기 위해, 가장 큰 정수가 존재한다고 가정하고 그것을 $N$이라 하자. 그러면 모든 정수 $n$에 대해 $n \le N$이다. $N$과 1이 정수이므로 $N + 1$도 정수이고(근거 ②), $N + 1 > N$이다. 둘째 문장을 $n = N + 1$에 적용하면 $N + 1 \le N$인데, 이는 $N + 1 > N$과 동시에 성립할 수 없다. 모순이다. 따라서 가장 큰 정수는 존재하지 않는다. $\blacksquare$ **복기.** 다섯 줄짜리 증명이지만 세 걸음이 모두 들어 있다. 가장 자주 빠지는 것은 둘째 줄("모든 정수 $n$에 대해 $n \le N$")이다 — 이 줄이 없으면 마지막에서 $N + 1 \le N$을 끌어낼 근거가 없어, 충돌 대신 "$N+1$이 더 크다"는 관찰 하나만 남는다. ### 문제 7 **접근.** 예제 2.2를 그대로 옮기되 2를 3으로 바꾼다. 조심할 곳은 부품 한 군데다 — "$a^2$이 짝수이면 $a$는 짝수"(19주차 예제 2.1)는 2 전용이므로, 3에 대해서는 "$3 \mid a^2$이면 $3 \mid a$"(19주차 예제 2.2)로 갈아 끼워야 한다. **풀이.** 모순을 이끌어내기 위해, $\sqrt{3}$이 유리수라고 가정하자. 그러면 $\sqrt{3} = \frac{a}{b}$인 정수 $a, b$($b \neq 0$)가 존재하고, 기약분수로 잡을 수 있다 — 곧 $a$와 $b$의 공통 약수는 $\pm 1$뿐이다. 양변을 제곱하면 $3 = \frac{a^2}{b^2}$, 곧 $$ a^2 = 3b^2 $$ 이다. 우변이 $3 \times (\text{정수})$ 꼴이므로 $3 \mid a^2$이고, 19주차 예제 2.2에 의해 $3 \mid a$이다. 그러면 $a = 3c$인 정수 $c$가 존재하고, 대입하면 $9c^2 = 3b^2$, 곧 $$ b^2 = 3c^2 $$ 이다. 같은 이유로 $3 \mid b^2$이고, 같은 부품에 의해 $3 \mid b$이다. 그러면 3이 $a$와 $b$의 공통 약수인데, 이는 공통 약수가 $\pm 1$뿐이라는 것과 동시에 성립할 수 없다. 모순이다. 따라서 $\sqrt{3}$은 무리수이다. $\blacksquare$ **복기.** 예제 2.2와 이 증명의 차이는 두 낱말("짝수" $\to$ "$3 \mid$")과 부품 인용처, 그리고 등식 속 숫자 2를 3으로 바꾼 계산뿐이다. 증명의 뼈대가 소재와 분리되어 있음을 확인하는 자리이고, 문제 15가 이 갈아 끼우기를 두 부품 동시에 하는 문제다. **검산.** $1.7^2 = 2.89$, $1.8^2 = 3.24$이므로 $\sqrt{3}$은 1과 2 사이에 있어 정수가 아니다. 다만 이 관찰은 무리수임의 증명이 아니다 — 정수가 아니라는 것과 유리수가 아니라는 것은 다른 주장이다($\frac{3}{2}$은 정수가 아니지만 유리수다). ### 문제 8 **접근.** 결론이 "무리수"이므로 부정하면 "$xy$가 유리수"가 되고, 이름을 붙여 $xy = q$로 둔다. 목표는 $y$를 유리수들만으로 표현하는 것 — $y = \frac{q}{x}$다. 나눗셈에는 분모가 0이 아니어야 한다는 조건이 붙고, 가정 "$x$가 0이 아닌 유리수"가 정확히 그 자리에서 소비된다. **풀이.** 모순을 이끌어내기 위해, $xy$가 유리수라고 가정하고 그것을 $q$라 하자. $x \neq 0$이므로 양변을 $x$로 나눌 수 있고, $$ y = \frac{xy}{x} = \frac{q}{x} $$ 이다. $q$는 유리수이고 $x$는 0이 아닌 유리수이므로, 15주차 문제 15(유리수를 0이 아닌 유리수로 나눈 몫은 유리수)에 의해 $y$는 유리수이다. 이는 $y$가 무리수라는 가정과 모순이다. 따라서 $xy$는 무리수이다. $\blacksquare$ **복기.** 가정 "$x \neq 0$"이 증명의 어느 지점에서 소비되는지 짚어 두는 습관 (18주차 확인 2)이 여기서 발동한다. 그 조건이 없으면 $x = 0$일 때 $xy = 0$이 유리수이므로 명제 자체가 거짓이 된다 — 조건이 없으면 무너지는 자리를 아는 것이 조건을 이해한 것이다. **검산.** $x = \frac{1}{2}$, $y = \sqrt{2}$로 두면 $xy = \frac{\sqrt{2}}{2}$ — 문제 11(b)가 이 명제의 특수한 경우다 ✓. ### 문제 9 **접근.** 부정하면 "가장 작은 양의 유리수 $q$"가 손에 들어온다. 그 최소성을 깨려면 $q$보다 작은 양의 유리수를 하나 만들면 되고, 후보는 $\frac{q}{2}$다. 확인할 것이 세 가지다 — ① 유리수인가 ② 양수인가 ③ $q$보다 작은가. 셋 중 하나라도 빠지면 "가장 작은 **양의 유리수**"라는 가정과 맞물리지 않는다. **풀이.** 모순을 이끌어내기 위해, 가장 작은 양의 유리수가 존재한다고 가정하고 그것을 $q$라 하자. 그러면 $q > 0$이고, 모든 양의 유리수 $r$에 대해 $q \le r$이다. 이제 $\frac{q}{2}$를 생각한다. ① $q$는 유리수이고 2는 0이 아닌 유리수이므로 $\frac{q}{2}$는 유리수이다 (15주차 문제 15). ② $q > 0$이고 $2 > 0$이므로 $\frac{q}{2} > 0$이다. ③ $0 < q$의 양변에 $q$를 더하면 $q < 2q$이고, 양변을 2로 나누면 $\frac{q}{2} < q$이다. ①②③에 의해 $\frac{q}{2}$는 양의 유리수이고 $q$보다 작다. ①②에 의해 둘째 문장을 $r = \frac{q}{2}$에 적용할 수 있으므로 $q \le \frac{q}{2}$인데, 이는 ③과 동시에 성립할 수 없다. 모순이다. 따라서 가장 작은 양의 유리수는 존재하지 않는다. $\blacksquare$ **복기.** 예제 2.1과 같은 유형이지만 만드는 방향이 반대다 — 최대를 깰 때는 더 큰 것을, 최소를 깰 때는 더 작은 것을 만든다. 그리고 만든 대상이 가정이 말하는 범위(여기서는 양의 유리수)에 속하는지 확인하는 줄이 문제 4와 같은 자리에서 필요하다. **검산.** $q = \frac{1}{1000}$이면 $\frac{q}{2} = \frac{1}{2000}$ — 유리수이고 양수이며 더 작다 ✓. 0에 아무리 가까운 양의 유리수를 잡아도 그 절반이 또 있다. ### 문제 10 **접근.** 예제 2.2의 일곱 줄 재현이다. 자주 비는 칸은 세 곳 — 둘째 줄의 "기약분수로 잡을 수 있다", 넷째$\cdot$여섯째 줄의 부품 인용(19주차 예제 2.1), 마지막 줄의 충돌 지목. 쓰기 전에 이 세 곳을 채점 기준으로 적어 둔다. **풀이.** 모순을 이끌어내기 위해, $\sqrt{2}$가 유리수라고 가정하자. 그러면 $\sqrt{2} = \frac{a}{b}$인 정수 $a, b$($b \neq 0$)가 존재하고, 기약분수로 잡을 수 있다 — 곧 $a$와 $b$의 공통 약수는 $\pm 1$뿐이다. 양변을 제곱하면 $2 = \frac{a^2}{b^2}$, 곧 $$ a^2 = 2b^2 $$ 이다. 우변이 $2 \times (\text{정수})$ 꼴이므로 $a^2$은 짝수이고, 19주차 예제 2.1에 의해 $a$는 짝수이다. 그러면 $a = 2c$인 정수 $c$가 존재하고, 대입하면 $4c^2 = 2b^2$, 곧 $$ b^2 = 2c^2 $$ 이다. 같은 이유로 $b^2$은 짝수이고, 같은 부품에 의해 $b$도 짝수이다. 그러면 $a$와 $b$가 모두 짝수이므로 2가 공통 약수인데, 이는 공통 약수가 $\pm 1$뿐이라는 것과 동시에 성립할 수 없다. 모순이다. 따라서 $\sqrt{2}$는 무리수이다. $\blacksquare$ **복기.** 채점 포인트 다섯 가지: ① 부정을 정확히("유리수라고 가정") ② 기약 선언 ③ $a^2$ 짝수에서 $a$ 짝수로 갈 때 근거 인용 ④ 같은 논증을 $b$에 반복 ⑤ 기약과의 충돌 지목. ③이 빠진 답안이 가장 많은데, 그 줄은 정의만으로는 나오지 않는 줄이므로 근거 없이 쓰면 증명이 끊긴다. ### 문제 11 **접근.** 두 항목 모두 이미 증명한 결과를 부품으로 쓰면 짧아진다(근거 ④). (a)는 $\sqrt{2}$를 $1 + \sqrt{2}$와 1만으로 표현하는 등식 한 줄이 몸통이다. (b)는 귀류를 새로 쓸 필요가 없다 — 문제 8이 이미 "0이 아닌 유리수 $\times$ 무리수 = 무리수"라는 일반 명제이므로, 이 문제는 그 명제의 한 사례일 뿐이다. **풀이.** (a) 모순을 이끌어내기 위해, $1 + \sqrt{2}$가 유리수라고 가정하자. 그러면 $$ \sqrt{2} = (1 + \sqrt{2}) - 1 $$ 이고, $1 = \frac{1}{1}$은 유리수이므로 우변은 유리수에서 유리수를 뺀 것 — 따라서 유리수이다(15주차 문제 9). 곧 $\sqrt{2}$가 유리수인데, 이는 예제 2.2에서 증명한 "$\sqrt{2}$는 무리수"와 모순이다. 따라서 $1 + \sqrt{2}$는 무리수이다. $\blacksquare$ (b) $\frac{\sqrt{2}}{2} = \frac{1}{2} \cdot \sqrt{2}$이다. $\frac{1}{2}$은 0이 아닌 유리수이고 $\sqrt{2}$는 무리수이므로(예제 2.2), 문제 8에 의해 곱 $\frac{1}{2} \cdot \sqrt{2}$는 무리수이다. 따라서 $\frac{\sqrt{2}}{2}$는 무리수이다. $\blacksquare$ **복기.** (b)에서 귀류를 새로 쓰지 않은 것이 요령이다. 이미 증명한 일반 명제가 있으면 개별 사례는 그 명제의 적용 한 줄로 끝난다 — 1주차 문제 13의 풀이 2와 같은 감각이고, 이것이 근거 ④가 목록에 있는 이유다. (a)도 훈련 1의 일반 명제 "유리수 + 무리수 = 무리수"를 $x = 1$, $y = \sqrt{2}$에 적용하는 한 줄로 대신할 수 있다 — 두 방식 모두 정답이다. **검산.** 소수 전개($2.414\dots$, $0.707\dots$)로는 무리수 여부를 판정할 수 없다 — 판정의 근거는 언제나 증명이지 수치가 아니다. ### 문제 12 **접근.** "정수 해가 없다"는 비존재형이므로 귀류법의 신호다. 해가 존재한다고 가정하면 등식 $a^2 - 4b = 2$가 손에 들어온다. 문제의 힌트대로 정리하면 $a^2 = 2(2b+1)$이므로 $a^2$이 짝수이고, 여기서 $a$가 짝수임을 끌어낸다 (19주차 예제 2.1). $a = 2c$를 대입해 양변을 2로 나누면 좌변과 우변의 홀짝이 갈라진다. **풀이.** 모순을 이끌어내기 위해, $a^2 - 4b = 2$인 정수 $a, b$가 존재한다고 가정하자. 그러면 $$ a^2 = 4b + 2 = 2(2b + 1) $$ 이고 $2b + 1$은 정수이므로(근거 ②) $a^2$은 짝수이다. 19주차 예제 2.1에 의해 $a$는 짝수이므로 $a = 2c$인 정수 $c$가 존재한다. 대입하면 $4c^2 = 4b + 2$이고, 양변을 2로 나누면 $$ 2c^2 = 2b + 1 $$ 이다. 좌변은 $2 \times (\text{정수})$이므로 짝수이고, 우변은 $2 \times (\text{정수}) + 1$이므로 홀수다. 두 변은 같은 수이므로 그 수는 짝수이면서 동시에 홀수인데, 어떤 정수도 그럴 수는 없다(인정하고 쓰는 사실, 22주차 문제 5에서 증명한다). 모순이다. 따라서 $a^2 - 4b = 2$를 만족하는 정수 $a, b$는 존재하지 않는다. $\blacksquare$ **복기.** 훈련 3과 같은 요령이다 — 같은 수를 두 방식으로 읽어 서로 다른 판정을 얻는다. 다른 점은 홀짝 정보를 바로 얻지 못하고 "$a$가 짝수"라는 중간 단계를 19주차 부품으로 확보해야 한다는 것이다. **검산.** $a^2 - 2 = 4b$여야 하므로 $a^2 - 2$가 4의 배수여야 한다. $a = 0, 1, 2, 3, 4$에서 $a^2 - 2 = -2, -1, 2, 7, 14$ — 어느 것도 4의 배수가 아니다 ✓. 검산은 증명이 아니지만 방향 확인에는 쓸 수 있다. ### 문제 13 **접근.** 예제 2.3의 재현이다. 채점 기준은 세 가지 — ① "소수가 유한 개뿐"이라는 부정을 정확히 쓰고 목록에 이름을 붙였는가 ② $N$의 소수 약수를 빌려 쓰는 사실 2로 확보했는가 ③ $N$이 소수라고 주장하지 않았는가. **풀이.** 모순을 이끌어내기 위해, 소수가 유한 개뿐이라고 가정하고 그 전부를 $p_1, p_2, \dots, p_n$이라 하자. 수 $N = p_1 p_2 \cdots p_n + 1$을 생각한다. $N \ge 2$이므로 $N$은 소수인 약수 $p$를 가진다(빌려 쓰는 사실 2). 목록이 소수 전부이므로 어떤 $i$에 대해 $p = p_i$이다. 그러면 $p \mid N$이고, $p$는 곱 $p_1 p_2 \cdots p_n$의 인수 중 하나이므로 $p \mid p_1 p_2 \cdots p_n$이다 (2주차 훈련 1). 2주차 문제 17에 의해 $$ p \mid \big(N - p_1 p_2 \cdots p_n\big) = 1 $$ 이다. 그러나 $p$는 소수이므로 $p \ge 2$인데, $1 = pc$인 정수 $c$가 있다면 $|p| \cdot |c| = 1$이고 $|c| \ge 1$이므로 $|p| \le 1$이 되어 $p \ge 2$와 어긋난다. 모순이다. 따라서 소수는 무한히 많다. $\blacksquare$ **복기.** 이 증명이 "$N$은 소수다"라고 주장한다는 오해가 가장 흔하다. 실제로 $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \times 509$는 합성수다. 논증이 말하는 것은 "$N$의 소수 약수가 목록 안에 있을 수 없다"는 것이고, 위 사례에서도 59와 509는 목록 $2, 3, 5, 7, 11, 13$ 밖에 있다. 이 구분을 설명할 수 있으면 재현이 완결된 것이다. **검산.** 목록이 $\{2, 3\}$이면 $N = 7$, 소수 약수 7 — 목록 밖이다 ✓. $\{2, 3, 5\}$면 $N = 31$, 소수 약수 31 — 역시 밖이다 ✓. ### 문제 14 **접근.** "정수 해를 갖지 않는다"는 비존재형이므로 귀류법이다. 해가 있다고 가정하면 $x^2 + x = 1$이라는 등식이 손에 들어온다. 좌변은 $x(x+1)$로 묶이는데, 연속한 두 정수의 곱이 짝수임은 1주차 문제 16에서 증명해 두었다. 우변 1은 홀수이므로 홀짝 충돌이 만들어진다. **풀이.** 모순을 이끌어내기 위해, $x^2 + x - 1 = 0$을 만족하는 정수 $x$가 존재한다고 가정하자. 그러면 $$ x^2 + x = 1 $$ 이다. 좌변은 $x^2 + x = x(x+1)$로 묶이고, 이는 연속한 두 정수의 곱이므로 짝수이다(1주차 문제 16). 곧 $x^2 + x = 2k$인 정수 $k$가 존재한다. 그러면 $2k = 1$인데, 좌변은 짝수이고 $1 = 2 \cdot 0 + 1$은 홀수이므로 같은 수가 짝수이면서 동시에 홀수가 된다 — 어떤 정수도 그럴 수는 없다(인정하고 쓰는 사실, 22주차 문제 5에서 증명한다). 모순이다. 따라서 이 방정식은 정수 해를 갖지 않는다. $\blacksquare$ **복기.** 근의 공식으로 $x = \frac{-1 \pm \sqrt{5}}{2}$를 구한 뒤 "정수가 아니다"라고 적는 길도 있지만, 그 길은 $\sqrt{5}$가 무리수인지까지 따로 따져야 한다. 홀짝 충돌은 근을 전혀 구하지 않고 세 줄로 끝난다 — 구하지 않고도 판정할 수 있으면 구하지 않는다. **검산.** $x = -2, -1, 0, 1$에서 $x^2 + x - 1$은 각각 $1, -1, -1, 1$이고, $|x| \ge 2$이면 $|x^2+x| \ge 2$이다 ✓. ### 문제 15 **접근.** 예제 2.2의 갈아 끼우기를 부품 두 개로 동시에 하는 문제다. $a^2 = 6b^2$ 하나에서 $a$의 성질을 두 번 읽는다 — 2의 배수임과 3의 배수임. 두 정보를 합쳐 $6 \mid a$를 얻는 것이 20주차 문제 13이고, 그래야 $a = 6c$를 대입했을 때 처음과 **같은 꼴**의 등식이 $b$에 대해 나와 논증을 반복할 수 있다. **풀이.** 모순을 이끌어내기 위해, $\sqrt{6}$이 유리수라고 가정하자. 그러면 $\sqrt{6} = \frac{a}{b}$인 정수 $a, b$($b \neq 0$)가 존재하고 기약분수로 잡을 수 있다. 양변을 제곱하면 $$ a^2 = 6b^2 $$ 이다. 이제 $a$에 대해 두 가지를 읽는다. ① $a^2 = 2(3b^2)$이므로 $a^2$은 짝수이고, 19주차 예제 2.1에 의해 $a$는 짝수다. 곧 $2 \mid a$. ② $a^2 = 3(2b^2)$이므로 $3 \mid a^2$이고, 19주차 예제 2.2에 의해 $3 \mid a$. ③ $2 \mid a$이고 $3 \mid a$이므로 20주차 문제 13에 의해 $6 \mid a$이다. 따라서 $a = 6c$인 정수 $c$가 존재한다. 대입하면 $36c^2 = 6b^2$, 곧 $$ b^2 = 6c^2 $$ 이다. 이는 처음 등식과 같은 꼴이므로 ①②③을 $b$에 그대로 반복할 수 있고, $6 \mid b$를 얻는다. 그러면 6이 $a$와 $b$의 공통 약수인데, 이는 공통 약수가 $\pm 1$뿐이라는 것과 동시에 성립할 수 없다. 모순이다. 따라서 $\sqrt{6}$은 무리수이다. $\blacksquare$ **복기.** ③이 없으면 논증이 닫히지 않는다. $2 \mid a$만으로 $a = 2c$를 대입하면 $4c^2 = 6b^2$, 곧 $2c^2 = 3b^2$이 되어 처음과 다른 꼴이 되고 반복이 끊긴다. "같은 꼴로 되돌아오는가"가 이 유형에서 확인할 지점이다. **검산.** $2.4^2 = 5.76$, $2.5^2 = 6.25$이므로 $\sqrt{6}$은 2와 3 사이에 있다. $6 = 2 \times 3$처럼 서로 다른 소수의 곱인 경우에 이 논법이 통하고, $4 = 2^2$처럼 제곱수인 경우에는 통하지 않는다 — 그 경계가 문제 18이다. ### 문제 16 **접근.** $\sqrt{2} + \sqrt{3}$을 직접 다루는 부품은 없다. 대신 유리수라고 가정한 뒤 제곱하면 $\sqrt{6}$이 유리수들의 식으로 표현되고, 이미 증명한 문제 15와 충돌시킬 수 있다. 이 문제의 설계는 "충돌 상대를 이미 증명된 정리에서 빌려 온다"는 것이다. **풀이.** 모순을 이끌어내기 위해, $\sqrt{2} + \sqrt{3}$이 유리수라고 가정하고 그것을 $r$이라 하자. 양변을 제곱하면 $$ r^2 = (\sqrt{2} + \sqrt{3})^2 = 2 + 2\sqrt{2}\sqrt{3} + 3 = 5 + 2\sqrt{6} $$ 이므로 $$ \sqrt{6} = \frac{r^2 - 5}{2} $$ 이다. $r$이 유리수이므로 $r^2 = r \cdot r$은 유리수이고(15주차 훈련 1, 곱 닫힘), $5 = \frac{5}{1}$은 유리수이므로 $r^2 - 5$도 유리수이며(15주차 문제 9, 차 닫힘), 2는 0이 아닌 유리수이므로 $\frac{r^2 - 5}{2}$도 유리수이다(15주차 문제 15, 몫 닫힘). 곧 $\sqrt{6}$이 유리수인데, 이는 문제 15와 모순이다. 따라서 $\sqrt{2} + \sqrt{3}$은 무리수이다. $\blacksquare$ **복기.** 무리수 둘의 합이 항상 무리수인 것은 아니다 — $\sqrt{2} + (-\sqrt{2}) = 0$이 반례다(15주차 문제 19). 일반 법칙이 없다는 것과 특정한 합이 무리수라는 것은 별개의 주장이므로, 이런 문제는 개별적으로 증명해야 한다. "무리수 + 무리수 = 무리수"를 정리처럼 인용한 답안은 그 반례 앞에서 무효가 된다. **검산.** $3.146^2 \approx 9.90 = 5 + 2 \times 2.449$ — $\sqrt{6} \approx 2.449$와 맞는다 ✓. ### 문제 17 **접근.** 예제 2.2의 제곱을 세제곱으로 바꾼다. 근호를 없애는 걸음이 "양변을 세제곱한다"로 바뀌고, 짝수 부품도 세제곱 버전(19주차 문제 8)으로 갈아 끼운다. 나머지 뼈대는 한 줄도 다르지 않다. **풀이.** 모순을 이끌어내기 위해, $\sqrt[3]{2}$가 유리수라고 가정하자. 그러면 $\sqrt[3]{2} = \frac{a}{b}$인 정수 $a, b$($b \neq 0$)가 존재하고 기약분수로 잡을 수 있다. 양변을 세제곱하면 $2 = \frac{a^3}{b^3}$, 곧 $$ a^3 = 2b^3 $$ 이다. 우변이 $2 \times (\text{정수})$ 꼴이므로 $a^3$은 짝수이고, 19주차 문제 8 ("$n^3$이 짝수이면 $n$은 짝수")에 의해 $a$는 짝수이다. 그러면 $a = 2c$인 정수 $c$가 존재하고, 대입하면 $8c^3 = 2b^3$, 곧 $$ b^3 = 4c^3 = 2(2c^3) $$ 이다. $2c^3$은 정수이므로 $b^3$은 짝수이고, 같은 부품에 의해 $b$도 짝수이다. 그러면 2가 $a$와 $b$의 공통 약수인데, 이는 공통 약수가 $\pm 1$뿐이라는 것과 동시에 성립할 수 없다. 모순이다. 따라서 $\sqrt[3]{2}$는 무리수이다. $\blacksquare$ **복기.** 예제 2.2$\cdot$문제 7$\cdot$문제 15$\cdot$문제 17을 나란히 놓으면 바뀐 것은 세 자리뿐이다 — 근호를 없애는 연산(제곱/세제곱), 인용하는 부품, 마지막 공통 약수의 값. 뼈대를 외우고 이 세 자리만 갈아 끼우는 것이 이 유형의 재현 방법이다. ### 문제 18 **접근.** $\sqrt{2}$ 증명의 각 줄을 $\sqrt{4}$ 버전과 나란히 놓고 어느 줄에서 갈라지는지 찾는다. 갈라지는 곳은 대입 직후의 등식이다 — $\sqrt{2}$ 쪽은 $b^2 = 2c^2$이고 $\sqrt{4}$ 쪽은 $b^2 = c^2$이다. 그리고 (b)는 $\sqrt{4}$의 값을 실제로 계산하면 바로 나온다. **풀이.** (a) $\sqrt{2}$ 증명에서는 대입 후 $b^2 = 2c^2$이 되어 우변이 $2 \times (\text{정수})$ 꼴이므로 $b^2$의 짝수성이 강제되고, 부품에 의해 $b$가 짝수가 되었다. $\sqrt{4}$ 시도에서는 $4b^2 = 4c^2$의 양변을 4로 나누어 $b^2 = c^2$이 되는데, 여기에는 2라는 인수가 남아 있지 않아 $b$의 홀짝에 대해 아무것도 강제하지 않는다. 실제로 $b = 1$, $c = 1$이면 $b^2 = c^2$이 성립하고 $b$는 홀수다 — 갈라지는 지점은 "우변에 2가 남는가"이다. (b) $\sqrt{4} = 2 = \frac{2}{1}$이므로 $\sqrt{4}$는 실제로 유리수다. 곧 이 시도가 가정한 "$\sqrt{4}$가 유리수이다"는 **참인 명제**이고, 참인 가정에서 유도되는 것은 참뿐이므로 모순이 나올 수 없다. 증명 시도가 막히는 것이 당연하다. (c) 귀류법은 거짓인 명제를 증명해 주지 않는다 — 모순이 나오지 않는 경험은 "전개가 아직 부족하다"는 신호일 수도 있고 "증명하려는 명제가 애초에 거짓이다"는 신호일 수도 있으며, 그 갈림길은 귀류법 자체가 알려 주지 않는다. **복기.** 문제 3(c)와 짝을 이루는 문제다. 문제 3(c)는 충돌 상대를 설치하지 않아 모순이 안 나오는 경우였고, 이 문제는 상대를 제대로 설치했는데도 모순이 안 나오는 경우다. 후자에서 읽어야 할 것은 명제 자체의 진위이며, 이 갈림길을 정식으로 다루는 것이 29주차의 반증이다. 22주차 문제 19가 이 진단을 다시 묻는다. **검산.** $\sqrt{6}$(문제 15)은 $6 = 2 \times 3$이라 논증이 닫혔고 $\sqrt{4}$는 $4 = 2^2$이라 닫히지 않았다 — 갈림은 제곱수인가에 있다 ✓. ### 문제 19 **접근.** 존재 가정에서 시작해 그 $n$에 17주차 문제 9를 적용한다. 그 결과가 말하는 나머지 후보(0 또는 1)와 가정이 말하는 나머지(3)가 충돌한다. 충돌을 성립시키려면 "한 수를 4로 나눈 나머지는 하나뿐"이라는 유일성이 필요하고, 그 근거는 나눗셈 정리다. **풀이.** 모순을 이끌어내기 위해, $n^2 \equiv 3 \pmod 4$인 정수 $n$이 존재한다고 가정하자. 정의 20.1에 의해 이는 $4 \mid (n^2 - 3)$, 곧 $n^2$을 4로 나눈 나머지가 3이라는 뜻이다. 한편 17주차 문제 9에 의해 모든 정수 $n$에 대해 $n^2$을 4로 나눈 나머지는 0 또는 1이다. 그러므로 $n^2$을 4로 나눈 나머지가 3이면서 동시에 0 또는 1이 되는데, 나눗셈 정리에 의해 한 수를 4로 나눈 나머지는 유일하므로 두 주장이 동시에 성립할 수는 없다. 모순이다. 따라서 $n^2 \equiv 3 \pmod 4$인 정수 $n$은 존재하지 않는다. $\blacksquare$ **복기.** 같은 사실을 17주차에서는 케이스 소진으로 증명했다 — $n$을 4로 나눈 나머지 네 가지를 전부 계산해 3이 나오지 않음을 보이는 방식이다. 불가능성은 케이스로도 귀류로도 잡힌다. 두 증명의 관계를 논평하는 것이 23주차 문제 13이다. **검산.** $n = 0, 1, 2, 3, 4, 5$에서 $n^2 = 0, 1, 4, 9, 16, 25$이고 4로 나눈 나머지는 $0, 1, 0, 1, 0, 1$ — 3이 한 번도 나오지 않는다 ✓. ### 문제 20 **접근.** (a)는 §1.7의 표를, (b)는 확인 8을 근거로 삼아 자기 문장으로 다시 쓴다. 서술 문제에서도 채점 기준은 같다 — 주장만 적지 말고 예를 들어 근거를 붙인다. 예제 2.1~2.3이 그 예다. **풀이.** (예시 답안) (a) 공통점: 두 기법 모두 결론의 부정을 가정 쪽으로 옮겨, 직접 증명이 막히는 자리에서 전개 가능한 재료를 만든다. 차이: 대우 증명은 $\neg Q$에서 출발해 $\neg P$라는 **정해진 도착점**으로 가야 하지만, 귀류법은 $\neg P$에서 출발해 어떤 모순이든 하나만 터뜨리면 되는 **열린 도착점**을 가진다. (b) 장점: 도착점이 열려 있으므로 어느 방향의 충돌이든 이용할 수 있고, 따라서 적용 범위가 가장 넓다 — 예제 2.1은 부등식 충돌, 예제 2.2는 약분 가능성 충돌, 예제 2.3은 나누어떨어짐 충돌로 서로 전혀 다른 방향이었지만 셋 다 같은 기법으로 처리되었다. 단점: 목표가 정해져 있지 않으므로 전개가 어디로 가는지 모른 채 밀고 나가야 하고, 모순이 나오지 않는 길로 오래 갈 수 있다 — 문제 18에서 본 대로, 모순이 나오지 않을 때 그것이 전개 부족 때문인지 명제가 거짓이기 때문인지도 기법 자체는 알려 주지 않는다. **복기.** 이 두 물음의 답이 곧 기법 선택의 기준이 된다. 직접 증명이 되면 직접, 조건문이고 가정 쪽이 빈약하면 대우, 결론이 부정형이거나 비존재형이면 귀류 — 이 순서를 정식으로 정하는 것이 22주차다. --- **다음 주 예고:** 귀류법을 조건문 $P \Rightarrow Q$에 적용한다. 조건문의 부정은 $P \land \neg Q$이므로(9주차), 가정이 하나가 아니라 **두 개**가 손에 들어온다. 그리고 대우 증명이 사실 귀류법의 특수한 경우임을 확인하고, "어떤 기법을 언제 쓰는가"의 선택 기준을 완성한다. 이번 주에 빌려 쓴 두 사실(기약분수 표현, 소수 약수의 존재)은 33주차에서 회수한다.