# C7주차 · 강의 — 예제 · 연습 · 해설 ## 예제 — 세 기술을 함께 만들기 완성된 답안을 먼저 보이지 않는다. 설계부터 한 줄씩 만든다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다. ### 예제 2.1 — 반례: 거짓 ∀ 명제 셋을 반증하기 **과제.** 다음 세 명제가 거짓임을 반례로 보이라. - $A$: 모든 소수는 홀수이다. - $B$: 모든 실수 $x$에 대해 $x^2 > x$이다. - $C$: 정수 $a, b$에 대해, $a \mid b^2$이면 $a \mid b$이다. **설계 — 쓰기 전에 정하는 두 가지.** 반증도 증명이므로 출발점과 도착점을 먼저 정한다. 반증에서 출발점과 도착점은 원래 명제가 아니라 **그 부정**에서 나온다. | | **말** | **수식 번역** | |---|---|---| | 출발점 (가정이 주는 것) | 없다 — 반증에는 가정이 없다 | 무대의 조건만 남는다 | | 도착점 (만들 것) | $C$가 거짓이다 | $\underline{\quad(?)\quad}$ | :::{container} quotebox **확인 10.** 도착점 칸을 채워 보자. "$C$가 거짓이다"를 S10주차의 규칙으로 전개하면 무엇을 증명해야 하는가. 규칙 번호까지 적는다. ::: :::{admonition} 답 :class: quotebox dropdown $\exists\, a, b \in \mathbb{Z}$: $a \mid b^2$ 이고 $a \nmid b$ [N5, N4]. 먼저 N5로 $\forall$를 뒤집어 $\exists$를 만들고, 이어 N4로 본체 조건문을 $\land$로 푼다. 도착점이 **존재 명제**가 되었으므로 이제 할 일은 구성법이다 — 증인을 내놓고 두 조각을 각각 검증한다. 출발점이 없다는 점은 걱정거리가 아니다. 존재 증명은 원래 가정에서 밀고 나가는 것이 아니라 증인을 만들어 내놓는 일이다. ::: **증인 찾기.** $C$의 반례가 되려면 $a \mid b^2$이면서 $a \nmid b$여야 한다. $a$가 $b^2$은 나누는데 $b$는 못 나누려면, $a$가 $b$의 소인수를 **중복해서** 가져야 한다. 가장 작은 후보는 $b = 2$, $a = 4$다. :::{container} quotebox **확인 11.** $A$와 $B$의 증인도 각각 찾아 보자. $B$에서는 어느 구간을 뒤져야 하는가. ::: :::{admonition} 답 :class: quotebox dropdown $A$: $x_0 = 2$. 짝수인 소수를 찾으면 되고, 소수를 작은 것부터 훑으면 첫 번째가 곧 답이다. $B$: $x_0 = \tfrac12$. $x^2 > x$는 양변을 $x$로 비교하는 문제이므로 $x$가 $0$과 $1$ 사이일 때 제곱이 작아진다. 경계와 특수 구간($0$, $1$, 음수, $0$과 $1$ 사이)을 먼저 뒤지는 것이 반례 수색의 표준 순서다 — 1권 29주차의 수색 목록과 같다. ::: :::{container} quotebox **확인 12.** 증인 $(a, b) = (4, 2)$의 **자격 검증**을 계산으로 적어 보자. 무엇을 보여야 하는가. ::: :::{admonition} 답 :class: quotebox dropdown 무대 소속과 가정 성립을 나란히 보인다: $4$와 $2$는 정수이므로 무대 안에 있고, $b^2 = 2^2 = 4$이고 $4 = 4 \cdot 1$이므로 $4 \mid 4$, 곧 $a \mid b^2$이다. 나눗셈의 정의를 실제로 적용해 정수 $k = 1$을 제시한 것이 검증이다. "$4$는 $4$를 나눈다, 당연하다"로 넘어가지 않는다 — 정의 꼴을 적는 것이 채점 대상이다. ::: :::{container} quotebox **확인 13.** 이어서 **사건 검증**을 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown 결론 "$a \mid b$"가 위반됨을 보인다: $4k = 2$인 정수 $k$는 없다($k = \tfrac12$은 정수가 아니다). 따라서 $4 \nmid 2$이다. 여기서도 정의로 돌아가 "그런 정수가 없음"을 말한 것이 요점이다. ::: :::{container} quotebox **확인 14.** 마지막 문장을 완성해 보자: "따라서 $\underline{\qquad}$이므로 명제 $C$는 거짓이다." ::: :::{admonition} 답 :class: quotebox dropdown "따라서 $a \mid b^2$이면서 $a \nmid b$인 정수쌍이 존재하므로 명제 $C$는 거짓이다." 도착점(확인 10에서 정한 존재 명제)이 증명되었음을 선언하고 끝낸다. 반증도 증명이므로 $\blacksquare$를 단다. ::: **완성본 ($C$의 반증).** 방금 만든 문장을 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 "왜"에 스스로 답해 본다. | 증명의 한 줄 | 왜 이 줄을 쓰는가? | |---|---| | 명제 $C$가 거짓임을 보인다. 곧 "$a \mid b^2$이고 $a \nmid b$인 정수 $a, b$가 존재한다"를 증명한다 [N5, N4]. | 반례 서식 걸음 ①. 도착점을 문장으로 못 박는다. 이 줄이 없으면 아래 두 검증이 무엇을 향한 것인지 확정되지 않는다. | | $a = 4$, $b = 2$로 두자. | 걸음 ②. 증인을 실제로 내놓는다 — 구성법의 "두자"다(S5주차). 검증이 가리킬 대상이 여기서 생긴다. | | $4$와 $2$는 정수이므로 무대 안에 있고, $b^2 = 4 = 4 \cdot 1$이므로 $a \mid b^2$이다. | 걸음 ③ 자격 검증. 무대 확인과 가정 확인을 한 줄에 나란히 둔다. 무대 조각을 빠뜨리면 §1.3의 삭제 실험이 경고한 자리가 열린다. | | $4k = 2$인 정수 $k$는 존재하지 않으므로 $a \nmid b$이다. | 걸음 ④ 사건 검증. 결론이 위반됨을 정의로 보인다. 이 줄과 앞 줄이 **둘 다** 있어야 반례가 완성된다. | | 따라서 그러한 정수쌍이 존재하므로 명제 $C$는 거짓이다. $\blacksquare$ | 도착점의 선언. 반증도 증명이므로 끝 표시를 단다. | **세 명제의 반례 정리.** | **명제** | **증인** | **자격 검증** | **사건 검증** | |---|---|---|---| | $A$ | $x_0 = 2$ | $2$는 소수이다 (약수가 $1$과 $2$뿐) | $2 = 2 \cdot 1$이므로 짝수이고, 따라서 홀수가 아니다 | | $B$ | $x_0 = \tfrac12$ | $\tfrac12$은 실수이다 | $\left(\tfrac12\right)^2 = \tfrac14$이고 $\tfrac14 < \tfrac12$이므로 $x^2 > x$가 위반된다 | | $C$ | $(a, b) = (4, 2)$ | $4$와 $2$는 정수이고 $4 \mid 4 = 2^2$ | $4 \nmid 2$ | $A$와 $B$는 조건문이 아니므로 자격 검증이 "무대에 속함"만 확인하면 되고, $C$는 조건문이므로 자격 검증이 **가정의 성립**까지 요구한다. 이 차이가 §1.3 표의 첫 조각이 조건문에서 무거워지는 자리다. ### 예제 2.2 — 귀류: 소수 $p$에 대해 $\sqrt p$는 무리수 **Result.** $p$가 소수이면 $\sqrt p$는 무리수이다. 이번에는 설계만 함께 하고, 본문은 완성본으로 본다. :::{container} quotebox **확인 15.** 번역표를 채워 보자. 가정: $p$는 $\underline{\quad}$이다. 결론: $\sqrt p$는 유리수가 $\underline{\quad}$. 결론이 부정형이므로 §1.5의 거래를 쓴다 — 개시문은 무엇인가. ::: :::{admonition} 답 :class: quotebox dropdown 가정: $p$는 **소수**이다. 결론: $\sqrt p$는 유리수가 **아니다**. 개시문: "결론을 부정하여, $\sqrt p$가 유리수라고 가정하자." 유리수라는 가정에서 곧바로 등식 $\sqrt p = a/b$가 나오고, 여기에 "기약분수로 잡을 수 있다"는 조각을 **개시문에서 미리 얹어 둔다**. 이 조각이 나중에 산지 ②의 충돌 상대가 된다 — 얹어 두지 않으면 모순을 만들 곳이 없다. ::: | 증명의 한 줄 | 왜 이 줄을 쓰는가? | |---|---| | $p$를 소수라 하자. 결론을 부정하여, $\sqrt p$가 유리수라고 가정한다. | 귀류 걸음 ①. 부정형 결론이 등식을 주는 가정으로 바뀐다. | | 그러면 $\sqrt p = \dfrac ab$인 양의 정수 $a, b$가 존재하고, 기약분수로 잡을 수 있으므로 $\gcd(a, b) = 1$이라 하자. | 개시문의 정규화. $\gcd(a,b) = 1$이 뒤에서 충돌할 당사자이므로 지금 확보한다. | | 양변을 제곱하면 $p = \dfrac{a^2}{b^2}$이고, 양변에 $b^2$을 곱하면 $a^2 = p b^2$이다. | 걸음 ②의 시작. 무리수를 다루는 유일한 통로는 제곱해서 유리식으로 바꾸는 것이다. | | 따라서 $p \mid a^2$이다. $p$는 소수이므로 유클리드 보조정리에 의해 $p \mid a$이다. | 근거 ④. 정리의 가정("$p$는 소수")이 충족됨을 밝히고 결론을 가져온다. 합성수에서는 이 줄이 무너진다(예제 2.1의 $C$). | | $a = pk$인 정수 $k$가 존재한다. 대입하면 $p^2 k^2 = p b^2$이고, 양변을 $p$로 나누면 $b^2 = p k^2$이다. | 얻은 나눗셈을 등식으로 풀어 다시 전진한다. $p \neq 0$이므로 나눗셈이 허용된다. | | 따라서 $p \mid b^2$이고, 같은 이유로 $p \mid b$이다. | 유클리드 보조정리를 두 번째로 적용한다. | | 그런데 $p \mid a$이고 $p \mid b$이므로 $p$는 $a$와 $b$의 공약수이고 $p \ge 2$이다. 이는 $\gcd(a, b) = 1$과 모순이다 [산지 ②]. | 걸음 ③. 충돌한 두 문장을 둘 다 지목한다. "$p$는 공약수"와 "$\gcd(a,b)=1$"이 당사자다. | | 따라서 $\sqrt p$는 무리수이다. $\blacksquare$ | 걸음 ④. 원래 결론의 문장으로 돌아온다. | :::{container} quotebox **확인 16.** 이 증명에서 "$p$는 소수"라는 가정이 실제로 소비되는 줄은 어디인가. 그 줄을 합성수 $p = 4$로 바꾸면 무엇이 무너지는가. ::: :::{admonition} 답 :class: quotebox dropdown 유클리드 보조정리를 인용하는 두 줄이다. 그 밖의 줄은 $p$가 소수라는 사실을 쓰지 않는다. $p = 4$로 바꾸면 "$4 \mid a^2 \Rightarrow 4 \mid a$"가 필요한데 이것은 거짓이다 — $a = 2$가 반례다(예제 2.1의 $C$). 실제로 $\sqrt4 = 2$는 유리수이므로 결론 자체가 거짓이 된다. **가정이 어느 줄에서 소비되는지 짚는 것**이 증명을 읽는 기술의 절반이다. ::: ### 예제 2.3 — 비구성적 존재: 무리수의 무리수 거듭제곱 **Result.** 어떤 두 무리수 $a, b$가 존재하여 $a^b$가 유리수이다. 이번에는 설계부터 스스로 해 보자. :::{container} quotebox **확인 17.** 번역표를 채워 보자. 도착점: $\underline{\qquad}$. 증인을 역산으로 만들 수 있는가 — $a^b$가 유리수가 되는 무리수 쌍의 공식이 있는가. ::: :::{admonition} 답 :class: quotebox dropdown 도착점: $\exists\, a, b$: $a$와 $b$가 무리수이고 $a^b \in \mathbb{Q}$. 역산은 막힌다. $a^b$가 유리수가 되도록 하는 무리수 쌍을 직접 만드는 공식이 이 시점의 도구로는 없다(S5주차 공급로 ①$\cdot$②가 둘 다 막힌 상태다). 남은 것은 공급로 ③ — 증인을 짓지 않고 존재를 보장하는 논증이며, 이번에는 인용할 기성 정리 대신 **경우법**(S15주차)이 그 일을 한다. ::: **증명 (비구성적).** $\sqrt2^{\sqrt2}$를 생각하자. 이 수는 유리수이거나 무리수이고, 두 경우가 전부다. - **경우 1: $\sqrt2^{\sqrt2}$가 유리수인 경우.** $a = b = \sqrt2$로 두자. $\sqrt2$는 무리수이므로 $a$와 $b$는 자격을 만족하고, $a^b = \sqrt2^{\sqrt2}$는 이 경우의 가정에 의해 유리수이다. 그러한 쌍이 존재한다. - **경우 2: $\sqrt2^{\sqrt2}$가 무리수인 경우.** $a = \sqrt2^{\sqrt2}$, $b = \sqrt2$로 두자. $a$는 이 경우의 가정에 의해 무리수이고 $b$도 무리수이므로 자격을 만족한다. 또한 $$ a^b = \left(\sqrt2^{\sqrt2}\right)^{\sqrt2} = \sqrt2^{\;\sqrt2 \cdot \sqrt2} = \sqrt2^{\,2} = 2 $$ 이고 $2$는 유리수이다. 그러한 쌍이 존재한다. 두 경우가 모든 가능성을 덮고 각 경우에서 그러한 쌍이 존재하므로, 어느 경우든 그러한 무리수 $a, b$가 존재한다. $\blacksquare$ 이 증명은 표 없이 산문으로 적었다. 표는 연습 단계의 장치이고, 실전의 답안은 처음부터 끝까지 이런 산문이다. 증명이 끝났지만 $\sqrt2^{\sqrt2}$가 유리수인지 무리수인지는 여전히 모른다. 따라서 증인 $(a, b)$가 $(\sqrt2, \sqrt2)$인지 $(\sqrt2^{\sqrt2}, \sqrt2)$인지도 특정되지 않았다. 그럼에도 존재는 확립되었다 — 두 후보 중 적어도 하나는 반드시 작동하기 때문이다. 이것이 비구성적 존재 증명의 표준 모양이다. ($\sqrt2^{\sqrt2}$는 실제로 무리수임이 알려져 있으나 그 정리는 이 과정의 목록 밖이고, 위 증명은 그것 없이 성립한다 — 확인 9의 (나)가 이 점이었다.) ### 관찰 — 세 예제의 같은 뼈대 예제 2.1, 2.2, 2.3은 소재가 전혀 다르지만 상대하는 것이 같다. | **항목** | **예제 2.1 (반례)** | **예제 2.2 (귀류)** | **예제 2.3 (존재)** | |---|---|---|---| | 실제로 증명한 명제의 꼴 | $\exists$ — 가정 성립$\cdot$결론 위반인 쌍이 있다 | $\neg\exists$ — $\sqrt p = a/b$인 기약 정수쌍은 없다 | $\exists$ — 조건을 만족하는 무리수 쌍이 있다 | | 증인을 답안에 적었는가 | 적었다 ($4, 2$) | $\underline{\quad(1)\quad}$ | $\underline{\quad(2)\quad}$ | | 무엇으로 마무리했는가 | 자격 검증과 사건 검증 | $\underline{\quad(3)\quad}$ | 경우법 — 두 경우 모두에서 존재 확인 | :::{container} quotebox **확인 18.** 표의 (1)(2)(3)을 채우고, 세 예제가 공통으로 상대하는 것을 한 낱말로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) 적지 않았다 — 없음을 주장하는 명제이므로 적을 증인이 아예 없다. 대신 있다고 가정한 뒤 그 가정을 무너뜨렸다. (2) 적지 않았다 — 두 후보를 제시했으나 어느 쪽이 실제 증인인지는 특정하지 않았다. (3) 모순 명시와 결론 복귀 (귀류 걸음 ③④). 공통으로 상대하는 것: **존재 명제($\exists$)**. ::: 방금 확인한 뼈대에 이름을 붙인다. :::{admonition} 백지 암기 대상 :class: keybox **이번 주의 세 기술** 세 기술은 모두 "무엇이 있고 무엇이 없는가"를 상대한다. ① **만들어 내놓는다** — 구성적 존재 증명, 그리고 반례(반례는 부정 전개가 만들어 낸 $\exists$ 를 구성으로 증명하는 것이다). ② **있음만 보장한다** — 비구성적 존재 증명(기성 정리$\cdot$경우법$\cdot$비둘기집). ③ **결론의 부정을 가정으로 삼아 무너뜨린다** — 귀류. 결론이 부재 명제일 때는 그 부정이 $\exists$ 이므로 대상에 이름을 붙여 받고, 부등식$\cdot$무리수처럼 $\exists$ 가 아닌 무대에서는 부정이 준 등식$\cdot$부등식을 그대로 전개한다. $\exists$ 로 묶이는 것은 ①②의 두 기술까지다. ③의 귀류는 §1.5의 네 무대 전체에서 운용되며, 그중 부재 무대에서만 $\exists$ 를 직접 상대한다. ::: 이 세 자세가 C8주차의 최소 반례법에서 한 번에 결합된다 — "반례가 있다면 가장 작은 것이 있다"(③ + 최소원리)를 잡아 무너뜨리는 기법이다. ## 빈칸 사다리 — 지지대를 하나씩 빼며 예제의 필사에서 자립으로 넘어가는 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 §6에 있다 — 다 채운 뒤에 대조한다. ### 훈련 1 ●○○ — 수식과 절차의 빈칸 **Result.** $\sqrt2 + \sqrt6$은 무리수이다. **증명.** 결론을 부정하여 $s = \sqrt2 + \sqrt6$이 $\underline{\quad(1)\quad}$라 가정하자. 양변을 제곱하면 $$ s^2 = 2 + 2\sqrt{12} + 6 = \underline{\quad(2)\quad} $$ 이므로 $\sqrt3 = \dfrac{s^2 - 8}{\underline{\quad(3)\quad}}$이다. 우변은 유리수의 대수 조작이므로 유리수이고 [닫힘성], 곧 $\sqrt3$이 유리수이다. 그런데 $\sqrt3$은 $\underline{\quad(4)\quad}$이다 (1권 21주차 문제 7). 모순이다. 따라서 $\sqrt2 + \sqrt6$은 무리수이다. $\blacksquare$ 검산: $\sqrt{12} = 2\sqrt3$이므로 $2\sqrt{12} = \underline{\quad(5)\quad}\sqrt3$이다. ### 훈련 2 ●●○ — 수식과 근거를 함께 이번에는 구조 낱말과 근거 문장, 산지 번호도 빈칸이다. **Result.** $r$가 $0$이 아닌 유리수이고 $t$가 무리수이면 $rt$는 무리수이다. **증명.** $r$를 $0$이 아닌 유리수, $t$를 무리수라 하자. 결론을 부정하여 $rt$가 $\underline{\quad(1)\quad}$라 가정하고, $rt = q$라 하자. $r \neq 0$이므로 양변을 $r$로 나누면 $$ t = \underline{\quad(2)\quad} $$ 이다. $q$와 $r$가 유리수이고 $r \neq 0$이므로, $\underline{\quad(3)\quad}$에 의해 우변은 유리수이다. 곧 $t$가 유리수이다. 그런데 가정에 의해 $t$는 $\underline{\quad(4)\quad}$이다. 두 문장이 충돌하므로 모순이다 [산지 $\underline{\quad(5)\quad}$]. 따라서 $\underline{\quad(6)\quad}$. $\blacksquare$ ### 훈련 3 ●●● — 뼈대만 남기고 이번에는 반례 서식의 네 걸음을 통째로 채운다. (1권 29주차 예제 2.1의 재방문 — 반례 자체는 이미 아는 것이므로, 이번의 학습 목표는 수색이 아니라 그 반례를 §1.4의 4단 서식 칸에 배치하는 것이다.) **주장.** 모든 자연수 $n$에 대해 $n^2 - n + 11$은 소수이다. $n = 1$부터 $n = 10$까지는 각각 $11, 13, 17, 23, 31, 41, 53, 67, 83, 101$로 전부 소수다. 그럼에도 이 주장은 거짓이다. **반증의 뼈대.** §1.4의 4단 서식의 각 칸을 통째로 채운다. - ① 부정 전개: $\underline{\quad(1)\quad}$ - ② 증인 제시: $\underline{\quad(2)\quad}$ - ③ 자격 검증: $\underline{\quad(3)\quad}$ - ④ 사건 검증과 결론: $\underline{\quad(4)\quad}$ (증인을 찾는 방향에 대한 안내: $n^2 - n + 11 = n(n-1) + 11$이므로, $n \equiv 0$ 또는 $n \equiv 1 \pmod{11}$이면 $n(n-1)$이 $11$의 배수이고 따라서 값 전체가 $11$의 배수가 된다. 다만 $n = 1$은 값이 $11$ 자신이라 합성수가 아니므로 제외되고, 그 다음이 $n = 11$과 $n = 12$이다.) ## 연습문제 (20문항) 해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 '접근'까지만 읽고 다시 시도한다 $\to$ 그래도 안 되면 풀이를 읽는다. :::{admonition} 이번 주의 채점 기준 :class: quotebox 답이 아니라 **근거**가 점수다. 세 기술마다 채점 항목이 정해져 있다. 반례: 증인 제시 + **두 검증**(자격$\cdot$사건). 하나만 있으면 미완성이다. 귀류: 4단 서식의 네 걸음 + 모순의 **두 당사자 지목** + 산지 번호. 존재: 구성적이면 증인 제시 + 자격$\cdot$사건 검증, 비구성적이면 존재를 보장하는 논증의 근거 명시. 답안 어딘가에 "구성적/비구성적" 중 무엇인지 한 줄로 밝힌다. 난이도와 무관하게, 힌트 상자는 5분 이상 막힌 뒤에만 연다. ::: ### 기본 ●○○ **1.** [백지] 반례 서식, 귀류 4단$\cdot$3산지, 존재 증명의 두 스타일(구성적/비구성적), "정확히 하나"의 구조를 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown 서식은 걸음의 목록만 외우면 절반이다. 걸음마다 "이것을 빼면 무엇이 무너지는가"를 함께 적어 두면, 일부를 잊었을 때 나머지에서 복구할 수 있다. §1.4와 §1.5의 두 해부 표가 그 복구의 재료다. ::: **2.** 다음 거짓 명제를 반례로 반증하시오. (a) 모든 정수 $n$에 대해 $2^n > n^2$. (b) 모든 실수 $x$에 대해 $\sqrt{x^2} = x$. (c) 모든 소수의 합은 소수이다 (두 소수의 합). :::{admonition} 힌트 :class: quotebox dropdown (a) 작은 $n$부터 표를 만든다. $n = 1, 2, 3, 4$에서 좌변과 우변을 나란히 적으면 부등호가 뒤집히거나 등호가 되는 자리가 보인다. (b) 양수에서는 성립한다. 무너지는 곳은 부호가 개입하는 자리다. (c) 소수 중 하나만 성질이 다른 수가 있다 — 그 수를 두 번 쓰면 어떻게 되는가. ::: **3.** 예제 2.1의 세 반례를 백지 재현하시오. :::{admonition} 힌트 :class: quotebox dropdown 증인만 적으면 절반이다. 세 명제 각각에 대해 자격 검증과 사건 검증을 문장으로 적는다. $C$는 조건문이므로 자격 검증이 "가정의 성립"임을 잊지 않는다. ::: **4.** 빈칸 훈련(§3의 훈련 1~3)을 백지에서 완성하시오. :::{admonition} 힌트 :class: quotebox dropdown 훈련 1과 2는 개시문에서 무엇을 얻는지가 전부다 — "유리수라 가정하면 등식이 생긴다". 훈련 3은 반례이므로 개시문이 아니라 부정 전개로 시작한다. ::: **5.** 예제 2.2($\sqrt p$ 무리수)를 백지 재현하시오 (4단 라벨). :::{admonition} 힌트 :class: quotebox dropdown 네 걸음의 라벨을 먼저 여백에 적어 두고 그 사이를 채운다. 유클리드 보조정리가 두 번 쓰인다는 것과, 마지막 충돌 상대가 개시문에 얹어 둔 $\gcd(a,b)=1$이라는 것을 기억하면 나머지는 계산이다. ::: **6.** 예제 2.3(무리수 거듭제곱)을 백지 재현하고, "비구성적"인 이유를 한 문장으로 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown 두 경우로 나누는 기준이 무엇이었는지부터 적는다. "비구성적"의 이유는 증명이 끝난 뒤에도 답하지 못하는 질문이 무엇인지 생각하면 나온다. ::: ### 표준 ●●○ **7.** $\sqrt5$가 무리수임을 귀류로 증명하시오 (예제 2.2의 $p=5$ 사례, 4단 서식). **8.** "가장 큰 소수는 없다"(= 소수가 무한히 많다)를 귀류로 증명하시오 (S11 문제 15의 재방문 — 전체 목록 + $N = p_1\cdots p_k + 1$). :::{admonition} 힌트 :class: quotebox dropdown 개시문에서 "소수가 유한 개"라고만 적으면 다음 줄이 나오지 않는다. 유한 개라는 사실에서 **전체 목록** $p_1, \ldots, p_k$를 꺼내 이름을 붙이는 것이 걸음 ①의 일이다. 목록에 이름이 붙어야 곱할 수 있고, 곱해야 $N$을 만들 수 있다. $N$이 소인수를 가진다는 사실도 별도의 근거로 밝힌다. ::: **9.** 존재 증명 (구성적): "$x^2 - x - 1 = 0$인 실수가 존재한다"를 증명하시오 (근의 공식으로 증인 $\frac{1 + \sqrt5}2$ 제시$\cdot$검증 — 구성적). **10.** 다음 제시된 증명을 평가하시오 (C5주차의 증명 평가). :::{admonition} 제시된 증명 — 평가 대상 :class: quotebox **Result.** $\sqrt2$는 무리수이다. **증명.** $\sqrt2 = 1.41421356\ldots$는 소수점 아래가 순환하지 않으므로 무리수이다. ::: :::{admonition} 힌트 :class: quotebox dropdown 결론은 참이다. 그러니 결론을 의심하지 말고 **근거**를 의심한다. "소수점 아래가 순환하지 않는다"를 이 답안은 어떻게 알았는가. 유한 개의 자릿수를 관찰해서 순환하지 않음을 확정할 수 있는가 — 순환 주기가 관찰 범위보다 길다면? ::: **11.** 존재 + 유일 (구성적): "$3x - 7 = 0$인 유리수가 정확히 하나 존재함"을 증명하시오 (존재: $x = \frac73$; 유일: S13 얼굴 1). **12.** 반례 수색: 다음 각 명제의 참$\cdot$거짓을 판정하고, 거짓이면 반례를 제시하시오. (a) $a \mid b$이고 $a \mid c$이면 $a \mid bc$. (b) $a \mid bc$이면 $a \mid b$ 또는 $a \mid c$. (c) $a^2 = b^2$이면 $a = b$ (정수). :::{admonition} 힌트 :class: quotebox dropdown 세 문항의 성격이 다르다. 하나는 참이므로 증명해야 하고, 둘은 거짓이므로 두 검증을 갖춘 반례가 필요하다. (b)는 예제 2.1의 $C$가 그대로 재료이고, (c)는 제곱이 부호를 지운다는 점을 노린다. ::: **13.** 비구성적 존재 (중간값): "$x^5 + x - 1 = 0$인 실수가 존재한다"를 중간값 정리로 증명하시오 (구성 없이 — $f(0) = -1 < 0 < 1 = f(1)$; S5 문제 18). "값을 모르지만 존재"를 확인하시오. :::{admonition} 이 문제가 인정하고 쓰는 사실 — 중간값 정리 :class: quotebox 닫힌 구간 $[c, d]$에서 연속인 함수 $f$가 $f(c) < 0 < f(d)$를 만족하면, $f(x_0) = 0$인 $x_0$가 $c$와 $d$ 사이에 존재한다. 이 정리는 1권 47주차의 연속 개념 위에 서지만 증명은 이 과정의 범위 밖이므로 끝까지 채택한 채로 쓴다 (S5주차 문제 18과 같은 취급). 이 정리는 해가 있다는 것만 말하고 값은 말하지 않는다 — 그래서 비구성적이다. ::: :::{admonition} 힌트 :class: quotebox dropdown 정리를 인용하려면 그 가정이 충족됨을 먼저 밝혀야 한다. 가정은 둘이다: 연속성과 부호 변화. 다항함수의 연속성은 인정하고 쓰되 그 사실을 답안에 적는다. ::: **14.** 귀류 in 부등식: "모든 $\varepsilon > 0$에 대해 $a < \varepsilon$인 실수 $a$는 $a \le 0$"을 귀류로 증명하시오 (S12 문제 16의 귀류판 — $a > 0$ 가정 $\to$ $\varepsilon = a$ 또는 $\frac a2$ 투입 $\to$ 모순). :::{admonition} 힌트 :class: quotebox dropdown 가정은 "**모든** $\varepsilon > 0$에 대해"이므로 특수화(S7주차)를 쓸 수 있다 — 양수를 하나 골라 $\varepsilon$ 자리에 넣으면 된다. 개시 가정 $a > 0$이 바로 그 양수를 공급한다. 그런데 $\varepsilon = a$를 넣으면 $a < a$가 나오고, $\varepsilon = a/2$를 넣으면 다른 모양의 모순이 나온다. 둘 다 유효하니 각각 어느 산지인지 따져 본다. ::: ### 도전 ●●● **15.** ($\sqrt2 + \sqrt3$ 종합) $\sqrt2 + \sqrt3$이 무리수임을 두 방법으로 증명하시오: (a) 귀류 + 제곱($\sqrt6$의 무리성을 경유) (b) $s - \sqrt2 = \sqrt3$으로 옮긴 뒤 제곱해 $\sqrt2$가 유리수임을 유도. 두 경로를 비교하시오. :::{admonition} 힌트 :class: quotebox dropdown 두 경로의 차이는 **어느 무리수를 고립시키는가**이다. (a)는 통째로 제곱해 $\sqrt6$을 고립시키고, (b)는 한 항을 옮긴 뒤 제곱해 $\sqrt2$를 고립시킨다. (b)에서 나누기가 필요하므로 $s \neq 0$을 밝혀야 한다. ::: **16.** (비구성적의 힘) "10개의 서로 다른 두 자리 정수 중에서, 합이 같은 두 부분집합이 존재한다"를 비둘기집으로 증명하시오 (부분집합 개수 $2^{10} = 1024 >$ 가능한 합의 범위 — 구성 없이 존재만; 1권 26주차 문제 19의 비둘기집). "어느 두 부분집합인지 모르지만 존재"를 확인하시오. :::{admonition} 이 문제가 인정하고 쓰는 사실 — 비둘기집 원리 :class: quotebox $n$개의 물건을 $m$개의 상자에 넣을 때 $n > m$이면, 물건이 둘 이상 든 상자가 존재한다. 1권 26주차 문제 19가 이 원리를 양말 문제로 다루었다. 지금은 증명 없이 인정하고 쓴다(정식 증명은 귀류다 — 각 상자에 하나 이하라면 전체가 $m$개 이하). 이 원리는 "그런 상자가 있다"만 주고 "어느 상자인지"는 주지 않는다. ::: :::{admonition} 힌트 :class: quotebox dropdown 물건과 상자를 무엇으로 삼을지 정하는 것이 전부다. 물건 = 부분집합, 상자 = 합의 값. 상자의 개수를 세려면 합이 가질 수 있는 값의 범위를 위아래로 막아야 한다 — 가장 큰 10개의 두 자리 정수는 $90, 91, \ldots, 99$이다. ::: **17.** (귀류 + 무한강하 맛보기) "$x^2 = 2y^2$인 양의 정수 $x, y$는 없다"를 증명하시오 ($\sqrt2$ 무리성과 동치 — 귀류: 최소 해 $(x, y)$ 잡기 $\to$ $x$ 짝수 $\to$ $x = 2x'$ $\to$ $y$ 짝수 $\to$ 더 작은 해 $\to$ 최소성 모순). 최소 반례와 무한강하의 예고 (C8). :::{admonition} 이 문제가 인정하고 쓰는 사실 — 최소원리(정렬성) :class: quotebox 공집합이 아닌 양의 정수 집합에는 최소원소가 존재한다 (1권 33주차). 이 사실을 귀류의 개시에 붙이면 "해가 있다면 가장 작은 해를 잡을 수 있다"가 된다. 다음 주 C8주차의 최소 반례법이 이 조합에 정식 이름을 붙인 것이다. ::: :::{admonition} 힌트 :class: quotebox dropdown "$x^2$이 짝수이면 $x$가 짝수"는 1권 19주차 예제 2.1이다. 이 부품을 $x$에 한 번, $y$에 한 번 쓴다. 마지막에 $(x/2, y/2)$가 **다시 해가 됨**을 등식으로 확인해야 모순이 완성된다 — 확인하지 않으면 "더 작은 해"라고 부를 근거가 없다. ::: **18.** (진단 종합) 다음 제시된 존재 증명을 평가하시오. :::{admonition} 제시된 증명 — 평가 대상 :class: quotebox **Result.** $x^2 = 2$인 유리수가 존재한다. **증명.** $x = \sqrt2$로 두면 $x^2 = 2$이다. 따라서 존재한다. ::: :::{admonition} 힌트 :class: quotebox dropdown S5주차 예제 2.3의 채점표를 그대로 만든다 — 자격 칸과 사건 칸을 나란히 두고 각각 검증되었는지 적는다. 이 명제에서 자격은 "$x$는 유리수"이다. 그리고 이 문항은 채점만으로 끝나지 않는다 — 명제 자체의 진위도 판정해야 한다. ::: **19.** (설계) "연속한 100개의 합성수가 존재한다"를 구성적으로 증명하시오 ($101! + 2, \ldots, 101! + 101$; S5 문제 15의 재방문). 그리고 이것이 "소수 간격이 얼마든지 벌어진다"의 존재 증명임을 한 문장으로 쓰시오. 구성적이지만 증인이 거대한 예이다. :::{admonition} 힌트 :class: quotebox dropdown 합성수의 정의를 정확히 쓰는 것이 채점의 핵심이다 — "$1$보다 큰 두 정수의 곱"이므로 인수 **둘 다** $1$보다 큼을 확인해야 한다. $101! + j$에서 $j$가 인수임을 보이는 것이 절반이고, 나머지 인수가 $1$보다 큼을 보이는 것이 나머지 절반이다. ::: **20.** (서술) (a) "반증 = 부정 전개 + 구성"임을 예제 2.1로 뒷받침하고, 조건문 $\forall$ 반례가 왜 두 검증(가정 참$\cdot$결론 거짓)을 요구하는지 세 문장 이내로 쓰시오. (b) 구성적/비구성적 존재 증명의 차이를 예제 2.3(무리수 거듭제곱)으로 설명하고, 비구성적 증명이 왜 "우아한"지 두 문장 이내로 쓰시오. ## 백지 재현 — 복습 프로토콜 이 과정의 한 주는 다섯 날로 나뉜다. 교안만 보는 주가 아니라 원서와 교안을 번갈아 읽는 주이므로, 백지 재현은 마지막 날에 놓인다. | **요일** | **할 일** | |---|---| | 1일차 | 원서 Chartrand 5장 통독 — 모르는 문장은 표시만 하고 통과한다 | | 2일차 | 교안 §0~§2 — 개념과 예제. 확인 상자를 연필로 먼저 채운다 | | 3일차 | 원서 5장 재독 — 1일차에 표시한 문장을 해결하고, 원서 연습문제 몇 개를 직접 시도한다 | | 4일차 | 교안 §3 빈칸 사다리와 §4 연습문제 20문항 | | 5일차 | 백지 재현 1차(틀 카드)$\cdot$2차(완전 백지) + 체크리스트 | **1차 시도 — 틀 카드 허용.** 세 서식(반례 4단$\cdot$귀류 4단$\cdot$구성법)과 산지 3표만 한 장에 적어 펴 놓고, 예제 2.2를 처음부터 끝까지 적는다. 본문과 계산은 보지 않는다. **2차 시도 — 완전 백지.** 아무것도 보지 않고 수행한다. - [ ] 반례의 정의와 4단 서식을 썼고, 조건문 $\forall$ 반례에 검증이 둘인 이유를 한 문장으로 적었다. - [ ] 귀류 4단 서식과 모순의 3대 산지를 썼다. - [ ] 존재 증명의 두 스타일을 정의로 구분해 썼고, 각각의 예를 하나씩 들었다. - [ ] 예제 2.1의 세 반례를 자격 검증$\cdot$사건 검증까지 재현했다. - [ ] 예제 2.2($\sqrt p$ 무리성)를 4단 라벨과 산지 번호까지 재현했다. - [ ] 예제 2.3(무리수 거듭제곱)을 재현하고 비구성적인 이유를 한 문장으로 적었다. - [ ] "정확히 하나"의 두 책임을 나누어 쓰고, 한쪽만 증명했을 때 무엇이 남는지 말했다. - [ ] 원서 5장을 두 번 읽었고, 1일차에 표시한 문장이 모두 해결되었다. **막힌 지점별 처방.** 막힌 지점이 무엇을 다시 볼지 알려 준다. | **막힌 지점** | **처방** | |---|---| | 반례를 적었는데 채점에서 반쪽으로 처리된다 | §1.4의 걸음 삭제 실험 — 빠진 것은 대개 자격 검증이다 | | 귀류의 첫 문장이 나오지 않는다 | §1.5의 무대 대응표 — 결론이 어느 무대인지 먼저 정하면 개시문의 꼴이 정해진다 | | 전진은 하는데 어디서 멈출지 모른다 | §1.5의 산지 3표 — "지금 가진 사실 중 부딪힐 두 문장"을 찾는다 | | 모순이라고 적었는데 당사자를 못 짚는다 | 예제 2.2의 마지막 두 줄 — 충돌한 두 문장을 이름으로 지목하는 형식 | | 존재 증명에서 무엇을 써야 할지 모른다 | §1.6의 대조표 — 증인을 만들 수 있는지 먼저 판정하고, 막히면 공급로 ③으로 간다 | | 유일성 절이 존재 절과 섞인다 | §1.7 — 두 문단으로 분리하고 각각의 개시문을 다르게 적는다 | 하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다. ## 해설 각 해설은 **접근**(문제 앞에서 무엇을 생각하는가)과 **풀이**로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다. ### 빈칸 사다리 — 훈련 1 (1) 유리수 (2) $8 + 4\sqrt3$ (3) $4$ (4) 무리수 (5) $4$ ※ (2)에서 $\sqrt{12} = \sqrt{4 \cdot 3} = 2\sqrt3$이므로 $2\sqrt{12} = 4\sqrt3$이고, $s^2 = 2 + 4\sqrt3 + 6 = 8 + 4\sqrt3$이다. 이 계산이 훈련 전체의 관절이다 — $\sqrt{12}$를 $\sqrt3$으로 바꾸지 못하면 다음 줄에서 $\sqrt3$을 고립시킬 수 없다. 충돌한 두 당사자는 유도 결과 "$\sqrt3$은 유리수"와 기지의 참 "$\sqrt3$은 무리수"이므로 산지 ③이다. ### 빈칸 사다리 — 훈련 2 (1) 유리수 (2) $\dfrac qr$ (3) 유리수의 나눗셈 닫힘성 (근거 ②; $0$이 아닌 유리수로 나눈 몫은 유리수) (4) 무리수 (5) ① (6) $rt$는 무리수이다 ※ 산지가 ①인 이유는 충돌한 두 당사자가 **유도 결과**("$t$는 유리수")와 **문제의 가정**("$t$는 무리수")이기 때문이다. 훈련 1은 유도 결과가 외부의 기지 사실과 부딪혔으므로 ③이었다. 같은 모양의 계산이라도 충돌 상대가 누구냐에 따라 산지가 갈린다는 점을 여기서 확인한다. $r \neq 0$ 조건이 어느 줄에서 소비되는지도 짚어 둔다 — 나누는 줄이다. ### 빈칸 사다리 — 훈련 3 (1) 주장이 거짓임을 보인다. 곧 "$n^2 - n + 11$이 소수가 아닌 자연수 $n$이 존재한다"를 증명한다 [N5]. (2) $n_0 = 11$로 두자. (3) $11$은 자연수이므로 무대 안에 있다. (4) $11^2 - 11 + 11 = 121 = 11 \cdot 11$이다. $11 > 1$이고 $11 > 1$이므로 $121$은 $1$보다 큰 두 정수의 곱이며, 따라서 소수가 아니다. 그러한 자연수가 존재하므로 주장은 거짓이다. $\blacksquare$ ※ 증인을 찾는 길은 인수분해의 가능성을 만드는 것이다. $n^2 - n + 11 = n(n-1) + 11$ 이므로 $n \equiv 0$ 또는 $n \equiv 1 \pmod{11}$이면 $n(n-1)$이 $11$의 배수이고, 따라서 값 전체가 $11$의 배수가 되어 $11$로 묶인다. 이 조건을 만족하는 가장 작은 자연수는 $n = 1$이지만 그때 값은 $11$ 자신이라 소수이므로 반례가 아니고, 그 다음이 $n = 11$($121 = 11 \cdot 11$)과 $n = 12$($143 = 11 \cdot 13$)이다. 곧 이 조건은 값이 $11$의 배수임까지만 보장하고, 그 값이 $11$보다 커야 합성수가 된다. $n = 1$부터 $10$까지 열 번 성립했다는 사실이 아무것도 보장하지 않는다는 것이 이 훈련의 요점이다. ### 문제 1 **접근.** 암기 항목을 문장으로만 외우면 일부를 잊었을 때 복구할 길이 없다. 각 서식은 **걸음의 목록**이고, 걸음마다 "이것을 빼면 무엇이 무너지는가"가 붙어 있다. 그 붕괴 사례를 함께 외우면 남은 걸음에서 나머지를 재구성할 수 있다. **풀이.** **반례 서식 4단.** ① 부정 전개 — "명제가 거짓임을 보인다. 곧 $\exists x_0$: 가정 성립 $\land$ 결론 위반을 증명한다" [N5, N4]. ② 증인 제시 — "$x_0 = \cdots$로 두자." ③ 자격 검증 — 증인이 무대에 있고 가정을 만족함. ④ 사건 검증 — 결론이 위반됨. ③을 빼면 무대 밖 대상이나 가정을 만족하지 않는 대상이 통과하고, ④를 빼면 평범한 사례가 반례로 불린다. **귀류 4단 서식.** ① 개시 선언("결론을 부정하여 ~라 가정하자" — 부정은 S10주차의 규칙으로 전개) ② 전진 ③ 모순 명시(충돌한 두 문장을 **둘 다** 지목) ④ 결론 선언(원문 복귀). ②에서 부정을 한 번도 쓰지 않으면 귀류의 껍질을 쓴 직접 증명이고, ③이 빠지면 어디서 멈춰도 되는 글이 된다. **모순의 3대 산지.** ① 유도한 것 $\leftrightarrow$ 원래 가정 ② 유도한 것 $\leftrightarrow$ 개시 가정의 다른 조각 ③ 유도한 것 $\leftrightarrow$ 이미 아는 참. **존재 증명의 두 스타일.** 구성적 — 증인을 명시적으로 제시하고 자격과 사건을 검증한다. 비구성적 — 증인을 제시하지 않고 존재만 확립한다(기성 정리 인용, 경우법, 비둘기집, 최소원리). 증명이 끝난 뒤 증인을 아는지가 갈림점이다. **"정확히 하나"의 구조.** 존재(적어도 하나) + 유일(많아야 하나)의 두 문단. 유일은 얼굴 1(둘을 잡아 같음을 보인다)과 얼굴 2(둘이 다르다고 가정해 모순을 낸다) 중 하나로 쓴다. 한쪽만 증명하면 "여러 개일 가능성" 또는 "하나도 없을 가능성"이 남는다. ### 문제 2 **접근.** 세 문항 모두 $\forall$ 명제이므로 증인 하나와 두 검증이면 끝난다. 증인을 찾는 자리는 정해져 있다 — 작은 수, 경계, 부호가 바뀌는 곳, 그리고 "예외적인 원소"다. **풀이.** **(a)** 반례: $n_0 = 3$. $3$은 정수이고(자격), $2^3 = 8$이며 $3^2 = 9$이므로 $8 > 9$가 거짓이다(사건). 따라서 명제는 거짓이다. $n_0 = 2$도 반례다 — $2^2 = 4$이고 $2^2 = 4$ 이므로 $4 > 4$가 거짓이다. $n_0 = 4$ 역시 $16 > 16$이 거짓이라 반례다. 무대가 정수 전체이므로 $0$과 음의 정수까지 훑어 참인 자격을 확정한다: $n = 0$에서 $2^0 = 1 > 0 = 0^2$이라 참이고, $n \le -1$에서는 좌변이 $1$보다 작은 양수인데 우변은 $1$ 이상이라 전부 거짓이다. 따라서 참이 되도록 자격을 수리하면 "$n = 0$, $n = 1$, 또는 $n \ge 5$"이다. **(b)** 반례: $x_0 = -1$. $-1$은 실수이고(자격), $\sqrt{(-1)^2} = \sqrt1 = 1$인데 $1 \neq -1$이다(사건). 따라서 명제는 거짓이다. **(c)** 반례: 소수 $2$와 $2$. 둘 다 소수이고(자격), $2 + 2 = 4 = 2 \cdot 2$는 소수가 아니다(사건). 따라서 명제는 거짓이다. $3 + 5 = 8$도 반례다. **복기.** (b)의 올바른 등식은 $\sqrt{x^2} = \lvert x \rvert$이다. 반례를 찾은 뒤 "그렇다면 참인 명제는 무엇인가"까지 적어 두면, 반례가 명제를 수리하는 방향까지 알려 준다. 이것이 반례의 두 번째 쓸모다. **검산.** (a) $n = 5$에서 $32 > 25$ ✓, $n = 6$에서 $64 > 36$ ✓ — 수리한 자격이 작동한다. 경계 쪽도 훑는다: $n = 0$에서 $2^0 = 1$이고 $0^2 = 0$이므로 $1 > 0$ ✓ — $0$은 수리한 자격에 들어가야 한다. $n = -1$에서 $2^{-1} = 0.5$이고 $(-1)^2 = 1$이므로 $0.5 > 1$이 거짓 ✓ — 음의 정수는 전부 반례이므로 자격에서 빠진다. ### 문제 3 **접근.** 증인만 적는 답안이 가장 흔하다. 세 명제 각각에 대해 자격과 사건을 **문장으로** 적는 것이 이 문항의 목적이고, 특히 $C$는 조건문이므로 자격이 "무대에 속함"이 아니라 "가정의 성립"임을 구분해야 한다. **풀이.** **$A$: 모든 소수는 홀수이다.** 반례: $x_0 = 2$. 자격 — $2$의 양의 약수는 $1$과 $2$ 뿐이므로 $2$는 소수이다. 사건 — $2 = 2 \cdot 1$이므로 $2$는 짝수이고, 따라서 홀수가 아니다. 그러한 소수가 존재하므로 $A$는 거짓이다. **$B$: 모든 실수 $x$에 대해 $x^2 > x$.** 반례: $x_0 = \tfrac12$. 자격 — $\tfrac12$은 실수이다. 사건 — $\left(\tfrac12\right)^2 = \tfrac14$이고 $\tfrac14 < \tfrac12$이므로 $x^2 > x$가 성립하지 않는다. 따라서 $B$는 거짓이다. **$C$: $a \mid b^2$이면 $a \mid b$.** 반례: $(a, b) = (4, 2)$. 자격 — $4$와 $2$는 정수이므로 무대 안에 있고, $b^2 = 4 = 4 \cdot 1$이므로 $4 \mid b^2$이다. 사건 — $4k = 2$인 정수 $k$가 없으므로 $4 \nmid 2$이다. 따라서 $C$는 거짓이다. **복기.** $C$의 반례가 존재하는 구조적 이유는 $4 = 2^2$이라는 것이다. $a$가 $b$의 소인수를 중복해서 가지면 $a$는 $b^2$을 나누면서 $b$는 나누지 못할 수 있다. $a$가 소수일 때 이 일이 일어나지 않는다는 것이 유클리드 보조정리이고, 예제 2.2가 그 정리를 쓰는 자리다. 반례와 정리가 정확히 서로의 경계를 그린다. ### 문제 4 **접근.** 사다리의 세 훈련은 지지대가 다르므로 백지에서 막히는 지점도 다르다. 훈련 1과 2는 개시문에서 무엇을 얻는지가 전부이고, 훈련 3은 개시문이 아니라 부정 전개로 시작한다는 것이 첫 갈림길이다. **풀이.** 훈련 1$\cdot$2$\cdot$3의 답은 위의 사다리 해설 세 항목에 있다. 백지 재현에서 확인할 것은 다음 세 가지다. ① 훈련 1에서 $\sqrt{12} = 2\sqrt3$ 변환을 스스로 떠올렸는가 — 이 변환이 없으면 $\sqrt3$을 고립시키지 못한다. ② 훈련 2에서 $r \neq 0$을 나누는 줄에서 인용했는가 — 조건이 어느 줄에서 소비되는지 짚는 것이 채점 항목이다. ③ 훈련 3에서 자격 검증("$11$은 자연수")을 적었는가 — 사건만 적고 넘어가는 답안이 가장 많다. **복기.** 세 훈련의 공통 골격은 "부정에서 등식을 얻거나(1$\cdot$2), 증인에서 계산을 얻는다(3)" 이다. 어느 쪽이든 **말을 등식으로 바꾸는 자리**가 첫 걸음이라는 점은 1권 1주차 이래 바뀌지 않았다. ### 문제 5 **접근.** 네 걸음의 라벨을 여백에 먼저 적어 두고 그 사이를 채운다. 계산의 관절은 두 곳이다 — 유클리드 보조정리를 인용하는 두 줄. 그 두 줄을 먼저 확보하면 나머지는 대입과 정리다. **풀이.** $p$를 소수라 하자. **① 개시.** 결론을 부정하여, $\sqrt p$가 유리수라고 가정하자. 그러면 $\sqrt p = \dfrac ab$인 양의 정수 $a, b$가 존재하고, 기약분수로 잡을 수 있으므로 $\gcd(a, b) = 1$이라 하자. **② 전진.** 양변을 제곱하면 $p = \dfrac{a^2}{b^2}$이고, 양변에 $b^2$을 곱하면 $$ a^2 = p b^2 $$ 이다. 따라서 $p \mid a^2$이다. $p$는 소수이므로 유클리드 보조정리에 의해 $p \mid a$ 이고, $a = pk$인 정수 $k$가 존재한다. 이를 대입하면 $p^2k^2 = pb^2$이고, $p \neq 0$ 이므로 양변을 $p$로 나누어 $b^2 = pk^2$을 얻는다. 따라서 $p \mid b^2$이고, 다시 유클리드 보조정리에 의해 $p \mid b$이다. **③ 모순.** $p \mid a$이고 $p \mid b$이므로 $p$는 $a$와 $b$의 공약수이다. $p$는 소수이므로 $p \ge 2$이고, 따라서 $\gcd(a, b) \ge 2$이다. 이는 개시에서 얹어 둔 $\gcd(a, b) = 1$과 모순이다 [산지 ②]. **④ 결론.** 따라서 $\sqrt p$는 무리수이다. $\blacksquare$ **복기.** 이 증명의 재사용 지점은 "$p$가 소수"라는 가정이 유클리드 보조정리를 인용하는 두 줄에서만 소비된다는 것이다. 그래서 $p$를 $2, 3, 5, 7, \ldots$ 어느 소수로 바꿔도 같은 답안이 그대로 작동하고(문제 7이 $p = 5$), 합성수로 바꾸면 정확히 그 두 줄에서 무너진다. **검산.** $p = 2$에서 $a^2 = 2b^2$은 문제 17의 방정식과 같다 — 같은 사실의 두 표현이다. ### 문제 6 **접근.** 두 경우로 나누는 기준을 먼저 적는다. 기준은 "$\sqrt2^{\sqrt2}$가 유리수인가" 이고, 이 질문의 답을 모른다는 것이 오히려 증명의 재료다. 배중률에 의해 두 경우가 전체를 덮으므로 각 경우에서 증인을 만들면 존재가 확립된다. **풀이.** $\sqrt2^{\sqrt2}$를 생각하자. 이 수는 유리수이거나 무리수이며 두 경우가 전부다. **경우 1: 유리수인 경우.** $a = b = \sqrt2$로 두자. $\sqrt2$는 무리수이므로 자격이 검증되고, $a^b = \sqrt2^{\sqrt2}$는 이 경우의 가정에 의해 유리수이므로 사건도 검증된다. **경우 2: 무리수인 경우.** $a = \sqrt2^{\sqrt2}$, $b = \sqrt2$로 두자. $a$는 이 경우의 가정에 의해 무리수이고 $b$도 무리수이므로 자격이 검증된다. 또한 $$ a^b = \left(\sqrt2^{\sqrt2}\right)^{\sqrt2} = \sqrt2^{\;\sqrt2 \cdot \sqrt2} = \sqrt2^{\,2} = 2 $$ 이고 $2$는 유리수이므로 사건도 검증된다. 두 경우가 전체를 덮고 각 경우에서 그러한 쌍이 존재하므로, 그러한 무리수 $a, b$가 존재한다. $\blacksquare$ **비구성적인 이유(한 문장).** 증명이 끝난 뒤에도 $\sqrt2^{\sqrt2}$의 유무리성을 모르므로 증인이 $(\sqrt2, \sqrt2)$인지 $(\sqrt2^{\sqrt2}, \sqrt2)$인지 특정하지 못한 채 존재만 확립했기 때문이다. **복기.** 경우법이 비구성적 존재 증명의 공급원이 되는 구조가 여기 있다 — 각 경우에서 증인을 만들 수 있으면, 어느 경우가 실제인지 몰라도 존재는 확립된다. 같은 구조가 문제 16(비둘기집)에서 상자를 특정하지 못한 채 존재를 얻는 방식으로 반복된다. ### 문제 7 **접근.** 예제 2.2에 $p = 5$를 대입하면 되지만, 백지에서 쓸 때는 유클리드 보조정리의 가정("$5$는 소수")을 명시하는 줄과 기약 조각을 개시문에 얹는 줄을 빠뜨리기 쉽다. 4단 라벨을 여백에 먼저 적고 채운다. **풀이.** **① 개시.** 결론을 부정하여, $\sqrt5$가 유리수라고 가정하자. 그러면 $\sqrt5 = \dfrac ab$인 양의 정수 $a, b$가 존재하고, 기약분수로 잡아 $\gcd(a, b) = 1$이라 하자. **② 전진.** 제곱하면 $5 = \dfrac{a^2}{b^2}$이고, $b^2$을 곱하면 $$ a^2 = 5b^2 $$ 이다. 따라서 $5 \mid a^2$이다. $5$는 소수이므로 유클리드 보조정리에 의해 $5 \mid a$ 이고, $a = 5k$인 정수 $k$가 존재한다. 대입하면 $25k^2 = 5b^2$이고, 양변을 $5$로 나누면 $b^2 = 5k^2$이다. 따라서 $5 \mid b^2$이고, 다시 유클리드 보조정리에 의해 $5 \mid b$이다. **③ 모순.** $5$가 $a$와 $b$의 공약수이므로 $\gcd(a, b) \ge 5$이고, 이는 개시에서 얹어 둔 $\gcd(a, b) = 1$과 모순이다 [산지 ②]. **④ 결론.** 따라서 $\sqrt5$는 무리수이다. $\blacksquare$ **검산.** $2.2^2 = 4.84$이고 $2.3^2 = 5.29$이므로 $\sqrt5$는 $2$와 $3$ 사이에 있어 정수가 아니다. 정수가 아니라는 사실만으로는 무리성이 나오지 않지만, 결론이 황당하지 않음을 확인하는 안전장치는 된다. ### 문제 8 **접근.** "소수는 무한히 많다"의 부정은 "소수가 유한 개다"이고, 유한 개라는 사실만으로는 다음 줄이 나오지 않는다. 유한 집합이므로 **전체를 목록으로 나열해 이름을 붙일 수 있다**는 것이 걸음 ①의 진짜 성과다. 이름이 붙어야 곱할 수 있다. **풀이.** **① 개시.** 결론을 부정하여, 소수가 유한 개라고 가정하자. 그러면 소수 전체를 $p_1, p_2, \ldots, p_k$로 남김없이 나열할 수 있다. $2$는 소수이므로 이 목록은 비어 있지 않다($k \ge 1$). **② 전진.** $N = p_1 p_2 \cdots p_k + 1$로 두자. $k \ge 1$이고 각 $p_i \ge 2$이므로 $p_1 p_2 \cdots p_k \ge 2$이고, 따라서 $N \ge 2 + 1 = 3 > 1$이다. $1$보다 큰 모든 정수는 소인수를 가지므로(1권 33주차), $N$의 소인수 $q$가 존재한다. $q$는 소수이므로 목록에 있고, 따라서 어떤 $i$에 대해 $q = p_i$이다. 그런데 $p_i$는 곱 $p_1 \cdots p_k$를 나누므로 $$ q \mid N \quad \text{이고} \quad q \mid p_1p_2\cdots p_k $$ 이고, 두 배수의 차도 배수이므로 $q \mid N - p_1\cdots p_k = 1$이다. **③ 모순.** $q \mid 1$이면 $q \le 1$인데, $q$는 소수이므로 $q \ge 2$이다. 두 문장이 충돌한다 [산지 ③ — 유도 결과가 소수의 정의와 부딪혔다]. **④ 결론.** 따라서 소수는 유한 개가 아니다. 곧 소수는 무한히 많고, 가장 큰 소수는 존재하지 않는다. $\blacksquare$ **복기.** 이 답안에서 개시 가정이 실제로 소비되는 곳은 두 군데다 — 목록을 만드는 줄과 "$q$는 목록에 있다"고 말하는 줄. 귀류 답안을 검사할 때는 이렇게 "개시 가정을 쓴 줄"에 표시해 본다. 표시가 하나도 없으면 그 답안은 귀류의 형식만 쓴 직접 증명이다. **검산.** $k = 3$, 목록이 $2, 3, 5$라면 $N = 31$이고 $31$은 소수이며 목록 밖이다. 목록이 $2, 3, 5, 7, 11, 13$이면 $N = 30031 = 59 \cdot 509$로 $N$ 자체는 소수가 아니지만 소인수 $59$가 목록 밖이다 — 증명이 "$N$이 소수"라고 주장하지 않는 이유가 여기 있다. ### 문제 9 **접근.** 결론이 존재 명제이고 방정식이므로 S5주차 공급로 ①(역산)이 그대로 맞는 자리다. 근의 공식으로 후보를 얻은 뒤, 답안에는 후보를 "두자"로 제시하고 대입 검증만 적는다 — 근의 공식을 유도한 과정은 연습장에 남긴다. **풀이.** $x = \dfrac{1 + \sqrt5}{2}$로 두자 [구성]. **자격 검증.** $\sqrt5$는 실수이므로 $x$는 실수이다. **사건 검증.** 먼저 $x^2$을 계산한다. $$ x^2 = \left(\frac{1 + \sqrt5}{2}\right)^2 = \frac{1 + 2\sqrt5 + 5}{4} = \frac{6 + 2\sqrt5}{4} = \frac{3 + \sqrt5}{2} $$ 이어서 $x + 1$을 계산한다. $$ x + 1 = \frac{1 + \sqrt5}{2} + \frac{2}{2} = \frac{3 + \sqrt5}{2} $$ 두 값이 같으므로 $x^2 = x + 1$, 곧 $x^2 - x - 1 = 0$이다. 따라서 $x^2 - x - 1 = 0$인 실수가 존재한다. $\blacksquare$ (구성적 — 증인의 값이 답안에 명시되어 있다.) **복기.** 존재 증명의 답안에서 "왜 이 값인가"는 적지 않아도 된다. 적어야 하는 것은 "이 값이 자격과 사건을 만족한다"뿐이다. 후보를 찾은 과정(근의 공식)은 연습장의 일이고, 답안은 검증의 기록이다 — S5주차 §1.4의 걸음 ①이 제출본에서 지워진다는 규칙이다. **검산.** $\sqrt5 \approx 2.236$이므로 $x \approx 1.618$이고 $x^2 \approx 2.618 \approx x + 1$ ✓. ### 문제 10 **접근.** 결론("$\sqrt2$는 무리수")은 참이다. 증명 평가에서 결론이 참일 때 의심할 곳은 **근거**뿐이다. 이 답안이 주장의 근거로 삼은 것은 "소수점 아래가 순환하지 않는다"는 관찰이므로, 그 관찰을 어떻게 얻었는지를 묻는다. **풀이.** **이 증명은 옳지 않다 — 근거가 확립되지 않았다.** ① 답안이 제시한 것은 유한 개의 소수 자릿수($1.41421356$)이다. 유한 개의 자릿수 관찰로는 순환 여부를 판정할 수 없다 — 순환 주기가 관찰한 자릿수보다 길 수 있고, 순환이 더 뒤에서 시작될 수도 있다. 순환 여부는 유한 관찰로 확정되지 않는다. ② 더 근본적인 문제가 있다. "십진 전개가 순환하지 않는다"와 "무리수이다"는 **동치**이다. 따라서 이 답안은 증명해야 할 것을 근거로 삼은 것이고, 순환하지 않음을 보이는 일은 무리성을 보이는 일과 정확히 같은 난이도다. 근거가 결론을 다시 말하고 있으므로 이 답안은 순환 논증이다. ③ 올바른 증명은 예제 2.2의 $p = 2$ 사례다: $\sqrt2 = a/b$를 기약분수로 가정하면 $a^2 = 2b^2$에서 $2 \mid a$, 이어 $2 \mid b$가 나와 $\gcd(a,b) = 1$과 모순이다 [산지 ②]. **복기.** 증명 평가의 순서를 고정해 둔다 — ① 결론의 진위 ② 각 줄의 근거가 목록 안에 있는가 ③ 근거가 결론을 다시 말하고 있지 않은가 ④ 검증이 빠진 칸은 없는가. 이 문항은 ③에서 걸리고, 문제 18은 ①과 ④에서 걸린다. ### 문제 11 **접근.** "정확히 하나"는 두 책임이므로 답안도 두 문단이다. 존재는 역산으로 증인을 만들고, 유일은 얼굴 1(둘을 잡아 같음을 보인다)이 가장 짧다 — 일차방정식이므로 뺄셈 한 번으로 끝난다. **풀이.** **(존재)** $x = \dfrac73$으로 두자. 자격 검증 — $7$과 $3$이 정수이고 $3 \neq 0$이므로 $\dfrac73$은 유리수이다. 사건 검증 — $3 \cdot \dfrac73 - 7 = 7 - 7 = 0$이다. 따라서 조건을 만족하는 유리수가 존재한다. **(유일 — 얼굴 1)** $x_1$과 $x_2$가 모두 조건을 만족한다고 하자. 곧 $3x_1 - 7 = 0$ 이고 $3x_2 - 7 = 0$이다. 두 식을 빼면 $3(x_1 - x_2) = 0$이고, $3 \neq 0$이므로 $x_1 - x_2 = 0$, 곧 $x_1 = x_2$이다. 서로 다르다고 가정하지 않았음에 주의한다. 두 책임이 모두 확립되었으므로 $3x - 7 = 0$인 유리수가 정확히 하나 존재한다. $\blacksquare$ **복기.** 얼굴 1이 짧게 끝나는 조건은 "두 등식에서 미지수를 소거할 수 있는가"이다. 소거가 되면 얼굴 1, 되지 않으면 얼굴 2(다르다고 가정해 모순)를 검토한다. 판정 기준은 S13주차에 있다. **검산.** $3 \cdot \dfrac73 = 7$ ✓. 또한 $\dfrac73$이 정수가 아니므로, 같은 명제를 "정수가 정확히 하나 존재한다"로 바꾸면 거짓이 된다 — 무대를 바꾸면 존재가 사라질 수 있다는 예다. ### 문제 12 **접근.** 세 문항의 성격이 다르므로 먼저 참$\cdot$거짓을 판정한다. 참이면 증명해야 하고, 거짓이면 두 검증을 갖춘 반례가 필요하다. 판정은 작은 수로 실험해 본 뒤 한다. **풀이.** **(a) 참.** $a \mid b$이므로 $b = ak$인 정수 $k$가 존재한다. 그러면 $bc = (ak)c = a(kc)$이고 $kc$는 정수이므로(닫힘성) $a \mid bc$이다. $\blacksquare$ 사실 가정 "$a \mid c$"는 쓰이지 않는다 — $a \mid b$만으로 결론이 나온다. 남는 가정이 있다는 점도 답안에 적어 두면 좋다. **(b) 거짓.** 반례: $a = 4$, $b = 2$, $c = 2$. 자격 검증 — $bc = 4$이고 $4 = 4 \cdot 1$이므로 $4 \mid bc$이다. 사건 검증 — $4 \nmid 2$이므로 $4 \mid b$도 $4 \mid c$도 성립하지 않는다. 따라서 명제는 거짓이다. 이 명제는 $a$가 소수이면 참이며, 그것이 유클리드 보조정리다. ("소수일 때만"이라고 적지는 않는다 — $\lvert a \rvert \le 1$과 $a = 0$에서도 자명하게 성립하고($a = \pm1$이면 $a \mid b$가 언제나 참이며, $a = 0$이면 $0 \mid bc$에서 $bc = 0$, 곧 $b = 0$ 또는 $c = 0$이 따라 나온다), $a = -p$처럼 부호만 뒤집힌 경우도 성립한다. 자명한 경우를 빼면 $\lvert a \rvert$가 소수인 것이 참$\cdot$거짓의 정확한 경계다.) **(c) 거짓.** 반례: $a = 1$, $b = -1$. 자격 검증 — $a^2 = 1$이고 $b^2 = 1$이므로 $a^2 = b^2$이다. 사건 검증 — $1 \neq -1$이다. 따라서 명제는 거짓이다. 참인 명제는 "$a^2 = b^2$이면 $a = b$ 또는 $a = -b$"이다. **복기.** (b)와 (c)의 반례가 사는 곳이 다르다. (b)는 **가정의 조건이 약해서**(소수가 아니어서) 생긴 반례이고, (c)는 **연산이 정보를 지워서**(제곱이 부호를 지워서) 생긴 반례이다. 반례 수색 목록에 이 두 항목을 나란히 적어 둔다. ### 문제 13 **접근.** 결론이 존재 명제인데 $x^5 + x - 1 = 0$의 해를 닫힌 식으로 적을 방법이 없다. 공급로 ①$\cdot$②가 막혔으므로 ③ — 기성 존재 정리를 인용한다. 정리를 인용할 때는 그 정리의 가정이 충족됨을 먼저 밝힌다. **풀이.** $f(x) = x^5 + x - 1$로 두자. **가정 1 (연속성).** $f$는 다항함수이므로 $[0, 1]$에서 연속이다. **가정 2 (부호 변화).** $f(0) = 0 + 0 - 1 = -1 < 0$이고 $f(1) = 1 + 1 - 1 = 1 > 0$이다. 중간값 정리의 가정이 모두 충족되었으므로, $f(x_0) = 0$인 실수 $x_0$가 $0$과 $1$ 사이에 존재한다. 곧 $x_0^5 + x_0 - 1 = 0$인 실수가 존재한다. $\blacksquare$ **비구성적임의 확인.** 이 답안 어디에도 "$x_0 = \cdots$"라는 식이 없다. 증명이 끝난 뒤에도 $x_0$의 값은 모르며, 아는 것은 $0 < x_0 < 1$이라는 위치뿐이다. **복기.** 공급로 ③의 답안 모양은 언제나 같다 — 정리의 이름을 밝히고, 가정을 하나씩 검증하고, 결론을 그대로 가져온다. 문제 16의 비둘기집도 정확히 같은 세 걸음이다. **검산.** $f(0.7) = 0.16807 + 0.7 - 1 = -0.13193 < 0$이고 $f(0.8) = 0.32768 + 0.8 - 1 = 0.12768 > 0$이므로 해는 $0.7$과 $0.8$ 사이에 있다. 값을 좁힐 수는 있어도 이 방법으로 값을 확정할 수는 없다. ### 문제 14 **접근.** 결론 "$a \le 0$"의 부정은 "$a > 0$"이고, 이것은 **양수 하나**를 손에 쥐여 준다. 가정은 "모든 $\varepsilon > 0$에 대해"이므로 특수화(S7주차)로 그 양수를 $\varepsilon$ 자리에 넣을 수 있다. 무엇을 넣느냐에 따라 모순의 모양이 달라진다. **풀이.** **① 개시.** 결론을 부정하여 $a > 0$이라고 가정하자. **② 전진.** $\varepsilon_0 = \dfrac a2$로 두자. $a > 0$이므로 $\varepsilon_0 > 0$이다. 가정("모든 $\varepsilon > 0$에 대해 $a < \varepsilon$")을 $\varepsilon = \varepsilon_0$ 에 특수화하면 $$ a < \frac a2 $$ 이고, 양변에서 $\dfrac a2$을 빼면 $\dfrac a2 < 0$, 곧 $a < 0$이다. **③ 모순.** 유도 결과 "$a < 0$"이 개시 가정 "$a > 0$"과 충돌한다 [산지 ② — 개시 가정이 스스로를 뒤집었다]. **④ 결론.** 따라서 $a \le 0$이다. $\blacksquare$ **다른 투입.** $\varepsilon_0 = a$로 두어도 된다. 그러면 $a < a$가 나오고, 이는 순서의 비반사성("$x < x$인 실수는 없다")과 충돌하므로 산지 ③이 된다. 같은 명제라도 무엇을 투입하느냐에 따라 충돌 상대가 바뀐다는 점을 답안에 한 줄로 적어 두면 좋다. **복기.** S12주차 문제 16은 같은 명제를 대우로 증명한다 — "$a > 0$이면 $a < \varepsilon$ 을 깨는 $\varepsilon$이 있다". 대우판과 귀류판의 차이는 도착점이 정해져 있는지뿐이고, 계산은 같다. 같은 정리를 두 기법으로 써 보면 두 기법의 관계가 손에 남는다. ### 문제 15 **접근.** 두 경로 모두 "제곱해서 하나의 무리수를 유리식으로 고립시킨다"는 같은 발상이고, 차이는 **어느 무리수를 고립시키는가**이다. (a)는 통째로 제곱해 $\sqrt6$을, (b)는 한 항을 옮긴 뒤 제곱해 $\sqrt2$를 고립시킨다. **풀이 (a) — $\sqrt6$ 경유.** 결론을 부정하여 $s = \sqrt2 + \sqrt3$이 유리수라고 가정하자. 양변을 제곱하면 $$ s^2 = 2 + 2\sqrt2\sqrt3 + 3 = 5 + 2\sqrt6 $$ 이므로 $\sqrt6 = \dfrac{s^2 - 5}{2}$이다. $s$가 유리수이므로 우변은 유리수의 곱$\cdot$차$\cdot$몫 이며 따라서 유리수이다 [닫힘성]. 곧 $\sqrt6$이 유리수이다. 그런데 $\sqrt6$은 무리수이다 (1권 21주차 문제 15). 두 문장이 충돌하므로 모순이다 [산지 ③]. 따라서 $\sqrt2 + \sqrt3$은 무리수이다. $\blacksquare$ **풀이 (b) — $\sqrt2$ 고립.** 결론을 부정하여 $s = \sqrt2 + \sqrt3$이 유리수라고 가정하자. $s - \sqrt2 = \sqrt3$ 이므로 양변을 제곱하면 $$ s^2 - 2\sqrt2\,s + 2 = 3 $$ 이고, 정리하면 $2\sqrt2\,s = s^2 - 1$이다. $\sqrt2 > 0$이고 $\sqrt3 > 0$이므로 $s > 0$이고, 따라서 $s \neq 0$이라 양변을 $2s$로 나눌 수 있다: $$ \sqrt2 = \frac{s^2 - 1}{2s} $$ 우변은 유리수이므로 [닫힘성] $\sqrt2$가 유리수이다. 그런데 $\sqrt2$는 무리수이다 (1권 21주차 예제 2.2). 모순이다 [산지 ③]. 따라서 $\sqrt2 + \sqrt3$은 무리수이다. $\blacksquare$ **두 경로 비교.** (a)는 나눗셈이 상수 $2$로만 이루어져 있어 조건 확인이 필요 없지만, $\sqrt6$의 무리성이라는 **별도의 기성 정리**를 인용해야 한다. (b)는 인용하는 정리가 $\sqrt2$의 무리성뿐이라 더 기본적이지만, $s$로 나누는 줄에서 $s \neq 0$을 확인하는 의무가 생긴다. 인용의 부담과 조건 확인의 부담을 맞바꾼 셈이다. **복기.** 무리수 합의 무리성을 다루는 표준 동작은 "유리수라 가정 $\to$ 제곱 $\to$ 하나의 무리수를 유리식으로 고립 $\to$ 기지의 무리성과 충돌"이다. 훈련 1($\sqrt2 + \sqrt6$)이 같은 동작이었다. 어느 무리수를 고립시킬지만 상황에 맞게 고르면 된다. ### 문제 16 **접근.** 비둘기집을 쓰려면 물건과 상자를 정해야 한다. 물건은 부분집합, 상자는 합의 값이다. 상자의 개수를 세려면 합이 가질 수 있는 값의 범위를 위아래로 막아야 한다. **풀이.** 여기서 두 자리 정수란 $10 \le x \le 99$인 정수를 말한다 — 이 무대 규정이 아래의 상자 개수와 "원소가 모두 양수"라는 사실을 함께 공급한다. 무대를 음수까지 넓히면 합의 범위가 $-945$부터 $945$까지 벌어져 상자가 $1891$개가 되고, $1024$개의 물건으로는 비둘기집이 작동하지 않는다. 서로 다른 두 자리 정수 $10$개로 이루어진 집합을 $S$라 하자. **물건.** $S$의 부분집합은 $2^{10} = 1024$개다. **상자.** 각 부분집합의 원소 합을 생각한다. 공집합의 합은 $0$이므로 합의 최솟값은 $0$이다. 두 자리 정수 중 가장 큰 $10$개는 $90, 91, \ldots, 99$이고 그 합은 $$ 90 + 91 + \cdots + 99 = \frac{(90 + 99) \cdot 10}{2} = 945 $$ 이므로 어떤 부분집합의 합도 $945$를 넘지 않는다. 따라서 합이 가질 수 있는 값은 $0$부터 $945$까지의 정수, 곧 많아야 $946$가지다. **비둘기집.** $1024 > 946$이므로 비둘기집 원리에 의해, 합이 같은 서로 다른 두 부분집합 $A$와 $B$가 존재한다. $\blacksquare$ **서로소로 만들기.** $A \neq B$이고 두 합이 같다고 하자. 공통 부분을 각각에서 제거해 $A' = A \setminus B$, $B' = B \setminus A$로 두면 $A'$과 $B'$은 서로소이고, 같은 값 (공통 부분의 합)을 양쪽에서 뺀 것이므로 두 합은 여전히 같다. 또한 $A' = \varnothing$ 이면 $A \subseteq B$이고 합이 같으므로 $B'$의 합이 $0$인데, 무대 규정에 의해 원소가 $10$ 이상이라 모두 양수이므로 $B' = \varnothing$이 되어 $A = B$가 된다 — 가정에 어긋난다. 따라서 $A'$과 $B'$은 둘 다 공집합이 아니다. **비구성적임의 확인.** 어느 두 부분집합인지는 이 증명이 알려 주지 않는다. 비둘기집 원리는 "둘 이상 든 상자가 있다"만 말하고 "어느 상자인지"는 말하지 않기 때문이다. **검산.** $S = \{10, 11, \ldots, 19\}$로 잡아 보면 실제로 $\{10, 13\}$과 $\{11, 12\}$가 둘 다 합 $23$이다. 특정한 $S$에서는 이렇게 손으로 찾을 수 있지만, 임의의 $S$에 대한 증명은 세는 논증으로만 나온다. ### 문제 17 **접근.** "그런 것이 없다"는 부재 명제이므로 귀류의 개시가 "있다"가 되고, 그 대상에 이름을 붙여 받는다. 그런데 그냥 하나 잡으면 모순이 나오지 않는다 — 최소원리로 **가장 작은 것**을 잡아야, 더 작은 것을 만들어 최소성과 충돌시킬 수 있다. **풀이.** **① 개시.** 결론을 부정하여, $x^2 = 2y^2$인 양의 정수 $x, y$가 존재한다고 가정하자. 그런 해의 $x$값들이 이루는 양의 정수 집합은 공집합이 아니므로, 최소원리에 의해 최소원소가 존재한다. $x$가 최소인 해를 $(x, y)$로 잡자. **② 전진.** $x^2 = 2y^2$이므로 $x^2$은 짝수이고, 따라서 $x$도 짝수이다 (1권 19주차 예제 2.1). $x = 2x'$인 양의 정수 $x'$이 존재한다. 대입하면 $4x'^2 = 2y^2$이고, 양변을 $2$로 나누면 $$ y^2 = 2x'^2 $$ 이다. 따라서 $y^2$도 짝수이고, 같은 이유로 $y$도 짝수이므로 $y = 2y'$인 양의 정수 $y'$이 존재한다. 이를 위 식에 대입하면 $4y'^2 = 2x'^2$이고, 양변을 $2$로 나누면 $$ x'^2 = 2y'^2 $$ 이다. 곧 $(x', y')$도 이 방정식의 양의 정수 해이다. **③ 모순.** $x' = \dfrac x2 < x$이므로 $(x', y')$은 $x$보다 작은 $x$값을 가지는 해이다. 이는 $(x, y)$가 $x$최소인 해라는 것과 모순이다 [산지 ②]. **④ 결론.** 따라서 $x^2 = 2y^2$인 양의 정수 $x, y$는 존재하지 않는다. $\blacksquare$ **복기.** 이 증명이 $\sqrt2$의 무리성과 같은 사실인 이유는 이렇다 — $\sqrt2 = x/y$이면 양변을 제곱해 $x^2 = 2y^2$이 되고, 거꾸로도 같다. 예제 2.2는 "기약"으로 모순을 만들고 이 문항은 "최소"로 모순을 만든다. 기약분수를 잡는 것과 최소 해를 잡는 것은 같은 장치의 두 표현이며, 다음 주 C8주차에서 최소 쪽이 **최소 반례법**이라는 이름을 얻는다. **검산.** $x = 2, y = 1$을 넣으면 $4 = 2$로 거짓, $x = 4, y = 3$이면 $16 = 18$로 거짓 — 작은 값에서 해가 없음이 확인된다. 물론 유한 확인은 증명이 아니고, 증명은 위의 무한강하가 한다. ### 문제 18 **접근.** 증명 평가의 순서대로 간다. 먼저 명제 자체의 진위를 판정하고, 이어 S5주차 예제 2.3의 채점표(자격 칸$\cdot$사건 칸)를 만들어 어느 칸이 비었는지 지목한다. **풀이.** **이 증명은 옳지 않고, 명제 자체도 거짓이다.** **① 채점표.** 증인은 $x = \sqrt2$이다. 사건 "$x^2 = 2$" — 검증됨. $(\sqrt2)^2 = 2$이다. 자격 "$x$는 유리수" — **검증되지 않았고, 검증할 수도 없다.** $\sqrt2$는 무리수이기 때문이다(예제 2.2의 $p = 2$). 답안은 사건만 보고 자격을 보지 않았다. **② 명제의 진위.** 이 명제는 거짓이다. $x^2 = 2$인 유리수 $x$가 있다고 하자. $x^2 = 2 \neq 0$이므로 $x \neq 0$이고, $\lvert x \rvert$도 유리수이며 $\lvert x \rvert^2 = x^2 = 2$이고 $\lvert x \rvert > 0$이므로 $\lvert x \rvert = \sqrt2$ 이다. 곧 $\sqrt2$가 유리수가 되어 예제 2.2($p = 2$)의 결과와 어긋난다. 따라서 그러한 유리수는 존재하지 않는다. 음의 유리수 $x = -\sqrt2$인 경우를 따로 빠뜨리지 않으려면 이렇게 절댓값을 거쳐야 한다. **③ 결론.** 증인이 자격을 만족하지 않으므로 답안은 미완성이고, 게다가 명제가 거짓이라 어떤 답안으로도 고칠 수 없다. 올바른 대응은 명제를 반증하는 것이다 — 위 ②가 그 반증이다. **복기.** 존재 증명의 채점표는 언제나 두 칸이다 — 자격과 사건. "사건만 보고 자격은 보지 않는" 오류가 존재 증명에서 가장 흔하며, S5주차 예제 2.3("$p = n+1$로 두자")이 같은 오류였다. 증인을 제시했다고 증명이 끝난 것이 아니다. ### 문제 19 **접근.** 결론이 존재 명제이고 증인을 식으로 적을 수 있으므로 구성적이다. 채점의 핵심은 합성수의 정의를 정확히 쓰는 것이다 — "$1$보다 큰 두 정수의 곱"이므로 인수 **둘 다** $1$보다 큼을 확인해야 한다. **풀이.** $101! + 2,\ 101! + 3,\ \ldots,\ 101! + 101$의 $100$개 정수를 제시한다 [구성]. 이들은 연속한 $100$개의 정수이다. $2 \le j \le 101$인 각 $j$에 대해, $j$는 $1$부터 $101$까지의 곱인 $101!$의 인수이므로 $101! = j \cdot m$인 정수 $m$이 존재한다. 따라서 $$ 101! + j = j \cdot m + j = j(m + 1) $$ 이다. 두 인수를 각각 확인한다. 첫째 인수는 $j \ge 2 > 1$이다. 둘째 인수는 $m + 1 = \dfrac{101!}{j} + 1$인데 $j \le 101$이므로 $\dfrac{101!}{j} \ge \dfrac{101!}{101} = 100!$ 이고, 따라서 $m + 1 \ge 100! + 1 > 1$이다. 두 인수가 모두 $1$보다 크므로 $101! + j$는 합성수이다. $j = 2, 3, \ldots, 101$의 $100$개 경우 모두에서 합성수이므로, 연속한 $100$개의 합성수가 존재한다. $\blacksquare$ **한 문장.** 이 구간에는 소수가 하나도 없으므로 그 앞뒤의 소수 사이 간격이 $100$보다 크고, 같은 논증을 $k$에 대해 반복하면 소수 사이 간격이 얼마든지 벌어짐이 따라 나온다. **복기.** 이 증인은 구성적이지만 $101!$은 $160$자리 수다. **구성적이라는 것은 값을 적었다는 뜻이지 값이 작다는 뜻이 아니다** — 확인 7의 (다)가 이 점이었다. 같은 문제를 S5주차 문제 15가 일반 $k$에 대해 다룬다. **검산.** 작은 규모로 확인한다. $k = 3$이면 $4! + 2 = 26 = 2 \cdot 13$, $4! + 3 = 27 = 3 \cdot 9$, $4! + 4 = 28 = 4 \cdot 7$ — 연속한 세 합성수다 ✓. ### 문제 20 **접근.** (a)는 예제 2.1을, (b)는 예제 2.3을 근거로 삼으라는 지시가 문제에 있다. 서술 문항의 채점은 "주장이 있는가"가 아니라 "그 주장이 지정된 예제로 뒷받침되는가" 이므로, 예제의 구체적인 줄을 인용하며 쓴다. **풀이 (예시 답안).** **(a)** 예제 2.1에서 $C$가 거짓임을 보인 과정은, 원래 명제의 부정을 S10주차의 N5와 N4로 전개해 얻은 존재 명제 "$a \mid b^2$이고 $a \nmid b$인 정수쌍이 존재한다"를 구성법으로 증명한 것이다 — 증인 $(4, 2)$를 제시하고 검증했으므로, 반증은 독립된 기법이 아니라 부정 전개와 구성법의 합성이다. 조건문 $\forall$ 명제 "$P(x) \Rightarrow Q(x)$"의 부정은 N4에 의해 "$P(x_0)$이고 $\neg Q(x_0)$"이므로, 반례는 가정을 만족하면서(검증 1) 결론을 위반하는(검증 2) 증인이어야 존재 명제의 두 조각이 모두 확립된다. 한쪽만 확인한 대상은 명제를 흔들지 못한다 — 가정을 만족하지 않는 쌍에서는 조건문 자체가 참이기 때문이다. **(b)** 예제 2.3은 $\sqrt2^{\sqrt2}$가 유리수인 경우와 무리수인 경우를 모두 덮어 조건을 만족하는 쌍의 존재를 확립하지만, 실제 증인이 $(\sqrt2, \sqrt2)$인지 $(\sqrt2^{\sqrt2}, \sqrt2)$인지는 특정하지 않는다 — 구성적 증명이 "이것이 증인이다"라고 값을 적어 주는 것과 대조된다. 문제가 말하는 "우아함"은 값을 모른 채 존재를 확립할 수 있다는 성질을 가리킨다 — 평가어가 아니라 이렇게 정의된 용어로 읽는다. 비구성적 증명이 증인의 정체를 몰라도 완결된 증명인 이유는, "적어도 하나는 있다"가 논리적으로 확립되면 존재 명제의 요구가 그것으로 충족되기 때문이다. **복기.** 서술 문항의 답안은 개념 절의 문장을 옮겨 적는 것이 아니라, 지정된 예제의 어느 줄이 그 개념의 근거인지 짚는 글이다. (a)는 "N4를 적용한 줄"과 "두 검증 줄"을, (b)는 "경우를 나눈 줄"과 "증인을 특정하지 못한다는 관찰"을 각각 짚어야 점수가 된다. --- **다음 주 예고 (C8주차):** Chartrand 6장 — 귀납법을 일반 원리와 **최소 반례법**으로 다룬다. 1권 31~33주차와 S14주차를 재조직하며, 약한 귀납$\cdot$강한 귀납에 더해 Chartrand가 강조하는 최소 반례법(smallest counterexample)을 세운다. 이번 주 문제 17에서 최소 해를 잡아 더 작은 해를 만들어 낸 그 동작이 다음 주에 정식 기법의 이름을 얻고, 세 형태가 모두 최소원리의 다른 표현임을 확인한다. 원서 6장을 먼저 통독한 뒤에 온다.