C7주차 · 강의 — 예제 · 연습 · 해설

C7주차 · 강의 — 예제 · 연습 · 해설#

예제 — 세 기술을 함께 만들기#

완성된 답안을 먼저 보이지 않는다. 설계부터 한 줄씩 만든다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다.

예제 2.1 — 반례: 거짓 ∀ 명제 셋을 반증하기#

과제. 다음 세 명제가 거짓임을 반례로 보이라.

  • \(A\): 모든 소수는 홀수이다.

  • \(B\): 모든 실수 \(x\)에 대해 \(x^2 > x\)이다.

  • \(C\): 정수 \(a, b\)에 대해, \(a \mid b^2\)이면 \(a \mid b\)이다.

설계 — 쓰기 전에 정하는 두 가지. 반증도 증명이므로 출발점과 도착점을 먼저 정한다. 반증에서 출발점과 도착점은 원래 명제가 아니라 그 부정에서 나온다.

말

수식 번역

출발점 (가정이 주는 것)

없다 — 반증에는 가정이 없다

무대의 조건만 남는다

도착점 (만들 것)

\(C\)가 거짓이다

\(\underline{\quad(?)\quad}\)

확인 10. 도착점 칸을 채워 보자. “\(C\)가 거짓이다”를 S10주차의 규칙으로 전개하면 무엇을 증명해야 하는가. 규칙 번호까지 적는다.

답

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

확인 11. \(A\)와 \(B\)의 증인도 각각 찾아 보자. \(B\)에서는 어느 구간을 뒤져야 하는가.

답

\(A\): \(x_0 = 2\). 짝수인 소수를 찾으면 되고, 소수를 작은 것부터 훑으면 첫 번째가 곧 답이다.

\(B\): \(x_0 = \tfrac12\). \(x^2 > x\)는 양변을 \(x\)로 비교하는 문제이므로 \(x\)가 \(0\)과 \(1\)

사이일 때 제곱이 작아진다. 경계와 특수 구간(\(0\), \(1\), 음수, \(0\)과 \(1\) 사이)을 먼저

뒤지는 것이 반례 수색의 표준 순서다 — 1권 29주차의 수색 목록과 같다.

확인 12. 증인 \((a, b) = (4, 2)\)의 자격 검증을 계산으로 적어 보자. 무엇을 보여야 하는가.

답

무대 소속과 가정 성립을 나란히 보인다: \(4\)와 \(2\)는 정수이므로 무대 안에 있고,

\(b^2 = 2^2 = 4\)이고 \(4 = 4 \cdot 1\)이므로 \(4 \mid 4\), 곧 \(a \mid b^2\)이다.

나눗셈의 정의를 실제로 적용해 정수 \(k = 1\)을 제시한 것이 검증이다.

“\(4\)는 \(4\)를 나눈다, 당연하다”로 넘어가지 않는다 — 정의 꼴을 적는 것이 채점 대상이다.

확인 13. 이어서 사건 검증을 적어 보자.

답

결론 “\(a \mid b\)”가 위반됨을 보인다: \(4k = 2\)인 정수 \(k\)는 없다(\(k = \tfrac12\)은

정수가 아니다). 따라서 \(4 \nmid 2\)이다.

여기서도 정의로 돌아가 “그런 정수가 없음”을 말한 것이 요점이다.

확인 14. 마지막 문장을 완성해 보자: “따라서 \(\underline{\qquad}\)이므로 명제 \(C\)는 거짓이다.”

답

“따라서 \(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\)는 무리수이다.

이번에는 설계만 함께 하고, 본문은 완성본으로 본다.

확인 15. 번역표를 채워 보자. 가정: \(p\)는 \(\underline{\quad}\)이다. 결론: \(\sqrt p\)는 유리수가 \(\underline{\quad}\). 결론이 부정형이므로 §1.5의 거래를 쓴다 — 개시문은 무엇인가.

답

가정: \(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\)

걸음 ④. 원래 결론의 문장으로 돌아온다.

확인 16. 이 증명에서 “\(p\)는 소수”라는 가정이 실제로 소비되는 줄은 어디인가. 그 줄을 합성수 \(p = 4\)로 바꾸면 무엇이 무너지는가.

답

유클리드 보조정리를 인용하는 두 줄이다. 그 밖의 줄은 \(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\)가 유리수이다.

이번에는 설계부터 스스로 해 보자.

확인 17. 번역표를 채워 보자. 도착점: \(\underline{\qquad}\). 증인을 역산으로 만들 수 있는가 — \(a^b\)가 유리수가 되는 무리수 쌍의 공식이 있는가.

답

도착점: \(\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}\)

경우법 — 두 경우 모두에서 존재 확인

확인 18. 표의 (1)(2)(3)을 채우고, 세 예제가 공통으로 상대하는 것을 한 낱말로 적어 보자.

답

(1) 적지 않았다 — 없음을 주장하는 명제이므로 적을 증인이 아예 없다. 대신 있다고

가정한 뒤 그 가정을 무너뜨렸다.

(2) 적지 않았다 — 두 후보를 제시했으나 어느 쪽이 실제 증인인지는 특정하지 않았다.

(3) 모순 명시와 결론 복귀 (귀류 걸음 ③④).

공통으로 상대하는 것: 존재 명제(\(\exists\)).

방금 확인한 뼈대에 이름을 붙인다.

백지 암기 대상

이번 주의 세 기술

세 기술은 모두 “무엇이 있고 무엇이 없는가”를 상대한다.

① 만들어 내놓는다 — 구성적 존재 증명, 그리고 반례(반례는 부정 전개가 만들어 낸 \(\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\) 그래도 안 되면 풀이를 읽는다.

이번 주의 채점 기준

답이 아니라 근거가 점수다. 세 기술마다 채점 항목이 정해져 있다.

반례: 증인 제시 + 두 검증(자격\(\cdot\)사건). 하나만 있으면 미완성이다.

귀류: 4단 서식의 네 걸음 + 모순의 두 당사자 지목 + 산지 번호.

존재: 구성적이면 증인 제시 + 자격\(\cdot\)사건 검증, 비구성적이면 존재를 보장하는

논증의 근거 명시. 답안 어딘가에 “구성적/비구성적” 중 무엇인지 한 줄로 밝힌다.

난이도와 무관하게, 힌트 상자는 5분 이상 막힌 뒤에만 연다.

기본 ●○○#

1. [백지] 반례 서식, 귀류 4단\(\cdot\)3산지, 존재 증명의 두 스타일(구성적/비구성적), “정확히 하나”의 구조를 쓰시오.

힌트

서식은 걸음의 목록만 외우면 절반이다. 걸음마다 “이것을 빼면 무엇이 무너지는가”를

함께 적어 두면, 일부를 잊었을 때 나머지에서 복구할 수 있다. §1.4와 §1.5의 두

해부 표가 그 복구의 재료다.

2. 다음 거짓 명제를 반례로 반증하시오. (a) 모든 정수 \(n\)에 대해 \(2^n > n^2\). (b) 모든 실수 \(x\)에 대해 \(\sqrt{x^2} = x\). (c) 모든 소수의 합은 소수이다 (두 소수의 합).

힌트

(a) 작은 \(n\)부터 표를 만든다. \(n = 1, 2, 3, 4\)에서 좌변과 우변을 나란히 적으면

부등호가 뒤집히거나 등호가 되는 자리가 보인다.

(b) 양수에서는 성립한다. 무너지는 곳은 부호가 개입하는 자리다.

(c) 소수 중 하나만 성질이 다른 수가 있다 — 그 수를 두 번 쓰면 어떻게 되는가.

3. 예제 2.1의 세 반례를 백지 재현하시오.

힌트

증인만 적으면 절반이다. 세 명제 각각에 대해 자격 검증과 사건 검증을 문장으로

적는다. \(C\)는 조건문이므로 자격 검증이 “가정의 성립”임을 잊지 않는다.

4. 빈칸 훈련(§3의 훈련 1~3)을 백지에서 완성하시오.

힌트

훈련 1과 2는 개시문에서 무엇을 얻는지가 전부다 — “유리수라 가정하면 등식이

생긴다”. 훈련 3은 반례이므로 개시문이 아니라 부정 전개로 시작한다.

5. 예제 2.2(\(\sqrt p\) 무리수)를 백지 재현하시오 (4단 라벨).

힌트

네 걸음의 라벨을 먼저 여백에 적어 두고 그 사이를 채운다. 유클리드 보조정리가

두 번 쓰인다는 것과, 마지막 충돌 상대가 개시문에 얹어 둔 \(\gcd(a,b)=1\)이라는 것을

기억하면 나머지는 계산이다.

6. 예제 2.3(무리수 거듭제곱)을 백지 재현하고, “비구성적”인 이유를 한 문장으로 쓰시오.

힌트

두 경우로 나누는 기준이 무엇이었는지부터 적는다. “비구성적”의 이유는 증명이 끝난

뒤에도 답하지 못하는 질문이 무엇인지 생각하면 나온다.

표준 ●●○#

7. \(\sqrt5\)가 무리수임을 귀류로 증명하시오 (예제 2.2의 \(p=5\) 사례, 4단 서식).

8. “가장 큰 소수는 없다”(= 소수가 무한히 많다)를 귀류로 증명하시오 (S11 문제 15의 재방문 — 전체 목록 + \(N = p_1\cdots p_k + 1\)).

힌트

개시문에서 “소수가 유한 개”라고만 적으면 다음 줄이 나오지 않는다. 유한 개라는

사실에서 전체 목록 \(p_1, \ldots, p_k\)를 꺼내 이름을 붙이는 것이 걸음 ①의 일이다.

목록에 이름이 붙어야 곱할 수 있고, 곱해야 \(N\)을 만들 수 있다.

\(N\)이 소인수를 가진다는 사실도 별도의 근거로 밝힌다.

9. 존재 증명 (구성적): “\(x^2 - x - 1 = 0\)인 실수가 존재한다”를 증명하시오 (근의 공식으로 증인 \(\frac{1 + \sqrt5}2\) 제시\(\cdot\)검증 — 구성적).

10. 다음 제시된 증명을 평가하시오 (C5주차의 증명 평가).

제시된 증명 — 평가 대상

Result. \(\sqrt2\)는 무리수이다.

증명. \(\sqrt2 = 1.41421356\ldots\)는 소수점 아래가 순환하지 않으므로 무리수이다.

힌트

결론은 참이다. 그러니 결론을 의심하지 말고 근거를 의심한다.

“소수점 아래가 순환하지 않는다”를 이 답안은 어떻게 알았는가. 유한 개의 자릿수를

관찰해서 순환하지 않음을 확정할 수 있는가 — 순환 주기가 관찰 범위보다 길다면?

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\) (정수).

힌트

세 문항의 성격이 다르다. 하나는 참이므로 증명해야 하고, 둘은 거짓이므로 두 검증을

갖춘 반례가 필요하다. (b)는 예제 2.1의 \(C\)가 그대로 재료이고, (c)는 제곱이 부호를

지운다는 점을 노린다.

13. 비구성적 존재 (중간값): “\(x^5 + x - 1 = 0\)인 실수가 존재한다”를 중간값 정리로 증명하시오 (구성 없이 — \(f(0) = -1 < 0 < 1 = f(1)\); S5 문제 18). “값을 모르지만 존재”를 확인하시오.

이 문제가 인정하고 쓰는 사실 — 중간값 정리

닫힌 구간 \([c, d]\)에서 연속인 함수 \(f\)가 \(f(c) < 0 < f(d)\)를 만족하면,

\(f(x_0) = 0\)인 \(x_0\)가 \(c\)와 \(d\) 사이에 존재한다. 이 정리는 1권 47주차의 연속 개념

위에 서지만 증명은 이 과정의 범위 밖이므로 끝까지 채택한 채로 쓴다

(S5주차 문제 18과 같은 취급).

이 정리는 해가 있다는 것만 말하고 값은 말하지 않는다 — 그래서 비구성적이다.

힌트

정리를 인용하려면 그 가정이 충족됨을 먼저 밝혀야 한다. 가정은 둘이다: 연속성과

부호 변화. 다항함수의 연속성은 인정하고 쓰되 그 사실을 답안에 적는다.

14. 귀류 in 부등식: “모든 \(\varepsilon > 0\)에 대해 \(a < \varepsilon\)인 실수 \(a\)는 \(a \le 0\)”을 귀류로 증명하시오 (S12 문제 16의 귀류판 — \(a > 0\) 가정 \(\to\) \(\varepsilon = a\) 또는 \(\frac a2\) 투입 \(\to\) 모순).

힌트

가정은 “모든 \(\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\)가 유리수임을 유도. 두 경로를 비교하시오.

힌트

두 경로의 차이는 어느 무리수를 고립시키는가이다. (a)는 통째로 제곱해 \(\sqrt6\)을

고립시키고, (b)는 한 항을 옮긴 뒤 제곱해 \(\sqrt2\)를 고립시킨다. (b)에서 나누기가

필요하므로 \(s \neq 0\)을 밝혀야 한다.

16. (비구성적의 힘) “10개의 서로 다른 두 자리 정수 중에서, 합이 같은 두 부분집합이 존재한다”를 비둘기집으로 증명하시오 (부분집합 개수 \(2^{10} = 1024 >\) 가능한 합의 범위 — 구성 없이 존재만; 1권 26주차 문제 19의 비둘기집). “어느 두 부분집합인지 모르지만 존재”를 확인하시오.

이 문제가 인정하고 쓰는 사실 — 비둘기집 원리

\(n\)개의 물건을 \(m\)개의 상자에 넣을 때 \(n > m\)이면, 물건이 둘 이상 든 상자가

존재한다. 1권 26주차 문제 19가 이 원리를 양말 문제로 다루었다. 지금은 증명 없이

인정하고 쓴다(정식 증명은 귀류다 — 각 상자에 하나 이하라면 전체가 \(m\)개 이하).

이 원리는 “그런 상자가 있다”만 주고 “어느 상자인지”는 주지 않는다.

힌트

물건과 상자를 무엇으로 삼을지 정하는 것이 전부다. 물건 = 부분집합, 상자 = 합의 값.

상자의 개수를 세려면 합이 가질 수 있는 값의 범위를 위아래로 막아야 한다 — 가장 큰

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).

이 문제가 인정하고 쓰는 사실 — 최소원리(정렬성)

공집합이 아닌 양의 정수 집합에는 최소원소가 존재한다 (1권 33주차).

이 사실을 귀류의 개시에 붙이면 “해가 있다면 가장 작은 해를 잡을 수 있다”가 된다.

다음 주 C8주차의 최소 반례법이 이 조합에 정식 이름을 붙인 것이다.

힌트

“\(x^2\)이 짝수이면 \(x\)가 짝수”는 1권 19주차 예제 2.1이다. 이 부품을 \(x\)에 한 번,

\(y\)에 한 번 쓴다. 마지막에 \((x/2, y/2)\)가 다시 해가 됨을 등식으로 확인해야

모순이 완성된다 — 확인하지 않으면 “더 작은 해”라고 부를 근거가 없다.

18. (진단 종합) 다음 제시된 존재 증명을 평가하시오.

제시된 증명 — 평가 대상

Result. \(x^2 = 2\)인 유리수가 존재한다.

증명. \(x = \sqrt2\)로 두면 \(x^2 = 2\)이다. 따라서 존재한다.

힌트

S5주차 예제 2.3의 채점표를 그대로 만든다 — 자격 칸과 사건 칸을 나란히 두고 각각

검증되었는지 적는다. 이 명제에서 자격은 “\(x\)는 유리수”이다. 그리고 이 문항은

채점만으로 끝나지 않는다 — 명제 자체의 진위도 판정해야 한다.

19. (설계) “연속한 100개의 합성수가 존재한다”를 구성적으로 증명하시오 (\(101! + 2, \ldots, 101! + 101\); S5 문제 15의 재방문). 그리고 이것이 “소수 간격이 얼마든지 벌어진다”의 존재 증명임을 한 문장으로 쓰시오. 구성적이지만 증인이 거대한 예이다.

힌트

합성수의 정의를 정확히 쓰는 것이 채점의 핵심이다 — “\(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장을 먼저 통독한 뒤에 온다.