# S1주차 — 증명이라는 과제: 명제, 함의, 진리표의 재정비 :::{admonition} 이 주의 길잡이 :class: keybox **핵심 문장**: 증명은 "A가 참"이라는 정보만으로 "B도 참"임을 회의적인 독자에게 확신시키는 과제다. **이 주의 위치**: 1학기(Solow) 20주의 1주차. 1권 7$\cdot$8주차의 진리표와 15주차의 직접 증명 서식을, "지금 손에 무엇이 있고 무엇을 만들어야 하는가"라는 관리 문제로 다시 세운다. **원서 대응**: Solow 1장. 주간 루틴 1일차에 원서 1장을 통독한 뒤 이 문서로 온다. ::: ## 이번 주 목표 1. 증명을 "$A \Rightarrow B$ 과제"로 보는 관점을 세운다 — 무엇이 주어지고(A), 무엇을 확신시켜야 하며(B), 어떤 근거가 허용되는가. 1. 임의의 수학 명제에서 **가설 A와 결론 B를 분해**하는 일을 즉답 수준으로 만든다 (숨은 가설 포함). 1. 진리표(1권 8주차)를 증명자의 책임 범위를 정하는 규칙서로 다시 읽는다 — 왜 "A 거짓" 두 행은 증명자의 일이 아닌가. 1. 이 책 전체의 지도를 그린다: 기법이란 "A는 참, B의 진리값은 미지"인 상황의 표준 공략법들이다. 본문 곳곳의 **확인** 상자는 연필로 먼저 답하는 자리다. 바로 아래의 **답** 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다. :::{admonition} 표기 — § 와 난이도 표시 :class: quotebox §는 "절"이라고 읽는다. §1.3은 이 주차의 1.3 절을, §5는 5절 전체를 가리킨다. 다른 주차를 가리킬 때는 "S2주차 §1.2"처럼 주차를 앞에 적고, 1권을 가리킬 때는 "1권 15주차 문제 18"처럼 적는다. 원서는 "Solow 1장"처럼 장 번호로만 적는다. 절 제목에 붙은 점 표시는 단계를 뜻한다. 연습문제는 기본 1~6번, 표준 7~14번, 도전 15~20번이고, 빈칸 사다리는 훈련 1에서 3으로 갈수록 지지대가 줄어든다. 이번 주에 반복해서 나오는 "허용된 근거"는 증명의 각 줄에 붙일 수 있는 것들의 목록을 가리킨다. 이 목록 밖에 있는 것은 증명에 쓸 수 없다 — 목록을 §1.7에서 확정한다. ::: ## 준비 운동 (1권 복습) 1. $P \Rightarrow Q$의 진리표를 백지에 그리시오 (1권 8주차). 1. "$P \Rightarrow Q$가 거짓이 되는 유일한 경우"는 언제인지 한 줄로 쓰시오. 1. 1권 15주차의 직접 증명 서식(오프닝 $\to$ 몸통 $\to$ 마감)을 아무 명제 하나로 재현하시오. 1. 명제 "$n^2$이 짝수인 정수 $n$은 짝수이다"에서 무엇을 가정하고 무엇을 보여야 하는지 각각 한 줄로 적으시오. 답을 노트에 적어 둔다. 4번의 답은 §1.5를 읽은 뒤 다시 본다. ### 자주 나오는 세 가지 답 4번에 적은 답은 대개 다음 세 유형 중 하나다. 셋 다 1권 범위 안에서만 움직인 답이고, 셋 다 이번 주에 메울 정확한 간격이 있다. - **유형 1 — 무대 선언 누락.** 가정을 "$n^2$은 짝수", 결론을 "$n$은 짝수"로 적는다. 이 두 줄은 옳다. 빠진 것은 "$n$은 정수"라는 한 줄이다. 무대 선언을 가정에서 빼면 $n = \sqrt2$ 같은 대상까지 논의에 들어오고, 그러면 "$n$이 짝수인가"라는 물음 자체가 판정 불가능해진다. 무대 선언도 가정의 일부다 — §1.3에서 이 누락이 실제로 무엇을 무너뜨리는지 본다. - **유형 2 — 방향 뒤집기.** "$n$이 짝수라 가정하고 $n^2$이 짝수임을 보인다"로 적는다. 1권 1주차 문제 9에서 실제로 증명한 것이 그 방향이므로 손이 그쪽으로 먼저 간다. 그러나 그것은 이 명제의 **역**(1권 9주차)이고, 별개의 명제다. 어느 쪽을 가정으로 놓았는지가 증명 전체를 결정한다 — 예제 2.3이 이 뒤집기를 정면으로 다룬다. - **유형 3 — 진리표는 그렸으나 쓰이는 곳을 모름.** 1번은 정확히 그렸는데 4번에서 진리표를 한 번도 쓰지 않는다. 진리표를 "명제의 진리값을 계산하는 표"로만 익힌 결과다. 진리표는 계산 도구이기 전에 **증명자의 책임 범위를 정하는 규칙서**이고, §1.4가 그 읽는 법을 세운다. ## 개념 — 증명이라는 과제 ### 1 기법을 다 알고도 막히는 자리 Solow 1장을 통독하면 "A가 참일 때 B가 참임을 보인다"는 서술은 남지만, 실제 명제 앞에서 무엇부터 적어야 하는지는 남지 않는다. 그 자리를 이 절에서 메운다. 1권에서 직접$\cdot$대우$\cdot$귀류$\cdot$경우 나누기$\cdot$귀납을 배웠다. 그 도구만 들고 다음 명제에 달려들어 보자. 이 명제는 §2와 S2$\cdot$S3주차에서 계속 쓴다. :::{admonition} 시도 — 1권의 직접 증명 서식으로 밀어붙이기 :class: quotebox 명제: 양의 실수 $x$에 대해, $x + \dfrac{1}{x} = 2$이면 $x = 1$이다. "1권 15주차의 서식대로 연다. 오프닝: '$x$를 $x + \frac1x = 2$인 양의 실수라 하자.' 몸통: 정의를 펼친다 — 그런데 펼칠 정의가 없다. '양의 실수'에는 $2k$ 같은 꼴이 없고, 가정의 등식은 이미 등식이라 더 풀 것이 없다. 마감: '따라서 $x = 1$이다' — 그런데 그 사이가 비어 있다." ::: 여기서 멈춘다. 1권의 3단계 틀 중 ②(정의 풀어쓰기)와 ③(목표 꼴 만들기)이 둘 다 작동하지 않는다. 도구가 부족한 것이 아니다. 도구는 다 있는데 **어느 도구를 어디에 쓸지 판단할 재료가 정리되어 있지 않다.** :::{container} quotebox **확인 1.** 위 시도가 멈춘 자리에서, 다음 줄을 찾으려면 무엇을 먼저 적어 두어야 하는가. "지금 손에 있는 것"과 "만들어야 할 것" 중 무엇이 정리되지 않았는가. ::: :::{admonition} 답 :class: quotebox dropdown 둘 다 정리되지 않았다. 손에 있는 것은 세 조각("$x$는 실수", "$x > 0$", "$x + \frac1x = 2$")인데 시도문은 그 세 조각을 목록으로 적어 두지 않았고, 만들어야 할 것은 "$x = 1$"인데 그것을 어떤 꼴로 바꿔도 되는지 정해 두지 않았다. 1권에서는 정의가 이 두 목록을 자동으로 채워 주었으므로 목록을 따로 적을 필요가 없었다. 정의가 자동으로 채워 주지 않는 명제에서는 목록을 손으로 적어야 한다. ::: :::{admonition} 이 주 전체의 기준 :class: quotebox 증명의 모든 순간은 두 목록으로 관리된다 — **가진 것(A와 A에서 유도한 것)**과 **만들 것(B 또는 B를 대신할 것)**. 이 두 목록을 명시적으로 적는 절차가 이번 주의 내용이다. ::: ### 2 구체 사례를 모아 보기 — 정리는 어떤 모양인가 1권 50주에서 증명한 명제들을 모양만 놓고 다시 본다. 표의 빈칸을 채워 보자. | **명제** | **가정에 해당하는 부분** | **결론에 해당하는 부분** | |---|---|---| | $n$이 홀수이면 $n^2$은 홀수이다 (1권 1주차 문제 11) | $n$은 정수이고 $n$은 홀수 | $n^2$은 홀수 | | $a \mid b$이고 $b \mid c$이면 $a \mid c$ (1권 2주차) | $\underline{\quad(1)\quad}$ | $a \mid c$ | | 짝수와 짝수의 합은 짝수이다 (1권 1주차 예제 2.1) | $m$, $n$은 정수이고 둘 다 짝수 | $\underline{\quad(2)\quad}$ | | 모든 실수 $x$에 대해 $x^2 + x + 1 > 0$ (1권 16주차 문제 5) | $\underline{\quad(3)\quad}$ | $x^2 + x + 1 > 0$ | :::{container} quotebox **확인 2.** 빈칸 (1)(2)(3)을 채우고, 네 줄에서 공통으로 관찰되는 것을 한 문장으로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) $a, b, c$는 정수이고 $a \mid b$이고 $b \mid c$ (2) $m + n$은 짝수 (3) $x$는 실수. 공통점: 네 명제 모두 **"어떤 것이 주어졌을 때, 어떤 것이 성립한다"**는 한 가지 모양이다. 넷째 줄처럼 "이면"이라는 낱말이 없는 명제도 무대 선언을 가정 쪽으로 올리면 같은 모양이 된다. ::: 이 관찰에 이름과 형식을 붙인다. 관찰 자체에 새로운 수학은 없다 — 1권 15주차에서 오프닝$\cdot$몸통$\cdot$마감으로 하던 일을 **목록 세 줄**로 굳혔을 뿐이다. :::{admonition} 백지 암기 대상 :class: keybox **증명 과제의 세 요소** 수학의 정리는 거의 전부 "**A이면 B이다**" 꼴이다. 이 명제를 증명한다는 것은: - **주어진 것**: "A는 참"이라는 정보 - **해야 할 일**: "B도 참"임을 확립하는 것 - **허용된 근거**: 정의, 공리, 이미 증명된 정리, 논리 규칙 이 세 가지가 정해진 상태에서 해야 할 일을 완수하는 것이다. ::: **1권의 어느 자리가 이것이었는가.** 1권 15주차에서 "$P$라 가정하자"로 열고 "따라서 $Q$이다"로 닫으라고 배운 서식이, 여기서 "주어진 것 A"와 "해야 할 일 B"라는 **두 목록의 이름**을 얻는다. 서식은 그대로이고, 달라지는 것은 그 두 목록을 증명 도중에도 계속 갱신한다는 점이다 — S2$\cdot$S3주차의 후진$\cdot$전진 과정이 그 갱신 절차다. ### 3 절차 해부 — 세팅의 네 걸음 명제를 받았을 때 실제로 하는 일은 네 걸음이다. 걸음마다 맡은 일이 다르고, 하나를 빼면 무엇이 무너지는지도 다르다. | **걸음** | **하는 일** | **이 걸음을 빼면 무엇이 무너지는가** | |---|---|---| | ① A를 남김없이 적는다 (숨은 무대 선언 포함) | 손에 쥔 정보의 목록을 만든다 | 판정 자체가 불가능해진다 (아래 실험 1) | | ② B를 정확히 적는다 | 언제 끝나는지의 기준을 만든다 | 원명제 대신 역을 증명하게 된다 (실험 2) | | ③ 허용된 근거의 목록을 확정한다 | 각 줄의 근거가 될 수 있는 것을 한정한다 | 거짓 명제가 정리 행세를 하고 통과한다 (실험 3) | | ④ "A가 참인 세계에 선다"를 선언한다 | 검토 범위를 A 참인 경우로 자른다 | 참이 아닌 더 강한 명제를 스스로 떠맡는다 (실험 4) | **걸음 삭제 실험 1 — ①을 빼면.** 명제 "$n^2$이 짝수이면 $n$은 짝수이다"에서 무대 선언 "$n$은 정수"를 A에서 빼 보자. 그러면 $n = \sqrt2$가 논의 대상이 되고, $n^2 = 2$는 짝수인데 $n = \sqrt2$는 짝수도 홀수도 아니다. 짝수의 정의(1권 1주차 정의 1.1)는 첫 조각에서 "**정수** $n$이"라고 판정 대상을 정수로 한정하므로, 정수가 아닌 $\sqrt2$에는 이 정의를 적용하는 것 자체가 불가능하다 — 따라서 "$\sqrt2$는 짝수인가"라는 물음이 참$\cdot$거짓을 갖지 못한다. 결론의 진리값이 정해지지 않으므로 명제의 판정이 성립하지 않는다. **걸음 삭제 실험 2 — ②를 빼면.** 명제 "이등변삼각형의 두 밑각은 같다"에서 B를 확정하지 않고 시작하면, "두 밑각이 같다고 하자"로 여는 답안이 나온다. 그 답안이 증명하는 것은 원명제가 아니라 **역**("두 밑각이 같으면 이등변삼각형이다")이다. 둘 다 참인 명제이지만 서로 다른 명제이고, 하나를 증명해도 다른 하나는 증명되지 않는다. 예제 2.3에서 이 답안을 정면으로 해부한다. **걸음 삭제 실험 3 — ③을 빼면.** 어떤 답안이 "무리수와 무리수의 곱은 무리수이다"를 정리로 인용해 $\sqrt2 \cdot \sqrt2$가 무리수라고 결론짓는다. 인용된 문장은 정리가 아니라 거짓 명제이고, 실제로 $\sqrt2 \cdot \sqrt2 = 2$는 유리수다. 허용된 근거의 목록을 미리 확정해 두었다면 "④ **이미 증명한** 명제"라는 자격 심사에서 이 인용이 걸렸을 것이다. 목록이 없으면 답안의 각 줄이 그럴듯해 보이는 한 그대로 통과한다. 이런 종류의 규칙 위반을 1권 23주차 문제 19에서 한 번 진단했고, 문제 13에서 그 사례를 회수한다. **걸음 삭제 실험 4 — ④를 빼면.** 명제 "실수 $x$가 $x > 5$이면 $x^2 > 25$이다"를 증명하면서 "$x \le 5$인 경우에 $x^2 \le 25$인 것도 보여야 완전하다"고 판단하면, 실제로 증명하려는 것은 "$x > 5 \iff x^2 > 25$"라는 더 강한 명제가 된다. 그런데 그 명제는 거짓이다 — $x = -6$은 $x^2 = 36 > 25$이면서 $x > 5$가 아니다. 검토 범위를 자르지 않으면 참인 명제를 증명하려다 거짓인 명제를 떠맡는다. 같은 병을 다른 수로 앓는 답안을 문제 10에서 진단한다. :::{container} quotebox **확인 3.** 네 걸음 중 하나를 빼면 "증명이 조금 허술해지는" 정도가 아니라 "증명 대상 자체가 다른 것이 되는" 걸음은 어느 것인가. 그 이유를 한 줄로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown ②와 ④. ②를 빼면 증명 대상이 역으로 바뀌고, ④를 빼면 증명 대상이 더 강한 명제로 바뀐다 — 둘 다 원명제가 아닌 **다른 명제**를 증명하게 된다. ①과 ③은 증명 대상은 그대로 두되 판정과 근거를 무너뜨린다. 네 걸음이 각각 다른 종류의 붕괴를 막는다는 것이 이 표의 요점이다. ::: ### 4 진리표를 규칙서로 읽기 1권 8주차에서 만든 진리표를 그대로 가져와, 각 행이 증명자에게 무엇을 지시하는지 넷째 열에 적는다. | **$A$** | **$B$** | **$A \Rightarrow B$** | **증명자에게 주는 지시** | |---|---|---|---| | T | T | T | 증명이 도달할 칸 | | T | F | F | 명제가 거짓이 되는 유일한 칸 — 이 칸이 불가능함을 보이는 것이 증명이다 | | F | T | T | 검토 대상 아님 — A가 거짓이면 보증할 일이 없다 | | F | F | T | 검토 대상 아님 — 셋째 행과 같다 | 셋째$\cdot$넷째 행에서 $A \Rightarrow B$는 진리표에 의해 **자동으로 참**이다(1권 8주차의 공허한 참). 증명자가 손댈 것이 없다. 남는 것은 A가 참인 두 행이고, 그중 둘째 행이 일어나지 않음을 보이면 명제가 참이다. :::{container} quotebox **확인 4.** 위 표에서, 증명자가 실제로 검토해야 하는 행은 몇 개이며 어느 것인가. 그리고 그 사실이 증명의 첫 문장을 어떻게 결정하는가. ::: :::{admonition} 답 :class: quotebox dropdown 두 개, 첫째$\cdot$둘째 행(A가 참인 행들)이다. 셋째$\cdot$넷째 행은 이미 참으로 확정되어 있어 증명할 것이 없다. 따라서 증명자는 처음부터 "A가 참인 세계"에 들어가 서면 되고, 그것을 선언하는 문장이 "A라 가정하자"이다. 이 첫 문장은 예의나 관습이 아니라 진리표의 직접 귀결이다. ::: :::{admonition} 백지 암기 대상 :class: keybox **A가 참인 세계만 검토한다** 증명자가 검토할 세계는 A가 참인 세계뿐이다. A가 거짓인 세계에서 $A \Rightarrow B$는 이미 참이므로, 그 세계에서 B가 무엇이든 명제를 훼손하지 못한다. 명제가 거짓이 되는 유일한 길은 "A는 참인데 B가 거짓인 세계"를 하나라도 찾는 것이고, 그런 세계가 곧 반례다(1권 29주차). ::: :::{admonition} 표기 — 문자 $A$, $B$ :class: quotebox 1권에서 $P \Rightarrow Q$로 쓰던 것을 이 학기에는 $A \Rightarrow B$로 쓴다. 원서가 가정을 $A$, 결론을 $B$로 고정해 두었기 때문이고, 원서를 읽는 동안 문자 대응이 흔들리지 않도록 교안도 같은 문자를 쓴다. 읽는 법은 그대로 "에이면 비" 또는 "에이는 비를 함의한다"이다. 뜻은 1권의 $P \Rightarrow Q$와 완전히 같다 — 바뀐 것은 이름뿐이다. ::: ### 5 가설과 결론의 분해 — 숨은 것까지 명제가 언제나 "A이면 B" 꼴로 오지는 않는다. 한국어 문장에서 A와 B를 끄집어내는 훈련을 한다. 표의 빈칸을 채워 보자. | **겉모습** | **A (가설)** | **B (결론)** | |---|---|---| | 직각삼각형의 빗변은 가장 긴 변이다 | 삼각형 $T$는 직각삼각형이다 | $T$의 빗변은 가장 긴 변이다 | | $n^2$이 짝수인 정수 $n$은 짝수다 | $n$은 정수이고 $n^2$은 짝수 | $\underline{\quad(1)\quad}$ | | 소수는 무한히 많다 | $\underline{\quad(2)\quad}$ | 소수의 집합은 무한하다 | | $x > 2 \Rightarrow x^2 > 4$ | $\underline{\quad(3)\quad}$ | $x^2 > 4$ | :::{container} quotebox **확인 5.** 빈칸 (1)(2)(3)을 채워 보자. (2)는 "이면"이 없는 명제라는 점에 주의한다. ::: :::{admonition} 답 :class: quotebox dropdown (1) $n$은 짝수 (2) 수학의 표준 정의와 공리들 — 언제나 참으로 주어져 있는 것 전부 (3) $x$는 실수이고 $x > 2$. (3)에서 "$x$는 실수"는 문장에 적혀 있지 않지만 A에 들어간다. 이런 조각을 **숨은 가설**이라 하고, 대개 무대 선언이다(1권 3주차에서 집합이 무대라고 부른 그 무대다). ::: **무조건 명제도 같은 틀로 다룬다.** "소수는 무한히 많다"처럼 "이면"이 없는 명제에서는 A 자리에 표준 정의와 공리 전부가 들어간다. 즉 손에 아무것도 없이 시작하는 것이 아니라, 언제나 주어져 있는 것으로 시작한다. 그래서 $A \Rightarrow B$ 틀은 예외 없이 적용된다. :::{container} quotebox **확인 6.** 무조건 명제의 A가 "표준 정의와 공리 전부"라면, 그런 명제에서 "A가 거짓인 세계"의 예를 들 수 있는가. ::: :::{admonition} 답 :class: quotebox dropdown 들 수 없다. 표준 정의와 공리는 이 논의 안에서 언제나 참이므로 A가 거짓이 되는 세계가 없다. 따라서 무조건 명제에서는 진리표의 셋째$\cdot$넷째 행이 아예 등장하지 않고, 검토할 행이 첫째$\cdot$둘째 행뿐이다. 이 관찰이 문제 8과 훈련 3의 요점이다. ::: 분해가 틀리면 그 뒤의 모든 줄이 틀린다. 이번 주 연습문제의 절반이 분해 훈련인 이유다. ### 6 이 책의 지도 — 기법은 상황별 표준 공략법 앞으로 배울 것을 미리 배치해 둔다. 지금 외울 것은 아니고, 이번 학기 내내 돌아와 읽을 지도다. :::{admonition} 기법을 정하는 것은 A와 B의 겉모양이다 :class: quotebox - B에서 출발해 거꾸로 묻기 $\to$ **후진 과정** (S2주차) - A에서 밀고 나가기 $\to$ **전진 과정** (S3주차) - B에 "존재한다" $\to$ **구성법** (S5주차) / B에 "모든" $\to$ **선택법** (S6주차) - A에 "모든" $\to$ **특수화** (S7주차) / 양화사가 겹치면 $\to$ **중첩 양화사** (S8주차) - B에 부정 $\to$ **귀류$\cdot$대우** (S10~S12주차) / "유일" $\to$ S13주차 / 귀납 꼴 $\to$ S14주차 - "또는" $\to$ S15주차 / 최대$\cdot$최소 $\to$ S16주차 ::: 1권 23주차에서 "기법은 취향이 아니라 신호가 정한다"고 배운 것이, 이 학기에 신호별 절차의 목록으로 확장된다. 1권이 기법을 하나씩 세운 과정이었다면 이 책은 그 기법들을 언제 어떤 순서로 꺼내는지의 관리 절차다. ### 7 근거 목록 갱신 — 1권의 ①~④에 ⑤가 붙는다 1권에서 증명의 각 줄에 붙일 수 있는 근거는 네 가지였다. 이번 학기의 "허용된 근거"는 그 네 가지에 하나를 더한 목록이다. | **근거** | **내용** | **허용된 근거 목록에서의 이름** | |---|---|---| | ① 정의 | 짝수$\cdot$홀수$\cdot$나누어떨어짐$\cdot$소수$\cdot$수렴 등 정의 전부 | 정의 | | ② 닫힘성 등 기본 성질 | 정수의 합$\cdot$곱은 정수, 부등식의 기본 성질 (1권 16주차 (W1)~(W6)) | 공리와 기본 성질 | | ③ 등식$\cdot$부등식의 조작 | 대입, 전개, 묶기, 양변에 같은 연산 | 공리와 기본 성질 | | ④ 이미 증명한 명제 | 1권 1~50주차의 예제$\cdot$문제 전부, 이 학기에 증명한 것 | 이미 증명된 정리 | | ⑤ 논리 규칙 | 진리표, 대우의 동치성(1권 9주차), 부정 만들기(1권 11주차) | 논리 규칙 | ⑤가 새로 목록에 오른다. 1권에서도 대우와 부정을 썼지만, 그때는 기법의 이름으로 썼다. 이번 학기에는 "이 줄의 근거는 논리 규칙"이라고 명시할 자리가 생긴다 — S10주차의 부정 계산이 그 자리를 본격적으로 쓴다. :::{container} quotebox **확인 7.** 다음 세 문장이 근거 목록의 몇 번에 해당하는지, 또는 목록 밖인지 판정해 보자. (가) "$2ab + a + b$는 정수이므로" (나) "그래프를 그려 보면 명백하므로" (다) "$P \Rightarrow Q$와 $\neg Q \Rightarrow \neg P$는 같은 명제이므로" ::: :::{admonition} 답 :class: quotebox dropdown (가) ② — 정수의 곱과 합은 정수. (나) 목록 밖 — 그림은 근거가 아니다. 그림에서 읽은 사실을 ①~⑤로 다시 세워야 쓸 수 있다. (다) ⑤ — 1권 9주차에서 진리표로 확인한 논리 규칙이다. :::