# 29주차 — 반증: 반례 찾기 (Disproof)

:::{admonition} 이 주의 길잡이
:class: keybox

**핵심 문장**: 반증은 증명의 반대가 아니라 $\neg S$의 증명이다.

**이 주의 위치**: 50주 과정의 29주차. 6부의 마지막 기법이며, 다음 주는 참$\cdot$거짓이 표시되지 않은 명제를 스스로 판별하는 종합 시험이다.

**원서 대응**: BoP(Book of Proof) 9.1–9.3 (Counterexamples / Disproving Existence Statements / Disproof by Contradiction). 원서 없이 읽을 수 있다.
:::

## 이번 주 목표

1. 반증이 곧 부정의 증명임을 정리하고, 명제 유형별 반증 전략을 표 한 장으로 갖춘다.
1. 반례 서술의 완전한 서식(제시 + 가정 검증 + 결론 위배 검증)을 백지에 쓸 수 있다.
1. 존재 명제의 반증이 왜 전칭 증명인지 설명하고, 실제로 수행한다.
1. 반례 수색 체크리스트를 만들고, 수학사의 유명 반례들을 그 서식에 대입해 읽는다.

본문 곳곳의 **확인** 상자는 연필로 먼저 답하는 자리다. 바로 아래의 **답** 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다.

## 준비 운동 (28주차 복습)

1. $\neg(\forall x,\ P(x)) \equiv \underline{\quad}$, $\neg(\exists x,\ P(x)) \equiv \underline{\quad}$ (11주차)
1. 반례가 갖춰야 할 두 조건은 무엇인가. (9주차 문제 20)
1. $\mathcal{P}(A \cup B) = \mathcal{P}(A) \cup \mathcal{P}(B)$의 반례를 재현하시오. (28주차 문제 9)

### 자주 나오는 세 가지 답 — 3번 문항

방금 쓴 답은 대개 다음 세 유형 중 하나다. 셋 다 옳은 부분이 있고, 셋 다 이번 주에 메울 정확한 간격이 있다.

- **유형 1 — 집합만 제시.** "$A = \{1, 2\}$, $B = \{2, 3\}$"이라고 적고 끝낸다.

고른 집합은 정확하다. 빠진 것은 그 집합이 왜 반례인지다 — 두 멱집합을 갈라놓는 원소를 하나 지목하고, 그것이 한쪽에는 있고 다른 쪽에는 없음을 각각 확인해야 "다르다"가 확정된다.

- **유형 2 — 한쪽만 검증.** $\{1, 3\} \subseteq A \cup B$이므로

$\{1,3\} \in \mathcal{P}(A \cup B)$까지 쓰고 멈춘다. 이 계산은 옳다. 남은 것은 반대쪽 확인이다 — $\{1,3\} \nsubseteq A$이고 $\{1,3\} \nsubseteq B$이므로 $\{1,3\} \notin \mathcal{P}(A) \cup \mathcal{P}(B)$라는 줄이 있어야 두 집합의 상등이 무너진다. 검증이 하나만 있으면 아무것도 확정되지 않는다.

- **유형 3 — 크기 비교로 설명.** "합집합의 멱집합이 더 크니까 같을 수 없다"고

적는다. 방향 관찰은 옳다. 빠진 것은 "더 크다"의 근거다 — 27주차 §1.7의 확인 8이 요구한 반례 완결 조건은 양변을 각각 계산해 서로 다름을 명시하는 것이었고, 이번 주는 거기서 한 걸음 더 조인다 — 다름을 주장하는 쪽이 한쪽에만 있는 원소를 실제로 지목해야 한다. 이번 주 전체가 이 요구를 서식으로 굳히는 작업이다.

## 개념 — 반증의 정체와 반례의 서식

### 1 증명에 실패하면 거짓인가

지금까지 배운 것은 전부 "참임을 보이는" 도구였다 — 직접 증명(15주차), 대우(19주차), 귀류(21주차), 유도(23주차). 이 도구들로 다음 명제를 밀어붙여 보자.

:::{admonition} 시도 — 직접 증명으로 밀어붙이기
:class: quotebox

명제: 모든 실수 $x$에 대해 $x^2 \ge x$이다.

"$x$를 임의의 실수라 하자. 보일 것은 $x^2 - x \ge 0$, 곧 $x(x - 1) \ge 0$이다.

두 인수의 부호가 같으면 곱은 0 이상이므로 $x \ge 1$이면 성립하고 $x \le 0$이어도

성립한다. 남은 것은 $0 < x < 1$인 경우인데 … "
:::

여기서 멈춘다. $0 < x < 1$이면 $x > 0$이고 $x - 1 < 0$이므로 곱 $x(x-1)$은 음수다 — 증명이 안 되는 정도가 아니라 목표와 반대 방향의 부등식이 나온다. 대우로 시작하든 귀류로 시작하든 같은 구간에서 같은 것이 나오므로, 기법을 바꾸는 것으로는 이 벽이 넘어가지 않는다.

그렇다면 "증명에 실패했으니 거짓이다"라고 적어도 되는가. 안 된다. 실패는 명제의 상태가 아니라 시도한 사람의 상태다. 문제 19의 콜라츠 추측은 오랫동안 아무도 증명하지 못했지만 거짓으로 확정된 것은 아니다 — 반례도 없기 때문이다. 거짓임을 **주장**하려면 그 주장 자체를 증명해야 한다.

:::{container} quotebox
**확인 1.** 위 시도가 막힌 구간 $0 < x < 1$에서 수 하나를 골라 $x^2$과 $x$를

실제로 계산해 보자. 그 계산 한 줄로 무엇이 확정되는가.
:::

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

$x = \frac12$이면 $x^2 = \frac14$이고 $\frac14 < \frac12$이다. 이 한 줄로

"모든 실수 $x$에 대해 $x^2 \ge x$"는 **거짓임이 확정**된다 — 짐작이 아니라

확정이다. "모든"이라고 주장한 명제는 어긋나는 사례 하나로 무너지기

때문이다(10주차 비대칭 표). 그 사례가 사는 곳을 알려 준 것이 다름 아닌

증명 시도가 막힌 구간이었다는 점은 §1.7에서 정식 동선이 된다.
:::

### 2 거짓의 확정은 무엇의 증명인가 — 표를 채워 보기

$x^2 \ge x$에서 한 일을 다른 명제들에도 적용해 보자. 각 행에서 $S$의 부정을 11주차 부정 규칙으로 만들고, 그 부정을 증명하려면 무엇을 해야 하는지 적는다.

| **반증할 명제 $S$** | **$\neg S$ (11주차 부정 규칙)** | **$\neg S$를 증명하려면** |
|---|---|---|
| 모든 실수 $x$에 대해 $x^2 \ge x$ | $x^2 < x$인 실수 $x$가 존재한다 | 그런 $x$ 하나를 제시하고 조건을 검증한다 |
| 모든 소수는 홀수이다 | $\underline{\quad(1)\quad}$ | $\underline{\quad(2)\quad}$ |
| $4 \mid (n^2 + 2)$인 정수 $n$이 존재한다 | $\underline{\quad(3)\quad}$ | $\underline{\quad(4)\quad}$ |

:::{container} quotebox
**확인 2.** 빈칸 (1)~(4)를 채우고, 세 행의 셋째 열이 공통으로 하는 일을

한 문장으로 적어 보자.
:::

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

(1) 홀수가 아닌 소수가 존재한다. (2) 그런 소수 하나를 제시하고 "소수임"과

"홀수가 아님"을 각각 검증한다. (3) 모든 정수 $n$에 대해 $4 \nmid (n^2 + 2)$이다

($\nmid$는 "나누지 않는다"로 읽는다 — 2주차 정의 2.1). (4) 모든 정수를 한 번에

처리하는 일반 논증을 쓴다 — 사례 하나로는 끝나지 않는다.

공통으로 하는 일은 **$\neg S$를 증명한다**이다. 행마다 달라지는 것은

$\neg S$의 모양뿐이고, 그 모양이 전략을 정한다.
:::

이 관찰에 이름을 붙인다. 식 자체에 새로운 것은 없다 — 방금 표의 셋째 열에서 한 일을 문장으로 굳혔을 뿐이다.

### 정의 29.1 — 반증 (disproof) [백지 암기 대상]

:::{container} quotebox
명제 $S$를 **반증한다**는 것은 $\neg S$를 증명한다는 뜻이다.

반증이 완료되면 $S$는 거짓임이 확정된다.
:::

기호 $\neg S$는 "$S$의 부정" 또는 "$S$가 아니다"로 읽는다(11주차). 읽는 법까지가 정의다.

### 3 정의 29.1 해부 — 조각마다 하는 일

| **조각** | **하는 일** | **증명에서의 역할** |
|---|---|---|
| "$\neg S$를" | 대상의 교체 | 다루는 명제가 $S$가 아니라 $\neg S$임을 못 박는다 — 부정을 먼저 정확히 만들어야 한다(11주차) |
| "증명한다" | 요구 수준의 선언 | 서식$\cdot$근거$\cdot$채점 기준이 지금까지의 증명과 전부 같다 — 반증에만 적용되는 느슨한 규칙은 없다 |

**조각 삭제 실험 — 한 번에 한 조각만 건드린다.** 판본 A는 첫째 조각만 지워 "반증한다 = $S$를 증명한다"로 바꾼 것이고, 판본 B는 둘째 조각만 바꿔 "반증한다 = $\neg S$의 증명에 실패한다"로 만든 것이다.

:::{container} quotebox
**확인 3.** 두 판본에서 각각 무엇이 무너지는가.

(가) 판본 A에서 이미 증명한 참인 명제 하나를 골라 "반증되었다"고 말해 보자.

(나) 판본 B에 콜라츠 추측(문제 19)을 넣어 보자.
:::

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

(가) 판본 A에서는 "$S$를 반증한다"와 "$S$를 증명한다"가 같은 말이 되므로,

"모든 자연수 $n$에 대해 $n^2 + n$은 짝수"(문제 14)를 증명하고 나면 같은

명제를 반증했다고도 말하게 된다. $S$와 $\neg S$가 구별되지 않으면 참과

거짓도 구별되지 않는다 — 첫째 조각이 대상을 **$\neg S$라는 명제**로 못 박아

이 붕괴를 막는다.

(나) 콜라츠 추측은 아무도 $\neg S$를 증명하지 못했으므로 판본 B에서는 이미

반증된 것, 곧 거짓으로 확정된 것이 된다. 그러나 반례도 없다.

"아직 모른다"와 "거짓임을 안다"가 구별되지 않는 정의는 아무것도 구별하지

못한다 — 둘째 조각의 "증명한다"가 이 붕괴를 막는다. 나의 실패는 명제가

아니다. 세 상태의 구분은 문제 19에서 정리한다.
:::

### 4 유형별 반증 전략 — $\neg S$의 모양이 전략을 정한다

할 일은 하나($\neg S$의 증명)지만 $\neg S$의 모양은 $S$의 모양에 따라 갈린다. 11주차 부정 규칙을 그대로 적용한 결과가 다음 표다.

| **반증할 명제 $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$귀류) |

둘째 행에서 화살표가 $\land$로 바뀐 것은 9주차의 동치 $\neg(P \Rightarrow Q) \equiv P \land \neg Q$ 때문이다. 부정 뒤에 조건문은 남지 않는다 — 그래서 검증이 **두 개**가 된다. 이 표가 10주차 비대칭 표의 완성형이다: $\forall$의 반증은 싸고(하나면 된다), $\exists$의 반증은 비싸다(전부 처리해야 한다).

:::{container} quotebox
**확인 4.** 다음 두 명제는 각각 표의 어느 행이며, 반증하려면 무엇을 제출해야 하는가.

(가) "$r^2 = 3$인 유리수 $r$이 존재한다"  (나) "모든 소수 $p$에 대해 $2^p - 1$은 소수이다"
:::

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

(가) 셋째 행($\exists$). $\neg S$가 "모든 유리수 $r$에 대해 $r^2 \neq 3$"이므로

전칭 증명을 제출한다 — 유리수를 몇 개 시험해 보는 것으로는 끝나지 않는다(문제 11).

(나) 둘째 행($\forall(P \Rightarrow Q)$). $\neg S$가 "소수이면서 $2^p - 1$이

소수가 아닌 $p$가 존재한다"이므로 그런 $p$ 하나와 검증 두 개를 제출한다(문제 7).
:::

### 정의 29.2 — 반례 (counterexample)와 반례 서술의 서식 [백지 암기 대상]

:::{container} quotebox
명제 "$\forall x \in U,\ (P(x) \Rightarrow Q(x))$"에 대해, $U$의 원소 $c$가

**반례**라는 것은 $P(c)$가 참이고 $Q(c)$가 거짓이라는 뜻이다.

("$\forall x \in U,\ Q(x)$" 꼴에서는 $P(c)$ 자리에 "$c \in U$"가 온다.)

**반증.** 반례로 $x = c$를 제시한다.

(검증 1) $c$는 가정 $P$를 만족한다: … ✓

(검증 2) $c$는 결론 $Q$를 위배한다: … ✗

따라서 $S$는 거짓이다. $\blacksquare$
:::

✓는 "성립함이 확인되었다", ✗는 "성립하지 않음이 확인되었다"로 읽는 표시다. 표시만으로는 근거가 되지 않으므로 각 줄의 "…" 자리에 실제 계산이나 인용이 들어가야 한다.

### 5 정의 29.2 해부 — 검증 두 개가 본체다

| **조각** | **하는 일** | **판정에서의 역할** |
|---|---|---|
| "$U$의 원소 $c$" | 무대의 확인 | 명제가 주장하는 범위 안에서 골랐음을 보증한다 |
| "$P(c)$가 참" | 검증 1 | $\neg(P \Rightarrow Q) \equiv P \land \neg Q$의 왼쪽 항 |
| "$Q(c)$가 거짓" | 검증 2 | 같은 동치의 오른쪽 항 — 여기가 명제를 무너뜨리는 자리 |
| "하나" (수량) | 요구량의 한정 | $\exists$의 증인이므로 하나면 충분하다 |

**조각 삭제 실험.** 명제 "모든 자연수 $n$에 대해 $2^n \ge n^2$이다"(문제 8)로 두 검증을 하나씩 지워 본다. 검증 1을 빼면 "$n = 2.5$가 반례다"가 통과한다 — $2^{2.5} \approx 5.66 < 6.25 = 2.5^2$으로 결론은 확실히 위배되지만 $2.5$는 자연수가 아니므로 명제가 애초에 주장한 적이 없는 값이다. 검증 2를 빼면 "$n = 5$가 반례다"가 통과한다 — $5$는 자연수이지만 $2^5 = 32 \ge 25 = 5^2$이므로 결론을 위배하지 않는다. 앞의 조각이 없으면 무대 밖의 수가, 뒤의 조각이 없으면 무대 안의 아무 원소나 반례가 된다.

:::{container} quotebox
**확인 5.** 어떤 답안에 "반례: $n = 40$"이라고만 적혀 있다. 정의 29.2의 어느

조각이 빠져 있으며, 이 답안이 확정한 것은 무엇인가.
:::

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

검증 1과 검증 2가 둘 다 빠졌고, 확정한 것은 아무것도 없다 — 수 하나를

적었을 뿐 그 수가 무대 안에 있다는 것도, 결론을 위배한다는 것도 보이지

않았다. 증명에서 계산 없이 "자명하다"라고 적은 것과 같은 미완성이다.

1주차 문제 18에서 $f(40) = 1681 = 41^2$까지 계산해 보인 것이 검증 2였고,

$40$이 자연수라는 한 줄이 검증 1이었다.
:::

### 6 반례 수색 체크리스트 — 어디를 먼저 뒤지는가

반례가 있다는 것을 알아도 어디를 뒤질지는 별개의 문제다. 다음은 수색 순서이며 근거가 아니라 **탐색 도구**다 — 답안에 "체크리스트 ③에 의해"라고 적을 수는 없고, 찾아낸 수를 정의 29.2의 서식으로 검증해야 한다.

- ① $0$, $1$, $2$ — 특수하게 작은 수
- ② 음수
- ③ 분수, 특히 $0 < x < 1$ (제곱하면 작아지는 구간)
- ④ 경계값 — 등호가 성립하는 지점, 또는 여유가 가장 좁아지는 지점
- ⑤ 소수 $2$ — 유일한 짝수 소수
- ⑥ 공집합과 한 원소 집합, 서로 겹치는 작은 집합 (집합 명제)
- ⑦ 작은 수를 표로 만들어 전수 대입

반례는 대개 "명제를 만든 사람이 깜빡한 특수 사례"에 산다. 그래서 수색은 일반적인 값이 아니라 특수한 값에서 시작한다.

:::{container} quotebox
**확인 6.** 명제 "모든 실수 $a, b$에 대해 $(a + b)^2 = a^2 + b^2$이다"를 수색한다.

참인 항등식과 비교하면 이 명제는 무엇을 빠뜨렸고, 반례의 조건은 무엇인가.
:::

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

참인 항등식이 $(a + b)^2 = a^2 + 2ab + b^2$이므로 명제는 $2ab$ 항을 빠뜨렸다.

따라서 $2ab \neq 0$이기만 하면, 곧 $a \neq 0$이고 $b \neq 0$이기만 하면

무엇이든 반례이며 체크리스트 ①의 $a = b = 1$이 가장 짧다(문제 2).

수색에서 가장 강력한 도구는 "참인 것과 나란히 놓고 차이를 보는 것"이다.
:::

### 7 증명 시도와 반례 수색의 왕복

참$\cdot$거짓이 표시되지 않은 상황(다음 주의 시험 형식)에서는 두 모드를 오간다. 22주차 문제 19에서 진단으로 물었던 동선을 여기서 공식화한다.

:::{admonition} 왕복 동선
:class: quotebox

실험(작은 사례 대입) $\to$ 참 같으면 증명 시도 $\to$ 막히면, **막힌 지점이 알려 주는

특수 사례**에서 반례 수색 $\to$ 반례가 나오지 않으면 그 관찰을 들고 다시 증명 시도 $\to$ …
:::

§1.1이 이 동선의 한 바퀴였다. 직접 증명이 $0 < x < 1$에서 막혔고 정확히 그 구간에서 반례가 나왔다. 이유는 단순하다 — 명제가 참이 아니라면 증명이 막히는 자리가 곧 명제가 깨지는 자리다.

:::{container} quotebox
**확인 7.** 명제 "모든 자연수 $n$에 대해 $3^n > n^3$이다"를 $n = 1, 2$에서

실험하면 $3 > 1$, $9 > 8$로 성립한다. 둘 중 수색 신호가 되는 것은 어느

쪽이고 왜인가.
:::

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

$n = 2$ 쪽이다. $n = 1$에서는 여유가 $3 - 1 = 2$이지만 $n = 2$에서는

$9 - 8 = 1$로 좁아졌다 — 여유가 좁아지는 방향으로 한 걸음 더 가면 뒤집힐

수 있다. 체크리스트 ④의 자리이며, 실제로 $n = 3$에서 $27 = 27$로 등호가

되어 $>$가 깨진다(예제 2.3).
:::

### 8 근거 목록 갱신 — 칸은 그대로 네 개

반증이 증명의 일종이므로 근거 목록도 그대로 쓴다. 칸이 늘어날 이유가 없다.

| **근거** | **내용** | **이번 주에는 이렇게 쓴다** |
|---|---|---|
| ① 정의 | 기존 정의들 + **정의 29.1(반증)$\cdot$정의 29.2(반례)** | "$S$를 반증한다"를 "$\neg S$를 증명한다"로 번역하고, 검증 두 개를 요구한다 |
| ② 닫힘성 | 정수의 합$\cdot$차$\cdot$곱은 정수 | 반례 검증과 전칭 증명의 계산에서 그대로 쓴다 (문제 16) |
| ③ 등식$\cdot$부등식의 성질 | 대입 / 전개 / 묶기 / 양변 연산 ((W2)(W3), 16주차) | 검증 2의 계산과 예제 2.2의 부등식 조작 |
| ④ 이미 증명한 명제 | 11주차 부정 규칙, 9주차 동치 $\neg(P{\Rightarrow}Q) \equiv P \land \neg Q$, 10주차 비대칭 표, 22주차 문제 5(짝수이면서 홀수인 정수는 없다), 1~28주차의 결과 | 존재 명제의 반증을 이미 증명된 불가능성 정리의 인용으로 끝낸다 (문제 10$\cdot$11) |

체크리스트(§1.6)는 목록에 없다. 그것은 반례를 **찾는** 도구이고, 찾은 뒤에는 정의 29.2의 검증으로 갈아입어야 근거가 된다.

:::{container} quotebox
**확인 8.** 어떤 답안에 다음 세 문장이 나왔다. 각각 허용되는가.

허용된다면 몇 번 근거인가.

(가) "여러 값을 넣어 보니 성립하지 않는 경우가 많으므로 거짓이다"

(나) "$n = 11$이면 $n^2 - n + 11 = 121 = 11 \times 11$이므로 소수가 아니다"

(다) "$4 \mid (n^2 + 2)$인 정수는 없다 — 17주차 문제 17에서 증명했다"
:::

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

(가) 불허. "많다"는 어느 하나도 확정하지 않는다. 반례는 하나면 충분한데

그 하나를 지목하고 검증하는 대신 인상을 적었다. 같은 내용을

"$x = \frac12$에서 $x^2 = \frac14 < \frac12$"로 적으면 근거가 된다.

(나) 허용 — 계산은 근거 ③, "1과 자신 외의 약수 11을 가지므로 소수가

아니다"라는 판정은 근거 ①이다. 검증 2의 정상적인 한 줄이다(예제 2.1).

(다) 허용 — 근거 ④. 이미 증명된 명제를 부품으로 인용했다.
:::

정의 29.1$\cdot$29.2와 §1.4의 유형 표는 외운다. 통째로만 외우지 말고 §1.3$\cdot$§1.5의 조각별 역할과 함께 외운다. 조각을 잊어도 "부정을 만들면 무엇이 남는가"에서 재구성할 수 있다.