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

내용

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

예제 — 반증을 함께 쓰기#

세 예제에서 지지대를 하나씩 뺀다. 예제 2.1은 설계부터 한 줄씩 함께 만들고, 예제 2.2는 설계만 함께, 예제 2.3은 설계부터 혼자 한 뒤 완성본과 대조한다.

예제 2.1 — 조건문 반례의 완전 서술#

명제(반증 대상). “모든 자연수 \(n\)에 대해, \(n^2 - n + 11\)은 소수이다.”

설계 — 쓰기 전에 정하는 두 가지. 반증도 증명이므로 출발점과 도착점을 먼저 번역한다. 반증에서 출발점은 \(S\)의 부정이고, 도착점은 그 부정을 증명하기 위해 제출해야 할 것이다.

	말	수식 번역
반증 대상 \(S\)	모든 자연수 \(n\)에 대해 \(n^2 - n + 11\)은 소수	\(\forall n \in \mathbb{N},\ Q(n)\) (\(Q(n)\): “\(n^2-n+11\)이 소수”)
출발점 \(\neg S\)	\(\underline{\quad(1)\quad}\)	\(\exists n \in \mathbb{N},\ \neg Q(n)\)
도착점	\(\underline{\quad(2)\quad}\)	검증 1: \(n \in \mathbb{N}\) / 검증 2: \(n^2-n+11\)이 소수가 아님

확인 9. 번역표의 빈칸 (1)(2)를 채워 보자. 이 명제는 §1.4 표의 어느

행인가.

답

(1) \(n^2 - n + 11\)이 소수가 아닌 자연수 \(n\)이 존재한다.

(2) 그런 \(n\)을 하나 제시하고 검증 두 개를 붙인다.

첫째 행(\(\forall x,\ P(x)\))이다. 다만 “자연수 \(n\)에 대해”라는 무대 제한이

붙어 있으므로 검증 1이 “무대 안에 있음”의 확인으로 나타난다 —

정의 29.2의 괄호 규정 그대로다.

1단계 — 수색. 도착점이 정해졌으니 이제 \(n\)을 찾는다. 작은 값부터 전수 대입해 본다(체크리스트 ⑦).

\(n\)	1	2	3	4	5	6	7	8	9	10
\(n^2-n+11\)	11	13	17	23	31	41	53	67	83	101

열 번 전부 소수다. 그러나 열 번의 성공은 열한 번째를 보장하지 않는다 (1주차 문제 20). 전수 대입이 소득 없이 끝났으므로 수색 방식을 바꾼다 — 값을 넣어 보는 대신 식의 구조를 본다. 세 항이 모두 같은 수의 배수가 되게 만들면 그 수가 \(n^2 - n + 11\)의 약수가 되므로 합성수 후보가 된다.

확인 10. \(n^2\), \(-n\), \(11\)의 세 항이 모두 11의 배수가 되게 하려면

\(n\)을 어떤 수로 잡아야 하는가. 가장 작은 자연수는 무엇인가.

답

\(n\)을 11의 배수로 잡으면 된다. \(n = 11m\)이면

\(n^2 - n + 11 = 121m^2 - 11m + 11 = 11(11m^2 - m + 1)\)이므로 항상 11의

배수다. 게다가 \(m \ge 1\)이면 \(11m^2 - m + 1 \ge 11 > 1\)이므로 값은 \(11\)과

\(1\)보다 큰 정수의 곱, 곧 합성수다. 가장 작은 자연수는 \(n = 11\)이고 값은

\(11 \times 11 = 121\)이다.

1주차 문제 18에서 \(n^2+n+41\)의 반례를 \(n = 41\)에서 찾은 것과 같은 발상이며,

상수항이 수색 방향을 알려 준다.

2단계 — 검증 2를 어떻게 적을 것인가. 반례를 찾았다고 끝이 아니다. “\(121\)은 소수가 아니다”도 근거가 필요한 주장이다.

확인 11. “\(121\)이 소수가 아니다”를 무엇으로 보이는가.

“\(\underline{\quad}\)이라는 약수를 제시한다” 꼴로 답해 보자.

답

\(121 = 11 \times 11\)이므로 \(11\)이라는 약수를 제시한다. 소수의 정의가

“1보다 큰 자연수이면서 양의 약수가 1과 자기 자신뿐”이므로, 그 둘이 아닌

약수 하나를 제시하면 “소수가 아님”이 확정된다 — 이것도 존재 주장의

증인 제시(26주차)다.

완성본. 지금까지 정한 것을 서식에 배치하면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 “왜”에 스스로 답해 본다.

증명의 한 줄	왜 이 줄을 쓰는가?
반례로 \(n = 11\)을 제시한다.	\(\neg S\)가 존재 명제이므로 증인 하나가 본체다(§1.4 첫째 행). \(n = 11\)은 1단계 수색의 결과이며, 상수항 11에 맞춰 세 항의 공통인수를 만든 것이다.
(검증 1) \(11 \in \mathbb{N}\)이므로 가정을 만족한다. ✓	무대 확인. 짧다고 생략하지 않는다 — §1.5의 삭제 실험이 이 줄이 빠질 때 무엇이 통과하는지 보였다.
(검증 2) \(11^2 - 11 + 11 = 121 = 11 \times 11\)이고, \(11\)은 1과 121이 아닌 양의 약수이므로 121은 소수가 아니다. ✗	결론 위배의 증명. 계산은 근거 ③, “소수가 아님”의 판정은 근거 ①(소수의 정의)이다. 약수를 실제로 제시하는 것이 이 줄의 본체다.
따라서 명제는 거짓이다. \(\blacksquare\)	반증 완료 선언. 무엇이 확정되었는지를 명시하고 닫는다.

대입 시뮬레이션 — 반례 하나가 명제 전체를 무너뜨리는 이유. \(n = 22\)로 바꾸어도 같은 네 줄이 그대로 작동한다: \(22^2 - 22 + 11 = 484 - 22 + 11 = 473 = 11 \times 43\).

확인 12. 반례가 \(n = 11, 22, 33, \dots\)으로 무한히 많다는 사실은 이 반증에

무엇을 더해 주는가.

답

아무것도 더해 주지 않는다. \(\neg S\)는 존재 명제이므로 증인 하나로 이미

증명이 끝났고, 증인을 더 모아도 명제가 “더 거짓”이 되지는 않는다

(§1.5의 “하나” 조각). 다만 수색 단계에서는 유용하다 — 반례가 여럿임을

알면 그중 검증이 가장 쉬운 것을 고를 수 있다.

예제 2.2 — 존재 명제의 반증#

명제(반증 대상). “\(x^2 < x < x^3\)인 실수 \(x\)가 존재한다.”

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

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

출발점 \(\neg S\): \(\underline{\qquad}\)

도착점: 반례 하나를 제시하면 되는가, 아니면 다른 것이 필요한가.

답

\(\neg S\): “모든 실수 \(x\)에 대해 \(x^2 < x < x^3\)은 성립하지 않는다.”

반례 하나로는 안 된다. \(\neg S\)가 전칭 명제이므로 모든 실수를 한 번에

처리하는 논증이 필요하다(§1.4 셋째 행). “\(x = 2\)에서는 성립하지 않는다”를

아무리 모아도 “어디에도 없다”가 되지 않는다 — 확인한 곳 밖에 남아 있는

실수가 언제나 무한히 많기 때문이다.

전칭 증명의 세 갈래(전수 조사\(\cdot\)일반 논증\(\cdot\)귀류) 중 여기서는 귀류를 쓴다. 조건 \(x^2 < x < x^3\)이 \(x\)의 범위를 강하게 좁히므로 그 안에서 모순을 만들기 쉽기 때문이다.

반증. 부정 — “모든 실수 \(x\)에 대해 \(x^2 < x < x^3\)은 성립하지 않는다” — 을 증명한다. 귀류법으로, \(x^2 < x < x^3\)인 실수 \(x\)가 존재한다고 가정하자.

첫째 부등식 \(x^2 < x\)에서 시작한다. 임의의 실수의 제곱은 0 이상이므로 \(0 \le x^2 < x\)이고, 따라서 \(x > 0\)이다. 양변을 양수 \(x\)로 나누면 (W3, 16주차 — 양수로 나누므로 방향이 유지된다) \(x < 1\)이므로 \(0 < x < 1\)이다. 다음으로 \(x^2 < x\)의 양변에 양수 \(x\)를 곱하면 (W3, 방향 유지)

\[ x^3 = x \cdot x^2 < x \cdot x = x^2 \]

이다. 가정의 첫째 부등식이 \(x^2 < x\)였으므로 부등식의 추이성((W6), 16주차)에 의해 \(x^3 < x\)이다. 그런데 가정의 둘째 부등식은 \(x < x^3\)이었다. 같은 두 수에 대해 \(x^3 < x\)와 \(x < x^3\)이 동시에 성립할 수는 없으므로 모순이다. 따라서 그런 실수는 존재하지 않으며, 원래 명제는 거짓이다. \(\blacksquare\)

이 증명이 반례로는 불가능한 이유. 사용한 것은 “\(x\)가 조건을 만족한다”는 가정뿐이고 구체적인 수는 한 번도 등장하지 않았다. 이것이 전칭 증명의 모양이다 — 어떤 실수가 오더라도 같은 줄들이 작동해야 하므로 어떤 실수도 특정하지 않는다.

예제 2.3 — 판별: 증명인가 반증인가#

명제. “모든 자연수 \(n\)에 대해 \(3^n > n^3\)이다.”

이번에는 설계부터 혼자 한다. 연필로 다음 순서를 직접 수행한 뒤 아래와 대조한다: ① 작은 \(n\)에서 실험한다 ② 참\(\cdot\)거짓을 판별한다 ③ 판별 결과에 맞는 서식으로 실행한다.

실험. \(n = 1\): \(3^1 = 3 > 1 = 1^3\) ✓ (여유 2). \(n = 2\): \(3^2 = 9 > 8 = 2^3\) ✓ (여유 1). \(n = 3\): 좌변 \(3^3 = 27\)이고 우변 \(3^3 = 27\)이므로 \(27 > 27\)은 거짓이다 ✗. 확인 7에서 예고한 대로 여유가 좁아지는 방향에서 뒤집혔고, 뒤집힌 원인은 등호다 — \(27 \ge 27\)은 참이지만 \(27 > 27\)은 거짓이다. 부등호가 \(\ge\)였다면 이 자리는 반례가 아니다.

판별. 거짓이다. 명제가 \(\forall\) 꼴이므로 반례 하나와 검증 두 개를 제출한다.

반증. 반례로 \(n = 3\)을 제시한다. (검증 1) \(3 \in \mathbb{N}\)이다 ✓. (검증 2) 좌변은 \(3^3 = 27\)이고 우변도 \(3^3 = 27\)이므로 \(3^n > n^3\)은 \(n = 3\)에서 \(27 > 27\)이 되어 성립하지 않는다 ✗. 따라서 명제는 거짓이다. \(\blacksquare\)

반례는 명제를 수선하기도 한다. \(n \ge 4\)에서는 다시 \(3^n > n^3\)이 참이다 (\(n = 4\): \(81 > 64\), \(n = 5\): \(243 > 125\)). 곧 “\(n \ge 4\)인 모든 자연수 \(n\)에 대해 \(3^n > n^3\)”으로 고치면 참인 명제가 된다. 그 증명은 귀납법이 필요하므로 지금은 인정하지 않고 남겨 둔다 — 32주차 문제 12에서 갚는다. 반례는 명제를 죽이기만 하는 것이 아니라 올바른 경계를 알려 준다.

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

세 예제가 밟은 단계를 표 한 장으로 맞춰 본다.

단계	예제 2.1	예제 2.2	예제 2.3
① \(\neg S\) 만들기 (11주차)	\(n^2-n+11\)이 소수가 아닌 자연수가 존재	\(\underline{\quad(1)\quad}\)	\(\underline{\quad(2)\quad}\)
② 전략 결정 (§1.4 표)	반례 하나	\(\underline{\quad(3)\quad}\)	반례 하나
③ 실행	제시 + 검증 2개	귀류법	\(\underline{\quad(4)\quad}\)

확인 14. 위 대응표의 빈칸 (1)~(4)를 채워 보자.

답

(1) 모든 실수 \(x\)에 대해 \(x^2 < x < x^3\)은 성립하지 않는다.

(2) \(3^n > n^3\)이 성립하지 않는 자연수 \(n\)이 존재한다.

(3) 전칭 증명.

(4) 제시 + 검증 2개.

세 예제 모두 ①에서 부정을 만들고 ②에서 그 모양으로 전략을 정한 뒤

③에서 실행했다. 달라진 것은 ②의 결과뿐이다.

이번 주에 확인한 것 — 반증 3단계 틀

① 부정 \(\neg S\)를 정확히 만든다(11주차 규칙).

② \(\neg S\)의 모양으로 전략을 정한다(\(\exists\)이면 반례 하나, \(\forall\)이면 전칭 증명).

③ 정해진 서식으로 실행한다(반례는 검증 두 개, 전칭 증명은 지금까지의 기법).

새로 배운 기법은 없다 — 지금까지의 증명 기법이 \(\neg S\)를 향할 뿐이다.

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

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

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

명제(반증 대상). “모든 실수 \(x\)에 대해 \(x^2 \ge x\)이다.”

반증. 반례로 \(x = \underline{\quad(1)\quad}\)을 제시한다. (검증 1) 이 수는 실수이다 ✓. (검증 2) \(x^2 = \underline{\quad(2)\quad}\)이고 \(x = \underline{\quad(1)\quad}\)이므로 \(x^2 \underline{\quad(3)\quad} x\)가 되어 결론을 위배한다 ✗. 따라서 명제는 거짓이다. \(\blacksquare\)

(수색 힌트: 체크리스트 ③ — \(0 < x < 1\)인 분수는 제곱하면 작아진다. §1.1에서 직접 증명이 막힌 구간이 정확히 여기였다.)

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

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

명제(반증 대상). “모든 정수 \(a, b\)에 대해, \(a \mid b\)이면 \(a \le b\)이다.”

반증. 이 명제의 부정은 “\(a \mid b\)이면서 \(a \le b\)가 아닌 정수 \(a, b\)가 \(\underline{\quad(1)\quad}\)한다”이므로(\(\underline{\quad(2)\quad}\)주차의 부정 규칙, 근거 ④), 그런 \(a, b\)를 한 쌍 제시하면 된다.

반례로 \(a = 2\), \(b = \underline{\quad(3)\quad}\)을 제시한다. (검증 1) \(a \mid b\)는 참이다: \(\underline{\quad(4)\quad} = 2 \times (-2)\)이고 \(-2 \in \mathbb{Z}\)이므로 정의 2.1에 의해 \(2 \mid (-4)\)이다 (근거 \(\underline{\quad(5)\quad}\)). (검증 2) \(a \le b\)는 거짓이다: \(2 \underline{\quad(6)\quad} -4\)이므로 \(2 \le -4\)는 성립하지 않는다 ✗. 따라서 명제는 거짓이다. \(\blacksquare\)

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

이번에는 반증 3단계 틀의 각 칸을 통째로 채운다.

명제(반증 대상). “\(3x + 6y = 4\)를 만족하는 정수 \(x, y\)가 존재한다.”

반증의 뼈대.

① 부정 \(\neg S\) 만들기: \(\underline{\quad(1)\quad}\)
② 전략 결정: \(\underline{\quad(2)\quad}\)
③ 실행: \(\underline{\quad(3)\quad}\)

(수색 힌트: 좌변을 묶으면 어떤 수의 배수인지 드러난다. 이 훈련이 문제 16의 예행연습이다.)

연습문제 (20문항)#

해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 ‘접근’까지만 읽고 다시 시도한다. 반례는 반드시 완전 서식 (제시 + 검증 1 + 검증 2)으로 적는다.

이번 주의 채점 기준

답이 아니라 근거가 점수다. “반례: \(n = 3\)”은 0점이고,

“\(3 \in \mathbb{N}\)이고 \(2^3 = 8 < 9 = 3^2\)이므로 결론을 위배한다”가 만점이다.

참\(\cdot\)거짓만 묻는 문항(문제 6)을 제외하면, 검증이 하나만 있는 답안은

미완성으로 본다. 힌트 상자는 5분 이상 막힌 뒤에만 연다.

기본 ●○○#

1. [백지] 명제 유형별 반증 전략 표(\(\forall\) / \(\forall(P{\Rightarrow}Q)\) / \(\exists\))와 반례 서술 서식을 쓰시오.

힌트

외우려 하지 말고 부정 규칙에서 재구성한다. \(\forall\)의 부정은 \(\exists\),

\(\exists\)의 부정은 \(\forall\)(11주차), 조건문의 부정은 \(P \land \neg Q\)(9주차) —

이 \(\land\)의 양쪽이 곧 검증 두 개다.

2. 반증하시오: “모든 실수 \(a, b\)에 대해 \((a+b)^2 = a^2 + b^2\)이다.”

힌트

확인 6에서 수색을 마쳤다. 참인 항등식과 나란히 놓으면 빠진 항이 보이고,

그 항이 0이 아니게 하는 가장 작은 수를 고르면 된다.

3. 반증하시오: “모든 실수 \(x, y\)에 대해 \(|x + y| = |x| + |y|\)이다.”

힌트

참인 정리는 등호가 아니라 \(\le\)였다(17주차). 두 수의 부호가 반대이면

합의 크기가 줄어든다 — 거기가 등호가 무너지는 자리다.

4. 반증하시오: “모든 소수는 홀수이다.” (1주차 문제 19의 완전 서식 재작성)

힌트

체크리스트 ⑤. 검증 1은 “소수임”을 소수의 정의로, 검증 2는 “홀수가 아님”을

짝수의 정의로 확인한다 — 두 줄 모두 정의가 근거다.

5. 빈칸 훈련을 백지에서 완성하시오.

힌트

훈련 1의 명제를 기억에서 꺼내 적고 서식 세 줄을 채운다. 검증 1(실수임)을

빠뜨리지 않았는지 확인한다.

6. 다음 각 명제의 참\(\cdot\)거짓만 판별하시오 (수색 실험 — 증명\(\cdot\)반증 불필요). (a) 모든 자연수 \(n\)에 대해 \(n^2 \ge 2n\)이다. (b) \(a \mid b\)이고 \(b \mid a\)인 서로 다른 정수 \(a, b\)가 존재한다. (c) 모든 집합 \(A\)에 대해 \(\emptyset \in \mathcal{P}(A)\)이다. (d) 두 무리수의 차는 항상 무리수이다.

힌트

네 항목 모두 체크리스트 앞쪽에서 끝난다. (a)는 ①, (b)는 ①과 ②, (c)는 이미

증명한 정리의 인용(4주차), (d)는 두 무리수를 같은 것으로 잡아 보는 ①이다.

표준 ●●○#

7. 반증하시오: “\(n\)이 소수이면 \(2^n - 1\)도 소수이다.” (수색: \(n = 2, 3, 5, 7\)에서는 \(3, 7, 31, 127\)로 전부 소수이다. 다음 소수에서: \(2^{11} - 1 = 2047 = 23 \times 89\))

힌트

수색 결과가 주어져 있으므로 할 일은 서식화뿐이다. 검증 1은 “11이 소수”,

검증 2는 인수분해의 제시다.

8. (a) 반증하시오: “모든 자연수 \(n\)에 대해 \(2^n \ge n^2\)이다.” (b) 이 명제를 참으로 만드는 범위 수정(”\(n \ge \_\)인 모든 자연수”)을 실험으로 제안하시오 (증명은 32주차 예제 2.1).

힌트

(a) \(n = 1, 2, 3\)을 차례로 대입한다 — 초반에 한 번 역전이 일어난다.

(b) \(n = 4\)부터 다시 계산해 어디서부터 뒤집히지 않는지 본다. 증명은

요구되지 않는다.

9. 반증하시오: “임의의 집합 \(A, B, C\)에 대해 \(A - (B - C) = (A - B) - C\)이다.”

힌트

수에서 먼저 확인한다: \(5 - (3 - 2)\)와 \((5 - 3) - 2\). 집합에서 같은 일이

일어나려면 \(C\)가 \(A\)와 겹쳐야 한다 — 체크리스트 ⑥으로 원소 하나짜리

집합부터 시도한다.

존재 명제의 반증 — 이번 주의 새 요구

세 문항(10\(\cdot\)11\(\cdot\)16)은 \(\exists\) 꼴 명제의 반증이다. 반례를 몇 개 제시해도

끝나지 않는다 — §1.4 표의 셋째 행대로 부정인 전칭 명제를 증명해야 한다.

방법은 셋 중 하나다: 후보가 유한하면 전수 조사, 좌변이 항상 갖는 성질이

있으면 일반 논증, 그 밖에는 귀류. 이미 증명된 불가능성 정리가 있으면

인용하는 것으로 끝난다(근거 ④).

10. 반증하시오: “\(4 \mid (n^2 + 2)\)인 정수 \(n\)이 존재한다.” (존재의 반증 — 부품: 17주차 문제 17, 또는 17주차 문제 9에서 직접)

힌트

부정은 “모든 정수 \(n\)에 대해 \(4 \nmid (n^2+2)\)”이다. \(n\)을 짝수와 홀수로

나누어 \(n^2 + 2\)를 각각 계산하면 4의 배수에서 얼마나 떨어져 있는지 보인다.

11. 반증하시오: “\(r^2 = 3\)인 유리수 \(r\)이 존재한다.” (한 줄 — 어느 정리의 재해석인가?)

힌트

“제곱해서 3이 되는 수”의 이름을 떠올리고, 21주차에서 그 수에 대해 무엇을

증명했는지 찾는다. \(r\)이 음수인 경우도 처리되는지 한 줄로 확인한다.

12. 반증하시오: “모든 정수 \(n\)에 대해 \(\dfrac{n^2 + n}{2}\)은 짝수이다.”

힌트

이 식이 항상 정수라는 것은 참이다(1주차 문제 16). 그 참인 사실이 어디서

과장되었는지 보려면 가장 작은 \(n\)부터 값을 적어 본다.

13. 반증하시오: “두 소수의 합은 항상 짝수이다.” 그리고 이 명제가 그럴듯해 보였던 이유(어떤 참인 정리와 닮았는가)를 한 문장으로 쓰시오.

힌트

체크리스트 ⑤. 그럴듯했던 이유는 문제 4의 결과와 짝을 이룬다 — 참인 정리

위에 거짓인 전제를 얹은 것이다.

14. 판별 후 실행(증명 또는 반증)하시오: “모든 자연수 \(n\)에 대해, \(n^2 + n\)은 짝수이다.”

힌트

실행 전에 판별이 먼저다. \(n = 1, 2, 3\)을 대입해 반례가 나오지 않으면 증명

모드로 전환한다. \(n^2 + n\)을 인수분해하면 아는 정리가 보인다(1주차 문제 16).

도전 ●●●#

서술형 문항의 채점 기준

문제 15\(\cdot\)19\(\cdot\)20은 계산이 아니라 서술을 요구하지만 기준은 같다 — 주장에 근거가

붙어 있는가. 이번 주의 용어(반증, 검증 1\(\cdot\)2, \(\forall\)\(\cdot\)\(\exists\)의 비대칭,

참\(\cdot\)거짓\(\cdot\)미해결)로 그 주장을 지목한 문장이 점수다.

15. (수학사) 페르마(1640경)는 \(F_n = 2^{2^n} + 1\) 꼴의 수가 모두 소수라고 추측했다. \(F_0 = 3\), \(F_1 = 5\), \(F_2 = 17\), \(F_3 = 257\), \(F_4 = 65537\) — 전부 소수. 오일러(1732)는 \(F_5 = 4{,}294{,}967{,}297 = 641 \times 6{,}700{,}417\)임을 밝혀 반증했다. (a) 이 반증에서 “검증 2”에 해당하는 것은 무엇인가? (b) 이 사례가 1주차 문제 20(“예시는 증명이 아니다”)에 더해 주는 교훈을 두 문장 이내로 쓰시오. (계산 재현은 요구하지 않음)

힌트

(a) 정의 29.2의 두 검증을 이 사례에 대입한다. 검증 1은 \(n = 5\)가 무대 안에

있다는 것, 검증 2는 \(F_5\)가 소수가 아니라는 것 — 후자를 무엇으로 보였는가.

(제시된 곱셈이 실제로 맞는다는 것은 지금은 인정하고 쓴다.)

16. 반증하시오: “\(6x + 9y = 1\)을 만족하는 정수 \(x, y\)가 존재한다.” (존재의 반증 — 좌변이 항상 갖는 성질을 찾아 일반 논증)

힌트

훈련 3과 같은 구조다. 좌변에서 공통인수를 꺼내면 좌변이 항상 어떤 수의

배수인지 보이고, 우변 1이 거기 속하는지 확인하면 끝난다.

17. 반증하시오: “모든 자연수는 제곱수 세 개(0 허용)의 합으로 나타낼 수 있다.” (수색: 작은 수부터 표를 만들 것. 반례 후보에서 “합으로 만들 수 없음”은 가능한 제곱수 조합의 전수 조사로 증명 — 존재의 반증이 반례 검증 안에 들어 있는 이중 구조)

힌트

\(n\) 이하의 제곱수만 재료가 되므로 후보가 유한하고, 그래서 전수 조사가

가능하다. 7 이하의 제곱수는 \(0, 1, 4\)뿐이므로 이 셋에서 세 개를 골라

만들 수 있는 값을 전부 나열하면 된다.

18. 명제 “모든 홀수 \(n \ge 3\)은 소수이거나, 소수 두 개의 합이다”를 실험하시오: \(n = 3, 5, 7, 9, \dots, 27\)에서 성립 여부를 표로 만들고, 반례를 찾으면 완전 서식으로 반증하시오. (힌트: 홀수가 소수 두 개의 합이려면 그중 하나는 2여야 한다 — 왜? 그러면 수색이 “\(n - 2\)가 소수인가”로 압축된다)

힌트

문제의 힌트를 먼저 근거로 만든다: 홀수 + 홀수 = 짝수(1주차 예제 2.3)이므로

두 소수가 모두 홀수일 수는 없고 짝수인 소수는 2뿐이다. 그러면 확인할 것이

“\(n\)이 소수인가”와 “\(n - 2\)가 소수인가” 둘로 줄어든다.

19. (읽을거리 + 서술) 콜라츠 추측: “임의의 자연수에서 시작해, 짝수면 반으로 나누고 홀수면 3배 하고 1을 더하는 조작을 반복하면 언젠가 1에 도달한다.” \(n = 6\)과 \(n = 7\)에 대해 궤적을 계산해 확인하고, 이 추측이 “증명도 반증도 안 된 채 남아 있는” 상태가 무엇을 의미하는지 — 참\(\cdot\)거짓\(\cdot\)미해결의 세 상태에 대해 — 두 문장 이내로 쓰시오.

힌트

궤적은 1에 도달할 때까지 빠짐없이 적는다. 서술의 핵심은 “명제의 진리값”과

“우리가 아는 상태”의 구분이다 — 확인 3의 삭제 실험이 그 구분이었다.

20. (서술) (a) “반증도 증명이다”를 반증의 서식(검증 의무)과 연결해 두 문장 이내로. (b) 자신의 반례 수색 체크리스트를 우선순위와 함께 작성하시오 (개념 절 목록의 개인화 — 이번 주 문제들에서 실제로 반례가 살던 곳을 반영할 것).

힌트

(b)는 §1.6의 목록을 베끼는 것이 아니라 이번 주 20문항에서 반례가 실제로

나온 자리를 되짚어 순서를 다시 매기는 작업이다. 각 항목 옆에 통했던 문제

번호를 적어 두면 다음 주 시험에서 바로 쓸 수 있다.

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

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

1차 시도 (4일차) — 틀 카드 허용. 반증 3단계 틀(§2 관찰)과 근거 목록(§1.8)만 펴 놓고, 예제 2.1을 처음부터 끝까지 적는다. 유형 표와 서식은 보지 않는다.

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

정의 29.1(반증)을 한 문장으로 정확히 썼다.
유형별 반증 전략 표 세 행을 백지에 재현했다.
반례의 완전 서식(제시 + 검증 1 + 검증 2)으로 문제 하나를 처음부터 끝까지 재현했다.
존재 명제의 반증이 왜 전칭 증명인지 예제 2.2로 설명했다.
“여유가 좁아지는 방향에 반례가 있다”(예제 2.3, 확인 7)를 예와 함께 설명했다.
증명 시도와 반례 수색의 왕복 동선(§1.7)을 설명했다.
체크리스트 일곱 항목을 순서대로 적고, 각 항목이 통했던 문제 번호를 붙였다.

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

막힌 지점	처방
부정을 만들지 못한다	11주차 부정 규칙 — 양화사를 뒤집고 조건문을 \(P \land \neg Q\)로 푼다
반례 하나로 끝나는지 아닌지 헷갈린다	§1.4 유형 표 — \(\neg S\)가 \(\exists\)인지 \(\forall\)인지만 본다
반례를 찾았는데 무엇을 더 써야 할지 모르겠다	§1.5 해부 표와 두 삭제 실험 — 검증 1과 검증 2가 각각 무엇을 막는지 확인한다
반례가 어디 있는지 짐작이 안 된다	§1.6 체크리스트 — 특수한 값부터, 그래도 없으면 §1.7의 왕복
“소수가 아니다”, “짝수가 아니다”를 근거 없이 적는다	확인 11 — 부정 판정도 증인(약수 등) 제시가 필요하다
존재 명제 앞에서 반례만 모으게 된다	예제 2.2 — 확인한 곳 밖에 무한히 남는다는 사실을 다시 읽는다

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

해설#

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

빈칸 사다리 — 훈련 1#

(1) \(\dfrac12\) (\(0 < x < 1\)인 아무 수나 된다) (2) \(\dfrac14\) (3) \(<\)

※ 이 구간 전체가 반례인 이유는 §1.1의 인수분해에 있다 — \(x^2 \ge x \iff x(x-1) \ge 0\)이고, 이 곱이 음수가 되는 구간이 정확히 \(0 < x < 1\)이다. 완성된 반증문은 문제 5의 풀이에 있다.

빈칸 사다리 — 훈련 2#

(1) 존재 (2) 11 (3) \(-4\) (4) \(-4\) (5) ① (6) \(>\)

※ 이 명제가 그럴듯한 이유는 양의 정수만 떠올리는 습관 때문이다. \(a, b\)가 모두 양이면 \(a \mid b\)에서 실제로 \(a \le b\)가 따라온다. 무대가 \(\mathbb{Z}\)로 넓어지는 순간 음수와 0이 들어오고 명제는 거기서 깨진다 — 체크리스트 ②의 자리다. \(a = 3\), \(b = 0\)도 반례다(\(3 \mid 0\)은 참, \(3 \le 0\)은 거짓).

빈칸 사다리 — 훈련 3#

(1) 모든 정수 \(x, y\)에 대해 \(3x + 6y \neq 4\)이다. (2) \(\neg S\)가 전칭 명제이므로 반례 하나로는 안 된다. 좌변이 항상 갖는 성질을 찾아 일반 논증을 쓴다(§1.4 셋째 행). (3) \(x, y\)를 임의의 정수라 하자. 공통인수로 묶으면 \(3x + 6y = 3(x + 2y)\)이고, \(x + 2y\)는 정수의 곱과 합이므로 정수다(근거 ②). 따라서 \(3 \mid (3x + 6y)\)이다. 한편 \(4 = 3m\)인 정수 \(m\)은 없다 — \(m \le 1\)이면 \(3m \le 3 < 4\)이고 \(m \ge 2\)이면 \(3m \ge 6 > 4\)이다. 그러므로 \(3x + 6y = 4\)는 불가능하다. \(x, y\)는 임의였으므로 모든 정수 쌍에 대해 성립한다. \(\blacksquare\)

※ 마지막 문장(”\(x, y\)는 임의였으므로”)이 전칭 증명을 닫는 줄이다. 이 줄이 없으면 특정한 두 정수에 대해서만 보인 것이 된다. 문제 16이 계수만 바뀐 같은 구조다.

문제 1#

접근. 표를 통째로 외워 두었다가 꺼내는 것이 아니라 부정 규칙에서 그 자리에서 재구성한다. \(\forall\)의 부정은 \(\exists\), \(\exists\)의 부정은 \(\forall\)이며(11주차), 조건문의 부정은 \(P \land \neg Q\)다(9주차).

풀이. 유형별 반증 전략 표는 다음과 같다.

반증할 명제 \(S\)	\(\neg S\) (증명할 것)	전략
\(\forall x,\ P(x)\)	\(\exists x,\ \neg P(x)\)	반례 하나 제시 + 검증
\(\forall x,\ (P(x) \Rightarrow Q(x))\)	\(\exists x,\ P(x) \land \neg Q(x)\)	가정은 만족하고 결론은 위배하는 반례
\(\exists x,\ P(x)\)	\(\forall x,\ \neg P(x)\)	전칭 증명 (전수 조사\(\cdot\)일반 논증\(\cdot\)귀류)

반례 서술의 서식은 이렇다. “반례로 \(x = c\)를 제시한다. (검증 1) \(c\)는 가정 \(P\)를 만족한다 ✓. (검증 2) \(c\)는 결론 \(Q\)를 위배한다 ✗. 따라서 \(S\)는 거짓이다. \(\blacksquare\)”

복기. 첫째\(\cdot\)셋째 행은 양화사를 뒤집은 것이고, 둘째 행은 첫째 행의 \(P(x)\) 자리에 조건문을 넣고 \(\neg(P \Rightarrow Q) \equiv P \land \neg Q\)를 적용한 결과다. 그 \(\land\)의 왼쪽이 검증 1, 오른쪽이 검증 2다 — 서식이 두 검증을 요구하는 이유가 동치 하나에서 나오므로, 표를 잊어도 다시 만들 수 있다.

문제 2#

접근. 확인 6에서 수색을 마쳤다. 참인 항등식이 \((a+b)^2 = a^2 + 2ab + b^2\) 이므로 명제는 \(2ab\)를 빠뜨렸고, \(2ab \neq 0\)이기만 하면 무너진다. 체크리스트 ①대로 가장 작은 수를 고른다.

풀이. 반례로 \(a = 1\), \(b = 1\)을 제시한다. (검증 1) \(1\)과 \(1\)은 실수이다 ✓. (검증 2) 좌변은 \((1 + 1)^2 = 2^2 = 4\)이고 우변은 \(1^2 + 1^2 = 2\)이므로 \(4 \neq 2\)이다 — 등식이 성립하지 않는다 ✗. 따라서 명제는 거짓이다. \(\blacksquare\) (검산: \(a = 2\), \(b = 3\)에서도 좌변 \(25\), 우변 \(13\)으로 어긋난다.)

복기. 거짓 명제는 대개 참인 정리에서 항 하나를 잃어버린 모양이다. 그래서 수색의 첫 수는 “참인 것을 옆에 적어 놓고 차이를 보기”이며, 문제 3과 문제 12도 같은 계보다.

문제 3#

접근. 참인 정리는 삼각부등식 \(|x + y| \le |x| + |y|\)(17주차)이고 명제는 그 \(\le\)를 \(=\)로 바꿔 놓았다. 부호가 반대이면 합에서 상쇄가 일어나 좌변만 작아진다 — 거기가 등호가 깨지는 자리다.

풀이. 반례로 \(x = 1\), \(y = -1\)을 제시한다. (검증 1) \(1\)과 \(-1\)은 실수이다 ✓. (검증 2) 좌변은 \(|1 + (-1)| = |0| = 0\)이고 우변은 \(|1| + |-1| = 2\)이므로 \(0 \neq 2\)이다 ✗. 따라서 명제는 거짓이다. \(\blacksquare\) (검산: \(x = 2\), \(y = -5\)이면 좌변 \(3\), 우변 \(7\) — 역시 어긋나고 \(3 \le 7\)이므로 참인 삼각부등식과는 모순되지 않는다.)

복기. 참인 정리가 \(\le\)인데 \(=\)로 기억하는 일은 자주 일어난다. 부등식 정리를 만나면 “등호는 언제 성립하는가”를 함께 기억해 둔다 — 여기서는 \(x\)와 \(y\)의 부호가 같거나 한쪽이 0일 때다.

문제 4#

접근. 체크리스트 ⑤. 소수 중 유일한 짝수 \(2\)가 반례이고, 검증 두 줄 모두 정의가 근거다 — 검증 1은 소수의 정의, 검증 2는 짝수의 정의(1주차)다.

풀이. 반례로 \(n = 2\)를 제시한다. (검증 1) \(2\)는 소수이다: \(2 > 1\)이고 \(2\)의 양의 약수는 \(1\)과 \(2\)뿐이다 ✓. (검증 2) \(2 = 2 \times 1\)이고 \(1 \in \mathbb{Z}\)이므로 \(2\)는 짝수이다(정의 1.1). 짝수이면서 홀수인 정수는 없으므로(22주차 문제 5, 근거 ④) \(2\)는 홀수가 아니다 ✗. 따라서 명제는 거짓이다. \(\blacksquare\)

복기. 1주차 문제 19에서는 “반례: 2”로 충분했다. 같은 반례를 이번 주에는 두 검증까지 붙여 다시 쓴 것이며, 달라진 것은 수학이 아니라 요구되는 서식이다.

문제 5#

접근. 훈련 1을 백지에서 다시 만든다. 명제를 기억에서 꺼내고, 반례를 체크리스트 ③으로 찾고, 서식 세 줄을 채운다. 자가 채점의 기준은 하나 — 검증이 두 개 있는가.

풀이. 명제: “모든 실수 \(x\)에 대해 \(x^2 \ge x\)이다.” 반증. 반례로 \(x = \frac12\)을 제시한다. (검증 1) \(\frac12 \in \mathbb{R}\)이다 ✓. (검증 2) \(x^2 = \left(\frac12\right)^2 = \frac14\)이고 \(x = \frac12 = \frac24\)이므로 \(\frac14 < \frac24\), 곧 \(x^2 < x\)이다 — \(x^2 \ge x\)를 위배한다 ✗. 따라서 명제는 거짓이다. \(\blacksquare\) (검산: \(x = 0.9\)이면 \(0.81 < 0.9\) ✓. \(x = 2\)이면 \(4 \ge 2\)로 성립하므로, 반례가 아무 데나 있는 것이 아니라 특정 구간에만 있다.)

복기. 반례 후보는 검증 계산이 쉬운 것으로 고른다. \(\frac12\)은 제곱이 암산으로 끝나 검증 2가 한 줄이다. 같은 구간의 \(\frac37\)도 반례지만 계산만 길어질 뿐 얻는 것은 같다.

문제 6#

접근. 판별만 요구하므로 서식은 필요 없다. 다만 판별의 근거는 스스로 확인해 두어야 다음 문제들에서 쓸 수 있다. 네 항목 모두 특수한 값 하나 또는 이미 증명한 정리 하나로 끝난다.

풀이. (a) 거짓. \(n = 1\)에서 \(n^2 = 1\)이고 \(2n = 2\)이므로 \(1 \ge 2\)가 아니다. (\(n \ge 2\)에서는 \(n^2 = n \cdot n \ge 2n\)으로 성립하므로 어긋나는 곳은 \(n = 1\) 하나뿐이다 — 체크리스트 ①의 자리다.) (b) 참. \(a = 1\), \(b = -1\)을 잡으면 \(-1 = 1 \times (-1)\)이므로 \(1 \mid (-1)\), \(1 = (-1) \times (-1)\)이므로 \((-1) \mid 1\), 그리고 \(1 \neq -1\)이다. 세 조건이 모두 성립하므로 그런 정수 쌍이 존재한다. (2주차 문제 20이 이런 쌍은 \(a = \pm b\) 꼴뿐임을 증명했다.) (c) 참. 임의의 집합 \(A\)에 대해 \(\emptyset \subseteq A\)이므로 \(\emptyset \in \mathcal{P}(A)\)이다 — 4주차 문제 15(a)의 정리를 인용한다. (d) 거짓. \(\sqrt2\)는 무리수이고(21주차) \(\sqrt2 - \sqrt2 = 0 = \frac01\)은 유리수다. 두 무리수의 차가 유리수가 되는 사례가 있으므로 “항상 무리수”는 성립하지 않는다.

복기. (b)는 쌍 하나를 제시하면 끝이지만 (c)는 정리 인용이 아니었다면 모든 집합을 처리해야 했다 — 판별 문항에서도 \(\forall\)과 \(\exists\)의 비대칭(10주차)이 작동한다. (d)에서 “두 무리수”를 같은 수로 잡는 것은 명제가 서로 다를 것을 요구하지 않았으므로 허용된다.

문제 7#

접근. 수색 결과가 문제에 주어져 있으므로 남은 일은 서식화다. 명제가 조건문 꼴이므로 §1.4 표의 둘째 행이고, 검증 1은 “\(11\)이 소수”, 검증 2는 “\(2^{11}-1\)이 소수가 아님”이다. 검증 2를 인수분해로 적는 것이 핵심이다.

풀이. 반례로 \(n = 11\)을 제시한다. (검증 1) \(11\)은 소수이다: \(11 > 1\)이고 \(2, 3\) 중 어느 것으로도 나누어떨어지지 않으며 \(11 < 4^2\)이므로, \(11\)의 양의 약수는 \(1\)과 \(11\)뿐이다 ✓. (검증 2) \(2^{11} = 2048\)이므로 \(2^{11} - 1 = 2047\)이고, \(23 \times 89 = 23 \times 90 - 23 = 2070 - 23 = 2047\)이다. 따라서 \(2047\)은 \(1\)과 \(2047\)이 아닌 양의 약수 \(23\)을 가지므로 소수가 아니다 ✗. 따라서 명제는 거짓이다. \(\blacksquare\)

복기. 이 반례를 8주차의 언어로 옮기면 이렇다 — “\(p\)가 소수”는 “\(2^p - 1\)이 소수”이기 위한 필요조건일 뿐 충분조건이 아니다. (\(2^p - 1\) 꼴의 소수를 메르센 소수라 부르며, 현재 알려진 가장 큰 소수들이 이 꼴이다.)

문제 8#

접근. (a) 지수 \(2^n\)과 이차식 \(n^2\)의 경주다. 작은 \(n\)부터 대입해 어디서 역전이 일어나는지 본다. (b) 역전 이후를 계속 계산해 다시 뒤집히지 않는 지점을 찾는다. 증명이 아니라 실험이 요구된다.

풀이. (a) 실험: \(n = 1\)이면 \(2 \ge 1\) ✓, \(n = 2\)이면 \(4 \ge 4\) ✓, \(n = 3\)이면 \(2^3 = 8\)이고 \(3^2 = 9\)이므로 \(8 \ge 9\)가 아니다 ✗. 반증. 반례로 \(n = 3\)을 제시한다. (검증 1) \(3 \in \mathbb{N}\)이다 ✓. (검증 2) \(2^3 = 8\)이고 \(3^2 = 9\)이므로 \(8 < 9\), 곧 \(2^n \ge n^2\)을 위배한다 ✗. 따라서 명제는 거짓이다. \(\blacksquare\)

(b) 실험을 이어 간다.

\(n\)	1	2	3	4	5	6	7
\(2^n\)	2	4	8	16	32	64	128
\(n^2\)	1	4	9	16	25	36	49
\(2^n \ge n^2\)	✓	✓	✗	✓	✓	✓	✓

\(n = 3\) 하나에서만 실패하고 \(n = 4\)부터는 격차가 계속 벌어진다. 따라서 제안하는 수정은 “\(n \ge 4\)인 모든 자연수 \(n\)에 대해 \(2^n \ge n^2\)이다”이며, \(n = 4\)에서 등호로 다시 시작하는 것이 경계 선택의 근거다. (증명에는 귀납법이 필요하므로 지금은 증명하지 않는다 — 31주차에서 기법을 배우고 32주차 예제 2.1에서 증명한다. 기초 사례가 왜 \(n = 4\)인지는 이 실험이 이미 정해 놓았다.)

복기. 반례는 명제를 죽이는 데서 끝나지 않고 올바른 경계를 알려 준다. 예제 2.3의 \(3^n > n^3\)에서도 반례 \(n = 3\)이 곧 “\(n \ge 4\)”라는 수정안의 근거였다. 반증 뒤에 “그러면 어디까지가 참인가”를 묻는 것이 다음 정리를 만드는 방법이다.

문제 9#

접근. 뺄셈에는 결합법칙이 없다. 수에서 먼저 확인하면 \(5 - (3 - 2) = 4\)이지만 \((5 - 3) - 2 = 0\)이다. 집합에서 같은 붕괴를 일으키려면 \(C\)의 원소가 \(A\)에도 있어야 한다 — 좌변에서는 \(C\)가 두 번 빠지면서 되살아나고 우변에서는 그냥 빠지기 때문이다. 체크리스트 ⑥대로 원소 하나짜리 집합에서 시도한다.

풀이. 반례로 \(A = \{1\}\), \(B = \emptyset\), \(C = \{1\}\)을 제시한다. (검증 1) \(A, B, C\)는 모두 집합이므로 “임의의 집합”이라는 가정을 만족한다 ✓. (검증 2) 좌변은 \(B - C = \emptyset\)이므로 \(A - (B - C) = \{1\} - \emptyset = \{1\}\)이고, 우변은 \(A - B = \{1\}\)이므로 \((A - B) - C = \{1\} - \{1\} = \emptyset\)이다. 원소 \(1\)이 좌변에는 속하고 우변에는 속하지 않으므로 \(\{1\} \neq \emptyset\)이고, 등식이 성립하지 않는다 ✗. 따라서 명제는 거짓이다. \(\blacksquare\)

복기. 집합 상등의 반증에서 검증 2를 닫는 방법은 27주차 §1.7(확인 8)의 완결 조건을 한 걸음 조인 것이다 — 양변을 계산해 다르다고 적는 데서 멈추지 말고 한쪽에만 있는 원소를 지목한다. 여기서는 \(1\)이 그 원소이고, 준비 운동 3번의 유형 1이 정확히 이 줄을 빠뜨린 답안이었다. (27주차 문제 14는 같은 좌변을 \((A-B) \cup C\)와 비교하는데 그 명제도 거짓이며, 참인 변형은 \(A - (B - C) = (A - B) \cup (A \cap C)\)이다 — 우변의 모양에 따라 진위가 갈린다.)

문제 10#

접근. 존재 명제이므로 부정은 “모든 정수 \(n\)에 대해 \(4 \nmid (n^2 + 2)\)”라는 전칭 명제다. \(n\)을 짝수와 홀수로 나누어 \(n^2 + 2\)를 각각 계산하면 두 경우 모두 4의 배수가 될 수 없음이 드러난다. 17주차 문제 17이 이미 증명한 내용이므로 인용만으로도 끝나지만, 여기서는 유도를 전부 적는다.

풀이. 부정 — “모든 정수 \(n\)에 대해 \(4 \nmid (n^2 + 2)\)이다” — 를 증명한다. \(n\)을 임의의 정수라 하자. 모든 정수는 짝수이거나 홀수이므로 두 경우로 나눈다.

경우 1: \(n\)이 짝수. \(n = 2k\)인 정수 \(k\)가 존재한다(정의 1.1). 그러면 \(n^2 + 2 = 4k^2 + 2\)이다. 만약 \(4 \mid (n^2+2)\)라면 \(4k^2 + 2 = 4m\)인 정수 \(m\)이 존재하므로 \(2 = 4(m - k^2)\), 곧 \(1 = 2(m - k^2)\)이다. \(m - k^2\)은 정수이므로 우변은 짝수인데 좌변 \(1\)은 홀수이므로 모순이다.

경우 2: \(n\)이 홀수. \(n = 2k + 1\)인 정수 \(k\)가 존재한다(정의 1.2). 그러면

\[ n^2 + 2 = (2k+1)^2 + 2 = 4k^2 + 4k + 3 = 4(k^2 + k) + 3 \]

이다. 만약 \(4 \mid (n^2+2)\)라면 \(4(k^2+k) + 3 = 4m\)인 정수 \(m\)이 존재하므로 \(3 = 4t\) (단 \(t = m - k^2 - k\)는 정수)이다. 그런데 \(t \le 0\)이면 \(4t \le 0 < 3\)이고 \(t \ge 1\)이면 \(4t \ge 4 > 3\)이므로 그런 정수 \(t\)는 없다. 모순이다.

두 경우가 모든 정수를 빠짐없이 덮고 각 경우에서 \(4 \nmid (n^2+2)\)이므로, 모든 정수 \(n\)에 대해 \(4 \nmid (n^2 + 2)\)이다. 따라서 원래 명제는 거짓이다. \(\blacksquare\) (검산: \(n = 0, 1, 2, 3\)에서 \(n^2+2\)는 각각 \(2, 3, 6, 11\)로 어느 것도 4의 배수가 아니다 ✓.)

복기. “불가능성 정리”와 “존재 명제의 반증”은 같은 내용의 두 포장이다. 17주차에서 정리로 증명한 것을 이번 주에는 존재 명제의 반증으로 읽었다. 새 문제를 만나면 “이것의 부정이 이미 증명된 정리 아닌가”를 먼저 묻는 것이 다음 주 시험의 시간을 줄인다.

문제 11#

접근. 존재 명제이므로 부정은 “모든 유리수 \(r\)에 대해 \(r^2 \neq 3\)”이고, 이것은 “\(\sqrt3\)은 무리수”(21주차 문제 7)를 다시 읽은 것이다. 다만 \(r\)이 음수인 경우도 같은 정리로 덮이는지 한 줄로 확인해야 완결된다.

풀이. 부정 — “모든 유리수 \(r\)에 대해 \(r^2 \neq 3\)이다” — 를 증명한다. 귀류법으로, \(r^2 = 3\)인 유리수 \(r\)이 존재한다고 가정하자. \(r^2 = 3 > 0\)이므로 \(r \neq 0\)이고, 따라서 \(r > 0\)이거나 \(r < 0\)이다. \(r > 0\)인 경우, 양수 중 제곱해서 3이 되는 수는 \(\sqrt3\)뿐이므로 \(r = \sqrt3\)이고 \(\sqrt3\)이 유리수가 된다. \(r < 0\)인 경우, \(-r > 0\)이고 \((-r)^2 = r^2 = 3\)이므로 앞의 논의에 의해 \(-r = \sqrt3\)이다. 유리수의 부호를 바꾼 것도 유리수이므로(\(r = \frac{p}{q}\)이면 \(-r = \frac{-p}{q}\)) 이 경우에도 \(\sqrt3\)이 유리수가 된다. 어느 경우든 \(\sqrt3\)이 유리수라는 결론이 나오는데, 21주차 문제 7에서 \(\sqrt3\)이 무리수임을 증명했으므로 모순이다. 따라서 그런 유리수는 존재하지 않으며, 원래 명제는 거짓이다. \(\blacksquare\)

복기. “무리수이다”라는 정리 자체가 존재 명제의 반증이었다 — “\(\sqrt3\)은 유리수가 아니다”는 “\(\sqrt3 = \frac{p}{q}\)인 정수 \(p, q\)가 존재한다”의 부정이기 때문이다. 음수 경우를 따로 처리한 한 줄이 이 풀이를 완결시킨 부분이며, 그 부호 처리를 빠뜨린 답안이 흔하다.

문제 12#

접근. \(\frac{n^2+n}{2} = \frac{n(n+1)}{2}\)이 항상 정수라는 것은 참이다 (1주차 문제 16). 명제는 그것을 “항상 짝수”로 한 칸 과장했다. 과장이 무너지는 곳을 찾으려면 가장 작은 \(n\)부터 값을 적어 본다(체크리스트 ①).

풀이. 먼저 값을 몇 개 적어 본다.

\(n\)	1	2	3	4	5
\(\dfrac{n^2+n}{2}\)	1	3	6	10	15

반증. 반례로 \(n = 1\)을 제시한다. (검증 1) \(1 \in \mathbb{Z}\)이다 ✓. (검증 2) \(\dfrac{1^2 + 1}{2} = 1\)이고 \(1 = 2 \times 0 + 1\)이므로 \(1\)은 홀수다. 짝수이면서 홀수인 정수는 없으므로(22주차 문제 5, 근거 ④) \(1\)은 짝수가 아니다 ✗. 따라서 명제는 거짓이다. \(\blacksquare\) (\(n = 2\)에서도 값이 \(3\)으로 홀수이므로 또 하나의 반례다.)

복기. 참인 정리를 한 칸 과장하면 거짓이 된다. “항상 정수”(참)와 “항상 짝수”(거짓) 사이의 간격이 그 한 칸이며, 수색의 첫 수는 여기서도 “참인 것과 나란히 놓기”였다.

문제 13#

접근. 체크리스트 ⑤ — 소수 중 유일한 짝수 \(2\)가 끼는 순간을 본다. 두 번째 물음은 문제 4와 짝을 이룬다: 참인 정리 위에 거짓인 전제를 얹으면 결론이 무너진다.

풀이. 반례로 소수 쌍 \((2, 3)\)을 제시한다. (검증 1) \(2\)와 \(3\)은 소수이다: \(2\)의 양의 약수는 \(1, 2\)뿐이고 \(3\)의 양의 약수는 \(1, 3\)뿐이다 ✓. (검증 2) \(2 + 3 = 5\)이고 \(5 = 2 \times 2 + 1\)이므로 \(5\)는 홀수다. 짝수이면서 홀수인 정수는 없으므로(22주차 문제 5, 근거 ④) 합은 짝수가 아니다 ✗. 따라서 명제는 거짓이다. \(\blacksquare\)

그럴듯해 보였던 이유: 참인 정리 “홀수 + 홀수 = 짝수”(1주차 예제 2.3)가 있고 대부분의 소수가 홀수라서 그 정리가 소수 전체에 적용되는 것처럼 보이지만, “모든 소수는 홀수”라는 전제가 이미 거짓이므로(문제 4) 그 위에 지은 일반화도 무너진다.

복기. 거짓 명제가 그럴듯한 이유를 말로 적어 두면 수색이 빨라진다. “어떤 참인 정리를 닮았는가”를 찾으면 그 정리가 요구하는 조건이 빠진 자리가 곧 반례가 나오는 자리이기 때문이다 — 여기서는 “홀수”라는 조건이 빠진 소수 \(2\)였다.

문제 14#

접근. 판별이 먼저다. \(n = 1, 2, 3\)에서 \(n^2 + n\)은 각각 \(2, 6, 12\)로 전부 짝수이고 체크리스트 앞쪽에서 반례가 나오지 않는다. 참 같으므로 증명 모드로 전환한다. \(n^2 + n = n(n+1)\)은 연속한 두 정수의 곱이므로 1주차 문제 16이 그대로 적용된다.

풀이. 참이다 — 증명한다. \(n\)을 임의의 자연수라 하자. 공통인수로 묶으면 \(n^2 + n = n(n+1)\)이다. 모든 정수는 짝수이거나 홀수이므로 두 경우로 나눈다.

경우 1: \(n\)이 짝수. \(n = 2k\)인 정수 \(k\)가 존재하므로 \(n^2 + n = n(n+1) = 2k(n+1) = 2\big(k(n+1)\big)\)이고, \(k(n+1)\)은 정수의 곱이므로 정수다(근거 ②). 따라서 \(n^2+n\)은 짝수다.

경우 2: \(n\)이 홀수. \(n = 2k + 1\)인 정수 \(k\)가 존재하므로 \(n + 1 = 2(k+1)\)이고, \(n^2 + n = n(n+1) = n \cdot 2(k+1) = 2\big(n(k+1)\big)\)이다. \(n(k+1)\)은 정수의 곱이므로 정수다. 따라서 \(n^2+n\)은 짝수다.

두 경우가 모든 자연수를 빠짐없이 덮고 각 경우에서 \(n^2+n\)이 짝수이므로, 모든 자연수 \(n\)에 대해 \(n^2 + n\)은 짝수다. \(\blacksquare\) (검산: \(n = 5\)이면 \(30 = 2 \times 15\) ✓.)

복기. “판별 후 실행” 문항에서 반증만 기대하지 않는다. 반증 주간이라는 맥락이 판별을 왜곡할 수 있지만 명제의 진위는 맥락과 무관하다. 반례가 나오지 않으면 지체 없이 증명 모드로 넘어가는 이 전환이 다음 주 시험의 본체이며, 이 결과가 문제 12에서 과장된 그 정리이기도 하다.

문제 15#

접근. 수학사 사례를 정의 29.2의 서식에 대입해 읽는 문항이다. 명제 \(S\)는 “모든 \(n\)에 대해 \(F_n\)은 소수”이고 반례는 \(n = 5\)이므로, 두 검증이 각각 무엇에 해당하는지 지목하면 (a)가 끝난다. (b)는 1주차 문제 20의 교훈에 이 사례가 무엇을 더 얹는지를 묻는다 — 규모와 권위의 문제다.

풀이. (a) 검증 2에 해당하는 것은 인수분해 \(F_5 = 641 \times 6{,}700{,}417\)의 제시다. 이것이 “\(F_5\)는 소수가 아니다”의 증명이며, \(1\)과 \(F_5\)가 아닌 양의 약수 \(641\)을 실제로 제시한 것이다(확인 11와 같은 요구). 검증 1에 해당하는 것은 \(n = 5\)가 무대 안의 값이라는 확인, 곧 \(F_5 = 2^{2^5} + 1 = 2^{32} + 1 = 4{,}294{,}967{,}297\) 이라는 대입 확인이다. (그 곱셈이 실제로 맞는다는 것은 지금은 인정하고 쓴다.)

(b) (예시 답안) 다섯 번의 성공이, 그것도 \(65{,}537\)까지 손으로 검증한 성공이 여섯 번째를 조금도 보장하지 않았으며, 반례는 열 자리 수라는 손 계산의 범위 밖에 있었다. 당대 최고 수준의 수학자가 세운 추측도 반례 하나에 무너진다는 점에서, 명제를 살리는 것은 제안자의 권위가 아니라 증명뿐이다.

복기. 체크리스트 ⑦(전수 대입)이 소득 없이 끝났을 때의 다음 수가 이 사례에 있다 — 오일러는 값을 계속 키우는 대신 \(F_5\)의 약수가 가질 수 있는 꼴을 먼저 좁혀 후보를 줄였다(그 사실은 이 교재의 범위 밖이므로 지금은 읽기만 한다). 예제 2.1의 1단계에서 전수 대입을 접고 식의 구조를 본 것과 같은 전환이다.

문제 16#

접근. 존재 명제이므로 부정은 전칭 명제 “모든 정수 \(x, y\)에 대해 \(6x + 9y \neq 1\)”이다. 좌변이 항상 갖는 성질을 찾는 것이 일반 논증의 길이고, 계수 \(6\)과 \(9\)의 공통인수 \(3\)이 그 성질을 준다. 훈련 3이 계수만 다른 같은 구조였다.

풀이. 부정 — “모든 정수 \(x, y\)에 대해 \(6x + 9y \neq 1\)이다” — 를 증명한다. \(x, y\)를 임의의 정수라 하자. 공통인수로 묶으면

\[ 6x + 9y = 3(2x + 3y) \]

이고 \(2x + 3y\)는 정수의 곱과 합이므로 정수다(근거 ②). 따라서 정의 2.1에 의해 \(3 \mid (6x + 9y)\)이다. 한편 \(3 \nmid 1\)이다: \(1 = 3m\)인 정수 \(m\)이 있다면 \(m \le 0\)일 때 \(3m \le 0 < 1\)이고 \(m \ge 1\)일 때 \(3m \ge 3 > 1\)이므로 그런 \(m\)은 없다. 그러므로 \(6x + 9y = 1\)이면 \(3 \mid 1\)이 되어 모순이고, \(6x + 9y \neq 1\)이다. \(x, y\)는 임의였으므로 모든 정수 쌍에 대해 성립한다. 따라서 원래 명제는 거짓이다. \(\blacksquare\) (검산: \(x = 2\), \(y = -1\)이면 \(3\), \(x = -1\), \(y = 1\)이면 \(3\) — 실제로 3의 배수다 ✓.)

복기. 존재의 반증에서 가장 자주 통하는 수는 “좌변이 항상 갖는 성질”을 찾는 것이고, 여기서는 3의 배수라는 성질이었다. 28주차 문제 14 (\(\{12a + 4b : a, b \in \mathbb{Z}\} = \{4k : k \in \mathbb{Z}\}\))가 계수만 다른 같은 구조다 — 같은 논증을 \(6\)과 \(9\)에 적용하면 \(\{6x + 9y : x, y \in \mathbb{Z}\}\)가 정확히 \(3\)의 배수 전체임을 얻고, \(1\)은 그 밖에 있다.

문제 17#

접근. 표를 만들어 작은 수부터 확인한다. \(n\)을 제곱수 세 개의 합으로 쓰려면 재료가 \(n\) 이하의 제곱수뿐이므로 후보가 유한하고, 따라서 “만들 수 없음”을 전수 조사로 증명할 수 있다 — 반례 검증 안에 존재 명제의 반증이 들어 있는 이중 구조다.

풀이. 작은 수부터 표를 만든다.

\(n\)	1	2	3	4	5	6	7
세 제곱수의 합	\(1+0+0\)	\(1+1+0\)	\(1+1+1\)	\(4+0+0\)	\(4+1+0\)	\(4+1+1\)	?

반증. 반례로 \(n = 7\)을 제시한다. (검증 1) \(7\)은 자연수이다 ✓. (검증 2) \(7\)을 세 제곱수(0 허용)의 합으로 쓸 수 없음을 전수 조사로 보인다. 합에 쓰일 수 있는 제곱수는 \(7\) 이하여야 하므로 \(0, 1, 4\)뿐이다(\(3^2 = 9 > 7\)). 이 셋에서 중복을 허용해 세 개를 고를 때 만들 수 있는 값은, \(4\)를 몇 개 쓰느냐로 나누면 전부 다음과 같다.

\(4\)의 개수	남은 자리에 쓰는 것	만들 수 있는 값
0개	\(0\)과 \(1\) 중 셋	\(0, 1, 2, 3\)
1개	\(0\)과 \(1\) 중 둘	\(4, 5, 6\)
2개	\(0\)과 \(1\) 중 하나	\(8, 9\)
3개	없음	\(12\)

가능한 값은 \(\{0,1,2,3,4,5,6,8,9,12\}\)이고 이 목록에 \(7\)이 없다 ✗. 따라서 명제는 거짓이다. \(\blacksquare\)

복기. 검증 2의 내용이 그 자체로 존재 명제(”\(7 = a^2+b^2+c^2\)인 정수 \(a,b,c\)가 존재한다”)의 반증이었다. 전수 조사가 가능했던 이유는 재료가 \(7\) 이하로 제한되어 후보가 유한했기 때문이며, 후보가 무한하면 이 방법은 통하지 않는다 — 문제 16이 그 경우였고 거기서는 일반 논증을 썼다. (배경으로 \(8k + 7\) 꼴의 자연수는 세 제곱수의 합이 될 수 없다는 르장드르의 세 제곱수 정리가 있다. 증명은 이 교재의 범위 밖이므로 지금은 인정하고 읽는다.)

문제 18#

접근. 문제의 힌트를 먼저 근거로 만든다. 홀수 \(n\)이 두 소수의 합이라면 두 소수가 모두 홀수일 수는 없고(홀수 + 홀수 = 짝수, 1주차 예제 2.3), 짝수인 소수는 \(2\)뿐이다. 그러면 각 \(n\)에서 확인할 것이 “\(n\)이 소수인가”와 “\(n - 2\)가 소수인가” 두 가지로 압축된다.

풀이. 먼저 압축을 정당화한다. 홀수 \(n \ge 3\)이 두 소수의 합 \(p + q\)라 하자. \(p\)와 \(q\)가 모두 홀수이면 \(p + q\)가 짝수가 되어 \(n\)이 홀수라는 것에 어긋나므로 적어도 하나는 짝수이고, 짝수인 소수는 \(2\)뿐이므로 그 하나는 \(2\)이다. 따라서 \(q = n - 2\)가 소수여야 하며, 명제의 조건은 “\(n\)이 소수이거나 \(n - 2\)가 소수”와 같다. 표로 실험한다.

\(n\)	3	5	7	9	11	13	15	17	19	21	23	25	27
\(n\)이 소수	✓	✓	✓	✗	✓	✓	✗	✓	✓	✗	✓	✗	✗
\(n-2\)가 소수	✗	✓	✓	✓	✗	✓	✓	✗	✓	✓	✗	✓	✗
성립	✓	✓	✓	✓	✓	✓	✓	✓	✓	✓	✓	✓	✗

(\(9 = 2+7\), \(15 = 2+13\), \(21 = 2+19\), \(25 = 2+23\)으로 각각 성립한다.)

반증. 반례로 \(n = 27\)을 제시한다. (검증 1) \(27\)은 홀수이고 \(27 \ge 3\)이므로 가정을 만족한다 ✓. (검증 2) \(27\)은 소수가 아니다: \(27 = 3 \times 9\)이므로 \(1\)과 \(27\)이 아닌 양의 약수 \(3\)을 가진다. 또한 두 소수의 합도 아니다: 앞의 압축에 의해 그러려면 \(27 - 2 = 25\)가 소수여야 하는데 \(25 = 5 \times 5\)이므로 소수가 아니다 ✗. 따라서 명제는 거짓이다. \(\blacksquare\)

복기. 수색의 비용을 줄인 것은 표가 아니라 압축이었다. 압축 없이 표를 만들면 각 \(n\)마다 두 소수의 조합을 전부 시험해야 하지만, “하나는 반드시 \(2\)”라는 한 줄이 확인 대상을 두 가지로 줄였다 — 수색 전에 명제를 논리적으로 조이는 것이 전수 조사보다 먼저다. (짝수판인 “\(4\) 이상의 모든 짝수는 두 소수의 합”은 골드바흐 추측이며 증명도 반증도 되지 않았다. 문제 19의 세 상태 중 셋째다.)

문제 19#

접근. 궤적은 1에 도달할 때까지 빠짐없이 적는다. 서술에서 구분해야 할 것은 “명제의 진리값”과 “우리가 아는 상태”다 — 확인 3의 삭제 실험이 이 구분을 다뤘고, 그 구분이 없으면 “아직 모른다”와 “거짓이다”가 뒤섞인다.

풀이. 규칙은 짝수이면 \(2\)로 나누고 홀수이면 \(3\)배 한 뒤 \(1\)을 더하는 것이다.

\(n = 6\): \(6 \to 3 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1\). (\(6\)은 짝수이므로 \(3\), \(3\)은 홀수이므로 \(3 \times 3 + 1 = 10\), \(10 \to 5\), \(5\)는 홀수이므로 \(16\), 이후는 계속 반으로 나눈다.) 여덟 걸음에 도달한다 ✓.

\(n = 7\): \(7 \to 22 \to 11 \to 34 \to 17 \to 52 \to 26 \to 13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1\). (\(3n+1\)을 적용한 곳은 \(7 \to 22\), \(11 \to 34\), \(17 \to 52\), \(13 \to 40\), \(5 \to 16\)이고 나머지는 반으로 나누는 걸음이다.) 열여섯 걸음에 도달한다 ✓. 한때 \(52\)까지 올라갔다 내려오는 것 — 값이 단조롭게 줄지 않는다는 것 — 이 이 추측을 어렵게 만드는 부분이다.

(예시 답안) 명제의 진리값은 참 아니면 거짓 둘 중 하나지만, 우리가 아는 상태는 “증명됨 / 반증됨 / 미해결”의 셋이다. 콜라츠 추측은 매우 큰 범위까지 확인되었으나 그 확인은 예시의 축적일 뿐이어서 증명이 아니고 반례도 없으므로 셋째 상태에 있다 — 검증이 아무리 쌓여도 증명을 대신하지 못한다는 1주차의 결론이 현재 진행 중인 수학에도 그대로 적용된다.

복기. 세 상태의 구분은 정의 29.1의 “증명한다”라는 조각에서 나온다. 반증이 \(\neg S\)의 증명을 요구하기 때문에 “아직 아무 증명도 없음”이라는 셋째 상태가 따로 생긴다. 이 셋에 네 번째 상태(독립 — 주어진 공리계로는 증명도 반증도 불가능함이 증명된 상태)가 더해지는 것은 49주차 문제 19다.

문제 20#

접근. (a) 정의 29.1을 서식과 연결한다. 반증이 \(\neg S\)의 증명이므로 증명에 요구되는 것이 그대로 요구되고, 그 구체적 형태가 검증 두 개다. (b) §1.6의 목록을 베끼는 것이 아니라 이번 주 문제들에서 반례가 실제로 나온 자리를 되짚어 순서를 다시 매긴다.

풀이. (예시 답안)

(a) 반증은 \(\neg S\)라는 명제의 증명이므로, 반례 제시도 “가정 만족”과 “결론 위배”라는 두 검증을 갖춘 완결된 논증이어야 한다. 검증 없이 “반례: \(n = 40\)” 한 줄만 적으면 그 수가 무대 안에 있다는 것도 결론을 위배한다는 것도 확정되지 않으며, 증명에서 계산 없이 “자명하다”라고 적는 것과 같은 미완성이다.

(b) (개인화 예 — §1.6의 번호와는 별개의 우선순위다. 각 항목 옆에 이번 주에 그것이 통한 자리를 적는다)

1순위: \(n = 1\)과 \(x = 0\) 같은 가장 작은 값 — 문제 6(a), 문제 12
2순위: 소수 \(2\) — 문제 4, 문제 13
3순위: \(0 < x < 1\)인 분수 — 훈련 1, 문제 5
4순위: 음수 또는 부호가 반대인 쌍(절댓값\(\cdot\)부등식 명제) — 문제 3, 훈련 2
5순위: 등호가 성립하는 경계, 여유가 좁아지는 지점 — 예제 2.3, 문제 8
6순위: 공집합과 서로 겹치는 한 원소 집합(집합 명제) — 문제 9, 준비 운동 3번
7순위: 표를 만들어 작은 수 전수 대입 — 문제 17, 문제 18
8순위: 그래도 없으면 값이 아니라 식의 구조를 본다 — 예제 2.1, 문제 15

복기. 체크리스트를 남의 목록으로 두지 않고 자기 경험으로 다시 쓰는 것이 이 문항의 목적이다. 다음 주 시험에서 실제로 꺼내 쓸 것은 §1.6의 일곱 항목이 아니라 각 항목 옆에 문제 번호가 붙은 이 개인 목록이며, 8순위가 끝에 오는 이유도 명확하다 — 값을 넣어 보는 수색이 전부 실패했을 때에만 구조를 보는 비싼 수색으로 넘어간다.

다음 주 예고: 6부의 졸업 시험이다. 참\(\cdot\)거짓이 표시되지 않은 명제 20개를 받아 스스로 판별하고 실행한다. 판별에는 이번 주의 왕복 동선(§1.7)을 쓰고, 참이면 23주차 선택 순서도로 기법을 고르며, 거짓이면 이번 주의 완전 서식으로 반증한다. 지금까지 배운 것 전부 — 4대 기법, iff, 존재와 유일, 집합 증명, 그리고 반증 — 가 한 자리에서 요구되는 형식이며, 이것이 표시 없는 명제를 만나는 실전 수학의 기본 모드다.