# C10주차 — Prove or Disprove: 추측의 세계 :::{admonition} 이 주의 길잡이 :class: keybox **핵심 문장**: 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$ 수리)으로 세우고 백지에 재현한다. 1. 정찰이 **증명이 아님**을 확인하되, 정찰이 **어느 쪽을 증명할지 정하는** 필수 걸음임을 구분해 설명한다. 1. 반례가 자주 나오는 자리(급소) 목록을 갖추고, 거짓 명제를 반례로 확정한다 (C7주차의 4단 서식). 1. 반례 뒤에 **자격을 좁혀** 참인 명제로 되물린다 — 가정 강화와 결론 약화의 두 방향 (S18주차). 본문 곳곳의 **확인** 상자는 연필로 먼저 답하는 자리다. 바로 아래의 **답** 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다. :::{admonition} 표기 — § 와 난이도 표시 :class: quotebox §는 "절"이라고 읽는다. §1.3은 이 주차의 1.3 절을, §6은 6절 전체를 가리킨다. 다른 주차를 가리킬 때는 "C7주차 §1.4"처럼 주차를 앞에 적는다. 연습문제는 기본 1~6번, 표준 7~14번, 도전 15~20번이고, 빈칸 사다리는 훈련 1에서 3으로 갈수록 지지대가 줄어든다. ::: ## 준비 운동 (C9주차 복습) 지난주까지의 도구를 손에 올려 둔다. 셋 다 이번 주 답안에서 그대로 쓴다. 1. C9주차 §1의 전반부 기법 지도를 재현하시오 — 결론의 겉모양이 기법을 정하는 0~4단계. 1. C7주차 §1.4의 반례 4단 서식(부정 전개 $\cdot$ 증인 제시 $\cdot$ 자격 검증 $\cdot$ 사건 검증)을 쓰시오. 1. 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주차의 기법 지도)만으로 두 명제를 실제로 밀어붙여 본다. :::{admonition} 시도 1 — 지도대로 직접 증명 :class: quotebox 명제: 정수 $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$이고 … " ::: 여기서 멈춘다. 남은 경우가 목표와 어긋난다. :::{admonition} 시도 2 — 준비 운동 4번을 대입으로 :class: quotebox 명제: 모든 양의 정수 $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$. 열 번 모두 소수다. 따라서 이 명제는 참이다." ::: 두 시도가 막힌 이유는 서로 다르다. :::{container} quotebox **확인 1.** 시도 1과 시도 2에서 잘못된 것은 각각 무엇인가. 한쪽은 "도구가 모자라서"이고 다른 한쪽은 그것이 아니다. 어느 쪽이 어느 쪽인가. ::: :::{admonition} 답 :class: quotebox dropdown 어느 쪽도 도구가 모자라서가 아니다. 시도 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$이므로 이 명제도 거짓이다. ::: :::{admonition} 이 주 전체의 기준 :class: quotebox 참$\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}$ | :::{container} quotebox **확인 2.** 표의 (1)(2)(3)을 채워 보자. 그리고 세 행이 공통으로 밟은 순서를 한 문장으로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) $n = 1$부터 $10$까지 대입했고, 이어 상수항 $11$에 맞춰 $n = 11$을 대입했다. (2) 거짓 쪽 — $n = 11$에서 값이 $121$이 되어 소수가 아니었다. (3) 반례 $n = 11$과 두 검증($11$은 양의 정수이고, $121 = 11 \cdot 11$은 소수가 아니다). 공통으로 밟은 순서: **먼저 몇 개를 대입해 방향을 정하고, 정한 방향에 맞는 확정 작업(증명 또는 반례)을 했다.** 셋 다 대입 자체를 결론으로 쓰지는 않았다. ::: 이 순서에 정식 이름과 형식을 붙인다. 절차 자체에 새로운 것은 없다 — C7주차의 반례와 C5~C8주차의 증명 앞에 **판정 한 걸음**을 붙여 묶었을 뿐이다. :::{admonition} 백지 암기 대상 :class: keybox **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의 되물림이 걸음 ④에 그대로 들어온다. :::{admonition} 표기 — Prove or Disprove :class: quotebox 원서의 지시문 "Prove or Disprove"는 "증명하거나 반증하라"로 읽는다. 참$\cdot$거짓이 미리 표시되지 않았다는 뜻이며, 답안의 첫 줄은 언제나 판정 선언이다 — "이 명제는 참이다" 또는 "이 명제는 거짓이다". 이 교안은 이 지시문을 **P-or-D**로 줄여 적는다. ::: :::{admonition} 표기 — 추측 (conjecture) :class: quotebox 정찰을 통과했으나 아직 증명되지 않은 명제에 붙이는 라벨이 **추측**이다. "$S$를 참으로 추측한다"로 읽는다. 추측은 근거 ④가 아니다 — 뒤 줄에서 "추측에 의해"라고 인용할 수 없고, 걸음 ③이 끝나기 전까지는 아무것도 지탱하지 않는다. ::: ### 3 절차 해부 — 걸음마다 하는 일 네 걸음은 각각 다른 일을 한다. 하나를 빼면 무엇이 무너지는지가 그 걸음의 존재 이유다. | **걸음** | **하는 일** | **이 걸음을 빼면 무엇이 무너지는가** | |---|---|---| | ① 정찰 | 명제를 실제 값에서 시험해 방향의 재료를 모은다 | 증명과 반례 중 무엇을 쓸지 근거 없이 고르게 된다. 거짓 명제를 증명하려 시간을 쓰거나(§1.1 시도 1), 참인 명제에서 반례를 찾느라 시간을 쓴다 | | ② 추측 | 방향 하나를 골라 선언한다 | 정찰 결과가 답안에 쌓이기만 하고 다음 줄이 정해지지 않는다. 걸음 ③의 기법 선택은 "참인가 거짓인가"가 정해져야 시작된다 | | ③ 결단 | 증명 또는 반례로 참$\cdot$거짓을 **확정**한다 | 정찰 결과가 그대로 결론이 된다 — 이것이 §0 유형 1이고 아래 삭제 실험이다 | | ④ 수리 | 거짓 명제를 참인 명제로 되물린다 | 반례를 찾은 뒤 남는 것이 "거짓"이라는 한 낱말뿐이다. 어디까지가 참인지는 여전히 모른다 | **걸음 삭제 실험 (가) — 걸음 ③을 지우면.** 확정 의무를 지우고 정찰 결과를 결론으로 삼는 답안을 검사해 보자. :::{admonition} 삭제 실험 — 정찰을 결론으로 삼은 답안 :class: quotebox 명제: 모든 자연수 $n$에 대해 $n^2 + n + 41$은 소수이다. "$n = 1, \ldots, 10$에서 $43, 47, 53, 61, 71, 83, 97, 113, 131, 151$이 전부 소수이다. 반례가 나오지 않았으므로 이 명제는 참이다." ::: :::{container} quotebox **확인 3.** 위 답안에서 계산이 틀린 줄이 있는가. 없다면 무엇이 잘못되었는가. 그리고 이 답안과 같은 형식을 준비 운동 4번의 명제에 적용하면 무엇이 나오는가. ::: :::{admonition} 답 :class: quotebox dropdown 계산은 한 줄도 틀리지 않았다. 열 값에서 실제로 전부 소수다. 잘못된 것은 **마지막 한 줄의 자격**이다 — "반례가 나오지 않았다"는 "아직 찾지 못했다"일 뿐이고, 이 명제는 $n = 40$에서 $40 \cdot 41 + 41 = 41^2$이 되어 무너진다(문제 8$\cdot$15). 같은 형식을 준비 운동 4번에 적용하면 열 번의 확인을 통과한 뒤 "참"이라고 적게 되는데, 그 명제는 바로 다음 값 $n = 11$에서 거짓이다. 곧 이 형식은 **거짓 명제를 참으로 선언하는 답안을 언제든 만들어 낸다.** 걸음 ③은 형식적 절차가 아니라 참$\cdot$거짓을 확정하는 유일한 걸음이다. ::: **걸음 삭제 실험 (나) — 걸음 ①을 지우면.** 정찰 없이 곧바로 걸음 ③으로 뛰는 답안을 검사해 보자. :::{admonition} 삭제 실험 — 정찰 없이 증명으로 뛴 답안 :class: quotebox 명제: 정수 $a, b$에 대해, $a \mid b$이고 $b \mid a$이면 $a = b$이다. "직접 증명. $b = ak$, $a = bl$이라 하자. $a = a(kl)$이므로 $kl = 1$이고, 따라서 $k = 1$이다. 그러면 $b = a$이다. 증명 끝." ::: :::{container} quotebox **확인 4.** 위 답안에서 거짓인 문장은 어느 것인가. 정찰 한 줄이 이 답안을 어떻게 막았겠는가. ::: :::{admonition} 답 :class: quotebox dropdown 거짓인 문장은 "따라서 $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$이다. :::{container} quotebox **확인 5.** 명제 "모든 실수 $x, y$에 대해 $\sqrt{x^2 + y^2} = x + y$이다"를 정찰한다. 위 목록에서 어느 급소를 먼저 넣겠는가. 그 급소를 고른 이유를 한 줄로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown **음수**를 먼저 넣는다. 좌변은 제곱을 거치므로 부호가 지워지지만 우변은 부호를 그대로 남기므로, 두 변이 부호에 다르게 반응한다. $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이 그 계산을 직접 밟는다. 여든 번의 통과도 보증이 아니라는 점이 이번 주의 요점이다. :::{container} quotebox **확인 6.** 정찰을 백 번 통과한 명제를 "정리"라 불러도 되는가. 정찰을 한 번 통과하지 못한 명제를 "거짓"이라 불러도 되는가. 두 물음의 답이 다른 이유는 무엇인가. ::: :::{admonition} 답 :class: quotebox dropdown 앞은 안 되고 뒤는 된다. 백 번의 통과는 "반례를 아직 찾지 못했다"는 뜻이므로 산물의 라벨은 여전히 **추측**이다. 반면 위반 하나는 전칭 명제의 부정을 증명하므로 **거짓**이라 부를 수 있다. 이유는 명제의 겉모양에 있다. "$\forall x,\ P(x)$"를 참으로 만들려면 무한히 많은 값 전부가 필요하지만, 거짓으로 만들려면 값 하나면 된다. 참과 거짓의 비용이 이렇게 다르기 때문에 정찰이 값싸면서도 반쪽짜리다. S18주차 확인 6이 같은 비대칭을 일반화의 언어로 짚은 자리다. ::: 정찰이 반쪽이라는 사실은 정찰을 버릴 이유가 아니다. 걸음 ③에서 증명을 쓸지 반례를 찾을지는 정찰 없이 정할 수 없고, 방향을 잘못 정하면 그 아래 모든 줄이 검사할 대상을 잃는다. 정찰은 **필수이면서 불충분한** 걸음이다. ### 6 수리 — 반례 뒤에 자격을 좁힌다 반례를 찾으면 명제를 버리지 않는다. 반례가 정확히 어느 자리에서 명제를 깼는지 읽고, 그 자리를 배제한 참인 명제로 되물린다. 되물림의 방향은 둘이다. :::{admonition} 백지 암기 대상 :class: keybox **수리의 두 방향** **가정 강화(무대 축소)** — 반례가 사는 영역을 가정에서 잘라 낸다. 명제의 주장은 그대로 두고 적용 범위를 좁힌다. **결론 약화(주장 완화)** — 무대는 그대로 두고 결론을 반례까지 포함하도록 고쳐 적는다. 좋은 수리는 반례를 정확히 배제하는 **최소한의** 조건이다 — 필요 이상으로 좁히면 참이지만 쓸모가 줄고, 덜 좁히면 여전히 거짓이다. ::: | **거짓 명제** | **반례** | **가정 강화** | **결론 약화** | |---|---|---|---| | 모든 자연수 $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$셋째 줄의 결론 약화는 무대를 잃지 않으면서 주장의 힘도 거의 유지한다. 어느 방향이 나은지는 반례의 성격이 정한다. :::{container} quotebox **확인 7.** 명제 "모든 실수 $x$에 대해 $x^3 \ge x$이다"의 반례로 $x = -2$가 있다. 이 명제를 가정 강화로 수리해 보자. 그리고 그 조건이 최소한인지 검토해 보자. ::: :::{admonition} 답 :class: quotebox dropdown $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의 내용이다. ::: :::{container} quotebox **확인 8.** 수리한 명제를 답안에 적을 때, 그 명제를 다시 정찰하고 증명해야 하는가. 아니면 원 명제의 반례를 제시한 것으로 충분한가. ::: :::{admonition} 답 :class: quotebox dropdown 다시 밟아야 한다. 수리는 **새 명제를 만드는 일**이므로 그 새 명제 역시 참$\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에 의해"처럼 출처를 대고 한 줄로 끝낸다 | 목록 밖의 것은 이번 주에도 근거가 되지 않는다. 특히 **"여러 사례에서 성립하므로"는 근거가 아니다** — 그것은 걸음 ①의 결과일 뿐이고, 걸음 ②에서 추측의 방향을 정하는 데만 쓰인다. :::{container} quotebox **확인 9.** 어떤 답안에 다음 두 문장이 나왔다. 각각 허용되는가. 허용된다면 몇 번 근거인가. (가) "$n = 1$부터 $20$까지 확인했으므로 모든 자연수에서 성립한다." (나) "$n(n+1)$은 연속한 두 정수의 곱이므로 짝수이다." ::: :::{admonition} 답 :class: quotebox dropdown (가) 불허 — 목록 밖이다. 이것은 걸음 ①의 정찰 기록이며, 답안에서는 "따라서 참으로 추측한다"까지만 쓸 수 있다. 확정은 걸음 ③이 한다. (나) 허용 — 근거 ④. 1권 1주차 문제 16이 출처이고, 인용할 때 그 출처를 밝힌다. 이 부품이 예제 2.1의 증명에서 그대로 쓰인다. :::