# 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$이 소수가 아님 |

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

행인가.
:::

:::{admonition} 답
:class: quotebox dropdown

(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$의 약수가 되므로 합성수 후보가 된다.

:::{container} quotebox
**확인 10.** $n^2$, $-n$, $11$의 세 항이 모두 11의 배수가 되게 하려면

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

:::{admonition} 답
:class: quotebox dropdown

$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$은 소수가 아니다"도 근거가 필요한 주장이다.

:::{container} quotebox
**확인 11.** "$121$이 소수가 아니다"를 무엇으로 보이는가.

"$\underline{\quad}$이라는 약수를 제시한다" 꼴로 답해 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

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

:::{container} quotebox
**확인 12.** 반례가 $n = 11, 22, 33, \dots$으로 무한히 많다는 사실은 이 반증에

무엇을 더해 주는가.
:::

:::{admonition} 답
:class: quotebox dropdown

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

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

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

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

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

**명제(반증 대상).** "$x^2 < x < x^3$인 실수 $x$가 존재한다."

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

:::{container} quotebox
**확인 13.** 번역표를 채워 보자.

출발점 $\neg S$: $\underline{\qquad}$

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

:::{admonition} 답
:class: quotebox dropdown

$\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}$ |

:::{container} quotebox
**확인 14.** 위 대응표의 빈칸 (1)~(4)를 채워 보자.
:::

:::{admonition} 답
:class: quotebox dropdown

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

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

(3) 전칭 증명.

(4) 제시 + 검증 2개.

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

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

:::{admonition} 이번 주에 확인한 것 — 반증 3단계 틀
:class: quotebox

① 부정 $\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)으로 적는다.

:::{admonition} 이번 주의 채점 기준
:class: quotebox

답이 아니라 **근거**가 점수다. "반례: $n = 3$"은 0점이고,

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

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

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

### 기본 ●○○

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

:::{admonition} 힌트
:class: quotebox dropdown

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

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

이 $\land$의 양쪽이 곧 검증 두 개다.
:::

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

:::{admonition} 힌트
:class: quotebox dropdown

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

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

**3.** 반증하시오: "모든 실수 $x, y$에 대해 $|x + y| = |x| + |y|$이다."

:::{admonition} 힌트
:class: quotebox dropdown

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

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

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

:::{admonition} 힌트
:class: quotebox dropdown

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

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

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

:::{admonition} 힌트
:class: quotebox dropdown

훈련 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) 두 무리수의 차는 항상 무리수이다.

:::{admonition} 힌트
:class: quotebox dropdown

네 항목 모두 체크리스트 앞쪽에서 끝난다. (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$)

:::{admonition} 힌트
:class: quotebox dropdown

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

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

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

:::{admonition} 힌트
:class: quotebox dropdown

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

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

요구되지 않는다.
:::

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

:::{admonition} 힌트
:class: quotebox dropdown

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

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

집합부터 시도한다.
:::

:::{admonition} 존재 명제의 반증 — 이번 주의 새 요구
:class: quotebox

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

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

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

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

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

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

:::{admonition} 힌트
:class: quotebox dropdown

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

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

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

:::{admonition} 힌트
:class: quotebox dropdown

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

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

**12.** 반증하시오: "모든 정수 $n$에 대해 $\dfrac{n^2 + n}{2}$은 짝수이다."

:::{admonition} 힌트
:class: quotebox dropdown

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

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

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

:::{admonition} 힌트
:class: quotebox dropdown

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

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

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

:::{admonition} 힌트
:class: quotebox dropdown

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

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

### 도전 ●●●

:::{admonition} 서술형 문항의 채점 기준
:class: quotebox

문제 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("예시는 증명이 아니다")에 더해 주는 교훈을 두 문장 이내로 쓰시오. (계산 재현은 요구하지 않음)

:::{admonition} 힌트
:class: quotebox dropdown

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

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

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

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

:::{admonition} 힌트
:class: quotebox dropdown

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

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

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

:::{admonition} 힌트
:class: quotebox dropdown

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

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

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

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

:::{admonition} 힌트
:class: quotebox dropdown

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

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

"$n$이 소수인가"와 "$n - 2$가 소수인가" 둘로 줄어든다.
:::

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

:::{admonition} 힌트
:class: quotebox dropdown

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

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

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

:::{admonition} 힌트
:class: quotebox dropdown

(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, 존재와 유일, 집합 증명, 그리고 반증 — 가 한 자리에서 요구되는 형식이며, 이것이 표시 없는 명제를 만나는 실전 수학의 기본 모드다.