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

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

이 주의 길잡이

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

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

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

이번 주 목표#

  1. 반증이 곧 부정의 증명임을 정리하고, 명제 유형별 반증 전략을 표 한 장으로 갖춘다.

  2. 반례 서술의 완전한 서식(제시 + 가정 검증 + 결론 위배 검증)을 백지에 쓸 수 있다.

  3. 존재 명제의 반증이 왜 전칭 증명인지 설명하고, 실제로 수행한다.

  4. 반례 수색 체크리스트를 만들고, 수학사의 유명 반례들을 그 서식에 대입해 읽는다.

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

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

  1. \(\neg(\forall x,\ P(x)) \equiv \underline{\quad}\), \(\neg(\exists x,\ P(x)) \equiv \underline{\quad}\) (11주차)

  2. 반례가 갖춰야 할 두 조건은 무엇인가. (9주차 문제 20)

  3. \(\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주차). 이 도구들로 다음 명제를 밀어붙여 보자.

시도 — 직접 증명으로 밀어붙이기

명제: 모든 실수 \(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의 콜라츠 추측은 오랫동안 아무도 증명하지 못했지만 거짓으로 확정된 것은 아니다 — 반례도 없기 때문이다. 거짓임을 주장하려면 그 주장 자체를 증명해야 한다.

확인 1. 위 시도가 막힌 구간 \(0 < x < 1\)에서 수 하나를 골라 \(x^2\)과 \(x\)를

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

답

\(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}\)

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

한 문장으로 적어 보자.

답

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

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

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

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

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

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

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

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

명제 \(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\)의 증명에 실패한다”로 만든 것이다.

확인 3. 두 판본에서 각각 무엇이 무너지는가.

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

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

답

(가) 판본 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\)의 반증은 비싸다(전부 처리해야 한다).

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

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

답

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

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

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

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

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

명제 “\(\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\)이므로 결론을 위배하지 않는다. 앞의 조각이 없으면 무대 밖의 수가, 뒤의 조각이 없으면 무대 안의 아무 원소나 반례가 된다.

확인 5. 어떤 답안에 “반례: \(n = 40\)”이라고만 적혀 있다. 정의 29.2의 어느

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

답

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

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

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

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

\(40\)이 자연수라는 한 줄이 검증 1이었다.

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

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

  • ① \(0\), \(1\), \(2\) — 특수하게 작은 수

  • ② 음수

  • ③ 분수, 특히 \(0 < x < 1\) (제곱하면 작아지는 구간)

  • ④ 경계값 — 등호가 성립하는 지점, 또는 여유가 가장 좁아지는 지점

  • ⑤ 소수 \(2\) — 유일한 짝수 소수

  • ⑥ 공집합과 한 원소 집합, 서로 겹치는 작은 집합 (집합 명제)

  • ⑦ 작은 수를 표로 만들어 전수 대입

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

확인 6. 명제 “모든 실수 \(a, b\)에 대해 \((a + b)^2 = a^2 + b^2\)이다”를 수색한다.

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

답

참인 항등식이 \((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에서 진단으로 물었던 동선을 여기서 공식화한다.

왕복 동선

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

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

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

확인 7. 명제 “모든 자연수 \(n\)에 대해 \(3^n > n^3\)이다”를 \(n = 1, 2\)에서

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

쪽이고 왜인가.

답

\(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의 검증으로 갈아입어야 근거가 된다.

확인 8. 어떤 답안에 다음 세 문장이 나왔다. 각각 허용되는가.

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

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

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

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

답

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

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

“\(x = \frac12\)에서 \(x^2 = \frac14 < \frac12\)”로 적으면 근거가 된다.

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

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

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

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