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

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

예제 — 조건문 귀류 증명을 함께 만들기#

예제 2.1 — 조건문 귀류의 기본형#

명제. \(a \ge 2\)인 정수 \(a\)와 임의의 정수 \(b\)에 대해, \(a \nmid b\) 또는 \(a \nmid (b+1)\)이다.

말로 옮기면 “2 이상의 정수는 연속한 두 정수를 동시에 나눌 수 없다”이다. 겉모습은 조건문이 아니지만, “\(a \ge 2\)인 정수 \(a\)에 대해”가 가정이므로 \(P \Rightarrow Q\) 꼴로 읽을 수 있다.

설계 — 쓰기 전에 정하는 두 가지. 가정이 주는 것(출발점)과 도착점을 먼저 정한다. 귀류에서는 도착점이 “아무 모순”이므로, 대신 충돌 후보를 적어 둔다.

말

번역

\(P\) (그대로 유지)

\(a\)는 \(2\) 이상의 정수

\(a \ge 2\)

\(Q\) (부정할 것)

\(a \nmid b\) 또는 \(a \nmid (b+1)\)

—

\(\neg Q\) — 새 출발점

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

\(b = ak\), \(b + 1 = am\)인 정수 \(k, m\)이 존재

충돌 후보

\(P\) 자체

\(\underline{\quad(2)\quad}\)와 부딪히는 문장을 만든다

확인 12. 번역표의 빈칸 (1)(2)를 채워 보자. (1)에서 “또는”의 부정에 적용할 규칙의 이름을 함께 적는다.

답

(1) \(a \mid b\)이고 \(a \mid (b+1)\)이다 — 드모르간 2(11주차 §1.3 둘째 행)로

“또는”이 “그리고”가 되고, \(\nmid\)의 부정은 \(\mid\)다.

(2) \(a \ge 2\). 부정한 결과 손에 들어온 것이 등식 두 개이므로 전개가

시작된다. 직접 증명에서는 “나누지 않는다”를 만들어야 했는데 만들 꼴이

없었다 — 부정이 그 자리를 재료로 바꿨다.

1단계 — 두 가정을 둘 다 선언한다. 서식(§1.4)의 첫 줄이다.

확인 13. 첫 문장을 완성해 보자: “모순을 이끌어내기 위해, \(\underline{\quad}\)인데 \(\underline{\qquad}\)이고 \(\underline{\qquad}\)라고 가정하자.”

답

“모순을 이끌어내기 위해, \(a \ge 2\)인데 \(a \mid b\)이고 \(a \mid (b+1)\)이라고

가정하자.” \(P\)(\(a \ge 2\))를 빠뜨리면 §1.3 삭제 실험의 상황이 되어 충돌할

상대가 사라진다 — 실제로 \(a = 1\)이면 \(1 \mid b\)이고 \(1 \mid (b+1)\)이므로

\(\neg Q\)만으로는 모순이 없다.

2단계 — 두 재료를 결합한다. 손에 \(a \mid b\)와 \(a \mid (b+1)\)이 있다. 둘을 함께 쓰는 부품이 2주차 문제 17이다.

확인 14. 둘째 문장을 완성해 보자: “\(a \mid (b+1)\)이고 \(a \mid b\)이므로 \(a \mid \big(\underline{\qquad}\big) = \underline{\quad}\)이다.” 근거는 무엇인가.

답

“\(a \mid \big((b+1) - b\big) = 1\)이다.” 근거는 2주차 문제 17(\(a \mid (b+c)\)이고

\(a \mid b\)이면 \(a \mid c\))이며, \(c\) 자리에 \(1\)이 들어간 판이다. 두 배수의

차를 잡는 것이 이 유형의 상투 수단이다 — 큰 정보 두 개에서 작은 정보 하나를

짜내면 \(1\)처럼 다루기 쉬운 수가 남는다.

3단계 — \(a \mid 1\)을 \(a\)에 대한 부등식으로 바꾼다. 지금 손에 있는 것은 “\(a\)가 1을 나눈다”이고, 충돌시킬 상대는 부등식 \(a \ge 2\)다. 같은 언어로 맞춰야 부딪힌다.

확인 15. \(a \mid 1\)에서 \(a\)에 대해 무엇을 말할 수 있는가. 근거는 §1.9의 무엇인가.

답

\(a = 1\) 또는 \(a = -1\)이다 — 보조 명제 22.A. 어느 쪽이든 \(a \le 1\)이므로

\(a \ge 2\)일 수 없다. 부등식과 나누어떨어짐은 서로 다른 언어이므로, 충돌을

만들려면 한쪽을 다른 쪽의 언어로 번역해야 한다. 22.A가 그 번역기다.

4단계 — 충돌을 지목하고 원명제를 회수한다.

확인 16. 마지막 문장을 완성해 보자: “이는 \(\underline{\qquad}\)와 모순이다. 따라서 \(\underline{\qquad}\). \(\blacksquare\)”

답

“이는 \(a \ge 2\)라는 가정과 모순이다. 따라서 \(a \nmid b\) 또는 \(a \nmid (b+1)\)이다.

\(\blacksquare\)” 충돌한 두 문장은 “\(a \ge 2\)”와 “\(a \le 1\)”이며, 정수 \(a\)에

대해 이 둘은 동시에 성립할 수 없다. (\(\neg C\)라는 이름을 붙이려면 한 줄이

더 필요하다 — \(\neg(a \ge 2)\)는 11주차 §1.3에 의해 \(a < 2\)이고, \(a\)가

정수이므로 거기서 \(a \le 1\)이 나온다. 모순을 선언하는 데 그 이름이 꼭

필요하지는 않다.) 마지막 줄에서 두 문장을 지목하는 것이 도착점의 확인이다.

완성본. 방금 만든 문장들을 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 “왜?”에 스스로 답해 본다.

증명의 한 줄

왜 이 줄을 쓰는가?

모순을 이끌어내기 위해, \(a \ge 2\)인데 \(a \mid b\)이고 \(a \mid (b+1)\)이라고 가정하자.

서식의 첫 줄. “또는”의 부정은 드모르간 2로 “그리고”가 된다(11주차). 가정 \(P\)를 함께 적어야 충돌 상대가 무대에 남는다.

\(a \mid (b+1)\)이고 \(a \mid b\)이므로 \(a \mid \big((b+1) - b\big) = 1\)이다.

두 재료를 결합하는 부품이 2주차 문제 17(근거 ④). 두 배수의 차에서 \(1\)을 짜냈다.

보조 명제 22.A에 의해 \(a = 1\) 또는 \(a = -1\)이므로 \(a \le 1\)이다.

나누어떨어짐을 부등식의 언어로 번역(근거 ④). 충돌시키려면 두 문장이 같은 언어여야 한다.

이는 \(a \ge 2\)라는 가정과 모순이다. 따라서 \(a \nmid b\) 또는 \(a \nmid (b+1)\)이다. \(\blacksquare\)

충돌한 두 문장(\(a \ge 2\)와 \(a \le 1\))을 지목하고 원명제를 회수한다.

이 네 줄이 “모든” 경우를 처리하는 이유. 완성본의 문자에 구체적인 수를 넣어 읽어 보자.

확인 17. \(a = 6\), \(b = 20\)일 때 둘째 줄과 셋째 줄은 각각 어떤 문장이 되는가. \(a = 2\), \(b = 7\)이면 어떤가.

답

\(a = 6\), \(b = 20\): 가정은 “\(6 \mid 20\)이고 \(6 \mid 21\)”이 된다. 둘째 줄은

“\(6 \mid (21 - 20) = 1\)”, 셋째 줄은 “\(6 \le 1\)”이 되어 \(6 \ge 2\)와 부딪힌다.

\(a = 2\), \(b = 7\): 가정은 “\(2 \mid 7\)이고 \(2 \mid 8\)”, 둘째 줄은 “\(2 \mid 1\)”,

셋째 줄은 “\(2 \le 1\)”이 되어 역시 부딪힌다.

어느 수를 넣어도 네 줄이 그대로 성립한다. 증명의 어느 줄도 \(a\)나 \(b\)가

특정한 수라는 사실을 쓰지 않았기 때문이다.

해석. 이 명제는 “연속한 두 정수는 서로소”라는 이름으로 정수론에서 상시 사용된다. 21주차 예제 2.3(소수 무한)에서 \(p \mid 1\)로 모순을 만들던 것과 같은 부품이다 — 그때도 목록의 소수 \(p\)가 \(2\) 이상이라는 사실이 충돌의 한쪽이었다.

예제 2.2 — “또는” 결론의 귀류#

명제. 실수 \(x, y\)에 대해, \(x + y \ge 2\)이면 \(x \ge 1\) 또는 \(y \ge 1\)이다.

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

확인 18. 번역표를 채워 보자.

\(P\): \(\underline{\qquad}\) / \(Q\): \(\underline{\qquad}\) /

\(\neg Q = \underline{\qquad}\) / 첫 줄에 적을 가정 \(P \land \neg Q = \underline{\qquad}\).

그리고 직접 증명이 막히는 이유를 한 문장으로 적어 보자.

답

\(P\)는 “\(x + y \ge 2\)”, \(Q\)는 “\(x \ge 1\) 또는 \(y \ge 1\)”이다. 드모르간 2와

\(\ge\)의 부정(\(<\))에 의해 \(\neg Q\)는 “\(x < 1\)이고 \(y < 1\)”이다. 첫 줄에 적을

가정은 “\(x + y \ge 2\)인데 \(x < 1\)이고 \(y < 1\)”이다.

직접 증명이 막히는 이유: 결론이 “또는”이므로 어느 쪽이 참인지 지목해야 하는데,

\(x + y \ge 2\)만으로는 지목할 수 없다(\(x = 100\)일 수도 \(y = 100\)일 수도 있다).

부정하면 그 “또는”이 부등식 두 개가 되어 손에 들어온다.

증명. 모순을 이끌어내기 위해, \(x + y \ge 2\)인데 \(x < 1\)이고 \(y < 1\)이라고 가정하자. 두 부등식을 변끼리 더하면(16주차 문제 2(c))

\[ x + y < 1 + 1 = 2 \]

이다. 이는 가정 \(x + y \ge 2\)와 모순이다. 따라서 \(x \ge 1\) 또는 \(y \ge 1\)이다. \(\blacksquare\)

확인 19. 이 증명을 대우로 다시 쓰면 어떤 명제를 증명하게 되는가. 몸통은 얼마나 달라지는가.

답

대우는 “\(x < 1\)이고 \(y < 1\)이면 \(x + y < 2\)이다”이고, 몸통은 “두 부등식을

변끼리 더한다” 한 줄로 위와 완전히 같다. 이 증명에서 \(P\)(\(x + y \ge 2\))는

마지막 충돌 선언에서만 쓰였으므로, §1.6의 관찰대로 **충돌 상대를 \(P\)로 정해

둔 귀류법** — 곧 대우 증명이다. 어느 쪽으로 적어도 정답이며, 서식만 정확하면

된다. 19주차 예제 2.3은 부등호를 \(>\)로 두고 숫자만 다르게 한 같은 유형을

대우로 증명한 자리다. 다만 부등호의 종류가 다르므로 몸통의 마지막 단계도

다르다 — 이번 주는 엄격 부등식 \(x < 1\)과 \(y < 1\)을 변끼리 더하는 16주차

문제 2(c)의 엄격 판본을 쓰고, 19주차는 \(x \le 5\)와 \(y \le 5\)를 (W2) 두 번과

추이성 (W6)으로 잇는 \(\le\) 판본을 쓴다. 두 판본을 나란히 놓고 비교해 둔다

(문제 9 복기의 일반형 \(x + y \ge 2s\)와도 맞물린다).

예제 2.3 — 귀류와 경우 나누기의 조합#

명제. \(x^2 - y^2 = 2\)를 만족하는 정수 \(x, y\)는 존재하지 않는다.

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

확인 20. 첫 줄에 가정할 \(\neg P\)는 무엇이고, 그 가정이 손에 쥐여 주는 것은 무엇인가. 그 등식을 곱의 꼴로 바꾸면 어떻게 되는가.

답

\(\neg P\)는 “\(x^2 - y^2 = 2\)를 만족하는 정수 \(x, y\)가 존재한다”이다(21주차

§1.6 둘째 신호 — 비존재의 부정은 존재이고, 존재하는 대상에는 이름을 붙일 수

있다). 손에 들어오는 것은 그런 정수 \(x, y\)와 등식 \(x^2 - y^2 = 2\)다.

인수분해하면 \((x - y)(x + y) = 2\) — 곱이 2가 되는 정수 두 개를 손에 쥔 셈이다.

증명. 모순을 이끌어내기 위해, \(x^2 - y^2 = 2\)를 만족하는 정수 \(x, y\)가 존재한다고 가정하자. 인수분해하면

\[ (x - y)(x + y) = 2 \]

이다. 여기서 \((x - y) + (x + y) = 2x\)는 짝수이므로, \(x - y\)와 \(x + y\)는 같은 홀짝이다. 만약 홀짝이 다르다면 그 합이 홀수가 되어(1주차 빈칸 사다리 훈련 1: 홀수와 짝수의 합은 홀수) \(2x\)가 짝수라는 것과 어긋나기 때문이다. 정수는 짝수이거나 홀수이므로(17주차 짝/홀 분할) 두 경우만 검사하면 된다.

경우 1: \(x - y\)와 \(x + y\)가 둘 다 짝수. \(x - y = 2s\), \(x + y = 2t\)인 정수 \(s, t\)가 존재하므로 곱은 \((2s)(2t) = 4st\)이고 \(st\)는 정수이므로 \(4 \mid 2\)가 된다. 그러나 \(2 = 4c\)인 정수 \(c\)는 없다(\(c = \frac{1}{2}\)은 정수가 아니다). 모순이다.

경우 2: \(x - y\)와 \(x + y\)가 둘 다 홀수. 홀수와 홀수의 곱은 홀수이므로 (1주차 문제 8) \((x-y)(x+y)\)는 홀수다. 그러나 \(2 = 2 \times 1\)이므로 2는 짝수다. 곧 같은 수가 짝수이면서 홀수가 되어 모순이다(문제 5에서 증명할 사실 — 지금은 인정하고 쓴다).

두 경우가 전체를 빠짐없이 덮고 어느 경우든 모순이므로, 그런 정수 \(x, y\)는 존재하지 않는다. \(\blacksquare\)

확인 21. 이 증명에서 “같은 홀짝이다”를 근거 없이 적으면 무엇이 무너지는가.

답

경우 나누기의 첫째 채점 기준 — 경우들이 전체를 빠짐없이 덮는가 — 가 무너진다

(17주차 §1.3). 근거 없이 두 경우만 검사하면 “하나는 홀수, 하나는 짝수”인

셋째 경우가 검사되지 않은 채 남는다. 합 \(2x\)가 짝수라는 관찰이 그 셋째 경우를

실제로 제거하는 문장이므로, 빠뜨리면 증명이 아니라 두 사례의 확인이 된다.

구조 읽기. 귀류(존재 가정)가 문을 열어 등식을 손에 쥐여 주고, 경우 나누기 (17주차)가 두 갈래를 각각 봉쇄한다. 기법은 서로를 대체하는 것이 아니라 부품처럼 조립된다 — 귀류가 바깥 틀이고 경우 나누기가 안쪽 몸통이다.

관찰 — 세 예제의 같은 뼈대#

세 예제는 소재가 각각 나누어떨어짐\(\cdot\)부등식\(\cdot\)인수분해로 전혀 다르다. 대응표의 빈칸을 채워 뼈대를 비교해 보자.

단계

예제 2.1

예제 2.2

예제 2.3

① \(P\)와 \(\neg Q\)를 둘 다 가정

\(a \ge 2\)인데 \(a \mid b\)이고 \(a \mid (b+1)\)

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

그런 정수 \(x, y\)가 존재한다 (\(P\)가 따로 없는 단일 명제)

② 두 가정을 결합해 모순 후보 제작

\(a \mid 1\)에서 \(a \le 1\)

변끼리 더해 \(x + y < 2\)

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

③ 충돌 지목과 원명제 회수

\(a \le 1\) vs \(a \ge 2\)

\(x + y < 2\) vs \(x + y \ge 2\)

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

확인 22. 표의 빈칸 (1)(2)(3)을 채워 보자. 그리고 ③의 충돌 상대가 세 예제에서 각각 무엇이었는지 비교해 보자.

답

(1) \(x + y \ge 2\)인데 \(x < 1\)이고 \(y < 1\)

(2) 인수분해 후 두 인수가 같은 홀짝임을 보이고, 경우마다 곱의 홀짝(또는 4의

배수 여부)을 판정한다

(3) 경우 1에서 \(4 \mid 2\) vs \(4 \nmid 2\), 경우 2에서 곱이 홀수 vs \(2\)는 짝수

충돌 상대 비교: 예제 2.1과 2.2는 둘 다 가정 \(P\)와 충돌했고 **몸통의 어느

줄도 \(P\)를 쓰지 않았으므로**, §1.6의 뜻에서 대우 증명으로 다시 쓸 수 있다.

예제 2.3은 \(P\)가 따로 없고 이미 아는 사실(4의 배수 판정, 짝/홀 배타성)과

충돌했으므로 대우로 바꿀 수 없다 — 귀류법이 대우보다 넓은 이유가 이 한 칸에

들어 있다.

조건 “몸통이 \(P\)를 쓰지 않았다”를 빠뜨리면 안 된다. 충돌 상대가 \(P\)인데도

옮겨 적을 수 없는 사례가 이번 주에 있다 — 문제 8이다(§1.6). 그 증명은 마지막에

가정의 조각 “\(p\)가 소수”와 충돌하지만 몸통이 다른 조각 “\(p > 2\)”를 이미

소비하고, 대우의 결론이 “또는”이 되어 §1.1 시도 3과 같은 자리에서 막힌다.

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

백지 암기 대상

조건문 귀류의 3단계 틀

① \(P\)와 \(\neg Q\)를 둘 다 가정하고, 각각을 정의로 풀어 재료로 만든다 \(\to\) ② 두 재료를 결합해 모순 후보를 제작한다 \(\to\) ③ 충돌한 두 문장을 지목하고 원명제를 회수한다

21주차의 3단계 틀과 다른 것은 ①뿐이다 — 가정이 하나에서 둘로 늘었다. 23주차에서는 같은 명제를 세 기법으로 각각 써 보며 ①의 선택 자체를 훈련한다.

빈칸 사다리 — 지지대를 하나씩 빼며#

필사에서 자립으로 넘어가는 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 해설(§6)에 있다 — 다 채운 뒤에 대조한다.

훈련 1 ●○○ — 수식 빈칸#

명제. 정수 \(n\)에 대해, \(n^2\)이 홀수이면 \(n\)은 홀수이다.

증명. 모순을 이끌어내기 위해, \(n^2\)이 홀수인데 \(n\)이 \(\underline{\quad(1)\quad}\)라고 가정하자. 그러면 정의 1.1에 의해 \(n = 2k\)인 정수 \(k\)가 존재하고,

\[ n^2 = (2k)^2 = \underline{\quad(2)\quad} \]

이므로 \(n^2\)은 짝수이다. 이는 \(n^2\)이 \(\underline{\quad(3)\quad}\)라는 가정과 모순이다(문제 5에서 증명할 사실 — 지금은 인정하고 쓴다). 따라서 \(n^2\)이 홀수이면 \(n\)은 홀수이다. \(\blacksquare\)

훈련 2 ●●○ — 수식과 근거를 함께#

이번에는 구조 낱말과 근거 문장도 빈칸이다.

명제. 정수 \(a, b\)에 대해, \(ab\)가 홀수이면 \(a\)와 \(b\)는 모두 홀수이다.

증명. 모순을 이끌어내기 위해, \(ab\)가 홀수인데 \(\underline{\quad(1)\quad}\)라고 가정하자. 결론의 부정은 \(\underline{\quad(2)\quad}\)에 의해 “\(a\)가 짝수이거나 \(b\)가 짝수”이므로, 두 경우로 나눈다.

경우 1: \(a\)가 짝수. \(a = 2s\)인 정수 \(s\)가 존재하므로 \(ab = \underline{\quad(3)\quad}\)이고, \(\underline{\quad(4)\quad}\)이므로 \(ab\)는 짝수이다.

경우 2: \(b\)가 짝수. 이번에는 \(b = 2t\)인 정수 \(t\)가 존재하므로 \(ab = 2(at)\)이고 \(at\)는 정수이므로 \(ab\)는 짝수이다.

어느 경우든 \(ab\)는 짝수인데 가정에서 \(ab\)는 홀수이므로, 문제 5에서 증명할 사실(지금은 인정하고 쓴다)에 의해 이는 \(\underline{\quad(5)\quad}\)이다. 따라서 \(ab\)가 홀수이면 \(a\)와 \(b\)는 모두 홀수이다. \(\blacksquare\)

훈련 3 ●●● — 뼈대만 남기고#

이번에는 3단계 틀(§2 관찰)의 각 칸을 통째로 채운다.

명제. \(x^2 - y^2 = 10\)을 만족하는 정수 \(x, y\)는 존재하지 않는다.

증명의 뼈대.

  • ① 부정 가정과 재료 확보: \(\underline{\quad(1)\quad}\)

  • ② 재료 결합과 모순 후보 제작: \(\underline{\quad(2)\quad}\)

  • ③ 충돌 지목과 원명제 회수: \(\underline{\quad(3)\quad}\)

(예제 2.3과 같은 설계다. 두 인수의 홀짝을 먼저 묶은 뒤 경우마다 판정한다. 이 훈련이 문제 14의 예행연습이다.)

연습문제 (20문항)#

해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 ‘접근’까지만 읽고 다시 시도한다 \(\to\) 그래도 안 되면 풀이를 읽는다.

이번 주의 채점 기준

답이 아니라 근거가 점수다. 이번 주 답안에서 가장 자주 비는 칸은 세

군데다 — 첫 줄에 가정 \(P\)를 함께 적었는가, \(\neg Q\)를 11주차 규칙으로

정확히 만들었는가, 마지막 줄에 충돌한 두 문장을 지목했는가. 셋 중 하나라도

비면 몸통의 계산이 전부 옳아도 증명이 닫히지 않는다.

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

기본 ●○○#

1. 다음 조건문을 귀류로 증명할 때 가정할 내용(\(P \land \neg Q\))을 정확히 쓰시오 (증명 불필요). (a) \(x\)가 무리수이면 \(x + 3\)은 무리수이다. (b) \(a \mid b\)이고 \(a \nmid c\)이면 \(a \nmid (b + c)\)이다. (c) \(x + y > 10\)이면 \(x > 5\) 또는 \(y > 5\)이다.

힌트

세 항목 모두 §1.4 서식의 첫 문장을 채우는 일이다. \(P\)는 손대지 않고 그대로

옮겨 적고, \(Q\)만 11주차 총목록으로 부정한다. (a)는 “무리수가 아니다”를

정의 15.1로 한 번 더 풀고, (c)는 “또는”이므로 드모르간 2가 들어간다.

2. [백지] 조건문 귀류 증명의 서식과, 직접\(\cdot\)대우\(\cdot\)귀류의 “가정/도착지” 비교표를 쓰시오.

힌트

서식은 §1.4의 네 줄, 비교표는 §1.5의 세 행이다. 표를 쓸 때 각 행의

“손에 쥐는 가정” 칸이 몇 개인지부터 채우면 나머지가 따라온다.

3. 빈칸 훈련(\(n^2\) 홀수 \(\Rightarrow\) \(n\) 홀수)을 백지에서 완성하고, 같은 명제의 19주차 대우 증명과 몸통이 어떻게 겹치는지 한 문장으로 쓰시오.

힌트

귀류 증명에서 첫 줄과 마지막 줄을 지운 뒤 남는 문장들을 소리 내어 읽어

본다. 그것이 어떤 조건문의 직접 증명인지 물으면 답이 나온다.

4. 예제 2.1(\(a \ge 2\)이면 연속 두 정수를 동시에 못 나눔)을 백지에 재현하시오.

힌트

네 줄이다. 두 배수의 차를 잡아 \(1\)을 만들고, 보조 명제 22.A로 부등식의

언어로 옮긴 뒤, \(a \ge 2\)와 부딪힌다.

5. 어떤 정수도 짝수이면서 동시에 홀수일 수 없음을 귀류법으로 증명하시오. (힌트: \(2a = 2b + 1\)이 되면 \(2 \mid 1\) — 17주차부터 “당연히” 써 온 사실의 빚 청산이다)

힌트

짝수와 홀수의 정의를 같은 수 \(n\)에 대해 동시에 적으면 등식 두 개가 생긴다.

두 등식의 우변을 같다고 놓고 정리하면 좌변에서 2를 묶어 낼 수 있고,

그 결과가 보조 명제 22.A와 부딪힌다.

6. \(x\)가 유리수이고 \(xy\)가 무리수이면 \(y\)는 무리수임을 귀류법으로 증명하시오.

힌트

가정이 둘(\(x\) 유리, \(xy\) 무리)이고 부정이 하나(\(y\) 유리) 얹힌다. 유리수

두 개로 만들 수 있는 것을 15주차 닫힘성 목록에서 찾으면 \(xy\)가 나온다.

표준 ●●○#

7. \(a \mid b\)이고 \(a \nmid c\)이면 \(a \nmid (b+c)\)임을 귀류법으로 증명하시오. (부품: 2주차 문제 17)

힌트

§1.1에서 막힌 그 명제다. 손에 쥔 세 문장 가운데 \(a \mid (b+c)\)와 \(a \mid b\)

둘을 결합하면 부품이 발동한다. 남은 하나가 충돌 상대다.

8. \(p\)가 소수이고 \(p > 2\)이면 \(p\)는 홀수임을 귀류법으로 증명하시오. (힌트: \(p\)가 짝수라면 2가 \(p\)의 약수 — 소수의 정의와 충돌시켜라)

힌트

정의 15.2는 “양의 약수가 1과 \(p\)뿐”이다. \(p\)가 짝수라면 2가 약수인데,

\(p > 2\)라는 가정이 2를 1도 \(p\)도 아닌 자리에 놓는다. 가정 \(P\)의 두 조각이

각각 어디서 소비되는지 확인한다.

9. 실수 \(x, y\)에 대해, \(x + y \ge 100\)이면 \(x \ge 50\) 또는 \(y \ge 50\)임을 귀류법으로 증명하시오.

10. 열린구간 \((0, 1)\)에는 최솟값이 존재하지 않음을 증명하시오. (힌트: 최솟값 \(m\)이 있다면 \(\frac{m}{2}\)는 어디에 있는가?)

힌트

최솟값 \(m\)이 만족하는 조건을 두 줄로 나눠 적는다 — ① \(m \in (0,1)\)

② 모든 \(z \in (0,1)\)에 대해 \(m \le z\). 반례가 될 \(z\)를 만들려면 ①과 ②를

동시에 어기는 수 하나면 되고, \(\frac{m}{2}\)가 구간 안에 있는지 확인하는

것이 증명의 절반이다.

11. 모든 정수 \(n\)에 대해 \(n\)과 \(n+1\)의 공통 약수는 \(\pm 1\)뿐임을 증명하시오. (힌트: 공통 약수 \(d\)에 대해 \(d \mid \big((n+1) - n\big)\))

12. \(r\)이 유리수이면 \(r + \sqrt{2}\)는 무리수임을 귀류법으로 증명하시오.

힌트

목표는 \(\sqrt{2}\)를 유리수들만으로 표현하는 등식 한 줄을 만드는 것이다.

\(\sqrt{2} = (r + \sqrt{2}) - r\)로 쓰면 우변이 무엇의 차인지 보인다

(21주차 빈칸 사다리 훈련 1과 같은 설계다).

13. 실수 \(x_1, x_2, \dots, x_n\)의 평균이 \(\mu\)이면, 적어도 하나의 \(x_i\)는 \(\mu\) 이상임을 귀류법으로 증명하시오. (힌트: 전부 \(\mu\) 미만이면 총합은?)

힌트

“적어도 하나가 ~이다”의 부정은 “전부 ~가 아니다”이다(11주차 총목록 다섯째

행). 부정하면 부등식이 \(n\)개 생기고, 그것을 전부 변끼리 더하면 평균의

정의에서 나온 등식과 부딪힌다.

14. 예제 2.3(\(x^2 - y^2 = 2\) 불가능)을 백지에 재현하시오.

힌트

세 관문이다 — 인수분해, “같은 홀짝”의 근거(합이 \(2x\)), 두 경우 각각의 충돌.

빈칸 사다리 훈련 3에서 숫자만 바꾼 판을 이미 한 번 썼다.

도전 ●●●#

이번 주에 처음 쓰는 기술 — 기약분수를 귀류의 재료로

문제 15는 21주차 예제 2.2(\(\sqrt{2}\))와 같은 설계를 쓴다. 유리수 해가

있다고 가정할 때 그 해를 기약분수로 잡아 두면(정의 21.2), 분자와 분모가

둘 다 짝수인 상황이 곧바로 모순이 된다. 곧 기약성은 나중에 충돌시킬 상대를

미리 설치해 두는 장치다. 설치해 두지 않으면 전개가 끝까지 가도 부딪힐 곳이

없다(21주차 확인 3).

15. \(a, b, c\)가 모두 홀수이면 방정식 \(ax^2 + bx + c = 0\)은 유리수 해를 갖지 않음을 증명하시오. (안내: 유리수 해 \(\frac{p}{q}\)(기약)가 있다고 가정 \(\to\) \(ap^2 + bpq + cq^2 = 0\) \(\to\) \(p, q\)의 홀짝은 (홀,홀), (홀,짝), (짝,홀)의 세 경우뿐(기약이므로 둘 다 짝수는 불가) \(\to\) 각 경우 좌변의 홀짝을 추적해 “홀수 = 0(짝수)” 충돌)

힌트

각 경우에서 세 항 \(ap^2\), \(bpq\), \(cq^2\)의 홀짝을 하나씩 판정한다.

\(a, b, c\)가 전부 홀수이므로 각 항의 홀짝은 \(p\)와 \(q\)의 홀짝만으로 결정된다

(홀수를 곱해도 홀짝이 바뀌지 않는다 — 1주차 문제 8). 세 항의 홀짝이

정해지면 합의 홀짝도 정해지고, 그것을 \(0\)(짝수)과 비교한다.

16. 정수 계수 방정식 \(x^3 + x + 1 = 0\)은 정수 해를 갖지 않음을 증명하시오. (힌트: \(x^3 + x = x(x^2+1)\)의 홀짝 — 케이스 또는 1주차식 부품)

힌트

등식을 \(x^3 + x = -1\)로 옮겨 두면 좌변과 우변의 홀짝을 각각 판정하는 문제가

된다. 좌변을 인수분해한 뒤 \(x\)가 짝수인 경우와 홀수인 경우를 나눠 보면,

두 경우 모두 같은 판정이 나온다.

17. (무리수 상등 — “계수 비교”의 정당화) \(a, b, c, d\)가 유리수이고 \(a + b\sqrt{2} = c + d\sqrt{2}\)이면 \(a = c\)이고 \(b = d\)임을 증명하시오. (힌트: \(b \neq d\)라고 가정하면 \(\sqrt2\)를 유리수들로 풀어낼 수 있다)

힌트

결론이 “그리고”이므로 두 주장을 각각 확보해야 한다. 먼저 \(b = d\)를 귀류로

얻은 뒤, 그것을 원래 등식에 대입하면 \(a = c\)가 따라온다. 귀류 부분에서

\(b - d \neq 0\)이라는 조건이 양변을 \(b - d\)로 나누는 줄에서 소비된다.

18. (귀류 남용 진단) 다음 답안을 읽고, 논리적으로 틀린 곳은 없지만 왜 “나쁜 증명”인지 지적하고 더 좋은 형태로 고치시오.

“명제: \(n\)이 짝수이면 \(n^2\)은 짝수이다. 증명: 모순을 위해 \(n\)이 짝수인데 \(n^2\)이 홀수라고 가정하자. \(n = 2k\)이므로 \(n^2 = 4k^2 = 2(2k^2)\)은 짝수이다. 이는 \(n^2\)이 홀수라는 가정과 모순. 따라서 명제가 성립한다. \(\blacksquare\)”

힌트

§1.8의 자기 점검 질문 하나면 된다 — 가정 “\(n^2\)이 홀수”가 모순 선언

이전의 어느 줄에서 쓰였는지 손가락으로 짚어 본다. 짚을 곳이 없다면 그

가정은 아무 일도 하지 않은 것이다.

19. (서술) 귀류법을 시도했는데 모순이 나오지 않는다. 가능한 원인 두 가지를 쓰고(21주차 문제 18 참고), 각각의 경우 다음 행동을 제안하시오.

힌트

갈림길은 “명제가 참인가 거짓인가”다. 참인데 못 찾은 경우와 애초에 거짓인

경우로 나누고, 각각에서 손이 할 일을 적는다. 21주차 문제 18의 \(\sqrt{4}\)가

둘째 경우의 실물이었다.

20. (서술) 기법 선택 가이드 ①~④를 자기 언어로 재구성하고, “귀류 껍데기 안의 직접 증명”(문제 18)을 판별하는 자기 점검 질문 하나를 만드시오.

백지 재현 — 복습 프로토콜#

권장 일정 — 1~3일차: §0~§4 학습과 연습문제 / 4일차: 1차 재현 / 5일차: 완전 백지 재현. 재현은 두 번으로 나눈다. 한 번에 완전 백지로 가지 않는다.

1차 시도 (4일차) — 틀 카드 허용. 조건문 귀류의 3단계 틀(§2 관찰)\(\cdot\)서식(§1.4)\(\cdot\) 근거 목록(§1.10)만 펴 놓고, 예제 2.1을 처음부터 끝까지 적는다. 본문과 2주차 부품 문장은 보지 않는다.

2차 시도 (5일차) — 완전 백지. 아무것도 보지 않고 수행한다.

  • \(\neg(P \Rightarrow Q) \equiv P \land \neg Q\)를 쓰고, 왜 조건문이 아니라 “그리고”가 되는지 8주차 정의 8.1로 설명했다.

  • 조건문 귀류 증명의 서식(§1.4) 네 줄을 조각 그대로 썼다 — 특히 첫 줄에 \(P\)를 함께 적었다.

  • 직접\(\cdot\)대우\(\cdot\)귀류의 “가정 개수 / 도착지 / 적용 대상” 비교표를 재현했다.

  • “대우는 충돌 상대를 \(P\)로 정해 둔 귀류법”을 예제 2.2로 설명했다.

  • 예제 2.1을 백지에 재현했다 — 두 배수의 차로 \(1\)을 짜내는 지점과 보조 명제 22.A가 소비되는 지점을 짚으면서.

  • 예제 2.3(귀류와 경우 나누기)을 재현했다 — “같은 홀짝”의 근거를 빠뜨리지 않고.

  • 기법 선택 가이드 네 조를 썼다 (특히 ④ 남용 점검).

  • 이번 주에 회수한 두 빚(“짝수이면서 홀수일 수 없다”, “1의 약수는 \(\pm 1\)뿐”)이 어디서 쓰이던 사실이었는지 말할 수 있다.

  • 모순이 끝까지 나오지 않을 때 무엇을 읽어야 하는지 말할 수 있다(문제 19).

막힌 지점별 처방. 막힌 지점이 무엇을 다시 볼지 알려 준다.

막힌 지점

처방

첫 줄에 무엇을 가정할지 모르겠다

§1.2의 표 — \(P\)는 그대로 옮기고 \(Q\)만 11주차 총목록으로 부정한다

\(\neg Q\)는 썼는데 \(P\)를 빠뜨린다

§1.3 조각 삭제 실험 — \(P\)가 없으면 충돌 상대가 무대에 없다

“또는” 결론의 부정에서 막힌다

예제 2.2 확인 18 — 드모르간 2로 부등식 두 개를 만든다

재료 두 개를 어떻게 결합할지 모르겠다

예제 2.1의 2단계 — 두 배수의 차를 잡아 작은 수를 짜낸다

전개는 되는데 모순이 안 보인다

§1.9 — 서로 다른 언어(나누어떨어짐 vs 부등식)를 한쪽으로 번역했는지 확인한다

경우가 전체를 덮는지 자신이 없다

예제 2.3 확인 21 — 분할의 근거를 문장으로 적었는지 본다

귀류로 썼는데 군더더기 같다

§1.8 자기 점검 질문 — \(\neg Q\)가 쓰인 줄을 짚어 본다

모순이 끝까지 나오지 않는다

문제 19 — 전개가 부족한 것인지 명제가 거짓인 것인지 갈림길을 확인한다

하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다.

해설#

각 해설은 접근(문제 앞에서 무엇을 생각하는가)과 풀이로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다.

빈칸 사다리 — 훈련 1#

(1) 짝수 (2) \(4k^2 = 2(2k^2)\) (3) 홀수

※ (2)에서 \(4k^2\)을 그대로 두지 않고 \(2(2k^2)\)으로 다시 묶는 것이 핵심이다. 짝수의 정의가 요구하는 꼴은 \(2 \times (\text{정수})\)이므로, 괄호 안이 \(2k^2\)이고 그것이 정수임(근거 ②)을 확인해야 “짝수이다”라고 선언할 수 있다. (3)에서 충돌 상대가 가정 \(P\)(\(n^2\)이 홀수)라는 점에 주목한다 — §1.6의 뜻에서 이 증명은 대우 증명으로 다시 쓸 수 있고, 문제 3이 그 겹침을 묻는다.

빈칸 사다리 — 훈련 2#

(1) \(a\)와 \(b\)가 모두 홀수는 아니다 (2) 드모르간 1 (11주차 §1.3 첫째 행) (3) \((2s)b = 2(sb)\) (4) \(sb\)는 정수 (근거 ②) (5) 모순

※ 결론이 “그리고”이므로 부정하면 “또는”이 되고, “또는”인 가정은 경우 나누기로 처리한다(17주차). 이 흐름이 19주차 §1.5의 셋째 신호와 같은 내용임을 확인한다 — 그쪽은 대우로, 이쪽은 귀류로 처리했을 뿐이다. 두 경우가 겹칠 수 있다는 점도 문제가 되지 않는다. 분할의 채점 기준은 “빠짐없이 덮는가”이지 “겹치지 않는가”가 아니다.

빈칸 사다리 — 훈련 3#

(1) 모순을 이끌어내기 위해, \(x^2 - y^2 = 10\)을 만족하는 정수 \(x, y\)가 존재한다고 가정하자. 인수분해하면 \((x - y)(x + y) = 10\)이다. (2) \((x-y) + (x+y) = 2x\)는 짝수이므로 \(x - y\)와 \(x + y\)는 같은 홀짝이다(홀짝이 다르면 합이 홀수가 되어 어긋난다 — 1주차 빈칸 사다리 훈련 1). 경우 1(둘 다 짝수): \(x - y = 2s\), \(x + y = 2t\)인 정수 \(s, t\)가 존재하므로 곱은 \(4st\)이고 \(st\)는 정수이므로 \(4 \mid 10\)이 된다. 경우 2(둘 다 홀수): 홀수와 홀수의 곱은 홀수이므로 (1주차 문제 8) 곱은 홀수인데 \(10 = 2 \times 5\)는 짝수다. (3) 경우 1에서는 \(10 = 4c\)인 정수 \(c\)가 없으므로(\(c = \frac{5}{2}\)) 모순이고, 경우 2에서는 같은 수가 짝수이면서 홀수가 되어 모순이다(문제 5). 두 경우가 전체를 덮으므로 그런 정수 \(x, y\)는 존재하지 않는다. \(\blacksquare\)

※ 예제 2.3과 숫자만 다르다. 이 설계가 통하는 조건은 “우변이 짝수이면서 4의 배수가 아닌 것”이다 — \(2, 6, 10, 14, \dots\)가 전부 같은 논증으로 처리된다. 반대로 \(x^2 - y^2 = 8\)은 \(x = 3, y = 1\)에서 실제로 성립하므로 같은 논증이 통하지 않는다. 어느 숫자에서 논증이 멈추는지 확인하는 것이 설계를 이해했다는 증거다.

문제 1#

접근. 세 항목 모두 §1.4 서식의 첫 문장을 채우는 일이다. 규칙은 둘 — \(P\)는 손대지 않고 그대로 옮겨 적고, \(Q\)만 11주차 총목록으로 부정한다. (a)는 “무리수가 아니다”를 정의 15.1로 “유리수이다”까지 풀어야 전개 가능한 문장이 되고, (b)는 \(\nmid\)의 부정이 \(\mid\)이며, (c)는 “또는”이므로 드모르간 2가 들어가고 \(>\)의 부정이 \(\le\)가 된다.

풀이. (a) “모순을 이끌어내기 위해, \(x\)가 무리수인데 \(x + 3\)이 유리수라고 가정하자.” (b) “모순을 이끌어내기 위해, \(a \mid b\)이고 \(a \nmid c\)인데 \(a \mid (b + c)\)라고 가정하자.” (c) “모순을 이끌어내기 위해, \(x + y > 10\)인데 \(x \le 5\)이고 \(y \le 5\)라고 가정하자.”

복기. 세 답안 모두 “\(P\)인데 \(\neg Q\)”의 한 문장이고, \(P\) 부분에는 손을 대지 않았다. (b)에서 \(P\)가 두 조각(\(a \mid b\)와 \(a \nmid c\))인데 둘 다 그대로 남았다는 점을 확인한다 — 부정은 결론에만 걸린다. 첫 줄을 정확히 쓰는 것만으로 증명의 절반이 끝난다는 것이 이번 주의 채점 기준이다.

문제 2#

접근. §1.4와 §1.5의 재현이다. 서식은 네 줄, 표는 세 행이며 각 행에 “손에 쥐는 가정 / 도착지 / 적용 대상” 세 칸이 있다. 외운 것을 적은 뒤 본문과 한 칸씩 대조한다.

풀이. 서식은 다음과 같다.

명제. \(P\)이면 \(Q\)이다.

증명. 모순을 이끌어내기 위해, \(P\)인데 \(Q\)가 아니라고 가정하자.

\(\quad\vdots\)

이는 ~와 모순이다. 따라서 \(P\)이면 \(Q\)이다. \(\blacksquare\)

비교표는 다음과 같다.

기법

손에 쥐는 가정

도착지

적용 대상

직접

\(P\) — 한 개

\(Q\) 하나로 고정

조건문 (존재 명제는 15주차 §1.7의 증인 제작 서식)

대우

\(\neg Q\) — 한 개

\(\neg P\) 하나로 고정

조건문

귀류

\(P\) 그리고 \(\neg Q\) — 두 개

아무 모순 (고정되지 않음)

아무 명제

복기. 표의 마지막 열이 세 기법의 위계를 정한다. 직접과 대우는 조건문에 걸리는 기법이다 — 조건문이 아닌 명제 가운데 존재 명제는 15주차 §1.7의 증인 제작 서식으로 귀류 없이 직접 증명한다(15주차 문제 19가 그 실물이다). 부정형\(\cdot\)비존재 결론처럼 만들 목표 꼴이 아예 없는 명제에는 귀류만 걸린다 — 21주차 예제 2.1~2.3이 조건문이 아닌데도 귀류로 처리된 이유가 이 칸이다.

문제 3#

접근. 겹침을 보려면 귀류 증명에서 첫 줄과 마지막 줄을 지우고 남는 문장들을 읽어 본다. 남는 것이 어떤 조건문의 직접 증명인지 물으면 답이 나온다.

풀이. 완성된 귀류 증명은 다음과 같다.

모순을 이끌어내기 위해, \(n^2\)이 홀수인데 \(n\)이 짝수라고 가정하자. 정의 1.1에 의해 \(n = 2k\)인 정수 \(k\)가 존재하고,

\[ n^2 = (2k)^2 = 4k^2 = 2(2k^2) \]

이며 \(2k^2\)은 정수이므로(근거 ②) \(n^2\)은 짝수이다. 이는 \(n^2\)이 홀수라는 가정과 모순이다(문제 5). 따라서 \(n^2\)이 홀수이면 \(n\)은 홀수이다. \(\blacksquare\)

겹침에 대한 한 문장: 이 귀류 증명에서 첫 줄과 마지막 줄을 지우면 “\(n\)이 짝수이면 \(n^2\)은 짝수이다”의 직접 증명이 그대로 남는데, 그것이 바로 원명제의 대우이므로(19주차 문제 1(a)에서 만든 그 대우다) 귀류 증명의 몸통은 대우 증명 전체와 한 줄도 다르지 않다.

복기. §1.6의 관찰이 실물로 확인된 자리다. 이 증명의 충돌 상대가 가정 \(P\)였다는 사실이 곧 “대우로 다시 쓸 수 있다”는 신호다. 대응이 하나 더 있다 — 문제 18에서 고쳐 쓴 직접 증명이 정확히 이 대우 증명이다. 같은 몸통이 어떤 명제의 대우 증명이면서 다른 명제의 직접 증명일 수 있다.

문제 4#

접근. 네 줄짜리 증명이고 관문은 두 곳이다 — 두 배수의 차를 잡아 \(1\)을 짜내는 것(2주차 문제 17), 그리고 나누어떨어짐을 부등식의 언어로 옮기는 것 (보조 명제 22.A). 첫 줄에 \(a \ge 2\)를 함께 적었는지도 확인한다.

풀이. 모순을 이끌어내기 위해, \(a \ge 2\)인데 결론이 거짓 — 곧 드모르간 2에 의해 \(a \mid b\)이고 \(a \mid (b+1)\)이라고 가정하자. \(a \mid (b+1)\)이고 \(a \mid b\)이므로 2주차 문제 17에 의해

\[ a \mid \big((b+1) - b\big) = 1 \]

이다. 보조 명제 22.A에 의해 \(a = 1\) 또는 \(a = -1\)이므로 \(a \le 1\)이다. 이는 \(a \ge 2\)라는 가정과 모순이다. 따라서 \(a \nmid b\) 또는 \(a \nmid (b+1)\)이다. \(\blacksquare\)

(검산: \(a = 5\), \(b = 24\)이면 \(5 \mid 25\)는 참이지만 \(5 \mid 24\)는 거짓이므로 결론의 “또는”이 성립한다. 두 배수 사이의 간격이 \(a\) 이상이므로 연속한 두 정수가 동시에 걸릴 수 없다는 것이 수치적 그림이다.)

복기. “두 배수의 차를 잡아 작은 수를 짜낸다”는 이 주차에서 가장 자주 재사용되는 수단이다. 문제 11이 같은 두 줄을 귀류 없이 쓰고, 21주차 예제 2.3의 \(p \mid 1\)도 같은 자리에서 나왔다.

문제 5#

접근. 같은 정수 \(n\)이 짝수이면서 홀수라고 가정하면 등식이 두 개 생긴다. 두 우변을 같다고 놓고 정리하면 \(2 \times (\text{정수}) = 1\) 꼴이 나오고, 그것이 보조 명제 22.A와 부딪힌다. 이 문제가 5주차부터 인정하고 써 온 사실을 정리로 승격시키는 자리다.

풀이. 모순을 이끌어내기 위해, 어떤 정수 \(n\)이 짝수이면서 동시에 홀수라고 가정하자. 정의 1.1과 정의 1.2에 의해 \(n = 2a\)인 정수 \(a\)와 \(n = 2b + 1\)인 정수 \(b\)가 존재한다. 두 표현이 같은 수 \(n\)을 나타내므로

\[ 2a = 2b + 1 \]

이고, 양변에서 \(2b\)를 빼면 \(2a - 2b = 1\), 곧

\[ 2(a - b) = 1 \]

이다. \(a - b\)는 정수이므로(근거 ②) 이 등식은 \(2 \mid 1\)을 뜻한다(정의 2.1). 그런데 보조 명제 22.A에 의해 1의 약수는 \(1\)과 \(-1\)뿐이고 \(2\)는 그중 어느 것도 아니다. 모순이다. 따라서 짝수이면서 동시에 홀수인 정수는 존재하지 않는다. \(\blacksquare\)

복기. 5주차 빈칸 사다리 훈련 1에서 \(E \cap O = \emptyset\)로 적었고, 17주차의 짝/홀 분할에서 “둘 중 정확히 하나”의 ‘정확히’가 이 사실이었으며, 21주차 빈칸 사다리 훈련 3이 이것을 명시적으로 빌렸다. 오래 인정하고 쓴 사실도 결국 정의 두 개와 뺄셈 한 번으로 갚아진다 — 인정하고 쓴다는 것은 포기가 아니라 회수 일정에 올린다는 뜻이다.

문제 6#

접근. 가정이 둘(\(x\)가 유리수, \(xy\)가 무리수)이고 거기에 부정 하나(\(y\)가 유리수)가 얹힌다. 손에 유리수가 둘(\(x\)와 \(y\)) 있으면 15주차 닫힘성 목록에서 곱을 꺼낼 수 있고, 그 결과가 남은 가정과 부딪힌다.

풀이. 모순을 이끌어내기 위해, \(x\)가 유리수이고 \(xy\)가 무리수인데 \(y\)가 유리수라고 가정하자. \(x\)와 \(y\)가 모두 유리수이므로, 유리수의 곱은 유리수라는 사실(15주차 빈칸 사다리 훈련 1)에 의해 \(xy\)는 유리수이다. 이는 \(xy\)가 무리수라는 가정과 모순이다(정의 15.1에 의해 한 실수가 유리수이면서 무리수일 수는 없다). 따라서 \(y\)는 무리수이다. \(\blacksquare\)

복기. 21주차 문제 8과 비교해 둔다. 그쪽 명제(”\(x\)가 0이 아닌 유리수이고 \(y\)가 무리수이면 \(xy\)는 무리수”)는 증명에서 \(\frac{xy}{x}\)를 만들어야 하므로 \(x \neq 0\)이 필요했다. 이번 방향은 곱만 쓰므로 그 조건이 필요 없다. 같은 재료라도 어느 연산을 쓰느냐에 따라 요구되는 조건이 달라진다 — 조건의 소비처를 확인하는 습관이 여기서 값을 한다.

문제 7#

접근. §1.1에서 세 기법이 차례로 막힌 그 명제다. 귀류로 첫 줄을 쓰면 손에 세 문장이 들어온다 — \(a \mid b\), \(a \nmid c\), 그리고 \(a \mid (b+c)\). 이 중 앞뒤 두 개를 결합하면 2주차 문제 17이 발동해 \(a \mid c\)가 나오고, 남은 \(a \nmid c\)가 충돌 상대다.

풀이. 모순을 이끌어내기 위해, \(a \mid b\)이고 \(a \nmid c\)인데 \(a \mid (b+c)\)라고 가정하자. \(a \mid (b+c)\)이고 \(a \mid b\)이므로 2주차 문제 17에 의해 \(a \mid c\)이다. 이는 \(a \nmid c\)라는 가정과 모순이다. 따라서 \(a \nmid (b+c)\)이다. \(\blacksquare\)

(검산: \(a = 3\), \(b = 6\), \(c = 4\)이면 \(3 \mid 6\)이고 \(3 \nmid 4\)이므로 가정이 성립하고, \(b + c = 10\)에 대해 \(3 \nmid 10\)으로 결론도 성립한다.)

복기. 세 줄짜리 증명이지만 §1.1에서 직접과 대우가 모두 막힌 명제다. 증명의 길이와 기법 선택의 난이도는 별개다. 이 명제는 2주차 문제 17에서 가정 하나(\(a \mid (b+c)\))와 결론(\(a \mid c\))을 서로 부정해 맞바꾼 동치 형태다 — “\(A\)이고 \(B\)이면 \(C\)”와 “\(B\)이고 \(\neg C\)이면 \(\neg A\)”는 언제나 동치이므로, 두 명제는 같은 내용의 두 포장이다. 다만 이것을 대우라고 부르지는 않는다. 문제 17의 진짜 대우는 “\(a \nmid c\)이면 \(a \nmid (b+c)\) 또는 \(a \nmid b\)이다”로 결론이 “또는”인 별개의 명제다. 그리고 이번 명제를 직접 대우로 쓰려 하면 \(\neg P\)가 “또는”이 되어 막힌다는 점이 §1.1 시도 3의 관찰이었다.

문제 8#

접근. 소수의 정의 15.2는 “양의 약수가 1과 \(p\)뿐”이다. \(p\)가 짝수라고 가정하면 2가 \(p\)의 양의 약수가 되고, 가정 \(p > 2\)가 2를 “1도 아니고 \(p\)도 아닌 자리”에 놓는다. 가정 \(P\)의 두 조각(\(p\)가 소수, \(p > 2\))이 각각 어디서 소비되는지 확인하며 쓴다.

풀이. 모순을 이끌어내기 위해, \(p\)가 소수이고 \(p > 2\)인데 \(p\)가 짝수라고 가정하자. \(p\)가 짝수이므로 정의 1.1에 의해 \(p = 2k\)인 정수 \(k\)가 존재하고, 정의 2.1에 의해 \(2 \mid p\)이다. 곧 2는 \(p\)의 양의 약수이다. 그런데 \(p > 2\)이므로 \(2 \neq p\)이고, 또 \(2 \neq 1\)이다. 따라서 \(p\)는 1도 \(p\) 자신도 아닌 양의 약수 2를 가진다. 이는 \(p\)가 소수라는 가정, 곧 정의 15.2(“양의 약수가 1과 \(p\)뿐”)와 모순이다. 따라서 \(p\)는 홀수이다. \(\blacksquare\)

복기. 가정의 두 조각이 서로 다른 곳에서 소비됐다 — “\(p\)가 소수”는 마지막 충돌 선언에서, “\(p > 2\)”는 2가 \(p\) 자신이 아님을 확인하는 줄에서. \(p > 2\)를 빠뜨리면 \(p = 2\)에서 실제로 반례가 된다(2는 짝수인 소수다). 따름정리로 “2는 유일한 짝수 소수”가 나오고, 이 진술은 26주차의 유일성 증명에서 다시 포장된다.

문제 9#

접근. 예제 2.2의 숫자를 바꾼 판이다. 결론이 “또는”이므로 부정하면 드모르간 2로 부등식 두 개가 손에 들어오고, 변끼리 더하면 가정과 정면으로 부딪힌다.

풀이. 모순을 이끌어내기 위해, \(x + y \ge 100\)인데 \(x < 50\)이고 \(y < 50\)이라고 가정하자. 두 부등식을 변끼리 더하면(16주차 문제 2(c))

\[ x + y < 50 + 50 = 100 \]

이다. 이는 가정 \(x + y \ge 100\)과 모순이다. 따라서 \(x \ge 50\) 또는 \(y \ge 50\)이다. \(\blacksquare\)

복기. 예제 2.2와 이 문제의 유일한 차이는 \(2\)가 \(100\)으로, \(1\)이 \(50\)으로 바뀐 것뿐이다. 일반형으로 적으면 “\(x + y \ge 2s\)이면 \(x \ge s\) 또는 \(y \ge s\)”이고, 증명은 글자 그대로 같다 — 이런 유형에서는 숫자를 문자로 바꿔 두면 문제 하나가 무한히 많은 문제를 덮는다. 문제 13이 같은 발상을 \(n\)개의 수로 확장한 판이다.

문제 10#

접근. “최솟값이 존재하지 않는다”는 비존재 결론이므로 부정하면 최솟값 \(m\)이 손에 들어온다(21주차 §1.6 셋째 신호). 최솟값이라는 말에는 조건이 두 개 들어 있다 — ① \(m\) 자신이 구간 안에 있다 ② 구간의 모든 원소가 \(m\) 이상이다. \(\frac{m}{2}\)를 만들어 ②를 어기되, ①의 검증(그 수가 정말 구간 안에 있는가)을 빠뜨리지 않는 것이 이 문제의 관문이다.

풀이. 모순을 이끌어내기 위해, 열린구간 \((0,1)\)에 최솟값 \(m\)이 존재한다고 가정하자. 최솟값의 뜻에 의해 \(m \in (0,1)\)이고, 모든 \(z \in (0,1)\)에 대해 \(m \le z\)이다.

\(m \in (0,1)\)이므로 \(0 < m < 1\)이다. \(\frac{m}{2}\)을 생각하자.

첫째, \(\frac{m}{2} \in (0,1)\)이다. \(m > 0\)이고 \(2 > 0\)이므로 \(\frac{m}{2} > 0\)이고, \(m < 1\)이므로 \(\frac{m}{2} < \frac{1}{2} < 1\)이다.

둘째, \(\frac{m}{2} < m\)이다. \(m > 0\)이므로 \(\frac{m}{2} < m\)은 양변에 2를 곱한 \(m < 2m\), 곧 \(0 < m\)과 같은 내용이고 이는 참이다.

따라서 \(\frac{m}{2}\)은 \((0,1)\)의 원소이면서 \(m\)보다 작다. 이는 모든 \(z \in (0,1)\)에 대해 \(m \le z\)라는 최소성과 모순이다. 따라서 \((0,1)\)에는 최솟값이 존재하지 않는다. \(\blacksquare\)

복기. 최소성을 어기는 원소를 만들 때는 두 검증이 모두 필요하다 — 만든 수가 무대 안에 있는가, 그리고 정말 더 작은가. 하나만 확인하면 반례가 되지 않는다. 이 구간이 최솟값을 갖지 않는다는 사실은 33주차 최소원리의 대조군으로 다시 등장한다. 자연수의 부분집합은 반드시 최소원소를 갖는데 실수의 구간은 그렇지 않다는 대비가, 최소원리가 자연수의 특권임을 보여 주는 자리다.

문제 11#

접근. “공통 약수는 \(\pm 1\)뿐”은 “모든 공통 약수 \(d\)에 대해 \(d = \pm 1\)”이므로, 임의의 공통 약수 \(d\)를 잡아 \(d = \pm 1\)을 직접 보이면 된다. 예제 2.1과 같은 부품을 쓰지만 귀류가 필요 없다 — 결론이 긍정형이고 목표 꼴이 있기 때문이다 (가이드 ①).

풀이. \(d\)를 \(n\)과 \(n+1\)의 공통 약수라 하자. 곧 \(d \mid n\)이고 \(d \mid (n+1)\)이다. \(d \mid (n+1)\)이고 \(d \mid n\)이므로 2주차 문제 17에 의해

\[ d \mid \big((n+1) - n\big) = 1 \]

이다. 보조 명제 22.A에 의해 \(d = 1\) 또는 \(d = -1\)이다. \(d\)는 임의의 공통 약수였으므로, \(n\)과 \(n+1\)의 공통 약수는 \(\pm 1\)뿐이다. \(\blacksquare\)

(검산: \(n = 8\)이면 8의 약수는 \(\pm 1, \pm 2, \pm 4, \pm 8\)이고 9의 약수는 \(\pm 1, \pm 3, \pm 9\)이므로 공통인 것은 \(\pm 1\)뿐이다.)

복기. 예제 2.1은 같은 사실을 귀류로 적었고 이 문제는 직접으로 적었다. 두 서술의 차이는 첫 줄뿐이며, 몸통(“두 배수의 차로 \(1\)을 짜낸다”)은 같다 — 가이드 ①의 실물 사례다. 이 명제는 “연속한 두 정수는 서로소”라는 이름으로 34주차 문제 12(연속한 피보나치 수)에서 같은 부품으로 재사용된다.

문제 12#

접근. 결론이 “무리수”라는 부정형 개념이므로 귀류다(21주차 §1.6 첫째 신호). 목표는 \(\sqrt{2}\)를 유리수들만으로 표현하는 등식 한 줄을 만드는 것이다. \(\sqrt{2} = (r + \sqrt{2}) - r\)로 쓰면 우변이 유리수 두 개의 차가 된다.

풀이. 모순을 이끌어내기 위해, \(r\)이 유리수인데 \(r + \sqrt{2}\)가 유리수라고 가정하자. 그러면

\[ \sqrt{2} = (r + \sqrt{2}) - r \]

이고, 우변은 유리수 \(r + \sqrt{2}\)에서 유리수 \(r\)을 뺀 것이므로 유리수이다 (15주차 문제 9: 두 유리수의 차는 유리수). 곧 \(\sqrt{2}\)가 유리수가 된다. 이는 \(\sqrt{2}\)가 무리수라는 사실(21주차 예제 2.2)과 모순이다. 따라서 \(r + \sqrt{2}\)는 무리수이다. \(\blacksquare\)

복기. 이 설계의 이름을 붙이면 “무리수를 유리수들로 고립시키기”다. 21주차 빈칸 사다리 훈련 1(유리수 + 무리수 = 무리수)이 같은 설계였고, 문제 17이 같은 설계를 한 단계 복잡한 식에 쓴다. 고립시킬 때 필요한 것은 유리수 닫힘성 다섯 개(합\(\cdot\)차\(\cdot\)곱\(\cdot\)역수\(\cdot\)몫)이며, 어느 것을 쓰는지에 따라 필요한 조건이 달라진다는 점을 문제 6에서 확인했다.

문제 13#

접근. 결론 “적어도 하나의 \(x_i\)가 \(\mu\) 이상”은 존재 주장이므로, 부정하면 “모든 \(i\)에 대해 \(x_i < \mu\)”가 된다(11주차 총목록 다섯째 행). 부정하면 부등식이 \(n\)개 생기고, 그것을 전부 변끼리 더하면 평균의 정의에서 나온 등식과 부딪힌다. 평균의 정의를 등식으로 먼저 적어 두는 것이 출발점이다.

풀이. 평균이 \(\mu\)이므로, 평균의 정의 \(\mu = \dfrac{x_1 + x_2 + \cdots + x_n}{n}\)의 양변에 \(n\)을 곱하면

\[ x_1 + x_2 + \cdots + x_n = n\mu \]

이다. 모순을 이끌어내기 위해, 모든 \(i\)에 대해 \(x_i < \mu\)라고 가정하자. 이 부등식 \(n\)개를 변끼리 더하면(16주차 문제 2(c)를 \(n-1\)번 적용)

\[ x_1 + x_2 + \cdots + x_n < \underbrace{\mu + \mu + \cdots + \mu}_{n\text{개}} = n\mu \]

이다. 그런데 위에서 좌변은 \(n\mu\)와 같으므로 \(n\mu < n\mu\)가 되어, 같은 수가 자기 자신보다 작다는 모순에 이른다. 따라서 적어도 하나의 \(x_i\)는 \(\mu\) 이상이다. \(\blacksquare\)

복기. 존재 결론(“적어도 하나”)의 귀류는 전칭 가정(“전부 아니다”)을 준다 — 11주차의 부정 규칙이 그대로 증명 전략이 되는 자리다. 이 증명은 어느 \(x_i\)가 \(\mu\) 이상인지 특정하지 않는다. 존재를 증명하면서 증인을 지목하지 않는 이런 증명을 26주차에서 비구성적 존재 증명이라는 이름으로 다시 다룬다. 정수 판으로 옮기면 26주차 문제 19의 비둘기집 원리가 된다.

문제 14#

접근. 세 관문이 있다 — 인수분해로 곱의 꼴을 만드는 것, 두 인수가 “같은 홀짝”임을 근거와 함께 보이는 것, 그리고 두 경우를 각각 봉쇄하는 것. 둘째 관문을 빠뜨리면 경우가 전체를 덮지 않는다.

풀이. 모순을 이끌어내기 위해, \(x^2 - y^2 = 2\)를 만족하는 정수 \(x, y\)가 존재한다고 가정하자. 인수분해하면 \((x-y)(x+y) = 2\)이다.

여기서 \((x-y) + (x+y) = 2x\)는 짝수이다. 만약 \(x - y\)와 \(x + y\)의 홀짝이 다르다면 그 합은 홀수이므로(1주차 빈칸 사다리 훈련 1: 홀수와 짝수의 합은 홀수) \(2x\)가 짝수라는 것과 어긋난다. 따라서 \(x - y\)와 \(x + y\)는 같은 홀짝이고, 정수는 짝수이거나 홀수이므로(17주차 짝/홀 분할) 다음 두 경우가 전체를 덮는다.

경우 1: 둘 다 짝수. \(x - y = 2s\), \(x + y = 2t\)인 정수 \(s, t\)가 존재하므로 \((x-y)(x+y) = 4st\)이고 \(st\)는 정수이다(근거 ②). 곧 \(2 = 4st\)이므로 \(4 \mid 2\)인데, \(2 = 4c\)인 정수 \(c\)는 존재하지 않는다(\(c = \frac{1}{2}\)은 정수가 아니다). 모순이다.

경우 2: 둘 다 홀수. 홀수와 홀수의 곱은 홀수이므로(1주차 문제 8) \((x-y)(x+y)\)는 홀수이다. 그런데 그 값은 \(2 = 2 \times 1\)로 짝수이다. 곧 같은 수가 짝수이면서 홀수이므로 문제 5에 의해 모순이다.

두 경우가 전체를 빠짐없이 덮고 어느 경우든 모순이므로, \(x^2 - y^2 = 2\)를 만족하는 정수 \(x, y\)는 존재하지 않는다. \(\blacksquare\)

복기. 귀류가 바깥 틀이고 경우 나누기가 안쪽 몸통인 이중 구조다. 기법은 서로를 대체하지 않고 층으로 쌓인다 — 문제 15가 같은 구조를 세 경우로 확장한 판이고, 빈칸 사다리 훈련 3에서 숫자만 바꾼 판을 한 번 썼다.

문제 15#

접근. 유리수 해가 있다고 가정하되 기약분수로 잡는다(정의 21.2). 기약성이 “\(p\)와 \(q\)가 둘 다 짝수인 경우”를 미리 제거해 주므로 검사할 경우가 셋으로 줄어든다. 각 경우에서 세 항 \(ap^2\), \(bpq\), \(cq^2\)의 홀짝을 하나씩 판정하고, 그 합의 홀짝을 \(0\)(짝수)과 비교한다. \(a, b, c\)가 전부 홀수라는 가정이 여기서 소비된다 — 홀수를 곱해도 홀짝이 바뀌지 않으므로(1주차 문제 8) 각 항의 홀짝이 \(p\)와 \(q\)의 홀짝만으로 결정된다.

풀이. 모순을 이끌어내기 위해, \(a, b, c\)가 모두 홀수인데 \(ax^2 + bx + c = 0\)이 유리수 해를 갖는다고 가정하자. 그 해를 기약분수 \(x = \dfrac{p}{q}\) (\(p, q\)는 정수, \(q \neq 0\))로 잡는다. 대입하면

\[ a\frac{p^2}{q^2} + b\frac{p}{q} + c = 0 \]

이고, 양변에 \(q^2\)을 곱하면

\[ ap^2 + bpq + cq^2 = 0 \]

이다. 기약분수이므로 \(p\)와 \(q\)의 공통 약수는 \(\pm 1\)뿐이고, 따라서 둘 다 짝수일 수는 없다(둘 다 짝수라면 2가 공통 약수가 된다). 정수는 짝수이거나 홀수이므로 남는 경우는 다음 셋뿐이고, 이 셋이 전체를 덮는다.

경우 1: \(p\) 홀수, \(q\) 홀수. \(ap^2\)은 홀수 세 개의 곱이므로 홀수이고 (1주차 문제 8을 두 번 적용), \(bpq\)도 홀수 세 개의 곱이므로 홀수이며, \(cq^2\)도 같은 이유로 홀수이다. 홀수 셋의 합은 홀수이다(홀+홀=짝, 짝+홀=홀 — 1주차 예제 2.3과 빈칸 사다리 훈련 1). 그런데 우변 \(0 = 2 \times 0\)은 짝수이므로, 같은 수가 홀수이면서 짝수가 되어 문제 5에 의해 모순이다.

경우 2: \(p\) 홀수, \(q\) 짝수. \(ap^2\)은 홀수 세 개의 곱이므로 홀수이다. \(bpq\)는 인수에 짝수 \(q\)가 있으므로 짝수이고, \(cq^2\)도 마찬가지로 짝수이다. 합은 홀수 + 짝수 + 짝수이므로 홀수이다. 우변 \(0\)은 짝수이므로 모순이다.

경우 3: \(p\) 짝수, \(q\) 홀수. \(ap^2\)은 인수에 짝수 \(p\)가 있으므로 짝수이고, \(bpq\)도 마찬가지로 짝수이다. \(cq^2\)은 홀수 세 개의 곱이므로 홀수이다. 합은 짝수 + 짝수 + 홀수이므로 홀수이다. 우변 \(0\)은 짝수이므로 모순이다.

세 경우가 전체를 덮고 어느 경우든 모순이므로, 유리수 해는 존재하지 않는다. \(\blacksquare\)

복기. 귀류 + 기약분수 + 경우 나누기가 한 증명에 겹쳐진 이번 주의 종합 문제다. 기약성은 여기서 두 가지 일을 한다 — 경우를 넷에서 셋으로 줄이고, \(p\)와 \(q\)의 홀짝 조합을 통제한다. 결과를 도구로 쓰면 \(x^2 + x + 1 = 0\)이나 \(3x^2 + 5x + 7 = 0\)이 유리근을 갖지 않음을 계산 없이 즉시 알 수 있다 — 계수 셋이 모두 홀수인지만 보면 된다.

문제 16#

접근. 등식을 \(x^3 + x = -1\)로 옮기면 좌변과 우변의 홀짝을 각각 판정하는 문제가 된다. 좌변을 \(x(x^2+1)\)로 인수분해한 뒤 \(x\)가 짝수인 경우와 홀수인 경우를 나누면, 두 경우 모두 좌변이 짝수라는 같은 판정이 나온다. 우변 \(-1\)은 홀수이므로 충돌한다.

풀이. 모순을 이끌어내기 위해, \(x^3 + x + 1 = 0\)을 만족하는 정수 \(x\)가 존재한다고 가정하자. 이항하면

\[ x^3 + x = -1 \]

이고, 좌변을 인수분해하면 \(x^3 + x = x(x^2 + 1)\)이다. 정수는 짝수이거나 홀수이므로(17주차 짝/홀 분할) 두 경우로 나눈다.

경우 1: \(x\)가 짝수. \(x = 2k\)인 정수 \(k\)가 존재하므로 \(x(x^2+1) = 2\big(k(x^2+1)\big)\)이고 \(k(x^2+1)\)은 정수이므로(근거 ②) 좌변은 짝수이다.

경우 2: \(x\)가 홀수. \(x\)가 홀수이면 \(x^2\)도 홀수이므로(1주차 문제 11) \(x^2 = 2j + 1\)인 정수 \(j\)가 존재하고, \(x^2 + 1 = 2j + 2 = 2(j+1)\)은 짝수이다. 따라서 \(x(x^2+1) = x \cdot 2(j+1) = 2\big(x(j+1)\big)\)이고 \(x(j+1)\)은 정수이므로 좌변은 짝수이다.

두 경우가 전체를 덮고 어느 경우든 좌변 \(x^3 + x\)는 짝수이다. 그런데 우변 \(-1 = 2 \times (-1) + 1\)은 홀수이다. 곧 같은 수가 짝수이면서 홀수이므로 문제 5에 의해 모순이다. 따라서 정수 해는 존재하지 않는다. \(\blacksquare\)

(검산: \(x = -2, -1, 0, 1\)을 넣으면 \(x^3 + x + 1\)의 값이 각각 \(-9, -1, 1, 3\)으로 \(0\)이 아니다. 실수 해는 \(-1\)과 \(0\) 사이에 하나 있지만 정수가 아니다.)

복기. “좌변과 우변의 홀짝을 각각 판정해 어긋남을 보인다”는 21주차 빈칸 사다리 훈련 3과 같은 요령이다. 이런 문제에서 경우 나누기는 좌변의 홀짝이 \(x\)에 따라 달라질 수 있다는 우려를 없애는 장치이고, 두 경우가 같은 결론에 도달하면 그 결론은 \(x\)와 무관하게 성립한다.

문제 17#

접근. 결론이 “\(a = c\)이고 \(b = d\)”라는 “그리고”이므로 두 주장을 각각 확보해야 한다. 순서를 잡으면 쉬워진다 — 먼저 \(b = d\)를 귀류로 얻고, 그것을 원래 등식에 대입하면 \(a = c\)가 따라온다. 귀류 부분의 설계는 문제 12와 같다. \(\sqrt{2}\)를 유리수들로 고립시키는 것이고, \(b - d \neq 0\)이 양변을 \(b - d\)로 나누는 줄에서 소비된다.

풀이. \(a, b, c, d\)를 유리수라 하고 \(a + b\sqrt{2} = c + d\sqrt{2}\)라 하자.

1단계: \(b = d\). 모순을 이끌어내기 위해 \(b \neq d\)라고 가정하자. 주어진 등식을 정리하면

\[ (b - d)\sqrt{2} = c - a \]

이고, \(b \neq d\)이므로 \(b - d \neq 0\)이어서 양변을 \(b - d\)로 나눌 수 있다.

\[ \sqrt{2} = \frac{c - a}{b - d} \]

우변에서 \(c - a\)는 두 유리수의 차이므로 유리수이고(15주차 문제 9), \(b - d\)도 같은 이유로 유리수이며 \(0\)이 아니다. 0이 아닌 유리수로 유리수를 나눈 몫은 유리수이므로(15주차 문제 15) 우변은 유리수이다. 곧 \(\sqrt{2}\)가 유리수가 된다. 이는 \(\sqrt{2}\)가 무리수라는 사실(21주차 예제 2.2)과 모순이다. 따라서 \(b = d\)이다.

2단계: \(a = c\). \(b = d\)를 원래 등식에 대입하면 \(a + b\sqrt{2} = c + b\sqrt{2}\)이고, 양변에서 \(b\sqrt{2}\)를 빼면 \(a = c\)이다.

두 주장이 모두 확보되었으므로 \(a = c\)이고 \(b = d\)이다. \(\blacksquare\)

복기. 고등학교에서 “무리수 부분끼리, 유리수 부분끼리 비교한다”고 외운 규칙의 증명이다. 규칙이 아니라 정리였고, 근거는 \(\sqrt{2}\)의 무리수성이었다. “그리고” 결론을 처리하는 표준 순서도 확인된다 — 두 주장을 동시에 만들려 하지 말고, 하나를 먼저 확보한 뒤 그것을 도구로 나머지를 얻는다.

문제 18#

접근. §1.8의 자기 점검 질문 하나면 된다 — 가정 “\(n^2\)이 홀수”가 모순 선언 이전의 어느 줄에서 쓰였는지 손가락으로 짚어 본다. 짚을 곳이 없으면 그 가정은 아무 일도 하지 않았고, 귀류의 껍데기가 군더더기라는 진단이 선다.

풀이. 논리적 오류는 없다. 각 줄의 근거도 정확하고 결론도 옳다. 문제는 귀류 가정 “\(n^2\)이 홀수”가 본문의 어느 줄에서도 사용되지 않았다는 점이다. 증명의 몸통 “\(n = 2k\)이므로 \(n^2 = 4k^2 = 2(2k^2)\)은 짝수이다”는 가정 “\(n\)이 짝수”만으로 완결되며, 그 자체가 원명제의 완전한 직접 증명이다. 곧 첫 줄과 마지막 두 줄이 전부 군더더기다.

고쳐 쓴 형태는 다음과 같다.

명제. \(n\)이 짝수이면 \(n^2\)은 짝수이다. 증명. \(n\)이 짝수라 가정하자. 정의 1.1에 의해 \(n = 2k\)인 정수 \(k\)가 존재한다. 그러면 \(n^2 = (2k)^2 = 4k^2 = 2(2k^2)\)이고 \(2k^2\)은 정수이므로 (근거 ②) \(n^2\)은 짝수이다. \(\blacksquare\)

가이드 ④의 문장 그대로다 — 부정 가정을 쓰지 않았다면 그것은 귀류법이 아니었다.

복기. 21주차 예제 2.2(\(\sqrt{2}\))와 비교하면 차이가 분명하다. 그쪽에서는 부정 가정(“유리수이다”)이 등식 \(\sqrt{2} = \frac{a}{b}\)를 낳았고 그 등식 없이는 한 줄도 나아갈 수 없었다. 여기서는 부정 가정이 아무것도 낳지 않는다. 판별의 기준은 감이 아니라 “그 가정에서 나온 문장이 하나라도 있는가”다. 이 문제의 수정본이 곧 문제 3에서 다룬 대우 증명과 같은 문장들이라는 점도 확인해 둔다.

문제 19#

접근. 21주차 문제 18(\(\sqrt{4}\))에서 실물로 본 상황의 일반화다. 갈림길은 “명제가 참인가 거짓인가” 하나이고, 두 갈래 각각에서 손이 할 일이 다르다.

풀이. (예시 답안)

원인 1 — 명제는 참인데 아직 충돌 지점을 찾지 못했다. 귀류법의 도착점은 “아무 모순”이므로 방향이 지정되어 있지 않고(§1.5), 따라서 전개가 모순에서 먼 쪽으로 갈 수 있다. 행동: ① 가정에서 아직 풀지 않은 정의가 있는지 확인해 전부 등식으로 바꾼다 ② 충돌 상대를 미리 설치했는지 점검한다(기약성 같은 조건 — 21주차 확인 3) ③ 경우 나누기로 분기해 각 갈래에서 다시 시도한다 ④ 직접이나 대우로 기법을 바꿔 본다.

원인 2 — 명제가 애초에 거짓이다. 명제가 거짓이면 \(\neg P\)가 참이고, 참인 가정에서는 모순이 유도될 수 없다. 아무리 오래 전개해도 모순이 나오지 않는 것이 당연하다. 행동: 작은 값들을 차례로 대입해 반례를 수색한다. 반례가 하나라도 나오면 그 명제는 거짓으로 확정된다.

두 원인을 구분하는 실전 동선은 왕복이다 — 증명이 막히면 반례를 찾고, 반례가 찾아지지 않으면 그 실패에서 얻은 정보(어떤 조건 때문에 반례가 안 되는가)를 가지고 다시 증명을 시도한다. 이 왕복을 정식 과목으로 다루는 것이 29주차의 반증이다.

복기. 21주차 문제 18의 \(\sqrt{4}\)는 원인 2의 실물이었다 — \(\sqrt{4} = 2\)는 유리수이므로 “무리수이다”라는 명제가 거짓이고, 그래서 \(\sqrt{2}\) 증명의 흉내가 \(b^2 = c^2\)에서 멈춘 것이다. 모순이 나오지 않는다는 사실 자체가 정보라는 것이 이 문제의 요점이다.

문제 20#

접근. 가이드 네 조를 외워 옮기는 것이 아니라, 이번 주에 푼 문제들을 조별로 분류해 각 칸에 문제 번호를 붙여 본다. 붙일 문제가 떠오르지 않는 조가 있으면 그 조를 아직 쓰지 못한 것이다.

풀이. (예시 답안)

① 먼저 직접을 시도한다 — 가정을 정의로 풀어 결론의 목표 꼴을 만든다. 가정도 결론도 긍정형이고 정의가 즉시 풀리면 직접이 최단이다. (이번 주에서는 문제 11이 그랬다 — 결론이 “\(d = \pm 1\)”이라는 긍정형이라 귀류가 필요 없었다.)

② 가정이 \(n^2\) 같은 합성식이거나 부정형이거나, 결론이 “또는”\(\cdot\)”그리고”이면 대우로 갈아탄다 — 가정과 결론이 자리를 바꾸면 다루기 쉬운 쪽이 가정이 된다. (문제 3에서 다룬 명제가 대우로도 같은 몸통이 되는 사례였고, 결론이 “또는”인 문제 1(c)\(\cdot\)문제 9는 대우로 적어도 몸통이 같다.)

③ 결론이 무리수\(\cdot\)비존재\(\cdot\)무한 등 부정 자체이거나, 대우로 뒤집어도 결론 쪽에 “또는”이 남아 지목이 안 되면 귀류로 간다 — 부정이 재료가 되기 때문이다. (문제 7, 10, 12, 14, 15가 전부 이 조에 해당한다.)

④ 다 쓴 뒤 점검한다 — 귀류 가정을 실제로 썼는가. 안 썼다면 껍데기를 벗긴다. (문제 18이 이 조의 실물이다.)

자기 점검 질문: “귀류 가정 \(\neg Q\)에서 유도된 문장이 모순 선언 이전에 하나라도 있는가.” 하나도 없다면 그 증명은 귀류법이 아니라, 직접 증명 앞뒤에 문장 두 개를 덧붙인 것이다.

복기. 가이드는 규칙이 아니라 순서다 — ①부터 시도해 막히면 다음으로 내려간다. 막히는 자리가 곧 신호이므로, 기법 선택은 취향이 아니라 문제 문장이 정한다. 이 순서를 세 기법 모두에 대해 한 명제로 실습하는 것이 다음 주의 내용이다.

다음 주 예고: 23주차에서는 같은 명제를 직접\(\cdot\)대우\(\cdot\)귀류 세 방식으로 각각 증명해 보고, 어느 문장에 어느 기법이 자연스러운지 비교한다. 이번 주에 세운 기법 선택 가이드 ①~④가 판단의 기준이 되고, 특히 ④(남용 점검)가 세 답안을 나란히 놓고 길이를 비교하는 자리에서 실물로 확인된다 — 기법 선택이 감이 아니라 신호 읽기가 되도록 만드는 훈련 주간이다.