C9주차 · 강의 — 예제 · 연습 · 해설

C9주차 · 강의 — 예제 · 연습 · 해설#

시험 규칙#

  • 1부 (기법 지도 + 채점 복원, 40분): 이 문서에는 1부의 문항 절이 따로 없다. 복원 대상은 §1 전체 — 기법 지도의 0~4단계 골격과 증명 평가 다섯 걸음, 그리고 판정 낱말 셋이다. 만점 20점(지도 골격 12점 — 0~4단계의 다섯 단계와 2단계의 여섯 갈래, 각 1점에 3단계의 다섯 무대 1점 / 평가 절차 8점 — 다섯 걸음 각 1점, 판정 낱말 셋 각 1점), 16점 이상 통과. §1이 그대로 정답지이므로 채점은 §1과의 대조로 한다.

  • 2부 (종합 시험, 150분): 20문항. 기본 6문항 \(\times\) 1점 + 표준 8문항 \(\times\) 2점 + 도전 6문항 \(\times\) 3점 = 40점 만점, 32점 이상 통과. 표준과 도전에 증명 평가 문항이 여섯 개 들어간다.

  • 교재\(\cdot\)원서\(\cdot\)노트 참조 금지. 해설은 채점이 끝난 뒤에만 연다.

  • 부분 점수 — 증명 평가 문항은 판정 낱말과 근거를 따로 채점하고 각각 절반을 배정한다. 판정만 맞고 근거가 비어 있으면 절반이다.

  • 기준에 미치지 못하면 아래 재학습 지도의 해당 주차를 복습하고 일주일 뒤 재시험을 본다. 통과 전에는 C10주차로 넘어가지 않는다.

1부는 §1을 백지에서 복원하는 시험이므로, 복원한 종이를 §1과 대조할 때 다음 칸을 하나씩 채운다. 칸의 수가 곧 배점이다.

1부 복원 체크리스트 (백지에서 채운 뒤 §1과 대조한다)

지도 골격 12점. ✓ 0단계 판 세팅 ✓ 1단계 진리 상태 점검 ✓ 2단계 구조 판독 ✓ 3단계 무대 전개 ✓ 4단계 검증 (다섯 단계 각 1점)

✓ 2단계의 여섯 갈래 — 부정형 / \(\exists\) / \(\forall\)\(\cdot\)총칭 / \(\lor\)\(\cdot\)\(\land\)\(\cdot\)”정확히 하나” / 자연수 전체의 \(\forall\) / 거짓인 \(\forall\) (각 1점)

✓ 3단계의 다섯 무대 — 나눗셈 \(\cdot\) 합동 \(\cdot\) 실수 부등식 \(\cdot\) 집합 포함 \(\cdot\) 데카르트 곱 (다섯을 묶어 1점)

평가 절차 8점. ✓ 걸음 ① 명제 진위 ✓ ② 논리 ✓ ③ 가정 사용 ✓ ④ 양화사와 자격 ✓ ⑤ 전달 (각 1점)

✓ 판정 낱말 셋 — 옳음 / 틀림(어느 줄이 왜) / 불완전(무엇이 빠졌는가) (각 1점)

주간 배분은 다음과 같다. 새 진도가 없으므로 제2권 5일 루틴의 원서 통독 자리가 재독으로 바뀐다.

요일

할 일

1일차

C5주차\(\cdot\)C6주차 재독

2일차

C7주차\(\cdot\)C8주차 재독

3일차

§1 암기 — 기법 지도와 증명 평가 다섯 걸음

4일차

1부 — 기법 지도 + 채점 복원 (40분)

5일차

2부 — 종합 시험 (150분)

2부 — 종합 시험 (20문항)#

이번 주의 채점 기준

증명 평가 문항의 답안은 판정 낱말 하나로 끝나지 않는다. “틀림”으로 판정했으면 어느

줄이 왜 틀렸는지 지목하고, “불완전”으로 판정했으면 무엇이 빠졌는지 적는다. 근거 없이

판정만 적은 채점표는 근거 없이 결론만 적은 증명과 같은 결함을 갖는다.

배점이 그 요구를 그대로 옮긴다 — 증명 평가 문항은 판정 낱말과 근거를 따로 채점하고

각각 절반을 배정한다. 판정만 맞고 근거가 비어 있으면 절반이다. 답이 아니라 근거가

점수다.

기본 ●○○ (각 1점)#

1. (판독 6연발 — 첫수 기법 이름만) 각 명제에 §1의 기법 지도를 적용해 첫수 기법을 지목하시오. (a) \(\sqrt7\)은 무리수이다. (b) 정수 \(n\)에 대해, \(n\)이 홀수이면 \(n^2 + 1\)이 짝수이다. (c) \(x^2 = 5\)인 실수가 존재한다. (d) 모든 자연수 \(n\)에 대해 \(\sum_{i=1}^n i = \frac{n(n+1)}2\). (e) 모든 정수 \(n\)에 대해 \(n^2 + n + 3\)이 짝수이다. (진리 상태 점검) (f) 어떤 두 무리수의 합은 유리수이다.

2. 자명한 증명과 공허한 증명의 정의를 쓰고, 각각의 예를 하나씩 만드시오.

3. 증명 평가 5단계를 쓰시오.

4. 합동의 대수 보존(덧셈\(\cdot\)곱셈\(\cdot\)거듭제곱)을 쓰고 \(3^{20} \pmod 4\)를 계산하시오.

5. 반례의 서식(부정 전개 + 구성)을 쓰고, “모든 소수는 홀수”를 반증하시오.

6. 최소 반례법 5단계를 쓰시오.

표준 ●●○ (각 2점) — 증명 평가 다수#

7. (증명) 정수 \(n\)에 대해, \(5n + 3\)이 짝수이면 \(n\)이 홀수임을 증명하시오 (대우).

8. (증명 평가) 다음을 평가하시오.

Result. 정수 \(a, b\)에 대해, \(a + b\)가 짝수이면 \(a\)와 \(b\)가 같은 홀짝이다.

증명. \(a = 2, b = 4\)이면 \(a + b = 6\) 짝수이고 둘 다 짝수. 따라서 성립.

9. (증명 평가) 다음을 평가하시오.

Result. \(\sqrt3\)은 무리수이다.

증명. \(\sqrt3 = \frac ab\)라 하자. 그러면 \(3b^2 = a^2\)이다. 따라서 \(a^2\)은 3의 배수이고 \(a\)도 3의 배수이다. \(a = 3c\)이면 \(3b^2 = 9c^2\), \(b^2 = 3c^2\)이라 \(b\)도 3의 배수. 모순.

10. (증명) 모든 자연수 \(n\)에 대해 \(2 \mid (n^2 + 3n)\)임을 증명하시오 (경우법 또는 인수분해).

11. (증명 평가) 다음을 평가하시오.

Result. 모든 실수 \(x\)에 대해, \(x^2 > 0\)이면 \(x \neq 0\)이다.

증명. \(x = 0\)이라 하자. 그러면 \(x^2 = 0\)이라 \(x^2 > 0\)이 거짓. 따라서 성립.

12. (증명) 어떤 유리수 \(r\)과 무리수 \(t\)에 대해 \(r + t\)가 무리수임을 증명하시오 — 정확히는 “모든 유리수 \(r\)과 무리수 \(t\)에 대해 \(r + t\)가 무리수” (귀류, C7주차).

13. (증명 평가) 다음을 평가하시오.

Result. 모든 자연수 \(n\)에 대해 \(n^2 + n\)이 짝수이다.

증명. 귀납. 기저 \(n=1\): \(2\) 짝수 ✓. 귀납: \((n+1)^2 + (n+1) = n^2 + 3n + 2 = (n^2 + n) + (2n + 2)\). \(n^2 + n\)은 가정으로 짝수, \(2n+2\)도 짝수, 합도 짝수. ✓

14. (증명) \(A \cap (B - A) = \emptyset\)임을 증명하시오 (원소 추적 — 공집합 증명은 귀류 또는 “원소가 없음”).

도전 ●●● (각 3점)#

15. (증명 평가 대작) 다음을 평가하시오 (여러 결함 가능).

Result. 정수 \(n\)에 대해, \(n^3\)이 짝수이면 \(n\)이 짝수이다.

증명. \(n^3\)이 짝수라 하자. \(n^3 = 2k\). 세제곱근을 취하면 \(n = \sqrt[3]{2k}\). 이것이 짝수이므로 \(n\)은 짝수이다.

16. (합동 종합) \(n\)이 양의 정수일 때 \(n^7 \equiv n \pmod 7\)을 \(n \in \{0, 1, \ldots, 6\}\)에서 확인하시오 (페르마 소정리 \(p=7\) — 각 나머지 계산; 일반형은 이 과정의 범위 밖이며 필요할 때 기성 정리로 인용한다).

17. (귀류 + 존재) \(\sqrt2 + \sqrt5\)가 무리수임을 증명하고, 별도로 “\(x^2 = 2 + \sqrt5\)인 실수가 존재한다”를 비구성적으로 논하시오 (전자: 제곱해 \(\sqrt{10}\) 고립; 후자: \(2 + \sqrt5 > 0\)이라 양의 제곱근 존재).

18. (강한 귀납) 모든 정수 \(n \ge 12\)가 \(4a + 5b\) (\(a, b \ge 0\) 정수) 꼴임을 증명하시오 (S14주차 문제 19\(\cdot\)C8주차 방식 — 기저 \(12,13,14,15\), \(n+1\)은 \(n-3\) 재활용).

19. (증명 평가 종합) 다음 세 제시를 각각 평가하시오.

(a) Result. \(x > 0\)이면 \(x^3 > 0\).

증명. \(x = 2\)면 \(8 > 0\) ✓, \(x = 5\)면 \(125 > 0\) ✓. 따라서 성립.

(b) Result. \(n\)이 3의 배수이면 \(n^2\)이 3의 배수.

증명. \(n = 3k\)면 \(n^2 = 9k^2 = 3(3k^2)\)이라 3의 배수. ✓

(c) Result. \(\sqrt2\)는 무리수.

증명. \(\sqrt2\)가 유리수면 \(\frac ab\) (기약). \(2b^2 = a^2\). \(a\) 짝수, \(a = 2c\). \(2b^2 = 4c^2\), \(b^2 = 2c^2\), \(b\) 짝수. 기약 모순. ✓

20. (서술) (a) Chartrand 전반부가 S17주차의 기법 선택 결정 나무를 어떻게 재조직했는지, 특히 “진리 상태 점검”(C5주차)과 “증명 평가”가 무엇을 더했는지 세 문장 이내로 쓰시오. (b) “채점 능력이 곧 자기 검증 능력”인 이유를 자신의 언어로 두 문장 이내로 쓰시오.

재학습 지도#

틀린 문항

복습

1, 20

기법 지도 (이 문서 §1)

2, 11

C5주차 (자명\(\cdot\)공허 증명, 대우의 판정)

3, 8, 9, 15, 19

C5주차 (증명 평가 다섯 걸음)

13

C5주차 (증명 평가) \(\cdot\) C8주차 (귀납의 서식)

4, 16

C6주차 (합동의 대수와 거듭제곱 보존)

5

C7주차 (반례 답안의 4단 서식)

6, 18

C8주차 (강한 귀납\(\cdot\)최소 반례법)

7

C5주차 (대우 증명)

12, 17

C7주차 (귀류\(\cdot\)존재)

10, 14

C6주차 (나눗셈\(\cdot\)집합의 원소 추적) \(\cdot\) 1권 17주차 (경우 나누기)

해설#

채점이 끝나기 전에는 열지 않는다. 1부의 정답지는 §1이며, 각 항목은 §1의 두 상자와 대조해 채점한다. 각 해설은 접근(문제 앞에서 무엇을 떠올리는가)과 풀이로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다.

문제 1#

접근. 여섯 명제 각각에 §1 지도의 1단계와 2단계를 차례로 적용한다. 요구된 것은 첫수 기법의 이름뿐이므로 계산은 한 줄도 하지 않는다. 계산을 시작했다면 문항이 요구한 범위를 벗어난 것이다. 1단계를 건너뛰면 (e)에서 걸리므로, 결론의 겉모양을 읽기 전에 “결론이 무대 전체에서 참인가 거짓인가”를 먼저 묻는 순서를 지킨다.

풀이. (a) 귀류. 결론에 부정형 낱말 “무리수”가 박혀 있어 부정 갈래로 내려가고, 명제가 조건문이 아니어서 뒤집을 가정이 없으므로 대우를 만들 자리가 없다. \(7\)이 소수이므로 C7주차 예제 2.2의 결과를 근거 ④로 인용해도 된다. (b) 직접 증명. 부정 신호가 없고 결론 “\(n^2+1\)이 짝수”는 숨은 \(\exists\)다 — \(n^2 + 1 = 2k\)인 정수 \(k\)의 존재. 가정을 정의로 펼쳐 \(n = 2k+1\)을 얻고 \(n^2 + 1 = 4k^2 + 4k + 2 = 2(2k^2 + 2k + 1)\)로 제작하면 끝난다. (c) 구성적 존재. 결론이 \(\exists\)이고 증인을 손으로 내놓을 수 있다. \(x = \sqrt5\)로 두고 자격(\(\sqrt5\)는 실수)과 사건(\((\sqrt5)^2 = 5\))을 확인한다. (d) 약한 귀납. 자연수 전체에 대한 \(\forall\)이고, \(n+1\)의 좌변이 \(n\)의 좌변에 항 하나를 더한 것이므로 직전 항에만 의존한다. (e) 반례. 1단계에서 걸린다. \(n^2 + n = n(n+1)\)은 연속한 두 정수의 곱이라 언제나 짝수이고, 따라서 \(n^2 + n + 3\)은 언제나 홀수다. 결론이 무대의 어떤 정수에서도 거짓이므로 명제 자체가 거짓이고, 첫수는 증명이 아니라 반례다. 아무 정수 하나를 대면 된다 — \(n = 1\)에서 \(5\)는 홀수다. (f) 구성적 존재. 결론이 \(\exists\)이고 증인이 손에 잡힌다. \(\sqrt2\)와 \(-\sqrt2\)가 증인이며 합은 \(0\)으로 유리수다.

복기. 여섯 중 (e)만 다른 갈래로 간 이유는 1단계를 실제로 돌렸기 때문이다. (d)의 무대는 자연수 전체이고 (e)의 무대는 정수 전체이지만, 겉모양은 똑같이 “모든 … \(n\)에 대해 …”이므로 2단계만 돌리면 둘 다 귀납으로 읽기 쉽다 — 지도의 귀납 갈래가 “자연수 전체에 대한 \(\forall\)”라 적혀 있어도, 겉모양만으로는 두 무대가 구별되지 않기 때문이다. 겉모양이 같은 두 명제를 갈라 놓는 것은 진리 상태 점검 하나뿐이다.

문제 2#

접근. 두 정의의 자리를 서로 대응시켜 외우면 헷갈리지 않는다. 검사 대상이 가정이면 공허, 결론이면 자명이다. 그리고 두 정의 모두 “무대 전체”를 요구한다는 조각을 빠뜨리지 않는다 — 사례 하나로는 어느 쪽도 선언할 수 없다.

풀이. 정의는 C5주차의 정의 1.1\(\cdot\)1.2다. 무대 \(S\)의 명제 “\(P(x)\)이면 \(Q(x)\)이다”에 대해, 자명한 증명이란 결론 \(Q(x)\)가 \(S\)의 모든 \(x\)에서 참임을 보이고 그것으로 명제의 증명을 삼는 것이다. 공허한 증명이란 가정 \(P(x)\)가 \(S\)의 어떤 \(x\)에서도 거짓임을 보이고 그것으로 명제의 증명을 삼는 것이다. 회수의 근거는 둘 다 1권 8주차의 조건문 진리표이며, 자명은 결론이 참인 행을, 공허는 가정이 거짓인 행을 인용한다.

예는 무대를 반드시 밝혀 만든다. 자명의 예 — 무대 \(\mathbb{R}\)에서 “\(x > 0\)이면 \(x^2 + 1 > 0\)이다”. 모든 실수에서 \(x^2 \ge 0\)이므로 \(x^2 + 1 \ge 1 > 0\)이고, 결론이 무대 전체에서 참이므로 가정을 쓰지 않고 명제가 증명된다. 공허의 예 — 무대 \(\mathbb{R}\)에서 “\(x^2 < 0\)이면 \(x = 5\)이다”. 모든 실수에서 \(x^2 \ge 0\)이므로 가정은 무대의 어떤 실수에서도 거짓이고, 결론을 보지 않고 명제가 증명된다.

복기. 두 예에서 실제로 논증한 문장은 각각 “모든 실수에서 \(x^2 + 1 > 0\)”과 “모든 실수에서 \(x^2 \ge 0\)” 하나뿐이다. 자명\(\cdot\)공허 증명의 노동은 전부 그 한 문장에 들어 있고, 나머지는 진리표 인용이다. 무대를 밝히지 않으면 이 한 문장이 무엇에 대한 주장인지 정해지지 않으므로 판정 자체가 성립하지 않는다.

문제 3#

접근. 순서에 뜻이 있으므로 순서대로 외운다. 명제 자체를 먼저 재고(①), 줄 사이 연결을 보고(②), 무엇을 증명했는지 묻고(③), 일반성을 검사하고(④), 마지막에 읽힘을 본다(⑤). 문항은 “5단계”라 적었고 C5주차는 “다섯 걸음”이라 부르지만 같은 절차다.

풀이. ① 명제 진위 — 명제 자체가 참인가. 거짓 명제에 붙은 증명은 반드시 틀렸다. ② 논리 — 각 줄이 앞 줄\(\cdot\)정의\(\cdot\)이미 증명한 명제에서 따라오는가. ③ 가정 사용 — 가정을 실제로 소비했는가. 소비하지 않았다면 자명한 증명인지, 아니면 다른 명제를 증명한 것인지 가른다. ④ 양화사와 자격 — 특정 값 몇 개로 전칭을 대신하지 않았는가, 문자에 붙은 자격을 지켰는가. ⑤ 전달 — 문자를 소개했는가, 완결된 문장인가.

판정 낱말은 셋이다. 틀림은 명제가 거짓이거나(①), 어느 줄이 앞 줄에서 따라오지 않거나(②), 요구된 명제가 아닌 다른 명제를 증명했을 때(③) 적는다. 불완전은 명제가 참이고 적힌 계산에 오류도 없는데 일반성이 없거나(④) 전달이 무너져(⑤) 증명이 되지 못했을 때 적는다. 옳음은 다섯 걸음을 모두 통과했을 때 적는다.

복기. 다섯 걸음을 한 줄로 줄이면 “무엇을, 어떻게, 무엇으로, 얼마나 넓게, 읽히게”다. 이 다섯 물음은 남의 답안에 돌리든 자기 답안에 돌리든 같으며, 지도의 4단계가 요구하는 것이 바로 후자다.

문제 4#

접근. 두 부분으로 된 문항이다. 앞은 C6주차의 합동의 대수 가운데 보존 규칙을 그대로 적는 일이고, 뒤는 그것을 계산 도구로 운용하는 일이다. 계산의 요령은 하나다 — 큰 수를 그와 합동인 작은 대표로 갈아 끼운다. 대표는 나머지일 필요가 없고, 계산이 쉬운 쪽을 고른다.

풀이. 보존 규칙은 다음 셋이다. 정수 \(a, b, c, d\)와 양의 정수 \(n\)에 대해, (C4) 합 보존 — \(a \equiv b\)이고 \(c \equiv d\)이면 \(a + c \equiv b + d \pmod n\)이다. (C5) 곱 보존 — \(a \equiv b\)이고 \(c \equiv d\)이면 \(ac \equiv bd \pmod n\)이다. 거듭제곱 보존 — \(a \equiv b \pmod n\)이면 모든 자연수 \(m\)에 대해 \(a^m \equiv b^m \pmod n\)이다. 셋째는 (C5)를 자기 자신에 반복 적용해 얻으며, 반복의 정당화는 귀납법으로 이미 끝나 있으므로 근거 ④로 인용한다.

계산은 대표를 \(-1\)로 잡는다. \(3 - (-1) = 4\)이고 \(4 \mid 4\)이므로 정의 6.2에 의해 \(3 \equiv -1 \pmod 4\)이다. 거듭제곱 보존에 의해

\[ 3^{20} \equiv (-1)^{20} = 1 \pmod 4 \]

이다. 따라서 \(3^{20}\)을 \(4\)로 나눈 나머지는 \(1\)이다.

복기. 대표를 \(3\) 그대로 두면 \(3^{20}\)을 직접 다뤄야 하지만, \(-1\)로 갈아 끼우면 지수가 짝수인지만 보면 된다. 검산은 작은 지수로 한다 — \(3^2 = 9 = 4 \cdot 2 + 1\)이므로 \(3^2 \equiv 1 \pmod 4\)이고, \(3^{20} = (3^2)^{10} \equiv 1^{10} = 1\)이다. 두 경로가 같은 답을 준다.

문제 5#

접근. 반례는 “예를 하나 들었다”가 아니라 부정 명제의 증명이다. 그러므로 답안의 첫 줄은 예가 아니라 무엇을 증명할지의 선언이어야 한다. C7주차의 4단 서식을 그대로 따르면 빠지는 칸이 없다.

풀이. 서식은 네 걸음이다. ① 부정 전개 — “명제가 거짓임을 보인다. 곧 가정을 만족하면서 결론을 위반하는 대상이 존재함을 증명한다”라고 선언한다. ② 증인 제시 — 값을 실제로 내놓는다. ③ 자격 검증 — 그 증인이 무대에 있고 가정을 만족함을 계산으로 보인다. ④ 사건 검증 — 그 증인에서 결론이 위반됨을 계산으로 보인다.

이제 “모든 소수는 홀수이다”를 반증한다. ① 이 명제가 거짓임을 보인다. 곧 소수이면서 홀수가 아닌 정수가 존재함을 증명한다. ② \(p = 2\)로 두자. ③ \(2\)의 양의 약수는 \(1\)과 \(2\)뿐이므로 \(2\)는 소수이고, 가정을 만족한다. ④ \(2 = 2 \cdot 1\)이므로 \(2\)는 짝수이고, 따라서 홀수가 아니다. 곧 결론이 위반된다. 그러므로 명제는 거짓이다. \(\blacksquare\)

복기. 걸음 ③을 빼면 무대 밖 대상이나 가정을 만족하지 않는 대상이 반례로 통과한다. 이 문항에서 ③에 해당하는 문장은 “\(2\)는 소수이다”이며, 이 한 줄이 없으면 답안은 “\(2\)는 짝수다”라는 참인 문장을 적었을 뿐 명제를 흔들지 못한다.

문제 6#

접근. 최소 반례법은 귀납의 귀류판이다. 그러므로 서식의 뼈대는 귀류의 4단(부정 가정 \(\to\) 유도 \(\to\) 모순 \(\to\) 회수)이고, 그 안에 최소원리가 들어와 “최소 반례보다 작은 곳은 전부 참”이라는 재료를 만들어 준다. 다섯 걸음을 외울 때 이 대응을 함께 붙여 두면 순서가 흔들리지 않는다.

풀이. ① \(P(n)\)이 거짓인 \(n\), 곧 반례가 있다고 가정한다(귀류의 개시). ② 반례들의 모임은 공집합이 아니고 아래로 유계인 정수 집합이므로, 최소원리에 의해 최소 반례 \(m\)이 존재한다(C8주차 정의 8.3의 걸음 ②). 무대가 자연수로 한정되지 않으므로 “자연수의 부분집합이라서”로 줄여 적으면 \(n_0\)이 \(0\) 이하인 명제에서 근거가 성립하지 않는다. ③ \(m > n_0\)임을 보인다 — 기저에서 \(n_0\)은 반례가 아님이 확인되므로 최소 반례가 \(n_0\)일 수는 없다. 그리고 \(m\)의 최소성에서 \(P(m-1)\)(또는 \(m\)보다 작은 것들 전부)이 참임을 얻는다. ④ 그 재료로 \(P(m)\)을 유도해 “\(m\)이 반례”와 모순을 만든다. ⑤ 따라서 반례는 없고, 모든 \(n\)에 대해 \(P(n)\)이 참이다.

복기. 걸음 ③이 두 가지 일을 한꺼번에 한다는 점이 이 서식의 요령이다 — 기저를 소비해 최소 반례의 위치를 \(n_0\) 위로 밀어 올리고, 동시에 최소성으로부터 귀납 가정에 해당하는 재료를 얻는다. 약한 귀납의 “기저 + \(P(n) \Rightarrow P(n+1)\)”이 여기서 “\(n_0\)은 반례가 아님 + 최소 반례에서 모순”으로 뒤집혀 나타난다.

문제 7#

접근. 결론 “\(n\)이 홀수”는 숨은 \(\exists\)이므로 직접 증명도 가능해 보이지만, 가정 “\(5n+3\)이 짝수”에서 \(n\)의 꼴을 뽑아내려면 나눗셈이 필요하다. 반면 대우를 잡으면 가정이 “\(n\)이 짝수”가 되어 \(n = 2k\)라는 등식이 곧바로 손에 들어온다. 가정 쪽에 정의를 펼칠 등식이 생기는 방향을 고르는 것이 판정 기준이다.

풀이. 대우를 증명한다. 대우는 “\(n\)이 홀수가 아니면 \(5n+3\)이 짝수가 아니다”, 곧 “\(n\)이 짝수이면 \(5n+3\)이 홀수이다”이다.

\(n\)을 짝수인 정수라 하자. 정의에 의해 \(n = 2k\)인 정수 \(k\)가 존재한다. 그러면

\[ 5n + 3 = 5(2k) + 3 = 10k + 3 = 2(5k + 1) + 1 \]

이다. \(k\)가 정수이므로 \(5k + 1\)도 정수이고(근거 ②), 따라서 \(5n + 3\)은 홀수의 정의를 만족한다. 대우가 증명되었으므로 원명제도 참이다. \(\blacksquare\)

복기. 핵심 변형은 \(10k + 3\)을 \(2(5k+1) + 1\)로 묶는 한 줄이다. 정의가 요구하는 꼴이 \(2 \times (\text{정수}) + 1\)이므로, \(3\)을 \(2 + 1\)로 쪼개 앞의 \(2\)를 괄호 안으로 보내는 조작이 필요하다. 검산은 \(k = 3\)으로 한다 — \(n = 6\)이면 \(5n + 3 = 33 = 2 \cdot 16 + 1\)이고 \(5k + 1 = 16\)이다.

문제 8#

접근. 제시된 답안이 다룬 것은 정수 쌍 하나뿐인데 명제는 모든 정수 쌍에 대한 전칭이다. 다섯 걸음 중 ④가 정확히 이 어긋남을 잡는다. 판정 낱말을 고를 때는 “적힌 것 중 거짓이 있는가”를 먼저 묻는다 — 없으면 틀림이 아니라 불완전이다.

풀이. 판정은 불완전이다. 걸린 걸음은 ④ 양화사와 자격이다. 명제는 참이고(① 통과), \(a = 2, b = 4\)에서 \(a+b = 6\)이 짝수이며 둘 다 짝수라는 계산에도 거짓인 문장은 없다(② 통과). 그러나 확인된 것은 무수히 많은 정수 쌍 가운데 한 쌍뿐이고, 나머지 전부에 대한 논증이 없다. 채점표에는 “임의의 정수 쌍을 잡는 첫 문장이 없다”라고 적는다.

올바른 답안은 대우와 경우 나누기로 만든다. 대우는 “\(a\)와 \(b\)가 다른 홀짝이면 \(a+b\)가 홀수이다”이다. \(a\)와 \(b\)가 다른 홀짝인 정수라 하자. 경우 1: \(a\)가 짝수이고 \(b\)가 홀수라 하자. 정의에 의해 \(a = 2k\), \(b = 2l+1\)인 정수 \(k, l\)이 존재하므로 \(a + b = 2k + 2l + 1 = 2(k+l) + 1\)이고, \(k+l\)이 정수이므로 \(a+b\)는 홀수다. 경우 2: \(a\)가 홀수이고 \(b\)가 짝수라 하자. \(a = 2k+1\), \(b = 2l\)이므로 \(a + b = 2(k+l) + 1\)로 같은 결론에 닿는다. “다른 홀짝”은 이 두 경우로 빠짐없이 덮이므로 대우가 증명되었고, 원명제도 참이다. \(\blacksquare\)

복기. 대우를 쓰지 않는 경로도 있다. \(a + b = 2m\)이라 하면 \(a - b = (a+b) - 2b = 2m - 2b = 2(m-b)\)이므로 차도 짝수이고, 차가 짝수인 두 정수는 같은 홀짝이다. 어느 경로든 답안의 첫 문장이 “임의의 정수 \(a, b\)를 잡자”로 시작한다는 점이 제시된 답안과의 결정적 차이다.

문제 9#

접근. 귀류법 답안의 채점에서 가장 먼저 보는 자리는 마지막 줄이다 — 유도된 결과가 정말로 앞에 놓인 가정과 충돌하는가. 이 답안은 “\(a\)도 3의 배수, \(b\)도 3의 배수”를 유도한 뒤 “모순”이라 적는다. 그 두 문장이 서로 충돌하려면 시작 줄에 무엇이 있어야 했는지를 묻는다.

풀이. 판정은 틀림이다. 걸린 걸음은 ②이고, 어긋난 줄은 마지막 “모순” 한 줄이다.

개시 줄에 기약 조건이 없다. “\(\sqrt3 = \frac ab\)라 하자”에는 \(a\)와 \(b\)가 서로소라는 조건이 붙어 있지 않으므로, “\(a\)도 3의 배수이고 \(b\)도 3의 배수”라는 유도 결과는 아무것과도 충돌하지 않는다. \(a = 6\), \(b = 6\)처럼 둘 다 3의 배수인 정수 쌍은 얼마든지 있다. 곧 마지막 “모순”은 앞 줄에서 따라오지 않으며, 이것이 걸음 ②가 잡는 결함이다. 채점표에는 “어느 줄이 왜”를 적는다 — “마지막 줄 ‘모순’이 앞 줄에서 따라오지 않는다. 개시 줄에 기약 조건이 없으므로 ‘a도 3의 배수, b도 3의 배수’는 아무것과도 충돌하지 않는다.”

부수 결함이 하나 더 있다. “\(a^2\)이 3의 배수이면 \(a\)도 3의 배수”는 유클리드 보조정리(\(p = 3\))이며 근거 ④로 인용해야 하는 기성 결과인데 아무 표시 없이 쓰였고, \(b\)에 대한 같은 단계도 마찬가지다. 다만 미인용 기성 정리는 그 자체로 판정을 바꾸지 않는 근거 표시 보완이다 — 같은 결함만 가진 문제 19(c)의 판정이 옳음(보완 필요)인 것이 그 증거다. 이 답안의 판정을 정한 것은 기약 조건 누락 하나다.

문제 8\(\cdot\)19(a)의 “불완전”과 갈리는 자리가 여기다. 그쪽은 적힌 줄이 모두 참이고 빠진 것이 일반 논증뿐이지만, 이 답안은 실제로 적힌 마지막 줄 자체가 근거 없는 주장이다. 앞 줄에서 따라오지 않는 줄이 답안에 남아 있으면, 빠진 것을 채우는 문제가 아니라 적힌 것을 지목하는 문제이므로 판정은 틀림이다.

결함을 고친 답안은 다음과 같다. \(\sqrt3\)이 유리수라 가정하자. 그러면 \(\sqrt3 = \frac ab\)인 정수 \(a\)와 0이 아닌 정수 \(b\)가 존재하고, 약분하여 \(a\)와 \(b\)는 서로소라 잡을 수 있다. 양변을 제곱하고 \(b^2\)을 곱하면 \(a^2 = 3b^2\)이다. 따라서 \(3 \mid a^2\)이고, 유클리드 보조정리(\(p=3\))에 의해 \(3 \mid a\)이다. \(a = 3c\)인 정수 \(c\)를 잡으면 \(9c^2 = 3b^2\), 곧 \(b^2 = 3c^2\)이므로 \(3 \mid b^2\)이고 다시 보조정리로 \(3 \mid b\)이다. 그런데 \(a\)와 \(b\)를 서로소로 잡았으므로 둘이 공약수 \(3\)을 가질 수는 없다 — 모순이다. 따라서 \(\sqrt3\)은 무리수이다. \(\blacksquare\)

복기. 무리수 명제의 귀류에서 모순의 산지는 언제나 개시 줄에 심어 둔 조건이다. 기약 조건은 답안을 다듬는 장식이 아니라 마지막 줄의 근거이며, 그것을 빠뜨린 답안은 마지막 줄만 근거를 잃는 것이 아니라 증명 전체가 아무것도 결론짓지 못한다.

문제 10#

접근. 결론 “\(2 \mid (n^2+3n)\)”은 숨은 \(\exists\)다 — \(n^2 + 3n = 2k\)인 정수 \(k\)의 존재. 그러므로 후진면이 요구하는 것은 “\(2 \times (\text{정수})\)” 꼴의 제작이다. 가정에는 \(n\)의 홀짝에 대한 정보가 없으므로 그 정보를 스스로 만들어야 하고, 그 장치가 경우 나누기다.

풀이. \(n\)을 자연수라 하자. \(n^2 + 3n = n(n+3)\)이다. \(n\)의 홀짝으로 경우를 나눈다.

경우 1: \(n\)이 짝수라 하자. 정의에 의해 \(n = 2k\)인 정수 \(k\)가 존재하므로 \(n(n+3) = 2k(n+3) = 2\bigl(k(n+3)\bigr)\)이고, \(k(n+3)\)은 정수이므로(근거 ②) \(2 \mid (n^2+3n)\)이다.

경우 2: \(n\)이 홀수라 하자. \(n = 2k+1\)인 정수 \(k\)가 존재하므로 \(n + 3 = 2k + 4 = 2(k+2)\)이고, 따라서 \(n(n+3) = 2\bigl(n(k+2)\bigr)\)이며 \(n(k+2)\)는 정수다. 곧 \(2 \mid (n^2+3n)\)이다.

모든 자연수는 짝수이거나 홀수이므로 두 경우가 전체를 빠짐없이 덮고, 어느 경우든 결론이 성립한다. \(\blacksquare\)

복기. 경우를 나누지 않는 경로도 있다. \(n^2 + 3n = (n^2 + n) + 2n = n(n+1) + 2n\)이고 \(n(n+1)\)은 연속한 두 정수의 곱이라 짝수이므로, 짝수 둘의 합으로 결론이 나온다. 어느 경로를 택하든 답안에 반드시 남겨야 하는 문장은 전수성 확인 — “모든 자연수는 짝수이거나 홀수이다” — 이다. 이 한 줄이 없으면 두 계산은 두 개의 특수 사례로 읽힌다(1권 17주차).

문제 11#

접근. 제시된 답안이 첫 줄에서 “\(x = 0\)이라 하자”라고 적은 것을 보고 곧바로 “결론을 가정했다”고 판정하기 쉽다. 그러나 \(x = 0\)은 결론이 아니라 결론의 부정이다. 걸음 ③은 “무엇을 증명했는가”를 묻는 걸음이므로, 이 답안이 실제로 증명한 명제가 무엇인지 먼저 적어 보고 그것이 원명제의 대우인지 확인한다.

풀이. 판정은 **옳음(전달 보완 필요)**이다. 원명제는 “\(x^2 > 0\)이면 \(x \neq 0\)이다”이고, 그 대우는 “\(x = 0\)이면 \(x^2 > 0\)이 아니다”이다. 제시된 답안은 \(x = 0\)을 가정해 \(x^2 = 0\)을 얻고 그로부터 “\(x^2 > 0\)이 거짓”을 유도했으므로, 정확히 그 대우를 증명했다. 걸음 ①~④는 통과한다 — 명제는 참이고, 각 줄이 앞 줄에서 따라오며, 가정에 해당하는 \(x = 0\)을 실제로 소비했고, 특정 값 몇 개로 전칭을 대신하지도 않았다.

남는 것은 걸음 ⑤다. 답안 어디에도 “대우를 증명한다”는 선언이 없고, 마지막의 “따라서 성립”이 무엇에서 무엇으로 건너간 것인지 적혀 있지 않다. 그런데 빠진 것은 그 선언 한 줄뿐이고, 그 한 줄은 답안의 흐름에서 유일하게 복원된다 — 결론의 부정 \(x = 0\)만 가정해 \(x^2 > 0\)의 부정을 유도한 형태는 대우 외에 달리 읽을 수 없다. 빠진 문장을 읽는 쪽이 유일하게 복원할 수 있으므로 판정은 불완전이 아니라 옳음(보완 필요)이다(C5주차 §1.6의 판정 규칙). 복원이 유일하지 않은 경우는 다르다 — 문제 13처럼 무엇에 대한 귀납인지조차 적히지 않은 표기 결함이 여럿 겹치면 채점자가 재구성한 문장이 답안에 있는 문장과 같다는 보장이 사라진다. 보완한 형태는 다음과 같다 — “대우를 증명한다. 대우는 ‘\(x = 0\)이면 \(x^2 > 0\)이 아니다’이다. \(x = 0\)이라 하자. 그러면 \(x^2 = 0\)이므로 \(x^2 > 0\)이 거짓이다. 대우가 증명되었으므로 원명제도 참이다.”

복기. 대우 증명과 귀류 증명은 첫 줄의 겉모양이 비슷해 채점에서 자주 뒤섞인다. 가르는 기준은 하나다 — 결론의 부정만 가정했으면 대우이고, 가정과 결론의 부정을 함께 놓았으면 귀류다. 이 답안은 \(x^2 > 0\)을 가정 목록에 올린 적이 없으므로 대우다.

문제 12#

접근. 결론 “\(r+t\)가 무리수”는 부정형이다. 부정형 결론에는 만들 등식이 없으므로 직접 증명이 시작되지 않는다. 지도의 2단계가 지목하는 처방은 둘 — 대우 또는 귀류다. 여기서는 부정을 가정 목록에 올리는 순간 “\(r+t\)는 유리수”라는 등식이 손에 들어오므로 귀류가 유리하다.

풀이. \(r\)을 유리수, \(t\)를 무리수라 하고, 결론을 부정해 \(r + t\)가 유리수라 가정하자. 그러면

\[ t = (r + t) - r \]

이고, 우변은 유리수에서 유리수를 뺀 것이다. 유리수의 차는 유리수이므로(두 유리수를 \(\frac pq\)와 \(\frac uv\)로 쓰면 차는 \(\frac{pv - uq}{qv}\)이고 분모가 0이 아닌 분수 꼴이다) \(t\)는 유리수다. 이것은 \(t\)가 무리수라는 가정과 충돌한다. 따라서 가정이 틀렸고, \(r + t\)는 무리수이다. \(r\)과 \(t\)가 임의였으므로 모든 유리수 \(r\)과 무리수 \(t\)에서 성립한다. \(\blacksquare\)

복기. 모순의 산지는 “유도한 것 \(\leftrightarrow\) 원래 가정”이다 — 새로 얻은 “\(t\)는 유리수”가 문제에 주어진 “\(t\)는 무리수”와 부딪힌다. 이 형태에서 실제로 한 일은 등식 하나를 옮겨 쓴 것뿐이며, 무리수를 다루는 답안이 계산을 시작할 수 있게 만든 것은 귀류의 개시 줄이다. 곱셈판(“0이 아닌 유리수 \(r\)과 무리수 \(t\)에 대해 \(rt\)는 무리수”)도 \(t = \frac{rt}r\)로 같은 구조를 따르며, 이때 \(r \neq 0\)이라는 조건이 왜 필요한지가 그대로 드러난다.

문제 13#

접근. 귀납 답안의 채점은 세 자리를 본다 — 기저가 실제로 확인되었는가, 귀납 가정이 어디서 소비되었는가, 그리고 \(n+1\)의 식을 \(n\)의 식이 드러나도록 쪼갰는가. 세 자리를 차례로 짚은 뒤에 걸음 ⑤로 넘어간다.

풀이. 판정은 옳음이다. 기저는 \(n = 1\)에서 \(1^2 + 1 = 2\)가 짝수임을 확인했고, 귀납 단계는 \((n+1)^2 + (n+1) = n^2 + 3n + 2\)를 \((n^2+n) + (2n+2)\)로 쪼개 앞 덩어리를 귀납 가정으로 소비했다. 전개도 맞다 — \((n+1)^2 + (n+1) = n^2 + 2n + 1 + n + 1 = n^2 + 3n + 2\)이고, \((n^2+n) + (2n+2)\) 역시 같은 식이다. 뒤 덩어리 \(2n+2 = 2(n+1)\)은 짝수이고, 짝수 둘의 합은 짝수이므로 \(P(n+1)\)이 얻어진다. 다섯 걸음 모두 통과한다.

보완할 곳은 걸음 ⑤ 하나다. “귀납.”, “\(2\) 짝수 ✓” 같은 표기는 완결된 문장이 아니고, 무엇에 대한 귀납인지(\(n\)에 대한 귀납법인지) 선언되어 있지 않으며, 짝수 둘의 합이 짝수라는 사용된 근거도 문면에 없다. 수학은 그대로 두고 문장만 세우면 그대로 모범 답안이 된다.

복기. 이 명제는 귀납을 쓰지 않고도 증명된다 — \(n^2 + n = n(n+1)\)은 연속한 두 정수의 곱이므로 짝수다. 그러나 “더 짧은 증명이 있다”는 것은 제시된 답안의 흠이 아니다. 채점은 제출된 논증이 명제를 증명하는가만 묻고, 다른 경로의 존재는 판정에 들어가지 않는다.

문제 14#

접근. 결론이 “\(= \emptyset\)”이라는 부재 주장이므로 부정형이다. 부재를 보이는 길은 둘 — 원소를 하나 잡아 모순을 내는 귀류, 또는 “임의의 \(x\)에 대해 \(x \notin A \cap (B-A)\)”를 직접 보이는 것이다. 어느 쪽이든 3단계의 무대는 집합이고, 펼칠 정의는 교집합과 차집합의 원소 조건이다.

풀이. 귀류로 증명한다. \(A \cap (B - A) \neq \emptyset\)이라 가정하면, 그 집합에 속하는 원소 \(x\)를 잡을 수 있다. 교집합의 정의에 의해 \(x \in A\)이고 \(x \in B - A\)이다. 차집합의 정의에 의해 \(x \in B - A\)는 “\(x \in B\)이고 \(x \notin A\)”를 뜻하므로, 특히 \(x \notin A\)이다. 그런데 앞에서 \(x \in A\)를 얻었다 — \(x \in A\)이면서 \(x \notin A\)인 대상이 있다는 것이므로 모순이다. 따라서 가정이 틀렸고 \(A \cap (B - A) = \emptyset\)이다. \(\blacksquare\)

복기. 모순의 산지는 “유도한 것 \(\leftrightarrow\) 유도한 것”이다. 충돌하는 두 문장이 모두 개시 이후에 만들어졌고, 둘 다 정의를 한 번씩 펼쳐 얻은 것이다. 가정에 아무 조건도 붙지 않은 \(B\)가 결론에 영향을 주지 않는다는 점도 답안이 보여 준다 — \(x \in B\)는 한 번 얻어지고 끝까지 쓰이지 않는다. 이는 명제가 임의의 집합 \(B\)에서 성립함을 뜻하고, 답안이 실제로 소비한 것은 차집합 정의의 \(x \notin A\) 조각뿐이다.

문제 15#

접근. 결함이 여럿일 수 있다는 단서가 붙었으므로 다섯 걸음을 처음부터 끝까지 돌린다. 명제 자체는 참이므로 걸음 ①은 통과한다. 문제는 줄 사이의 연결이며, 특히 “이것이 짝수이므로”라는 구절이 어디서 왔는지를 묻는 자리에서 답안이 무너진다.

풀이. 판정은 틀림이다. 걸린 걸음은 ②이고, 어긋난 줄은 마지막 줄이다.

\(n^3 = 2k\)에서 세제곱근을 취해 \(n = \sqrt[3]{2k}\)를 얻은 것까지는 실수 안에서 참이다. 그러나 “이것이 짝수이므로”에는 근거가 하나도 없다. \(\sqrt[3]{2k}\)라는 표현이 정수인지조차 이 답안 안에서는 보장되지 않고(\(k = 1\)이면 \(\sqrt[3]{2}\)는 정수가 아니다), 정수라 하더라도 그것이 짝수라는 것은 바로 이 문항이 증명하라고 요구한 결론 자체다. 곧 결론을 근거로 삼아 결론을 얻었다. 덧붙여 걸음 ⑤도 걸린다 — \(k\)가 어떤 자격의 수인지 소개되지 않았다.

올바른 답안은 대우로 만든다. 대우는 “\(n\)이 홀수이면 \(n^3\)이 홀수이다”이다. \(n\)을 홀수인 정수라 하자. 정의에 의해 \(n = 2k+1\)인 정수 \(k\)가 존재한다. 그러면

\[ n^3 = (2k+1)^3 = 8k^3 + 12k^2 + 6k + 1 = 2(4k^3 + 6k^2 + 3k) + 1 \]

이고, \(4k^3 + 6k^2 + 3k\)는 정수이므로 \(n^3\)은 홀수다. 대우가 증명되었으므로 원명제도 참이다. \(\blacksquare\)

복기. 이 답안이 무너진 지점은 계산이 아니라 방향이다. 가정 “\(n^3\)이 짝수”에서 \(n\)의 꼴로 내려가는 통로가 없다는 것이 이 명제의 어려움이고, 대우를 잡으면 가정 쪽에 \(n = 2k+1\)이라는 등식이 생겨 통로가 열린다. 근호나 세제곱근으로 정수 세계를 빠져나가는 조작은, 나온 값이 다시 정수라는 보장을 답안이 스스로 대야 한다.

문제 16#

접근. \(2^7 = 128\)부터 \(6^7 = 279936\)까지를 직접 나누는 것도 답이지만, 그것은 합동을 쓰지 않은 계산이다. 문항이 “합동 종합”인 이유는 큰 수를 작은 대표로 갈아 끼우는 절차를 보라는 것이다. \(n^7 = n \cdot (n^3)^2\)으로 쪼개면 \(n^3\)의 나머지만 알면 되고, \(n^3\)은 손으로 계산할 수 있는 크기다. 문항이 “양의 정수”라 적었으나 확인 범위에 \(0\)이 들어 있으므로, \(0\)은 나머지 \(0\)의 대표로 함께 확인한다.

풀이. 쓸 근거는 C6주차의 곱 보존 (C5)와 거듭제곱 보존이다. 모든 \(n\)에 대해 \(n^7 = n \cdot (n^3)^2\)으로 쪼개고 \(n^3\)을 먼저 잰다.

\(n = 0\): \(0^7 = 0 \equiv 0 \pmod 7\)이다.

\(n = 1\): \(1^7 = 1 \equiv 1 \pmod 7\)이다.

\(n = 2\): \(2^3 = 8 = 7 + 1\)이므로 \(2^3 \equiv 1 \pmod 7\)이다. 거듭제곱 보존으로 \((2^3)^2 \equiv 1\)이고, 곱 보존으로 \(2^7 = 2 \cdot (2^3)^2 \equiv 2 \cdot 1 = 2 \pmod 7\)이다.

\(n = 3\): \(3^3 = 27 = 21 + 6\)이므로 \(3^3 \equiv 6 \equiv -1 \pmod 7\)이다. 따라서 \((3^3)^2 \equiv (-1)^2 = 1\)이고, \(3^7 \equiv 3 \cdot 1 = 3 \pmod 7\)이다.

\(n = 4\): \(4^3 = 64 = 63 + 1\)이므로 \(4^3 \equiv 1 \pmod 7\)이고, \(4^7 \equiv 4 \cdot 1 = 4 \pmod 7\)이다.

\(n = 5\): \(5^3 = 125 = 119 + 6\)이므로 \(5^3 \equiv 6 \equiv -1 \pmod 7\)이고, \(5^7 \equiv 5 \cdot 1 = 5 \pmod 7\)이다.

\(n = 6\): \(6 \equiv -1 \pmod 7\)이므로 거듭제곱 보존으로 \(6^7 \equiv (-1)^7 = -1 \equiv 6 \pmod 7\)이다.

일곱 나머지 전부에서 \(n^7 \equiv n \pmod 7\)이 확인되었다.

복기. 검산은 직접 나눗셈으로 한다 — \(2^7 = 128 = 7 \cdot 18 + 2\), \(3^7 = 2187 = 7 \cdot 312 + 3\), \(4^7 = 16384 = 7 \cdot 2340 + 4\), \(5^7 = 78125 = 7 \cdot 11160 + 5\)로 모두 일치한다. 확인한 것은 \(0\)부터 \(6\)까지 일곱 개뿐이지만, 임의의 정수는 그중 하나와 법 \(7\)에 대해 합동이고 거듭제곱 보존이 그 합동을 \(n^7\)까지 옮겨 주므로 이 일곱 줄이 실제로는 모든 정수를 덮는다. 같은 문항의 \(p = 5\) 판이 C6주차 문제 12이며, 일반형 “\(a^p \equiv a \pmod p\)”(페르마 소정리)의 증명은 이 과정의 범위 밖이다 — 필요할 때는 기성 정리로 인용하고, 이 문항이 확인한 것은 \(p = 7\) 사례 하나다.

문제 17#

접근. 두 부분은 서로 다른 도구를 쓴다. 앞은 부정형 결론이므로 귀류이고, 요령은 제곱해서 무리수 조각 하나만 남기는 것이다. 뒤는 \(\exists\) 결론이므로 존재 증명이며, 증인을 손으로 만들지 않고 기성 정리로 있음만 보장하는 형태다. 앞 부분에서 \(\sqrt{10}\)의 무리성을 인용하려면 \(10\)이 소수가 아니므로 C7주차 예제 2.2를 그대로 쓸 수 없고, 그 한 줄을 따로 증명해야 한다.

풀이. 먼저 보조 사실을 증명한다. \(\sqrt{10}\)은 무리수이다. 유리수라 가정하면 \(\sqrt{10} = \frac ab\)인 정수 \(a\)와 0이 아닌 정수 \(b\)가 존재하고, 약분하여 서로소라 잡을 수 있다. 제곱하면 \(a^2 = 10b^2\)이므로 \(a^2\)은 짝수이고, 따라서 \(a\)도 짝수다(대우: \(a\)가 홀수면 \(a^2\)이 홀수). \(a = 2c\)를 넣으면 \(4c^2 = 10b^2\), 곧 \(2c^2 = 5b^2\)이다. 좌변이 짝수이므로 \(5b^2\)이 짝수이고, \(5\)가 홀수이므로 \(b^2\)이 짝수이며 따라서 \(b\)도 짝수다. 그러면 \(a\)와 \(b\)가 공약수 \(2\)를 가져 서로소라는 설정과 모순이다. 그러므로 \(\sqrt{10}\)은 무리수이다.

이제 본증명이다. \(s = \sqrt2 + \sqrt5\)가 유리수라 가정하자. 양변을 제곱하면

\[ s^2 = 2 + 2\sqrt2\sqrt5 + 5 = 7 + 2\sqrt{10} \]

이므로 \(\sqrt{10} = \dfrac{s^2 - 7}2\)이다. 우변은 유리수의 제곱에서 유리수를 뺀 뒤 유리수로 나눈 것이므로 유리수다. 그런데 방금 \(\sqrt{10}\)이 무리수임을 증명했으므로 모순이다. 따라서 \(\sqrt2 + \sqrt5\)는 무리수이다. \(\blacksquare\)

존재 부분은 다음과 같다. \(\sqrt5 > 0\)이므로 \(2 + \sqrt5 > 0\)이다. “임의의 양의 실수 \(a\)에 대해 \(x^2 = a\)인 양의 실수 \(x\)가 존재한다”는 실수의 완비성에서 나오는 기성 정리이며, S13주차 문제 11과 S17주차 문제 18도 이 존재를 증명한 것이 아니라 같은 자격으로 인정하고 쓴 뒤 유일성만 다뤘다. 이 정리를 \(a = 2 + \sqrt5\)에 특수화하면 \(x^2 = 2 + \sqrt5\)인 양의 실수 \(x\)가 존재한다. \(\blacksquare\)

복기. 앞부분의 요령은 제곱 한 번으로 두 근호를 하나로 줄인 것이다 — \(\sqrt2\)와 \(\sqrt5\)를 각각 상대하려 하면 어느 쪽도 고립되지 않지만, 제곱하면 교차항에 \(\sqrt{10}\) 하나만 남고 나머지는 정수가 된다. 뒷부분이 비구성적이라 불리는 이유는 존재의 근거가 값의 제시가 아니라 실수 체계의 정리이기 때문이다. 기호 \(\sqrt{2+\sqrt5}\)를 적을 수는 있으나, 그 기호가 가리키는 실수가 있다는 것 자체를 보장하는 것이 바로 인용한 정리다.

문제 18#

접근. \(n+1\)을 만들려면 \(4\)를 더할지 \(5\)를 더할지 정해야 하고, \(4\)를 더한다면 필요한 것은 \(P(n)\)이 아니라 \(P(n-3)\)이다. 곧 \(P(n+1)\)을 만드는 데 쓰는 것이 \(P(n)\)이 아니라 \(P(n-3)\), 결론에서 네 칸 아래의 항이므로 직전 항만 쓰는 약한 귀납이 아니라 강한 귀납이고, 참조 거리가 \(4\)이므로 기저도 네 개가 필요하다. 기저 개수를 정하는 근거를 답안에 적는 것까지가 이 문항의 요구다.

풀이. \(P(n)\)을 “\(n = 4a + 5b\)인 음이 아닌 정수 \(a, b\)가 존재한다”로 두고, \(n \ge 12\)에 대해 강한 귀납법으로 증명한다.

기저. \(12 = 4 \cdot 3 + 5 \cdot 0\), \(13 = 4 \cdot 2 + 5 \cdot 1\), \(14 = 4 \cdot 1 + 5 \cdot 2\), \(15 = 4 \cdot 0 + 5 \cdot 3\)이므로 \(P(12), P(13), P(14), P(15)\)가 모두 참이다.

귀납 단계. \(n \ge 15\)라 하고, \(12\)부터 \(n\)까지의 모든 정수에서 \(P\)가 참이라고 가정하자. \(n \ge 15\)이므로 \(n - 3 \ge 12\)이고, \(n - 3 \le n\)이므로 \(n-3\)은 가정의 범위 안에 있다. 강한 귀납 가정에 의해 \(n - 3 = 4a + 5b\)인 음이 아닌 정수 \(a, b\)가 존재한다. 양변에 \(4\)를 더하면

\[ n + 1 = 4a + 5b + 4 = 4(a+1) + 5b \]

이고, \(a + 1\)과 \(b\)는 음이 아닌 정수이므로 \(P(n+1)\)이 참이다.

기저와 귀납 단계에 의해 \(12\) 이상의 모든 정수 \(n\)에서 \(P(n)\)이 참이다. \(\blacksquare\)

복기. 기저를 네 개 잡은 근거는 귀납 단계가 \(n-3\)을 참조한다는 사실 하나다. 기저가 \(12\) 하나뿐이면 \(P(16)\)은 \(P(12)\)로 만들어져 넘어가지만 \(P(17)\)에서 막힌다 — 그때 필요한 \(P(13)\)이 확보되지 않기 때문이다. 네 대응을 나란히 적으면 기저가 정확히 네 개 필요한 이유가 그대로 보인다 — \(P(16) \leftarrow P(12)\), \(P(17) \leftarrow P(13)\), \(P(18) \leftarrow P(14)\), \(P(19) \leftarrow P(15)\)이고, \(P(20)\)부터는 앞의 넷이 재료를 대 준다. 참조 거리가 \(k\)인 구조에서는 기저도 \(k\)개가 필요하며, 이 대응이 강한 귀납 답안에서 가장 자주 비는 칸이다. 같은 명제가 S14주차 문제 19와 1권 33주차 문제 12에 있고, 검산은 \(n = 23\)으로 한다 — \(23 - 3 = 20 = 4 \cdot 5\)이므로 \(24 = 4 \cdot 6\)이다.

문제 19#

접근. 세 제시를 같은 순서로, 각각 다섯 걸음을 돌려 판정한다. 판정 낱말을 고르기 전에 “적힌 것 중 거짓인 문장이 있는가”를 먼저 묻는다 — 없으면 틀림이 아니다. 셋 다 명제 자체는 참이므로 걸음 ①은 모두 통과하고, 갈리는 자리는 ④와 ⑤다.

풀이.

(a) 판정은 불완전이고, 걸린 걸음은 ④다. \(x = 2\)에서 \(8 > 0\), \(x = 5\)에서 \(125 > 0\)은 둘 다 참인 계산이므로 거짓인 문장은 없다. 그러나 명제는 양의 실수 전체에 대한 전칭이고, 확인된 것은 두 값뿐이다. 나머지 전부에 대한 논증이 빠졌다. 올바른 답안은 임의로 잡는다 — \(x > 0\)인 실수 \(x\)를 임의로 잡자. 양수끼리의 곱은 양수이므로 \(x^2 = x \cdot x > 0\)이고, 다시 양수끼리의 곱이므로 \(x^3 = x^2 \cdot x > 0\)이다. \(x\)가 임의였으므로 모든 양의 실수에서 성립한다.

(b) 판정은 옳음이다. 가정 “\(n\)이 3의 배수”를 정의로 펼쳐 \(n = 3k\)를 얻고, \(n^2 = 9k^2 = 3(3k^2)\)로 결론이 요구하는 “\(3 \times (\text{정수})\)” 꼴을 제작했다. 가정을 실제로 소비했고(③), 특정 값을 쓰지 않았으며(④), 논리에도 끊긴 자리가 없다(②). 걸음 ⑤에서 아주 작게 보완할 것은 \(k\)의 자격을 밝히는 일과 \(3k^2\)이 정수임을 한 번 적는 일이다.

(c) 판정은 **옳음(보완 필요)**이다. 문제 9의 제시와 결정적으로 다른 점은 개시 줄에 “기약”이 명시되어 있다는 것이다. 그 조건이 있으므로 마지막의 “기약 모순”이 실제로 딛고 설 자리를 갖는다. \(2b^2 = a^2\)에서 \(a\)가 짝수, \(a = 2c\)에서 \(2b^2 = 4c^2\), 곧 \(b^2 = 2c^2\)이므로 \(b\)도 짝수라는 흐름에도 끊긴 곳이 없다. 보완할 것은 “\(a^2\)이 짝수이면 \(a\)가 짝수”와 “\(b^2\)이 짝수이면 \(b\)가 짝수”라는 두 인용을 근거 ④로 표시하는 일이다. 문제 9와 달리 여기서는 미인용 두 줄이 유일한 결함이므로 판정이 바뀌지 않는다 — 미인용 기성 정리는 어느 답안에서도 근거 표시 보완일 뿐이고, 문제 9의 판정을 틀림으로 내린 것은 그 미인용이 아니라 마지막 줄이 앞 줄에서 따라오지 않는다는 사실이었다.

복기. (a)와 (c)를 나란히 놓으면 두 판정 낱말의 경계가 보인다. 둘 다 적힌 문장 중 거짓인 것은 없지만, (a)는 다뤄야 할 대상의 대부분을 다루지 않았고 (c)는 다뤄야 할 대상을 전부 다룬 뒤 근거 표시만 생략했다. “무엇이 빠졌는가”의 크기가 판정을 가른다.

문제 20#

접근. 서술 문항이므로 채점 기준을 먼저 정한다. (a)는 세 요소를 본다 — 무엇이 무엇으로 재조직되었는가, 진리 상태 점검이 더한 것, 증명 평가가 더한 것. (b)는 두 절차가 왜 같은 절차인지를 한 문장 안에 담았는지를 본다. 문장 수 제한은 요약 능력 자체를 검사하는 장치다. 넉 문장 이상으로 늘어난 답안은 재조직의 골자 대신 주차 목록을 나열한 것이 되어, 검사하려던 능력이 답안에 드러나지 않는다.

풀이. 예시 답안은 다음과 같다.

(a) Chartrand 전반부는 S17주차의 기법 선택 결정 나무를 나눗셈\(\cdot\)합동\(\cdot\)집합\(\cdot\)데카르트 곱이라는 네 무대 위에서 다시 배열했고, 갈래 끝에 놓인 기법은 바뀌지 않은 채 그 기법이 펼칠 정의만 무대별로 갈아 끼워졌다. 여기에 “진리 상태 점검”(C5주차)이 나무 앞에 한 단계를 더해, 가정이 언제나 거짓이거나 결론이 언제나 참인 명제를 증명 노동에 들어가기 전에 걸러 낸다. 그리고 “증명 평가”가 나무 뒤에 한 단계를 더해, 완성된 답안을 다섯 걸음으로 다시 재는 일을 절차의 일부로 만든다.

(b) 남의 답안에서 결론을 가정한 줄, 특정 값 몇 개로 전칭을 대신한 줄, 가정을 한 번도 쓰지 않은 줄을 찾아내는 검사는 자기 답안에서 같은 세 가지를 찾아내는 검사와 항목이 같다. 다른 것은 채점 대상이 누구의 종이인가뿐이므로, 채점할 수 있는 항목의 수가 곧 자기 답안에서 점검할 수 있는 항목의 수다.

복기. 이 문항의 실제 목적은 (b)에 있다. 시험장에서 마지막 5분에 할 수 있는 일은 새 증명을 쓰는 것이 아니라 이미 쓴 답안에 다섯 걸음을 돌리는 것이고, 그 5분이 회수하는 점수의 크기가 이번 주가 전반부에 더한 것이다. 자기가 자주 걸리는 걸음 번호를 적어 두면 다음 주부터의 점검이 전 범위 재독이 아니라 한두 항목의 확인으로 줄어든다.

다음 주 예고 (C10주차): Chartrand 8장 — Prove or Disprove. 지금까지는 “증명하시오”라는 지시를 받았고, 그것은 명제가 참이라는 정보를 함께 받았다는 뜻이었다. 다음 주에는 참\(\cdot\)거짓이 표시되지 않은 명제를 받는다. 작은 사례로 정찰해 참\(\cdot\)거짓을 추측하고, 참이면 증명하고 거짓이면 반례를 댄다. 1권 29주차의 반증과 30주차의 참\(\cdot\)거짓 판별, 그리고 S18주차의 일반화와 반례 검문이 여기서 하나의 절차로 묶인다. 원서 8장을 통독하고 온다.