C10주차 — Prove or Disprove: 추측의 세계

이 주의 길잡이

핵심 문장: C9주차의 지도는 1단계에서 “이 명제가 참인가”를 묻기는 하지만, 그 물음에 어떻게 답하는지(무엇을 어떤 순서로 대입해 판정하는지)는 정해 두지 않았다. 이번 주에 그 절차를 채운다 — 참\(\cdot\)거짓이 표시되지 않은 명제를 받아 정찰로 방향을 정하고, 참이면 증명하고 거짓이면 반례를 댄다. 정찰은 방향만 정할 뿐 아무것도 확정하지 않는다.

이 주의 위치: 2학기 20주 과정의 C10주차. C5~C8주차가 기법을 하나씩 세웠고 C9주차가 그것을 겉모양 지도로 접었다. 그 지도의 입구에는 “이 명제는 참이다”라는 표시가 늘 붙어 있었고, 이번 주에 그 표시가 떨어진다. 1권 29주차(반증)\(\cdot\)30주차(참\(\cdot\)거짓 판별)에서 동선으로 익힌 것과 S18주차(일반화와 반례 검문)에서 절차로 익힌 것이 여기서 Prove-or-Disprove라는 한 서식으로 합쳐진다. 다음 주 C11주차부터는 다시 참인 정리를 다루지만, 이번 주의 판정 걸음은 이후 모든 주차의 첫 걸음으로 남는다.

원서 대응: Chartrand 8장 (Prove or Disprove). 1일차에 이 장을 통독한 상태로 이 교안에 온다.

이번 주 목표

1. Prove-or-Disprove의 작업 흐름을 네 걸음(정찰 \(\to\) 추측 \(\to\) 결단 \(\to\) 수리)으로 세우고 백지에 재현한다.

2. 정찰이 증명이 아님을 확인하되, 정찰이 어느 쪽을 증명할지 정하는 필수 걸음임을 구분해 설명한다.

3. 반례가 자주 나오는 자리(급소) 목록을 갖추고, 거짓 명제를 반례로 확정한다 (C7주차의 4단 서식).

4. 반례 뒤에 자격을 좁혀 참인 명제로 되물린다 — 가정 강화와 결론 약화의 두 방향 (S18주차).

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

표기 — § 와 난이도 표시

§는 “절”이라고 읽는다. §1.3은 이 주차의 1.3 절을, §6은 6절 전체를 가리킨다.

다른 주차를 가리킬 때는 “C7주차 §1.4”처럼 주차를 앞에 적는다.

연습문제는 기본 1~6번, 표준 7~14번, 도전 15~20번이고, 빈칸 사다리는 훈련 1에서

3으로 갈수록 지지대가 줄어든다.

준비 운동 (C9주차 복습)

지난주까지의 도구를 손에 올려 둔다. 셋 다 이번 주 답안에서 그대로 쓴다.

1. C9주차 §1의 전반부 기법 지도를 재현하시오 — 결론의 겉모양이 기법을 정하는 0~4단계.

2. C7주차 §1.4의 반례 4단 서식(부정 전개 \(\cdot\) 증인 제시 \(\cdot\) 자격 검증 \(\cdot\) 사건 검증)을 쓰시오.

3. S18주차 §1.4의 반례 검문 서식(작은 사례 정찰 \(\cdot\) 경계와 특수 사례 \(\cdot\) 위반 시 되물림)을 쓰시오.

이어서 진단 문제 하나를 풀어 보자. 풀지 못해도 된다 — 이번 주가 무엇을 메우는지 가늠하기 위한 기록이다.

1. (진단) 명제 “모든 양의 정수 \(n\)에 대해 \(n^2 - n + 11\)은 소수이다”를 증명하거나

반증하시오. 참\(\cdot\)거짓은 표시되어 있지 않다.

답을 노트에 적어 둔다. §5의 백지 재현 뒤에 이 기록을 다시 본다.

자주 나오는 세 가지 답

방금 쓴 답은 대개 다음 세 유형 중 하나다. 셋 다 자연스러운 출발점이고, 셋 다 이번 주에 메울 정확한 간격이 있다.

• 유형 1 — 대입 후 “참”. \(n = 1, 2, 3, 4, 5\)에서 \(11, 13, 17, 23, 31\)이 모두

소수임을 확인하고 “참”이라고 적는다. 계산은 한 줄도 틀리지 않았고, 확인한 다섯 값에 대해서는 옳다. 문제는 명제가 모든 양의 정수에 대한 주장이라는 것이다. 이 명제는 실제로 거짓이며 반례는 확인 범위에서 여섯 걸음 밖에 있다 — 확인을 열 값까지 늘려도 통과하고 그 바로 다음 값에서 무너진다(§1.1에서 찾는다). 다섯 번의 확인이 무엇을 보장하고 무엇을 보장하지 않는지가 §1.5다.

• 유형 2 — 증명 시도만 반복. “소수임을 보이려면 약수가 1과 자기 자신뿐임을

보여야 한다”까지 갔으나 다음 줄이 나오지 않아 몇 시간을 쓴다. 방향은 지도가 가르친 그대로이고 잘못이 없다. 빠진 것은 그 앞의 한 걸음이다 — 지도의 1단계가 진리 상태를 묻기는 하지만, 그 물음에 어떤 값을 어떤 순서로 대입해 답하는지는 정해 두지 않았다. 증명이 오래 막히면 도구를 더 찾기 전에 “이 명제가 참이기는 한가”를 실제로 판정해야 하며, §1.2가 그 판정의 절차를 네 걸음으로 채운다.

• 유형 3 — 백지. 참인지 거짓인지 모르므로 증명을 쓸지 반례를 찾을지 정하지

못했고, 그래서 아무것도 적지 못했다. 참\(\cdot\)거짓이 표시되지 않은 명제 앞에서 손을 대는 순서 자체가 규칙으로 정해져 있으며, §1.2가 그 순서를 네 걸음으로 제시한다.

개념 — 판정이 먼저다

1 C9주차의 지도만으로 밀어붙이면 어디서 막히는가

새 걸음을 꺼내기 전에, 지금 가진 도구(C9주차의 기법 지도)만으로 두 명제를 실제로 밀어붙여 본다.

시도 1 — 지도대로 직접 증명

명제: 정수 \(a, b\)에 대해, \(a \mid b\)이고 \(b \mid a\)이면 \(a = b\)이다.

“결론이 등식이므로 지도의 2단계는 직접 증명을 가리킨다.

\(a \mid b\)이고 \(b \mid a\)라 하자. 정의에 의해 \(b = ak\), \(a = bl\)인 정수 \(k, l\)이

존재한다. 대입하면 \(a = (ak)l = a(kl)\)이고, 이항하면 \(a(1 - kl) = 0\)이다.

\(a \neq 0\)인 경우 \(kl = 1\)이므로 \(k = l = 1\) 또는 \(k = l = -1\)이다.

\(k = 1\)이면 \(b = ak = a\)로 목표에 닿는다. 그런데 \(k = -1\)이면 \(b = -a\)이고 … “

여기서 멈춘다. 남은 경우가 목표와 어긋난다.

시도 2 — 준비 운동 4번을 대입으로

명제: 모든 양의 정수 \(n\)에 대해 \(n^2 - n + 11\)은 소수이다.

“\(n = 1\): \(11\). \(n = 2\): \(13\). \(n = 3\): \(17\). \(n = 4\): \(23\). \(n = 5\): \(31\).

\(n = 6\): \(41\). \(n = 7\): \(53\). \(n = 8\): \(67\). \(n = 9\): \(83\). \(n = 10\): \(101\).

열 번 모두 소수다. 따라서 이 명제는 참이다.”

두 시도가 막힌 이유는 서로 다르다.

확인 1. 시도 1과 시도 2에서 잘못된 것은 각각 무엇인가. 한쪽은 “도구가 모자라서”이고 다른 한쪽은 그것이 아니다. 어느 쪽이 어느 쪽인가.

답

어느 쪽도 도구가 모자라서가 아니다.

시도 1은 명제가 거짓이다. \(a = -2\), \(b = 2\)에서 \(2 = (-2)(-1)\)이므로

\(-2 \mid 2\)이고 \(-2 = 2 \cdot (-1)\)이므로 \(2 \mid -2\)인데 \(-2 \neq 2\)이다.

\(k = -1\)인 경우가 목표와 어긋난 것은 계산 실수가 아니라 그 자리에 반례가

살고 있다는 신호다. 아무리 좋은 도구를 가져와도 거짓 명제의 증명은 나오지 않는다.

시도 2는 판정을 대입으로 대신했다. 열 번의 확인은 확인한 열 값에 대해서만

옳고, 나머지 무한히 많은 값에 대해서는 아무것도 말하지 않는다. 실제로 \(n = 11\)에서

\(121 - 11 + 11 = 121 = 11 \cdot 11\)이므로 이 명제도 거짓이다.

이 주 전체의 기준

참\(\cdot\)거짓이 표시되지 않은 명제 앞에서는 두 가지를 순서대로 한다.

① 무엇을 증명할지 먼저 정한다 — 증명할 것인가 반증할 것인가.

② 그 결정은 정찰로 하되, 정찰은 결정만 하고 아무것도 확정하지 않는다.

확정은 걸음 ③의 증명 또는 반례가 한다.

2 사례를 모아 보기 — 참·거짓이 갈린 명제들

참\(\cdot\)거짓이 이미 알려진 명제 몇 개를 놓고, 각각에서 실제로 한 일이 무엇이었는지 적어 보자. 셋 다 이 과정에서 이미 다룬 것이다.

명제	처음에 한 일	그 결과 정한 방향	마지막에 확정한 것
모든 소수는 홀수이다 (1권 29주차)	\(2, 3, 5, 7\)을 훑었다	거짓 쪽	반례 \(2\)와 두 검증
모든 정수 \(n\)에 대해 \(n^2 + n\)은 짝수이다 (S5주차 문제 3)	\(n = 0, 1, 2, -1\)을 대입했다	참 쪽	\(n(n+1)\)의 인수분해로 쓴 증명
모든 양의 정수 \(n\)에 대해 \(n^2 - n + 11\)은 소수이다	\(\underline{\quad(1)\quad}\)	\(\underline{\quad(2)\quad}\)	\(\underline{\quad(3)\quad}\)

확인 2. 표의 (1)(2)(3)을 채워 보자. 그리고 세 행이 공통으로 밟은 순서를 한 문장으로 적어 보자.

답

(1) \(n = 1\)부터 \(10\)까지 대입했고, 이어 상수항 \(11\)에 맞춰 \(n = 11\)을 대입했다.

(2) 거짓 쪽 — \(n = 11\)에서 값이 \(121\)이 되어 소수가 아니었다.

(3) 반례 \(n = 11\)과 두 검증(\(11\)은 양의 정수이고, \(121 = 11 \cdot 11\)은 소수가 아니다).

공통으로 밟은 순서: **먼저 몇 개를 대입해 방향을 정하고, 정한 방향에 맞는 확정

작업(증명 또는 반례)을 했다.** 셋 다 대입 자체를 결론으로 쓰지는 않았다.

이 순서에 정식 이름과 형식을 붙인다. 절차 자체에 새로운 것은 없다 — C7주차의 반례와 C5~C8주차의 증명 앞에 판정 한 걸음을 붙여 묶었을 뿐이다.

백지 암기 대상

Prove-or-Disprove 작업 흐름

참\(\cdot\)거짓이 표시되지 않은 명제 \(S\)를 받으면 네 걸음을 밟는다.

① 정찰 — 작은 사례와 경계 사례(\(0\), \(1\), 음수, 등호가 성립하는 자리, 빈 집합, 소수 \(2\))에서 \(S\)를 시험한다.

② 추측 — 정찰 결과로 “\(S\)는 참으로 보인다” 또는 “\(S\)는 거짓으로 보인다”를 정한다. 이 시점의 라벨은 추측이며 근거가 아니다.

③ 결단 — 참 추측이면 증명한다(C9주차 지도의 2단계로 기법을 고른다). 거짓 추측이면 반례를 댄다(C7주차 §1.4의 4단 서식).

④ 수리 — 거짓으로 확정된 경우, 자격을 좁혀 참이 되는 명제로 되물린다.

1권에서 감각으로 하던 것이 여기서 이름을 얻는 자리. 1권 30주차 §0의 동선 “실험 \(\to\) 판정 \(\to\) 기법 선택 \(\to\) 실행 \(\to\) 검산”으로 손에 익힌 것이, 여기서 걸음 ①②③의 이름과 서식을 얻는다. 그때는 시험을 치르는 요령이었고 지금은 답안에 적는 절차다. S18주차 §1.4의 반례 검문이 걸음 ①에, S18주차 §1.5의 되물림이 걸음 ④에 그대로 들어온다.

표기 — Prove or Disprove

원서의 지시문 “Prove or Disprove”는 “증명하거나 반증하라”로 읽는다. 참\(\cdot\)거짓이

미리 표시되지 않았다는 뜻이며, 답안의 첫 줄은 언제나 판정 선언이다 —

“이 명제는 참이다” 또는 “이 명제는 거짓이다”. 이 교안은 이 지시문을 P-or-D로

줄여 적는다.

표기 — 추측 (conjecture)

정찰을 통과했으나 아직 증명되지 않은 명제에 붙이는 라벨이 추측이다.

“\(S\)를 참으로 추측한다”로 읽는다. 추측은 근거 ④가 아니다 — 뒤 줄에서

“추측에 의해”라고 인용할 수 없고, 걸음 ③이 끝나기 전까지는 아무것도 지탱하지 않는다.

3 절차 해부 — 걸음마다 하는 일

네 걸음은 각각 다른 일을 한다. 하나를 빼면 무엇이 무너지는지가 그 걸음의 존재 이유다.

걸음	하는 일	이 걸음을 빼면 무엇이 무너지는가
① 정찰	명제를 실제 값에서 시험해 방향의 재료를 모은다	증명과 반례 중 무엇을 쓸지 근거 없이 고르게 된다. 거짓 명제를 증명하려 시간을 쓰거나(§1.1 시도 1), 참인 명제에서 반례를 찾느라 시간을 쓴다
② 추측	방향 하나를 골라 선언한다	정찰 결과가 답안에 쌓이기만 하고 다음 줄이 정해지지 않는다. 걸음 ③의 기법 선택은 “참인가 거짓인가”가 정해져야 시작된다
③ 결단	증명 또는 반례로 참\(\cdot\)거짓을 확정한다	정찰 결과가 그대로 결론이 된다 — 이것이 §0 유형 1이고 아래 삭제 실험이다
④ 수리	거짓 명제를 참인 명제로 되물린다	반례를 찾은 뒤 남는 것이 “거짓”이라는 한 낱말뿐이다. 어디까지가 참인지는 여전히 모른다

걸음 삭제 실험 (가) — 걸음 ③을 지우면. 확정 의무를 지우고 정찰 결과를 결론으로 삼는 답안을 검사해 보자.

삭제 실험 — 정찰을 결론으로 삼은 답안

명제: 모든 자연수 \(n\)에 대해 \(n^2 + n + 41\)은 소수이다.

“\(n = 1, \ldots, 10\)에서 \(43, 47, 53, 61, 71, 83, 97, 113, 131, 151\)이 전부

소수이다. 반례가 나오지 않았으므로 이 명제는 참이다.”

확인 3. 위 답안에서 계산이 틀린 줄이 있는가. 없다면 무엇이 잘못되었는가. 그리고 이 답안과 같은 형식을 준비 운동 4번의 명제에 적용하면 무엇이 나오는가.

답

계산은 한 줄도 틀리지 않았다. 열 값에서 실제로 전부 소수다. 잘못된 것은

마지막 한 줄의 자격이다 — “반례가 나오지 않았다”는 “아직 찾지 못했다”일 뿐이고,

이 명제는 \(n = 40\)에서 \(40 \cdot 41 + 41 = 41^2\)이 되어 무너진다(문제 8\(\cdot\)15).

같은 형식을 준비 운동 4번에 적용하면 열 번의 확인을 통과한 뒤 “참”이라고 적게

되는데, 그 명제는 바로 다음 값 \(n = 11\)에서 거짓이다. 곧 이 형식은 **거짓 명제를

참으로 선언하는 답안을 언제든 만들어 낸다.** 걸음 ③은 형식적 절차가 아니라

참\(\cdot\)거짓을 확정하는 유일한 걸음이다.

걸음 삭제 실험 (나) — 걸음 ①을 지우면. 정찰 없이 곧바로 걸음 ③으로 뛰는 답안을 검사해 보자.

삭제 실험 — 정찰 없이 증명으로 뛴 답안

명제: 정수 \(a, b\)에 대해, \(a \mid b\)이고 \(b \mid a\)이면 \(a = b\)이다.

“직접 증명. \(b = ak\), \(a = bl\)이라 하자. \(a = a(kl)\)이므로 \(kl = 1\)이고,

따라서 \(k = 1\)이다. 그러면 \(b = a\)이다. 증명 끝.”

확인 4. 위 답안에서 거짓인 문장은 어느 것인가. 정찰 한 줄이 이 답안을 어떻게 막았겠는가.

답

거짓인 문장은 “따라서 \(k = 1\)이다”이다. \(kl = 1\)인 정수쌍은 \((1, 1)\)과 \((-1, -1)\)의

두 가지인데, 답안은 뒤쪽을 적지 않고 넘어갔다. 곱이 \(1\)이라는 조건만으로는 부호가

정해지지 않으므로, 이 자리에서 경우를 나누지 않으면 한 경우가 검사되지 않은 채

결론으로 간다.

게다가 그 앞 줄 “\(a = a(kl)\)이므로 \(kl = 1\)”도 양변을 \(a\)로 나누는 조작이라

\(a \neq 0\)을 쓰고 있는데 그 조건이 적혀 있지 않다. \(a = 0\)인 경우는 따로 처리해야

한다 — 그때는 \(b = ak = 0\)이라 결론이 성립하지만, 그 줄이 정당화된 것은 아니다.

§1.1의 시도 1은 “\(a \neq 0\)인 경우”라고 적어 이 자리를 열어 두었다.

정찰 한 줄 — \(a = -2\), \(b = 2\) 대입 — 이 있었다면 명제가 거짓임이 먼저 드러났고,

그러면 증명을 쓸 일 자체가 없었다. **정찰은 시간을 아끼는 장치일 뿐 아니라

거짓 명제를 증명했다고 착각하는 것을 막는 장치다.**

4 급소 — 반례가 자주 나오는 자리

정찰에서 아무 값이나 넣으면 대개 참인 값만 나온다. 반례는 “명제를 만든 사람이 빠뜨린 특수 사례”에 살기 때문이다. 그런 자리를 급소라 부르고, 정찰은 급소부터 넣는다. 1권 29주차 §1.6의 수색 체크리스트 일곱 줄이 그 출발점이다. 이번 주는 그 목록의 첫 줄(“특수하게 작은 수”)을 \(0\)과 “아주 작은 수” 두 줄로 나눈 뒤, \(1\) — 소수도 합성수도 아니다와 상수항이 지목하는 값 두 줄을 새로 더해 열 줄로 만들고, 그 열 줄을 걸음 ① 안에 배치한다.

급소	무너지는 명제의 예	그 자리의 반례
\(0\)	모든 실수 \(x\)에 대해 \(1/x\)이 정의된다	\(x = 0\)
음수	모든 실수 \(x\)에 대해 \(\sqrt{x^2} = x\)	\(x = -1\)
\(0\)과 \(1\) 사이의 분수	모든 실수 \(x\)에 대해 \(x^2 \ge x\)	\(x = \tfrac12\)
등호가 성립하는 자리	모든 자연수 \(n\)에 대해 \(2^n > n^2\)	\(n = 2\) (\(4 > 4\)가 거짓)
아주 작은 수	모든 자연수 \(n\)에 대해 \(n^2 \ge 2n\)	\(n = 1\) (\(1 \ge 2\)가 거짓)
소수 \(2\)	모든 소수는 홀수이다	\(p = 2\)
\(1\) — 소수도 합성수도 아니다	모든 자연수는 소수이거나 합성수이다	\(n = 1\)
빈 집합과 한 원소 집합	모든 집합은 진부분집합을 갖는다	\(\emptyset\)
작은 수 전수 대입	모든 정수는 두 제곱수의 합이다	\(3\)
상수항이 지목하는 값	모든 자연수 \(n\)에 대해 \(n^2 - n + 11\)은 소수이다	\(n = 11\)

마지막 줄은 급소가 산술로 계산되는 경우다. \(n^2 - n + 11 = n(n-1) + 11\)이므로 \(n(n-1)\)이 \(11\)의 배수가 되는 순간 값 전체가 \(11\)의 배수가 된다. 그런 \(n\)은 \(11\)의 배수이거나 \(11\)의 배수보다 \(1\) 큰 수이며, 그 중 값이 \(11\)보다 커지는 가장 작은 것이 \(n = 11\)이다.

확인 5. 명제 “모든 실수 \(x, y\)에 대해 \(\sqrt{x^2 + y^2} = x + y\)이다”를 정찰한다. 위 목록에서 어느 급소를 먼저 넣겠는가. 그 급소를 고른 이유를 한 줄로 적어 보자.

답

음수를 먼저 넣는다. 좌변은 제곱을 거치므로 부호가 지워지지만 우변은 부호를

그대로 남기므로, 두 변이 부호에 다르게 반응한다. \(x = -1\), \(y = 0\)을 넣으면

좌변은 \(\sqrt{1} = 1\)이고 우변은 \(-1\)이므로 즉시 무너진다.

\(x = y = 1\)(\(0\)도 음수도 아닌 평범한 값)도 반례다 — 좌변 \(\sqrt2\), 우변 \(2\).

급소 목록은 근거가 아니라 탐색 도구다. 답안에 “급소 목록에 의해”라고 쓸 수는

없고, 찾아낸 값을 C7주차 §1.4의 4단 서식으로 검증해야 반례가 된다.

5 정찰의 비대칭 — 통과와 위반은 무게가 다르다

정찰 결과는 두 방향으로 쓰이는데, 두 방향의 힘이 전혀 다르다.

정찰 결과	무엇이 확정되는가	산물의 라벨
대입한 값 전부에서 성립했다	아무것도 확정되지 않는다 — 확인하지 않은 값은 그대로 남는다	참 추측
대입한 값 하나에서 위반이 나왔다	명제가 거짓임이 확정된다	거짓 명제

아래쪽이 확정인 이유는 C7주차 §1.2에서 확립되었다. “\(\forall x,\ P(x)\)”의 부정은 “\(\exists x,\ \neg P(x)\)”이므로, 위반 하나는 그 존재 명제의 완전한 증명이다. 위쪽이 확정이 아닌 이유도 같은 자리에서 나온다 — 유한 개의 확인은 전칭 명제의 증명이 아니고, 전칭 명제를 증명하려면 문자를 세워 모든 값을 한 번에 처리해야 한다 (1권 1주차 확인 13).

이 비대칭이 얼마나 큰지 보여 주는 사례가 셋 있다.

사례	정찰이 통과한 횟수	무너진 자리
\(n^2 + n + 41\)이 소수 (오일러)	\(n = 0\)부터 \(39\)까지 마흔 번	\(n = 40\)에서 \(41^2\)
\(n^2 - 79n + 1601\)이 소수	\(n = 0\)부터 \(79\)까지 여든 번	\(n = 80\)에서 \(41^2\)
\(F_k = 2^{2^k} + 1\)이 소수 (페르마)	\(k = 0\)부터 \(4\)까지 다섯 번	\(k = 5\)에서 \(641 \cdot 6700417\)

첫 사례는 1권 1주차 문제 18과 S18주차 문제 14가, 마지막 사례는 S18주차 문제 18이 다룬 것이다. 둘째 사례는 이 과정에서 처음 나오며, 이번 주 문제 18이 그 계산을 직접 밟는다. 여든 번의 통과도 보증이 아니라는 점이 이번 주의 요점이다.

확인 6. 정찰을 백 번 통과한 명제를 “정리”라 불러도 되는가. 정찰을 한 번 통과하지 못한 명제를 “거짓”이라 불러도 되는가. 두 물음의 답이 다른 이유는 무엇인가.

답

앞은 안 되고 뒤는 된다. 백 번의 통과는 “반례를 아직 찾지 못했다”는 뜻이므로

산물의 라벨은 여전히 추측이다. 반면 위반 하나는 전칭 명제의 부정을 증명하므로

거짓이라 부를 수 있다.

이유는 명제의 겉모양에 있다. “\(\forall x,\ P(x)\)”를 참으로 만들려면 무한히 많은

값 전부가 필요하지만, 거짓으로 만들려면 값 하나면 된다. 참과 거짓의 비용이 이렇게

다르기 때문에 정찰이 값싸면서도 반쪽짜리다. S18주차 확인 6이 같은 비대칭을

일반화의 언어로 짚은 자리다.

정찰이 반쪽이라는 사실은 정찰을 버릴 이유가 아니다. 걸음 ③에서 증명을 쓸지 반례를 찾을지는 정찰 없이 정할 수 없고, 방향을 잘못 정하면 그 아래 모든 줄이 검사할 대상을 잃는다. 정찰은 필수이면서 불충분한 걸음이다.

6 수리 — 반례 뒤에 자격을 좁힌다

반례를 찾으면 명제를 버리지 않는다. 반례가 정확히 어느 자리에서 명제를 깼는지 읽고, 그 자리를 배제한 참인 명제로 되물린다. 되물림의 방향은 둘이다.

백지 암기 대상

수리의 두 방향

가정 강화(무대 축소) — 반례가 사는 영역을 가정에서 잘라 낸다. 명제의 주장은 그대로 두고 적용 범위를 좁힌다.

결론 약화(주장 완화) — 무대는 그대로 두고 결론을 반례까지 포함하도록 고쳐 적는다.

좋은 수리는 반례를 정확히 배제하는 최소한의 조건이다 — 필요 이상으로 좁히면 참이지만 쓸모가 줄고, 덜 좁히면 여전히 거짓이다.

거짓 명제	반례	가정 강화	결론 약화
모든 자연수 \(n\)에 대해 \(n^2 \ge 2n\)	\(n = 1\)	\(n \ge 2\)에서 \(n^2 \ge 2n\)	모든 자연수 \(n\)에 대해 \(n^2 \ge n\) — 참이지만 원래 주장보다 약하다
모든 실수 \(x\)에 대해 \(\sqrt{x^2} = x\)	\(x = -1\)	\(x \ge 0\)이면 \(\sqrt{x^2} = x\)	모든 실수 \(x\)에 대해 \(\sqrt{x^2} = \lvert x \rvert\)
정수 \(a, b\)에 대해 \(a \mid b\)이고 \(b \mid a\)이면 \(a = b\)	\(a = -2\), \(b = 2\)	양의 정수 \(a, b\)에 대해 \(a = b\)	정수 \(a, b\)에 대해 \(\lvert a \rvert = \lvert b \rvert\)

셋째 줄이 예제 2.3에서 두 방향을 다 밟는 명제다. 세 줄 모두 두 방향이 열려 있으나 얻는 것이 다르다 — 첫째 줄의 결론 약화는 참이 되는 대신 주장이 눈에 띄게 약해지고, 둘째\(\cdot\)셋째 줄의 결론 약화는 무대를 잃지 않으면서 주장의 힘도 거의 유지한다. 어느 방향이 나은지는 반례의 성격이 정한다.

확인 7. 명제 “모든 실수 \(x\)에 대해 \(x^3 \ge x\)이다”의 반례로 \(x = -2\)가 있다. 이 명제를 가정 강화로 수리해 보자. 그리고 그 조건이 최소한인지 검토해 보자.

답

\(x^3 - x = x(x-1)(x+1)\)이므로 이 값이 음수가 되는 곳은 \(x < -1\)인 구간과

\(0 < x < 1\)인 구간이다. 반례가 사는 영역은 그 둘의 합이고, 남는 영역만 자격으로

적으면 “\(-1 \le x \le 0\) 또는 \(x \ge 1\)이면 \(x^3 \ge x\)”가 되며 이것이 최소한의

수리다. “\(x \ge 1\)이면”으로 좁혀도 참이지만 \(-1 \le x \le 0\)을 함께 버린 것이므로

최소가 아니다.

반례를 하나만 보고 “\(x \ge 0\)이면”으로 좁히는 답안이 흔한데, 그 자격은 여전히

\(x = \tfrac12\)을 담고 있어 거짓이다 — 수리한 명제도 정찰을 다시 받아야 한다는

것이 확인 8의 내용이다.

확인 8. 수리한 명제를 답안에 적을 때, 그 명제를 다시 정찰하고 증명해야 하는가. 아니면 원 명제의 반례를 제시한 것으로 충분한가.

답

다시 밟아야 한다. 수리는 새 명제를 만드는 일이므로 그 새 명제 역시 참\(\cdot\)거짓이

표시되지 않은 상태이고, 걸음 ①②③을 처음부터 다시 받는다. S18주차 §1.5의

세 산물 표가 같은 규칙이다 — 검문을 통과한 것과 증명된 것은 다르다.

예제 2.3이 이 왕복을 한 번 밟는다: 명제 A가 반례로 무너지고, 수리한 명제 B가

다시 정찰과 증명을 받는다. 증명과 반증은 대립이 아니라 한 탐구의 두 방향이며,

이 왕복이 그 두 방향이 실제로 하는 일이다.

7 이번 주에 쓸 수 있는 근거 — 목록 갱신

허용 목록은 1권 이래 네 줄이다: ① 정의 ② 닫힘성 ③ 등식\(\cdot\)부등식의 성질 ④ 이미 증명한 명제. 이번 주가 채우는 것은 ①과 ④다.

근거	이번 주에 추가\(\cdot\)갱신되는 것	이번 주에는 이렇게 쓴다
① 정의	새 정의는 없다. Prove-or-Disprove 흐름과 수리의 두 방향은 절차이며 근거가 아니다	답안의 구조를 정하는 데만 쓰고 “흐름에 의해”라고 인용하지 않는다
② 닫힘성	변화 없음	정수\(\cdot\)유리수의 사칙 닫힘성을 별도 설명 없이 쓴다
③ 등식\(\cdot\)부등식의 성질	변화 없음	1권 16주차 (W1)~(W6). 부등식 명제의 정찰에서 등호가 성립하는 자리를 찾는 데 쓴다
④ 이미 증명한 명제	연속한 두 정수의 곱은 짝수(1권 1주차 문제 16) \(\cdot\) 홀수 \(n\)에 대해 \(8 \mid n^2 - 1\)(1권 1주차 문제 17) \(\cdot\) \(a \mid b\)이고 \(b \mid a\)이면 \(a = b\) 또는 \(a = -b\)(1권 2주차 문제 20) \(\cdot\) \(\sqrt{a+b} \le \sqrt a + \sqrt b\)(S6주차 문제 13) \(\cdot\) \(n \ge 5\)에서 \(2^n > n^2\)(S14주차 문제 11) \(\cdot\) 유클리드 보조정리(S15주차 문제 10) \(\cdot\) \(n^3 \equiv n \pmod 6\)(C6주차 문제 15) \(\cdot\) 반례의 4단 서식(C7주차 §1.4)	“1권 1주차 문제 16에 의해”처럼 출처를 대고 한 줄로 끝낸다

목록 밖의 것은 이번 주에도 근거가 되지 않는다. 특히 “여러 사례에서 성립하므로”는 근거가 아니다 — 그것은 걸음 ①의 결과일 뿐이고, 걸음 ②에서 추측의 방향을 정하는 데만 쓰인다.

확인 9. 어떤 답안에 다음 두 문장이 나왔다. 각각 허용되는가. 허용된다면 몇 번 근거인가.

(가) “\(n = 1\)부터 \(20\)까지 확인했으므로 모든 자연수에서 성립한다.”

(나) “\(n(n+1)\)은 연속한 두 정수의 곱이므로 짝수이다.”

답

(가) 불허 — 목록 밖이다. 이것은 걸음 ①의 정찰 기록이며, 답안에서는

“따라서 참으로 추측한다”까지만 쓸 수 있다. 확정은 걸음 ③이 한다.

(나) 허용 — 근거 ④. 1권 1주차 문제 16이 출처이고, 인용할 때 그 출처를 밝힌다.

이 부품이 예제 2.1의 증명에서 그대로 쓰인다.