# C4주차 · 강의 — 예제 · 연습 · 해설 ## 예제 — 판정과 부정을 함께 만들기 완성된 답을 먼저 보이지 않는다. 백지에서 시작해 한 줄씩 만든다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다. ### 예제 2.1 — 양화 명제의 진위와 부정 **과제.** 다음 네 명제의 진위를 판정하고, 각각의 부정을 양화사로 쓰시오. 무대는 $\mathbb{R}$이다. $A$: $\forall x,\ x^2 \ge 0$. $\quad B$: $\exists x,\ x^2 = 2$. $\quad C$: $\forall x \exists y,\ x + y = 0$. $\quad D$: $\exists y \forall x,\ xy = 0$. **설계 — 쓰기 전에 정하는 두 가지.** 증명이든 판정이든 먼저 정하는 것은 같다. 과제가 주는 것(출발점)과 만들어야 할 것(도착점)이다. 둘 다 정의 4.1로 번역해서 얻는다. | | **말** | **수식$\cdot$제출물로의 번역** | |---|---|---| | 주어진 것 (출발점) | 네 명제, 무대 $\mathbb{R}$ | 각 명제를 양화사 층 / 무대 / 열린 문장으로 분해한 형태 | | 목표 (만들 것) | 진위와 부정 | 진위: $\underline{\quad(?)\quad}$ / 부정: $\sim$가 남지 않은 끝 모양 | :::{container} quotebox **확인 14.** 목표 칸의 진위 쪽 빈칸을 채워 보자. §1.4의 비대칭 표에 따르면, 참일 때와 거짓일 때 각각 무엇을 제출해야 하는가. ::: :::{admonition} 답 :class: quotebox dropdown $\forall$ 명제라면 참일 때 일반 논증, 거짓일 때 반례와 검증 계산. $\exists$ 명제라면 참일 때 증인과 검증 계산, 거짓일 때 전원 탈락의 일반 논증. 어느 칸이든 값만으로는 제출물이 되지 않고 **검증 계산까지**가 제출물이다. ::: **1단계 — $A$를 판정한다.** 바깥 층이 $\forall$이므로 참을 주장하려면 문자를 잡은 일반 논증이 필요하다. :::{container} quotebox **확인 15.** $A$가 참임을 보이는 한 줄을 적어 보자. 어떤 사실을 인용하는가. ::: :::{admonition} 답 :class: quotebox dropdown "임의의 실수 $x$에 대해 $x^2 \ge 0$이다 — 실수의 제곱은 음이 아니다(1권 16주차의 실수 기본 성질)." 특정한 $x$를 넣어 확인한 것이 아니라 임의의 $x$를 문자로 잡은 논증이므로 $\forall$의 참 칸을 채운다. $A$는 참이다. ::: **2단계 — $B$를 판정한다.** 바깥 층이 $\exists$이므로 증인 하나와 검증 계산이면 끝난다. :::{container} quotebox **확인 16.** $B$의 증인을 제시하고 검증까지 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown 증인 $x = \sqrt2$. 검증: $\sqrt2 \in \mathbb{R}$이고 $(\sqrt2)^2 = 2$이므로 열린 문장 "$x^2 = 2$"를 통과한다. $B$는 참이다. 무대가 $\mathbb{Q}$였다면 이 증인이 무대 밖이라 쓸 수 없고 명제는 거짓이 된다 — §1.3의 무대 표 그대로다. ::: **3단계 — $C$를 판정한다.** 두 겹이므로 순서부터 읽는다. $\exists y$가 $\forall x$ 안쪽에 있으므로 증인은 맞춤이어도 된다. :::{container} quotebox **확인 17.** $C$의 증인을 $x$의 식으로 제시하고 검증까지 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown $x$가 주어진 뒤 $y = -x$로 둔다. 검증: $-x \in \mathbb{R}$이고 $x + (-x) = 0$이므로 통과한다. $C$는 참이다. $y$가 $x$에 의존하는 것이 합법인 이유는 $\exists y$가 $\forall x$의 안쪽에 있어 $y$를 고르는 시점에 $x$가 이미 정해져 있기 때문이다 (§1.6). ::: **4단계 — $D$를 판정한다.** 이번에는 $\exists y$가 바깥이므로 만능 증인이 필요하다. 만능 증인을 요구하는 쪽은 훨씬 강한 주장이라 대개 거짓이지만, 이 명제는 예외다. :::{container} quotebox **확인 18.** $D$의 만능 증인을 제시하고, 그것이 만능임을 검증해 보자. ::: :::{admonition} 답 :class: quotebox dropdown $y = 0$. 검증: $0 \in \mathbb{R}$이고 **모든** 실수 $x$에 대해 $x \cdot 0 = 0$이다. 이 증인의 식에 $x$가 한 번도 나오지 않으므로 만능 증인이다. $D$는 참이다. $C$와 $D$가 둘 다 참인 것은 $D$의 증인이 우연히 $x$에 무관하기 때문이고, 그런 상수 증인을 잡을 수 있을 때만 순서를 바꿔도 진위가 유지된다. ::: **5단계 — 네 부정을 만든다.** §1.5의 절차를 바깥 층부터 한 겹씩 적용한다. 무대 $\mathbb{R}$은 네 줄 모두에서 그대로 남는다. :::{container} quotebox **확인 19.** 네 명제의 부정을 각각 적어 보자. $C$와 $D$는 두 겹이므로 두 걸음이다. ::: :::{admonition} 답 :class: quotebox dropdown $\sim A$: $\exists x,\ x^2 < 0$. ($\ge$의 부정은 $<$다.) $\sim B$: $\forall x,\ x^2 \neq 2$. $\sim C$: $\exists x\, \forall y,\ x + y \neq 0$. (첫 걸음에서 $\forall x$가 $\exists x$로, 둘째 걸음에서 $\exists y$가 $\forall y$로 뒤집힌다.) $\sim D$: $\forall y\, \exists x,\ xy \neq 0$. 원명제 넷이 전부 참이므로 부정 넷은 전부 거짓이다. ::: **완성본.** 방금 만든 것을 제출 형식으로 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 "왜?"에 스스로 답해 본다. | 증명의 한 줄 | 왜 이 줄을 쓰는가? | |---|---| | $A$는 참이다. 임의의 실수 $x$에 대해 $x^2 \ge 0$이므로 예외가 없다. 부정은 "$\exists x,\ x^2 < 0$"이고 거짓이다. | $\forall$의 참 칸 — 문자를 잡은 일반 논증. 부정은 한 걸음이고 맨 안쪽에서 $\ge$가 $<$로 뒤집힌다. | | $B$는 참이다. $x = \sqrt2$가 증인이고 $(\sqrt2)^2 = 2$이다. 부정은 "$\forall x,\ x^2 \neq 2$"이고 거짓이다. | $\exists$의 참 칸 — 증인과 검증 계산이 함께 제출물이다. 부정도 한 걸음이다. | | $C$는 참이다. 실수 $x$가 주어지면 $y = -x$로 두어 $x + y = 0$이다. 부정은 "$\exists x \forall y,\ x + y \neq 0$"이고 거짓이다. | 맞춤 증인 — $\exists y$가 안쪽이라 $y$를 $x$의 식으로 둘 수 있다. 부정은 바깥부터 두 걸음이고 층의 순서는 그대로 유지된다. | | $D$는 참이다. $y = 0$이 만능 증인이며 모든 실수 $x$에 대해 $x \cdot 0 = 0$이다. 부정은 "$\forall y \exists x,\ xy \neq 0$"이고 거짓이다. | 만능 증인 — 증인의 식에 $x$가 없어야 한다. 부정에서도 층의 배치는 바뀌지 않고 양화사만 각각 반전된다. | **[주의] 자주 하는 실수: 층의 순서를 함께 뒤집기.** $\sim C$를 "$\forall y \exists x$"로 적는 경우가 있다. 부정 규칙은 각 층의 양화사를 제자리에서 반전시킬 뿐 층의 배치를 바꾸지 않는다. 배치가 바뀌면 원명제와 무관한 명제가 되어 진리값이 반대라는 보장이 사라진다 (문제 3의 복기에서 다시 짚는다). ### 예제 2.2 — 중첩 부정: 수렴의 부정 **과제.** "$a_n \to L$"의 정의 "$\forall \varepsilon > 0,\ \exists N \in \mathbb{N},\ \forall n \in \mathbb{N}\ (n > N),\ \lvert a_n - L \rvert < \varepsilon$"의 부정을 유도하시오. 이번에는 설계만 함께 하고, 본문은 완성본으로 본다. :::{container} quotebox **확인 20.** 번역표를 채워 보자. 출발점: 층이 $\underline{\quad}$겹이고, 각 층에 붙은 자격은 $\underline{\quad}$과 $\underline{\quad}$이다. 도착점: $\sim$가 $\underline{\qquad}$까지 흡수된 끝 모양. ::: :::{admonition} 답 :class: quotebox dropdown 세 겹이고, 자격은 "$\varepsilon > 0$"과 "$n > N$"이다($\exists N$에는 자격이 붙어 있지 않다 — 다만 무대 $\mathbb{N}$은 붙어 있다. 자격과 무대는 다른 조각이고, 걸음 ③은 둘 다 보존한다). 도착점은 $\sim$가 **맨 안쪽 부등식**까지 흡수된 끝 모양이다. 자격 둘과 무대 셋은 세 걸음 내내 그대로 남는다. 1권 45주차 정의 45.1은 셋째 층을 "$\forall n \in \mathbb{N},\ (n > N \Rightarrow \cdots)$"로 적는다. 자격을 조건문으로 푼 형태이고, 확인 6에서 본 대로 같은 문장이다. 무대 $\mathbb{N}$을 빠뜨리면 안 된다 — $n$이 $\mathbb{R}$을 훑는다면 $a_n$이라는 표기 자체가 뜻을 잃는다. ::: | **걸음** | **결과** | **근거** | |---|---|---| | 시작 | $\sim(\forall \varepsilon > 0,\ \exists N \in \mathbb{N},\ \forall n \in \mathbb{N}\ (n > N),\ \lvert a_n - L \rvert < \varepsilon)$ | 부정할 대상을 층으로 분해해 적는다 (걸음 ①) | | 바깥 $\forall \varepsilon$ 반전 | $\exists \varepsilon > 0,\ \sim(\exists N \in \mathbb{N},\ \forall n \in \mathbb{N}\ (n > N),\ \lvert a_n - L \rvert < \varepsilon)$ | $\forall$ 반전 규칙. 자격 "$> 0$"은 그대로 (걸음 ②③) | | $\exists N$ 반전 | $\exists \varepsilon > 0,\ \forall N \in \mathbb{N},\ \sim(\forall n \in \mathbb{N}\ (n > N),\ \lvert a_n - L \rvert < \varepsilon)$ | $\exists$ 반전 규칙. 무대 $\mathbb{N}$은 그대로 (걸음 ④로 돌아와 ② 반복) | | $\forall n$ 반전 + 본체 부정 | $\exists \varepsilon > 0,\ \forall N \in \mathbb{N},\ \exists n \in \mathbb{N}\ (n > N),\ \lvert a_n - L \rvert \ge \varepsilon$ | $\forall$ 반전 + 맨 안쪽에서 $<$의 부정은 $\ge$ (걸음 ⑤) | **결과를 말로 옮기면.** "$(a_n)$이 $L$로 수렴하지 않는다"는 "어떤 오차 폭 $\varepsilon > 0$이 있어서, 아무리 큰 문턱 $N$을 잡아도, 그 너머에 $L$과의 거리가 $\varepsilon$ 이상인 항 $a_n$이 있다"는 뜻이다. $\blacksquare$ 세 겹이 $\exists\forall\exists$로 뒤집혔고, 각 층의 자격("$> 0$", "$> N$")과 무대 ($\mathbb{N}$)는 한 번도 건드려지지 않았다. S8주차에서 절차로 익히고 S10주차에서 기계로 굳힌 것이 여기서 양화 명제의 부정으로 정식화된다. ### 예제 2.3 — 특성화 사용: 표현을 갈아 끼우기 **과제.** "임의의 정수 $n$에 대해 $n^2 + n$은 짝수이다"를 정의로 한 번, 이미 증명된 정리로 한 번, 특성화로 한 번 증명하고, 어느 것이 가장 짧은지 보시오. 이번에는 설계부터 스스로 해 보자. :::{container} quotebox **확인 21.** 번역표를 채워 보자. 목표 "$n^2 + n$이 짝수"를 정의로 번역하면 무엇을 만들어야 하는가. 그리고 정의 대신 쓸 수 있는 재료로 무엇이 손에 있는가. ::: :::{admonition} 답 :class: quotebox dropdown 정의로 번역하면 $n^2 + n = 2 \times (\text{정수})$ 꼴을 실제로 만들어 제시해야 한다. 정의 대신 쓸 재료는 두 가지다 — 이미 증명된 정리 "연속한 두 정수의 곱은 짝수이다"(1권 1주차 문제 16)는 인수분해 $n^2 + n = n(n+1)$과 겉모양이 맞고, 특성화 "$m$이 짝수 $\iff m \equiv 0 \pmod 2$"는 합동 계산과 겉모양이 맞는다. 어느 쪽을 고르는지의 기준은 손에 있는 재료의 겉모양이다 (S4주차 §1.6의 조준 규칙). ::: **표현 1 (정의 — 경우 나누기).** $n$이 짝수인 경우와 홀수인 경우로 나눈다. $n = 2k$이면 $n^2 + n = 4k^2 + 2k = 2(2k^2 + k)$이고, $n = 2k+1$이면 $n^2 + n = (4k^2 + 4k + 1) + (2k + 1) = 4k^2 + 6k + 2 = 2(2k^2 + 3k + 1)$이다. 두 경우 모두 괄호 안이 정수이므로 짝수다. 모든 정수는 짝수이거나 홀수이므로 (1권 17주차) 두 경우로 충분하다. $\blacksquare$ **표현 2 (기증명 정리 — 연속한 두 정수의 곱).** $n^2 + n = n(n+1)$은 연속한 두 정수의 곱이고, 연속한 두 정수의 곱이 짝수라는 것은 1권 1주차 문제 16에서 경우 나누기로 증명했다. 따라서 $n^2 + n$은 짝수다 (근거 ④). $\blacksquare$ 표현 2가 인용한 것은 iff가 아니라 한 방향 정리이므로 특성화가 아니다. 정의 4.2의 해부 표대로, 특성화는 왼쪽 항이 개념의 **이름**이고 **양방향**이 증명된 것만 가리킨다. 근거 ④를 쓴다는 점은 특성화와 같지만, 조건에서 이름으로 되돌아가는 길은 없다. **표현 3 (특성화 — 법 2의 합동).** "$m$이 짝수 $\iff m \equiv 0 \pmod 2$"라는 특성화를 쓴다(확인 12에서 확인했다). 법 2에서 $n^2 \equiv n$이므로 $n^2 + n \equiv n + n = 2n \equiv 0 \pmod 2$이고, 따라서 $n^2 + n$은 짝수다. $\blacksquare$ 세 표현 모두 옳지만 길이가 다르다. 정의로 간 표현 1은 경우 나누기 두 벌이 필요했고, 기증명 정리를 인용한 표현 2와 특성화로 간 표현 3은 한 줄로 끝났다. 짧아진 이유는 계산이 영리해서가 아니라 **과녁을 손에 있는 재료의 겉모양에 맞췄기** 때문이다. 다만 표현 3에는 확인할 것이 하나 더 있다. 인용한 "$n^2 \equiv n \pmod 2$" 역시 그 자체가 증명이 필요한 문장이다($n^2 - n = n(n-1)$이 연속한 두 정수의 곱이므로 짝수라는 것이 그 증명이고, 결국 표현 2와 같은 사실을 쓴다). 특성화는 자유를 주지만 그 동치가 증명됐는지 확인할 책임이 따른다. ### 관찰 — 세 작업의 같은 뼈대 예제 2.1, 2.2, 2.3은 과제가 다르지만 걸음의 배치가 같다. 대응표의 빈칸을 채워 보자. | **걸음** | **예제 2.1** | **예제 2.2** | **예제 2.3** | |---|---|---|---| | ① 층 분해 | 네 명제를 양화사$\cdot$무대$\cdot$열린 문장으로 | 수렴의 정의를 세 겹으로 | $\underline{\quad(1)\quad}$ | | ② 층별 처리 | 비대칭 표로 각 층 판정 | $\underline{\quad(2)\quad}$ | 표현을 골라 갈아 끼운다 | | ③ 끝 모양 판정 | 증인$\cdot$반례에 검증 계산이 붙었는가 | $\sim$가 안쪽까지 흡수됐는가 | $\underline{\quad(3)\quad}$ | :::{container} quotebox **확인 22.** 빈칸 (1)~(3)을 채워 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) "$n^2 + n$이 짝수"를 정의로 펴서 "$n^2 + n = 2k$인 정수 $k$가 존재한다"는 존재 명제로 적는다. (2) 바깥 층부터 반전 규칙을 한 겹씩 적용한다. (3) 인용한 정리나 동치가 증명된 것인지, 출처를 댈 수 있는지 확인한다. ::: :::{container} quotebox **확인 23.** 세 예제에서 공통으로 반복된 순서를 세 걸음으로 적어 보자. 순서를 바꾸면 무엇이 어긋나는가. ::: :::{admonition} 답 :class: quotebox dropdown ① 층을 분해해 양화사$\cdot$무대$\cdot$열린 문장을 분리한다 $\to$ ② 바깥 층부터 규칙 하나씩 처리한다 $\to$ ③ 끝 모양이 제출 조건을 만족하는지 판정한다. ①을 건너뛰면 뒤집거나 갈아 끼울 대상이 문면에 없어 ②가 시작되지 않는다(§1.5의 걸음 ①). ③을 건너뛰면 증인만 적고 검증을 빠뜨리거나(§1.4), $\sim$가 남은 중간 상태에서 멈추거나(확인 8), 증명되지 않은 동치를 인용하게 된다(§1.7의 삭제 실험). ::: 방금 확인한 뼈대에 이름을 붙인다. :::{admonition} 백지 암기 대상 :class: keybox **양화 작업의 3단 뼈대** ① 층 분해 — 양화사 층 / 무대와 자격 / 맨 안쪽 열린 문장을 분리해 적는다 $\to$ ② 층별 처리 — 가장 바깥 층 하나만 규칙 한 줄로 처리하고, 남은 안쪽을 한 겹 줄어든 새 문제로 삼아 반복한다 $\to$ ③ 끝 모양 판정 — 제출물이 그 칸의 완결 조건(검증 계산 / $\sim$의 흡수 / 인용 동치의 출처)을 갖췄는지 확인한다. ::: 이 뼈대는 C5주차의 증명 평가와 C7주차의 반례$\cdot$존재 증명에서 그대로 쓰인다. 바뀌는 것은 ②에서 적용할 규칙의 종류뿐이다. ## 빈칸 사다리 — 지지대를 하나씩 빼며 필사에서 자립으로 넘어가는 다리다. 베끼지 말고 빈칸만 스스로 채운다. 훈련이 진행될수록 빈칸이 커진다. 답은 §6에 있다 — 다 채운 뒤에 대조한다. ### 훈련 1 ●○○ — 수식과 절차 빈칸 **명제.** $\forall x \in \mathbb{R},\ \exists y \in \mathbb{R},\ y > x$ (어떤 실수를 잡아도 그보다 큰 실수가 있다). - 진위 판정: 실수 $x$가 주어진 뒤 $y = x + 1$로 두면 $y > x$이다. 증인이 $x$의 식이므로 이것은 $\underline{\quad(1)\quad}$ 증인이고, $\exists y$가 $\forall x$의 안쪽에 있으므로 합법이다. 따라서 원명제는 $\underline{\quad(2)\quad}$이다. - 부정 첫 걸음: 바깥 층 $\forall x$를 반전하면 $\exists x \in \mathbb{R},\ \sim(\exists y \in \mathbb{R},\ y > x)$. - 부정 둘째 걸음: 안쪽 층 $\exists y$를 반전하면 $\exists x \in \mathbb{R},\ \underline{\quad(3)\quad} y \in \mathbb{R},\ y \le x$. (맨 안쪽에서 $>$의 부정이 $\le$가 된 것에 주의한다.) - 부정의 뜻: "어떤 실수 $x$가 있어 모든 실수 $y$가 $y \le x$이다" = "$\underline{\quad(4)\quad}$ 실수가 존재한다". 실수에는 그런 것이 없으므로 이 부정은 $\underline{\quad(5)\quad}$이다. - 순서를 바꾼 "$\exists y \in \mathbb{R},\ \forall x \in \mathbb{R},\ y > x$"는 만능 증인을 요구하므로 $\underline{\quad(6)\quad}$이다 (원명제와 진위가 다르다). ### 훈련 2 ●●○ — 부정과 근거를 함께 이번에는 각 걸음의 근거 이름도 빈칸이다. **명제.** $\forall x \in \mathbb{R},\ \exists n \in \mathbb{N},\ n > x$. - 진위: 실수 $x$가 주어지면 $x$보다 큰 자연수를 잡을 수 있으므로 참이다. 이 사실이 아르키메데스 성질이고, 1권 45주차 §1.5에서 정식으로 채택했으며 S5주차 문제 14가 그 한 조각($\frac1n < \varepsilon$인 양의 정수 $n$의 존재)을 증인 $n = \lceil \frac1\varepsilon \rceil + 1$로 증명했다. 근거 ④로 출처와 함께 인용한다. - 부정 1걸음: $\exists x \in \mathbb{R},\ \sim(\exists n \in \mathbb{N},\ n > x)$. 근거는 $\underline{\quad(1)\quad}$ 반전 규칙이고, 무대 $\mathbb{R}$은 $\underline{\quad(2)\quad}$. - 부정 2걸음: $\exists x \in \mathbb{R},\ \underline{\quad(3)\quad} n \in \mathbb{N},\ n \le x$. 근거는 $\underline{\quad(4)\quad}$ 반전 규칙 + 맨 안쪽 부등호 처리. - 끝 모양 판정: $\sim$가 $\underline{\quad(5)\quad}$까지 흡수됐으므로 절차가 끝났다. - 부정의 뜻: "모든 자연수보다 크거나 같은 실수가 존재한다". 원명제가 참이므로 이 부정은 $\underline{\quad(6)\quad}$이다. ### 훈련 3 ●●● — 뼈대만 남기고 이번에는 특성화를 처음부터 스스로 세운다. 3단 뼈대의 각 칸을 통째로 채운다. **과제.** "정수 $n$이 3의 배수 $\iff$ $n^2$이 3의 배수"를 특성화로 확립하고, 그것을 인용해 "$n^2$이 3의 배수이면 $n^2 + n$도 3의 배수이다"를 증명한다. - ① 두 방향 중 정의로 곧장 되는 쪽과 막히는 쪽을 가른다: $\underline{\quad(1)\quad}$ - ② 곧장 되는 방향의 증명: $\underline{\quad(2)\quad}$ - ③ 막히는 방향의 처리와 증명: $\underline{\quad(3)\quad}$ - ④ 확립된 특성화를 인용한 짧은 증명: $\underline{\quad(4)\quad}$ (이 훈련이 문제 9와 19의 예행연습이다.) ## 연습문제 (20문항) 해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 접근까지만 읽고 다시 시도한다 $\to$ 그래도 안 되면 풀이를 읽는다. 이 순서가 답지 암기 습관을 끊는 장치다. :::{admonition} 이번 주의 채점 기준 :class: quotebox 답이 아니라 근거가 점수다. 이번 주의 근거는 세 가지 형태로 제출된다. ① 진위 판정 문제에서는 값이 아니라 **검증 계산**이 점수다 — "증인은 $\sqrt2$"는 절반이고 "$(\sqrt2)^2 = 2$이므로 통과한다"까지가 만점이다. ② 부정 문제에서는 끝 모양이 점수다 — $\sim$가 양화사 밖에 남아 있으면 중간 상태이고, 자격이나 무대가 뒤집혀 있으면 그 순간 다른 명제가 된다. ③ 특성화를 인용하는 문제에서는 **출처**가 점수다 — "특성화에 의해"만 적으면 어디서 증명됐는지 검사할 수 없다. 힌트 상자는 5분 이상 막힌 뒤에만 연다. ::: ### 기본 ●○○ **1.** [백지] 양화사의 정의, 부정 규칙(양화사 반전과 무대$\cdot$자격 보존), 중첩 양화사의 순서 차이, 특성화의 정의(증명된 iff)를 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown 네 항목을 한 줄씩 떠올리려 하면 중간에서 끊긴다. 두 묶음으로 나눈다 — 문장을 닫는 층(정의 4.1과 비대칭 표)과 문장을 다루는 층(부정 규칙, 순서, 특성화). 묶음이 서면 그 안의 항목은 따라 나온다. ::: **2.** 각 명제의 진위를 판정하시오 (무대 $\mathbb{R}$). (a) $\forall x,\ x + 1 > x$ (b) $\exists x,\ x^2 = -4$ (c) $\forall x \exists y,\ xy = 1$ (d) $\exists x \forall y,\ x + y = y$ :::{admonition} 힌트 :class: quotebox dropdown 네 문제 모두 층 분해부터 한다. (a)(b)는 한 겹, (c)(d)는 두 겹이다. 두 겹짜리는 안쪽 $\exists$가 맞춤인지 만능인지부터 판정하고, 맞춤이면 증인을 바깥 변수의 식으로 써 보고, 만능이면 상수 후보를 하나 잡아 무너지는지 시험한다. (c)에서 $x = 0$을 넣어 보면 무엇이 걸리는가. ::: **3.** 문제 2의 각 명제의 부정을 양화사로 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown 진위를 몰라도 부정은 쓸 수 있다 — 부정은 규칙의 적용이지 판정이 아니다. 두 겹짜리는 바깥부터 두 걸음이고, 층의 배치는 바뀌지 않는다. 맨 안쪽에서 $>$의 부정은 $\ge$가 아니라 $\le$, $=$의 부정은 $\neq$다. ::: **4.** §3의 훈련 1~3을 백지에서 완성하시오. :::{admonition} 힌트 :class: quotebox dropdown 훈련 3이 막히면 ①만 먼저 판정한다. 두 방향 중 가정이 $n$ 자체의 성질인 쪽이 정의로 곧장 풀리고, 가정이 $n^2$의 성질인 쪽이 §1.7의 시도처럼 막힌다. 막히는 쪽은 1권 19주차가 쓴 기법으로 돌린다. ::: **5.** 예제 2.2(수렴의 부정)를 백지에서 재현하시오 — 세 겹 뒤집기. :::{admonition} 힌트 :class: quotebox dropdown 정의를 먼저 정확히 적는 것이 절반이다. 층 세 개와 자격 두 개, 무대 $\mathbb{N}$을 종이에 나열한 뒤 걸음 ②를 세 번 돌린다. 옮겨 적을 때 "$> 0$"과 "$> N$", 그리고 $\in \mathbb{N}$이 그대로 따라오는지 매 줄 확인한다. ::: **6.** 특성화의 예 세 개를 드시오 (짝수$\cdot$부분집합$\cdot$단사 중에서 — 각각 정의와 동치인 조건). :::{admonition} 힌트 :class: quotebox dropdown 각 예에서 정의가 무엇인지부터 적고, 그 옆에 동치인 조건을 적는다. 짝수는 §1의 확인 12, 부분집합은 S4주차 문제 13, 단사는 정의의 대우 형태에서 재료를 얻는다. 세 예 모두 "이 동치는 어디서 증명됐는가"를 한 줄로 함께 적어야 완결이다. ::: ### 표준 ●●○ **7.** 명제 "$\forall x \in \mathbb{R},\ x^2 \ge x$"의 진위를 판정하고, 거짓이면 반례를, 참이면 증명을 제시하시오. 이어서 그 부정을 쓰고, 부정이 참임을 증인으로 보이시오. :::{admonition} 힌트 :class: quotebox dropdown $x = 2$나 $x = -1$처럼 큰 수와 음수만 시험하면 전부 통과한다. 부등식 $x^2 \ge x$를 $x(x-1) \ge 0$으로 바꿔 보면 어느 구간에서 무너지는지 보인다. ::: **8.** $C$: $\forall x \exists y,\ y = x^2$ 과 $D$: $\exists y \forall x,\ y = x^2$의 진위를 각각 판정하고, 순서 차이를 설명하시오. **9.** 특성화 증명: "정수 $n$이 짝수 $\iff$ $n^2$이 짝수"를 양방향으로 증명해 특성화를 확립하시오. 그리고 이 특성화를 써서 "$n^2$이 짝수이면 $n^2 + n$도 짝수이다"를 짧게 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 두 방향의 난이도가 다르다. 한 방향은 정의를 풀어 제곱하면 끝나고, 다른 방향은 §1.7의 시도처럼 막힌다. 막히는 방향은 대우로 돌린다 — 대우의 가정이 $n$ 자체의 성질이 되어 정의가 즉시 풀린다 (1권 19주차 §1.5의 판정 표). ::: **10.** 다음 부정을 진단하시오. :::{container} quotebox "'$\forall x > 0,\ x^2 > 0$'의 부정은 '$\exists x \le 0,\ x^2 \le 0$'이다." ::: :::{admonition} 힌트 :class: quotebox dropdown 원명제와 그 "부정"의 진위를 각각 판정해 나란히 놓아 본다. 둘이 동시에 참이면 부정의 자격이 무너진 것이고, 무너진 자리는 §1.5의 다섯 걸음 중 하나다. ::: :::{admonition} 새 도구 — 양화사 층 안에 조건문이 있을 때 :class: quotebox 문제 11의 안쪽 층에는 부등식이 아니라 조건문이 들어 있다. 절차는 달라지지 않는다 — 걸음 ②를 양화사 층에 계속 적용하다가, 마지막에 남은 $\sim(P \Rightarrow Q)$를 C3주차의 조건문 부정 $\sim(P \Rightarrow Q) \equiv P \wedge (\sim Q)$로 처리하면 된다. 화살표가 $\wedge$로 바뀌므로 부정 뒤에 조건문은 남지 않는다. ::: **11.** "$\forall \varepsilon > 0,\ \exists \delta > 0,\ \forall x \in \mathbb{R},\ (\lvert x - a \rvert < \delta \Rightarrow \lvert f(x) - f(a) \rvert < \varepsilon)$"($f : \mathbb{R} \to \mathbb{R}$가 $a$에서 연속이라는 정의)의 부정을 유도하시오. :::{admonition} 힌트 :class: quotebox dropdown 네 걸음이다 — 양화사 세 층을 바깥부터 뒤집고, 마지막에 조건문 하나를 처리한다. 자격 "$\varepsilon > 0$"과 "$\delta > 0$"은 네 걸음 내내 그대로 따라온다. 완성된 문장을 말로 옮겨 "어떤 오차 폭이 있어서 …"로 읽어 보면 검산이 된다. ::: **12.** 특성화와 정의: "홀수 = 짝수가 아닌 정수"라고 쓸 때, 이것이 정의가 아니라 증명이 필요한 특성화인 이유를 설명하시오. 그리고 "$n = 2k+1$ 꼴"과 "짝수가 아님"이 동치임을 보이시오. :::{admonition} 힌트 :class: quotebox dropdown 동치를 보이려면 두 방향이다. 한 방향은 "$2k+1$ 꼴이면 짝수가 아니다"이고 귀류로 처리한다. 다른 방향은 "짝수가 아니면 $2k+1$ 꼴이다"인데, 여기서 인용하는 사실이 1권 17주차의 그것이다. 두 방향이 각각 어떤 성질(배타성$\cdot$전수성)을 쓰는지 이름을 붙여 두면 답이 정리된다. ::: :::{admonition} 이 문제가 빌려 쓰는 사실 — 무대와 $\sqrt2$ :class: quotebox 문제 13은 무대를 $\mathbb{N} \subset \mathbb{Q} \subset \mathbb{R} \subset \mathbb{C}$로 바꿔 가며 같은 문장의 진위를 묻는다. 판정에 "$\sqrt2$는 무리수이다"가 필요한데, 이 사실은 1권 21주차에서 귀류법으로 증명했다. 인용할 때 출처를 함께 적는다. ::: **13.** "$\exists x,\ x^2 = 2$"의 진위를 무대별로 판정하시오: (a) $\mathbb{N}$ (b) $\mathbb{Q}$ (c) $\mathbb{R}$ (d) $\mathbb{C}$. 각 무대에서 참$\cdot$거짓과 그 이유를 쓰시오. **14.** 다음 셋이 서로 특성화(동치)임을 확인하고, 각각이 어느 상황에 편한지 쓰시오 — "$A \subseteq B$" $\iff$ "$A \cup B = B$" $\iff$ "$A \cap B = A$". 각 동치를 원소 추적 또는 집합 대수로 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 셋을 두 쌍으로 나눠 각각 양방향으로 증명하면 세 개의 동치가 전부 이어진다. 집합의 상등은 두 포함으로 쪼갠다(1권 27주차). 원소 추적은 "$x \in$ 좌변"에서 시작해 "$x \in$ 우변"으로 가는 한 줄씩의 논증이다. ::: ### 도전 ●●● **15.** "$\forall m \in \mathbb{N},\ \exists n \in \mathbb{N},\ \forall k \in \mathbb{N},\ (k \le m \Rightarrow k \le n)$"의 진위를 판정하시오. 부정을 유도하고, 그 부정이 왜 거짓인지 확인하시오. :::{admonition} 힌트 :class: quotebox dropdown 세 겹이지만 안쪽 두 겹은 $m$이 정해진 뒤의 문제다. $\exists n$이 $\forall m$의 안쪽에 있으므로 $n$을 $m$의 식으로 둘 수 있다 — 가장 게으른 선택을 시험해 본다. 부정을 유도할 때 마지막 조건문 하나가 남는 것에 주의한다. ::: :::{admonition} 이 문제가 빌려 쓰는 사실 — 무한등비급수의 합 :class: quotebox 문제 16(a)은 $0.2727\ldots$을 분수로 되돌리는 계산을 요구한다. 이때 쓰는 것이 공비 $r$이 $\lvert r \rvert < 1$일 때의 무한등비급수 합 공식 $\frac{a}{1-r}$이다. 이 공식은 1권 46주차 문제 17에서 부분합의 닫힌 꼴 $\frac{1-r^{n+1}}{1-r}$과 $r^{n+1} \to 0$(1권 46주차 문제 16)으로 증명했다 — 근거 ④로 출처와 함께 인용한다. ::: **16.** "실수 $r$이 유리수 $\iff$ $r$의 십진 전개가 유한하거나 순환한다"는 유명한 특성화다. (a) 이 특성화의 한 방향("유한하거나 순환하면 유리수")을 $0.2727\ldots = \frac{27}{99} = \frac3{11}$ 같은 예로 설명하시오. (b) 이 특성화를 정의로 쓰면 왜 안 되는지 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown (a)는 $0.2727\ldots$을 $\frac{27}{100} + \frac{27}{10000} + \cdots$로 펼치는 데서 시작한다. 공비가 무엇인지 먼저 확정한다. (b)는 §1.7의 삭제 실험을 유리수에 적용하는 문제다 — 유리수의 정의가 무엇이었는지부터 적는다. ::: **17.** "$\forall x \in \mathbb{R},\ \exists y \in \mathbb{R},\ y > x$"는 참이고 "$\exists y \in \mathbb{R},\ \forall x \in \mathbb{R},\ y > x$"는 거짓임을 증명하시오. 그리고 한 방향 교환 정리가 이 경우 역으로 가지 않는 이유를 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown 거짓 쪽은 만능 증인 $y_0$이 있다고 가정한 뒤 그 $y_0$을 무너뜨리는 $x$를 만든다. $y_0$ 자신을 $x$ 자리에 넣어 보는 것이 가장 짧다. 마지막 물음은 참인 쪽의 증인 $y = x + 1$이 왜 만능이 될 수 없는지를 한 문장으로 적는 것이다. ::: **18.** 다음 부정들의 오류를 각각 찾으시오. (a) "'$\exists x,\ P(x)$'의 부정은 '$\exists x,\ \sim P(x)$'." (b) "'$\forall x \exists y,\ P(x,y)$'의 부정은 '$\forall x \exists y,\ \sim P(x,y)$'." (c) "'$\forall n \in \mathbb{N},\ n \ge 1$'의 부정은 '$\exists n \notin \mathbb{N},\ n < 1$'." :::{admonition} 힌트 :class: quotebox dropdown 세 오류가 서로 다른 걸음에서 났다. 각각을 §1.5의 다섯 걸음 표에 대 보고, 어느 칸이 비었는지 지목한다. 진단이 끝나면 반드시 올바른 부정까지 적는다 — 오류만 지적하고 수정본을 쓰지 않으면 절반만 제출한 것이다. ::: **19.** "정수 $n$이 3의 배수 $\iff$ 각 자리 숫자의 합이 3의 배수"를 두 자리 수 $n = 10a + b$에 대해 증명하시오. 그리고 이 특성화가 "3으로 직접 나눠 보기"보다 편한 이유를 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown $10a + b$에서 $a$의 계수 10을 "3의 배수 + 나머지"로 쪼갠다. 쪼갠 뒤 3의 배수 부분을 옆으로 밀어내면 남는 것이 자리합이다. 마지막 물음은 두 자리 수가 아니라 여섯 자리 수를 판정하는 상황을 상상하면 답이 나온다. ::: **20.** (서술) (a) 양화 명제의 부정이 S8주차(중첩 절차)$\cdot$S10주차(NOT 기계)의 논리적 정식화임을 예제 2.2로 뒷받침하고, "자격 보존"이 왜 핵심인지 세 문장 이내로 쓰시오. (b) 특성화가 S4주차의 "동치인 표현 고르기"를 정식 개념으로 세운 것임을 예제 2.3으로 설명하고, "특성화는 자유를 주지만 동치 증명의 책임이 따른다"를 두 문장 이내로 쓰시오. ## 백지 재현 — 복습 프로토콜 **이번 주의 5일 루틴.** 원서와 교안을 번갈아 쓰는 순서다. | **요일** | **할 일** | |---|---| | 1일차 | 원서 Chartrand 2.10~2.11 통독 (모르는 문장은 표시만 하고 통과) | | 2일차 | 교안 §0~§2 — 개념과 예제. 확인 상자는 연필로 먼저 답한다 | | 3일차 | 원서 재독 — 1일차에 표시한 문장을 해결하고, 원서 2.10~2.11의 연습문제 몇 개를 직접 시도 | | 4일차 | 교안 §3 빈칸 사다리 + §4 연습문제 20문항 | | 5일차 | 백지 재현 1차(틀 카드)$\cdot$2차(완전 백지) + 체크리스트 | 원서의 2.11절은 짧다. 대신 그 절이 던지는 물음("이 동치를 정의로 써도 되는가")은 학기 내내 되돌아오므로, 3일차 재독에서 2.11절의 예마다 "이것은 정의인가 특성화인가"를 표시하며 읽는다. **1차 시도 — 틀 카드 허용.** 다음 세 상자만 옮겨 적은 카드를 펴 놓는다: 정의 4.1, 양화 명제의 부정 규칙, 양화 작업의 3단 뼈대. 그 상태에서 예제 2.1의 네 명제를 처음부터 끝까지 판정하고 부정까지 적는다. 예제 본문과 확인 상자는 보지 않는다. **2차 시도 — 완전 백지.** 아무것도 보지 않고 수행한다. - [ ] 정의 4.1(양화 명제)과 정의 4.2(특성화)를 조각 그대로 백지에 썼다. - [ ] 진위의 비대칭 표 네 칸을 쓰고, 각 칸의 제출물에 검증 계산이 포함됨을 밝혔다. - [ ] 양화 명제의 부정 규칙 두 줄과 다섯 걸음을 쓰고, 걸음 ③을 뺐을 때의 붕괴 사례를 들었다. - [ ] 예제 2.1의 네 명제를 진위와 부정까지 재현했다 (검증 계산 포함). - [ ] 예제 2.2의 수렴 부정을 세 걸음으로 재현하고 자격 두 개와 무대 $\mathbb{N}$이 살아남는지 확인했다. - [ ] 예제 2.3의 세 표현을 재현하고, 어느 것이 정의이고 어느 것이 기증명 정리이며 어느 것이 특성화인지 표시했다. - [ ] 맞춤 증인과 만능 증인의 차이를 한 쌍의 예로 설명하고, 교환이 한 방향뿐인 이유를 적었다. - [ ] 원서 2.10~2.11을 완독했고, 1일차에 표시한 문장이 전부 해결되었다. **막힌 지점별 처방.** 막힌 지점이 무엇을 다시 볼지 알려 준다. | **막힌 지점** | **처방** | |---|---| | 부정을 적다가 어디까지 가야 할지 모르겠다 | §1.5 걸음 ⑤와 확인 8 — 끝 모양의 판정 기준은 $\sim$의 위치 하나다 | | 자격을 뒤집어야 할지 말지 헷갈린다 | §1.5의 걸음 삭제 실험과 확인 6 — 조건문 부정으로 계산해 보면 살아남는 것이 보인다 | | 증인을 적었는데 점수가 깎인다 | §1.4 — 값만으로는 절반이고 검증 계산까지가 제출물이다 | | 맞춤인지 만능인지 판정이 안 된다 | §1.6 — 증인의 식에 바깥 변수가 나오는지만 본다 | | 두 겹 부정에서 층의 순서가 헷갈린다 | 예제 2.1의 5단계와 자주 하는 실수 상자 — 배치는 바뀌지 않는다 | | 어떤 동치를 인용해도 되는지 모르겠다 | §1.7의 정의 4.2와 삭제 실험 — 출처를 댈 수 있는가로 판정한다 | | 정의와 특성화의 구분이 계속 흐려진다 | 확인 12와 §1.8 근거 목록 — 근거 ①인가 ④인가로 되물으면 갈린다 | 하나라도 실패하면 그 항목만 다시 적고 다음날 재시도한다. ## 해설 각 해설은 **접근**(문제 앞에서 무엇을 생각하는가)과 **풀이**로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다. ### 빈칸 사다리 — 훈련 1 (1) 맞춤 (2) 참 (3) $\forall$ (4) 가장 큰 (최대인) (5) 거짓 (6) 거짓 ※ (3)이 이 훈련의 핵심이다. 안쪽 $\exists y$를 뒤집으면 $\forall y$가 되고, 층의 자리는 그대로 둔 채 양화사만 바뀐다. (6)은 원명제와 같은 재료로 순서만 바꾼 문장이 진위까지 달라지는 것을 확인하는 자리다 — 원명제의 증인 $y = x+1$은 $x$에 의존하므로 만능이 될 수 없다. ### 빈칸 사다리 — 훈련 2 (1) $\forall$ (전칭) (2) 그대로 보존된다 (3) $\forall$ (4) $\exists$ (존재) (5) 맨 안쪽 부등식 (6) 거짓 ※ (2)가 이 훈련에서 새로 요구되는 판정이다. 무대 $\mathbb{R}$과 $\mathbb{N}$은 두 걸음 내내 손대지 않는다 — 무대까지 뒤집으면 "어떤 실수 아닌 것이 …"라는 원명제와 무관한 문장이 된다(§1.5의 걸음 삭제 실험). (6)은 원명제가 참이므로 자동으로 정해진다 — 부정의 진위는 따로 판정하는 것이 아니라 원명제의 진위에서 나온다. ### 빈칸 사다리 — 훈련 3 (1) "$n$이 3의 배수 $\Rightarrow$ $n^2$이 3의 배수"는 가정이 $n$ 자체의 성질이므로 정의가 즉시 풀린다. 반대 방향 "$n^2$이 3의 배수 $\Rightarrow$ $n$이 3의 배수"는 가정이 $n^2$이라는 합성된 식의 성질이라 $n$을 꺼낼 등식이 없다 — §1.7의 시도와 같은 자리에서 막힌다 (1권 19주차 §1.5의 신호 그대로다). (2) $n$이 3의 배수라 하자. 정의에 의해 $n = 3k$인 정수 $k$가 존재한다. 그러면 $n^2 = 9k^2 = 3(3k^2)$이고 $3k^2$은 정수이므로 $n^2$은 3의 배수이다. (3) 막히는 방향은 대우로 돌린다. 대우는 "$n$이 3의 배수가 아니면 $n^2$도 3의 배수가 아니다"이다. $n$이 3의 배수가 아니라 하자. 나눗셈 정리(1권 33주차)에 의해 $n = 3k + 1$ 또는 $n = 3k + 2$인 정수 $k$가 존재한다. 앞의 경우 $n^2 = 9k^2 + 6k + 1 = 3(3k^2 + 2k) + 1$이고, 뒤의 경우 $n^2 = 9k^2 + 12k + 4 = 3(3k^2 + 4k + 1) + 1$이다. 두 경우 모두 $n^2$을 3으로 나눈 나머지가 1이므로 $n^2$은 3의 배수가 아니다. 대우가 증명되었으므로 원명제가 성립한다. 두 방향을 합쳐 특성화 "$n$이 3의 배수 $\iff$ $n^2$이 3의 배수"가 확립된다. (4) $n^2$이 3의 배수라 하자. 방금 확립한 특성화의 $\Leftarrow$ 방향에 의해 $n$도 3의 배수이므로 $n = 3k$인 정수 $k$가 존재하고, $n^2 = 3m$인 정수 $m$도 존재한다. 그러면 $n^2 + n = 3m + 3k = 3(m + k)$이고 $m + k$는 정수이므로 $n^2 + n$은 3의 배수이다. $\blacksquare$ ※ 이 훈련의 값은 ③에 있다. 특성화는 "양방향이 증명된 iff"이므로, 쉬운 방향 하나만 적고 멈추면 확립되지 않는다. 막히는 방향에 기법을 갈아 끼우는 일까지가 특성화를 세우는 일이다. ### 문제 1 **접근.** 네 항목을 한 줄씩 순서대로 떠올리면 중간에서 끊긴다. 두 묶음으로 나눈다. 문장을 **닫는** 층(양화사의 정의와 진위 판정)과 문장을 **다루는** 층(부정, 순서, 특성화)이다. 묶음 이름이 서면 그 안의 항목이 따라 나온다. **풀이.** 자가 채점 기준은 다음과 같다. 양화사 — $\forall x \in S,\ P(x)$는 $S$의 모든 $x$가 $P(x)$를 만족한다는 뜻이고, $\exists x \in S,\ P(x)$는 그런 $x$가 적어도 하나 있다는 뜻이며, $\exists!$는 정확히 하나다. 무대 $S$를 적는 것까지가 정의다. 부정 규칙 — $\sim(\forall x \in S, P(x)) \equiv \exists x \in S, \sim P(x)$이고 $\sim(\exists x \in S, P(x)) \equiv \forall x \in S, \sim P(x)$이며, 무대와 자격은 양쪽 모두에서 보존된다. 순서 — $\forall x \exists y$는 맞춤 증인($y$가 $x$의 식이어도 된다)을 허용하고 $\exists y \forall x$는 만능 증인을 요구하며, $\exists\forall$에서 $\forall\exists$로 가는 한 방향만 성립한다. 특성화 — 개념의 이름과 다른 조건을 잇는 **증명된** iff이고, 정의와 다른 점은 iff의 출처 하나다. ### 문제 2 **접근.** 네 문제 모두 층 분해부터 한다. (a)(b)는 한 겹이므로 비대칭 표의 네 칸 중 하나를 곧장 고르면 되고, (c)(d)는 두 겹이므로 안쪽 $\exists$가 맞춤인지 만능인지부터 판정한다. 맞춤이면 증인을 바깥 변수의 식으로 써 보고, 만능이면 상수 후보를 잡아 무너지는지 시험한다. **풀이.** (a) **참.** 바깥 층이 $\forall$이므로 일반 논증이 필요하다. 임의의 실수 $x$에 대해 $(x+1) - x = 1 > 0$이므로 $x + 1 > x$이다. 예외가 없다. (b) **거짓.** 바깥 층이 $\exists$이므로 거짓을 보이려면 전원 탈락의 일반 논증이 필요하다. 임의의 실수 $x$에 대해 $x^2 \ge 0 > -4$이므로 $x^2 = -4$는 어떤 실수에서도 성립하지 않는다. (c) **거짓.** $\exists y$가 안쪽이므로 맞춤 증인이 허용되지만, $x = 0$이면 모든 실수 $y$에 대해 $0 \cdot y = 0 \neq 1$이라 증인이 아예 없다. 즉 $x = 0$이 바깥 $\forall$의 반례다. 검증: $0 \cdot y = 0$이고 $0 \neq 1$이다. (d) **참.** $\exists x$가 바깥이므로 만능 증인이 필요하다. $x = 0$을 제시한다. 검증: 모든 실수 $y$에 대해 $0 + y = y$이다. 증인의 식에 $y$가 나오지 않으므로 만능이다. **검산.** (c)와 (d)를 나란히 보면 같은 값 $0$이 한쪽에서는 반례로, 다른 쪽에서는 증인으로 쓰였다. 무엇이 되는지는 그 값이 어느 층에 놓이는지가 정한다. ### 문제 3 **접근.** 진위를 몰라도 부정은 쓸 수 있다 — 부정은 규칙의 적용이지 판정이 아니다. 바깥 층부터 한 겹씩 반전하고, 층의 배치는 건드리지 않으며, 맨 안쪽에서 부등호와 등호를 "성립하지 않는 경우 전부"로 바꾼다. **풀이.** (a) $\exists x,\ x + 1 \le x$. 원명제가 참이므로 이 부정은 거짓이다. (b) $\forall x,\ x^2 \neq -4$. 원명제가 거짓이므로 이 부정은 참이다. (c) $\exists x\, \forall y,\ xy \neq 1$. 원명제가 거짓이므로 이 부정은 참이고, 실제로 $x = 0$이 증인이다 — 모든 실수 $y$에 대해 $0 \cdot y = 0 \neq 1$이다. (d) $\forall x\, \exists y,\ x + y \neq y$. 원명제가 참이므로 이 부정은 거짓이고, 실제로 $x = 0$이 이 $\forall$의 반례다 — $0 + y = y$이므로 조건을 만족하는 $y$가 없다. **복기.** 네 줄 모두에서 층의 개수와 배치가 원명제와 같다. 두 겹짜리에서 순서까지 뒤집어 (c)를 "$\forall y \exists x$"로 적는 실수가 잦은데, 그렇게 적으면 원명제와 무관한 명제가 되어 진리값이 반대라는 보장이 사라진다. ### 문제 4 **접근.** 백지 재현이므로 답을 옮겨 적는 것이 아니라 훈련의 **판정 지점**을 다시 통과하는 것이 목적이다. 훈련 1은 증인이 맞춤인지, 훈련 2는 무대$\cdot$자격이 보존됐는지, 훈련 3은 두 방향이 모두 증명됐는지가 각각의 판정 지점이다. **풀이.** 세 훈련의 결론은 다음과 같다. 훈련 1 — 원명제 "$\forall x \in \mathbb{R},\ \exists y \in \mathbb{R},\ y > x$"는 참이고, 증인은 맞춤 증인 $y = x + 1$이다(검증: $(x+1) - x = 1 > 0$). 부정은 두 걸음으로 "$\exists x \in \mathbb{R},\ \forall y \in \mathbb{R},\ y \le x$"가 되고, 이는 "가장 큰 실수가 존재한다"는 뜻이라 거짓이다. 순서를 바꾼 "$\exists y \forall x,\ y > x$"는 만능 증인을 요구하므로 거짓이다. 훈련 2 — 원명제 "$\forall x \in \mathbb{R},\ \exists n \in \mathbb{N},\ n > x$"는 아르키메데스 성질(1권 45주차 §1.5에서 채택, S5주차 문제 14에서 한 조각을 증명)에 의해 참이다. 부정은 두 걸음 모두에서 무대 $\mathbb{R}$과 $\mathbb{N}$을 보존한 채 "$\exists x \in \mathbb{R},\ \forall n \in \mathbb{N},\ n \le x$"가 되고, 원명제가 참이므로 거짓이다. 훈련 3 — 쉬운 방향("$n$이 3의 배수 $\Rightarrow$ $n^2$이 3의 배수")은 정의를 풀어 $n = 3k$에서 $n^2 = 3(3k^2)$을 얻으면 끝난다. 막히는 방향은 대우 "$n$이 3의 배수가 아니면 $n^2$도 3의 배수가 아니다"로 돌리고, 나눗셈 정리(1권 33주차)로 $n = 3k+1$과 $n = 3k+2$ 두 경우를 만들어 각각 나머지가 1임을 계산한다. 두 방향을 합쳐 특성화가 확립되고, 그것을 인용하면 "$n^2$이 3의 배수 $\Rightarrow$ $n^2 + n$이 3의 배수"가 $n^2 + n = 3m + 3k = 3(m+k)$ 한 줄로 끝난다. 자세한 유도는 위의 빈칸 사다리 답 항목에 있다. 대조할 때 다음 세 자리를 특히 확인한다. 훈련 1의 (3) — $\exists y$를 뒤집은 결과가 $\forall y$이고, 층의 자리는 그대로다. 훈련 2의 (2) — 무대 $\mathbb{R}$과 $\mathbb{N}$이 두 걸음 내내 살아 있다. 훈련 3의 ③ — 막히는 방향을 대우로 돌리고 나눗셈 정리로 두 경우를 만들었다. 세 자리 중 하나라도 다르게 적었다면 그 항목의 본문 절(§1.6, §1.5, §1.7)로 돌아간다. ### 문제 5 **접근.** 정의를 정확히 적는 것이 절반이다. 층 세 개와 자격 두 개, 그리고 무대 $\mathbb{N}$을 먼저 종이에 나열한 뒤 걸음 ②를 세 번 돌린다. 매 줄에서 자격 "$> 0$"과 "$> N$", 그리고 무대 $\in \mathbb{N}$이 그대로 따라오는지 확인하는 것이 이 문제의 채점 지점이다. **풀이.** 부정할 대상은 $\sim(\forall \varepsilon > 0,\ \exists N \in \mathbb{N},\ \forall n \in \mathbb{N}\ (n > N),\ \lvert a_n - L \rvert < \varepsilon)$이다. 첫 걸음에서 바깥 층 $\forall \varepsilon$을 반전하면 $\exists \varepsilon > 0,\ \sim(\exists N \in \mathbb{N},\ \forall n \in \mathbb{N}\ (n > N),\ \lvert a_n - L \rvert < \varepsilon)$이 된다. 둘째 걸음에서 $\exists N$을 반전하면 $\exists \varepsilon > 0,\ \forall N \in \mathbb{N},\ \sim(\forall n \in \mathbb{N}\ (n > N),\ \lvert a_n - L \rvert < \varepsilon)$이 된다. 셋째 걸음에서 $\forall n$을 반전하고 맨 안쪽에서 $<$를 $\ge$로 바꾸면 다음이 끝 모양이다. $$ \exists \varepsilon > 0,\ \forall N \in \mathbb{N},\ \exists n \in \mathbb{N}\ (n > N),\ \lvert a_n - L \rvert \ge \varepsilon $$ 말로 옮기면 "어떤 오차 폭 $\varepsilon > 0$이 있어서, 아무리 큰 문턱 $N$을 잡아도, 그 너머에 $L$과의 거리가 $\varepsilon$ 이상인 항이 있다"이다. $\blacksquare$ **검산.** 자격 두 개와 무대 $\mathbb{N}$이 끝 모양에 그대로 남아 있고, $\sim$가 양화사 밖에 하나도 없다. 두 조건이 모두 충족되면 절차가 끝난 것이다. ### 문제 6 **접근.** 각 예에서 정의가 무엇인지부터 적고 그 옆에 동치인 조건을 적는다. 세 예 모두 "이 동치가 어디서 증명됐는가"를 한 줄로 함께 적어야 완결이다 — 출처가 없으면 §1.7의 삭제 실험이 경고한 상태로 돌아간다. **풀이.** ① 짝수. 정의는 "$n = 2k$인 정수 $k$가 존재한다"이고, 특성화는 "$n^2$이 짝수이다"이다. 이 동치는 1권 19주차 예제 2.1이 $\Leftarrow$ 방향을 대우로, 1권 1주차 문제 9가 $\Rightarrow$ 방향을 직접으로 증명한다. ② 부분집합. 정의는 "$A$의 모든 원소가 $B$에 속한다"이고, 특성화는 "$A \cup B = B$"이다. 이 동치는 S3주차 문제 11이 한 방향을, S4주차 문제 13이 나머지 방향을 증명한다. ③ 단사. 정의는 "$f(a) = f(b)$이면 $a = b$"이고, 특성화는 그 대우인 "$a \neq b$이면 $f(a) \neq f(b)$"이다. 이 동치는 대우 동치 $P \Rightarrow Q \equiv \sim Q \Rightarrow \sim P$ (C3주차 §1의 논리 동치 법칙)가 보증하므로 지금 인용할 수 있다. ③에 흔히 함께 적히는 "$f$가 단사 $\iff$ $f$를 되돌리는 함수가 있다"는 사정이 다르다. 역함수를 다루는 것은 C12주차이고, 그 주차가 세우는 것은 **전단사**에 대한 동치 "$f$가 전단사 $\iff$ $f$가 역함수를 갖는다"다. 단사 하나만으로 되돌리는 함수를 얻는 동치는 이 책 어디에도 증명이 없으므로 특성화의 **후보**에 머물고, 근거로 인용할 수 없다. **복기.** ③의 두 문장이 이 문제의 갈림길이다. 증명된 동치(대우)는 지금 쓸 수 있고, 증명이 없는 동치는 특성화의 **후보**일 뿐이다. 후보를 근거로 삼는 순간 §1.7의 삭제 실험이 경고한 상태로 돌아간다. ### 문제 7 **접근.** $x = 2$나 $x = -1$처럼 큰 수와 음수만 시험하면 전부 통과해 참으로 보인다. 부등식을 $x^2 - x \ge 0$, 곧 $x(x-1) \ge 0$으로 정리하면 두 인수의 부호가 갈리는 구간이 보인다 — $0 < x < 1$에서 $x > 0$이고 $x - 1 < 0$이므로 곱이 음수다. **풀이.** 명제는 **거짓**이다. 반례로 $x = \frac12$을 제시한다. 검증: $\left(\frac12\right)^2 = \frac14$이고 $\frac14 < \frac12$이므로 $x^2 \ge x$가 성립하지 않는다. 반례 하나로 $\forall$ 명제가 무너진다. 부정은 $\exists x \in \mathbb{R},\ x^2 < x$이다($\ge$의 부정은 $<$다). 이 부정은 **참**이고, 증인은 같은 $x = \frac12$이다. 검증: $\frac14 < \frac12$. **복기.** 원명제의 반례와 부정의 증인이 같은 값인 것은 우연이 아니다. $\forall$ 명제의 반례란 정확히 그 부정($\exists$ 명제)의 증인이다 — §1.5의 부정 규칙이 두 칸을 잇는 다리이고, 그래서 $\exists$의 거짓 칸이라는 가장 비싼 칸을 부정으로 우회할 수 있다. ### 문제 8 **접근.** 재료가 같고 순서만 다른 한 쌍이다. 먼저 안쪽 $\exists$가 어느 층 안에 있는지 확인해 맞춤인지 만능인지를 판정하고, 만능이 요구되면 상수 후보를 하나 잡아 두 개의 서로 다른 $x$로 충돌시킨다. **풀이.** $C$는 **참**이다. 실수 $x$가 주어진 뒤 $y = x^2$으로 둔다. 검증: $x^2 \in \mathbb{R}$이고 등식 $y = x^2$이 정의대로 성립한다. $\exists y$가 $\forall x$의 안쪽에 있으므로 $y$를 $x$의 식으로 두는 것이 합법이다 — 맞춤 증인이다. $D$는 **거짓**이다. 만능 증인 $y_0$이 있다고 하자. $x = 0$을 대입하면 $y_0 = 0^2 = 0$이고, $x = 1$을 대입하면 $y_0 = 1^2 = 1$이다. 그러면 $0 = y_0 = 1$이 되어 모순이다. 따라서 모든 $x$를 감당하는 하나의 $y$는 존재하지 않는다. 순서 차이: $C$에서는 $y$가 $x$가 정해진 뒤에 정해지므로 $x$를 참조할 수 있고, $D$에서는 $y$가 먼저 정해지므로 $x$를 참조할 수 없다 (S8주차 §1.4의 의존성 문법). **검산.** 한 방향 교환 정리에 따르면 $D$가 참이면 $C$도 참이어야 한다. 여기서는 $C$가 참이고 $D$가 거짓이므로 정리와 어긋나지 않는다 — 정리가 금지하는 것은 "$D$ 참, $C$ 거짓"뿐이다. ### 문제 9 **접근.** 두 방향의 난이도가 다르다. $\Rightarrow$ 방향은 가정이 $n$ 자체의 성질이라 정의가 즉시 풀리고, $\Leftarrow$ 방향은 가정이 $n^2$이라는 합성된 식의 성질이라 $n$을 꺼낼 등식이 없어 막힌다(1권 19주차 §1.5의 신호). 막히는 방향은 대우로 돌린다. **풀이.** ($\Rightarrow$) $n$이 짝수라 하자. 정의에 의해 $n = 2k$인 정수 $k$가 존재한다. 그러면 $n^2 = 4k^2 = 2(2k^2)$이고 $2k^2$은 정수이므로 $n^2$은 짝수이다. ($\Leftarrow$) 대우로 증명한다. "$n^2$이 짝수이면 $n$이 짝수이다"의 대우는 정확히 "$n$이 짝수가 아니면 $n^2$도 짝수가 아니다"이다. 여기에 두 사실을 넣으면 다루기 쉬운 꼴이 된다. 모든 정수는 짝수이거나 홀수이므로(1권 17주차의 짝$\cdot$홀 이분, 1권 33주차의 나눗셈 정리) 가정 "$n$이 짝수가 아니다"는 "$n$이 홀수이다"가 되고, 짝수이면서 홀수인 정수는 없으므로(1권 22주차 문제 5) 결론 "$n^2$이 짝수가 아니다"는 "$n^2$이 홀수이다"와 같다. 그래서 다음을 보이면 된다 — "$n$이 홀수이면 $n^2$도 홀수이다". $n$이 홀수라 하자. 정의에 의해 $n = 2k+1$인 정수 $k$가 존재한다. 그러면 $$ n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1 $$ 이고 $2k^2 + 2k$는 정수이므로 $n^2$은 홀수이다. 대우가 증명되었으므로 $n^2$이 짝수이면 $n$은 짝수이다. 두 방향을 합쳐 특성화가 확립된다. $\blacksquare$ **응용.** $n^2$이 짝수라 하자. 방금 확립한 특성화의 $\Leftarrow$ 방향에 의해 $n$도 짝수이므로 $n = 2a$인 정수 $a$가 존재하고, $n^2 = 2b$인 정수 $b$도 존재한다. 그러면 $n^2 + n = 2b + 2a = 2(a + b)$이고 $a + b$는 정수이므로 $n^2 + n$은 짝수이다. $\blacksquare$ **복기.** §1.7의 시도가 막힌 자리가 정확히 여기다. 그때 없던 것은 계산 능력이 아니라 "$n^2$의 성질에서 $n$의 성질로 건너가는 다리"였고, 그 다리가 방금 확립한 특성화다. 다리를 손에 넣으면 §1.7의 명제 "$n^2$이 짝수이면 $n+2$도 짝수이다"는 "$n$이 짝수이므로 $n = 2a$이고 $n + 2 = 2(a+1)$이다"로 한 줄에 끝난다. 위의 응용에 대해서는 한 가지를 구분해 두어야 한다. "$n^2 + n$이 짝수"는 특성화 없이도 얻을 수 있다 — 예제 2.3의 표현 1이 경우 나누기만으로 더 강한 명제 "임의의 정수 $n$에 대해 $n^2 + n$은 짝수이다"를 증명했다. 그러므로 여기서 특성화가 하는 일은 길을 여는 것이 아니라 길을 짧게 하는 것이다. 특성화가 없으면 아예 막히는 사례는 §1.7의 $n+2$ 명제이고, 훈련 3의 3의 배수판($n^2 + n$이 늘 3의 배수는 아니다 — $n = 1$이면 2다)이다. ### 문제 10 **접근.** 원명제와 그 "부정"의 진위를 각각 판정해 나란히 놓는다. 부정의 자격은 하나뿐이다 — 어떤 상황에서도 진리값이 원문과 반대여야 한다. 둘이 동시에 참이면 그 자격이 무너진 것이고, 무너진 자리는 §1.5의 다섯 걸음 중 하나다. **풀이.** 진단: 걸음 ③(무대$\cdot$자격 보존)을 어겼다. 자격 "$x > 0$"까지 부정해 "$x \le 0$"으로 바꾼 것이 오류다. 확인: 원명제 "$\forall x > 0,\ x^2 > 0$"은 참이다(양수의 제곱은 양수). 그런데 제시된 "부정" "$\exists x \le 0,\ x^2 \le 0$"도 참이다 — $x = 0$이 $x \le 0$을 만족하고 $0^2 = 0 \le 0$이기 때문이다. 원문과 부정이 동시에 참이므로 부정이 아니다. 올바른 부정: $\exists x > 0,\ x^2 \le 0$. 자격은 그대로 두고 본체만 뒤집는다. 이 문장은 거짓이고(양수의 제곱은 항상 양수), 원명제가 참이므로 진리값이 반대다. **복기.** 자격이 왜 보존되는지는 확인 6에서 계산으로 확인했다. 자격 붙은 전칭을 조건문으로 풀면 $\forall x \in \mathbb{R},\ (x > 0 \Rightarrow x^2 > 0)$이고, 여기에 반전과 조건문 부정을 차례로 적용하면 $\exists x \in \mathbb{R},\ (x > 0 \wedge x^2 \le 0)$이 되어 자격이 $\wedge$의 한쪽으로 살아남는다. ### 문제 11 **접근.** 층이 세 개이고 맨 안쪽이 부등식이 아니라 조건문이다. 절차는 달라지지 않는다 — 양화사 세 층을 바깥부터 뒤집은 뒤, 마지막에 남은 $\sim(P \Rightarrow Q)$를 C3주차의 조건문 부정으로 처리한다. 자격 "$\varepsilon > 0$"과 "$\delta > 0$"은 네 걸음 내내 그대로 따라온다. **풀이.** 부정할 대상은 다음과 같다. $$ \sim\big(\forall \varepsilon > 0,\ \exists \delta > 0,\ \forall x \in \mathbb{R},\ (\lvert x-a \rvert < \delta \Rightarrow \lvert f(x)-f(a) \rvert < \varepsilon)\big) $$ 첫 걸음($\forall \varepsilon$ 반전): $\exists \varepsilon > 0,\ \sim(\exists \delta > 0,\ \forall x \in \mathbb{R},\ (\cdots))$. 둘째 걸음($\exists \delta$ 반전): $\exists \varepsilon > 0,\ \forall \delta > 0,\ \sim(\forall x \in \mathbb{R},\ (\cdots))$. 셋째 걸음($\forall x$ 반전, 무대 $\mathbb{R}$은 그대로): $\exists \varepsilon > 0,\ \forall \delta > 0,\ \exists x \in \mathbb{R},\ \sim(\lvert x-a \rvert < \delta \Rightarrow \lvert f(x)-f(a) \rvert < \varepsilon)$. 넷째 걸음(조건문 부정 $\sim(P \Rightarrow Q) \equiv P \wedge \sim Q$): $$ \exists \varepsilon > 0,\ \forall \delta > 0,\ \exists x \in \mathbb{R},\ \big(\lvert x-a \rvert < \delta \ \wedge\ \lvert f(x)-f(a) \rvert \ge \varepsilon\big) $$ 말로 옮기면 "어떤 오차 폭 $\varepsilon > 0$이 있어서, 아무리 작은 $\delta > 0$을 잡아도, $a$에서 $\delta$보다 가까우면서 함숫값은 $f(a)$에서 $\varepsilon$ 이상 떨어진 $x$가 있다"이다. 이것이 "$f$가 $a$에서 연속이 아니다"의 뜻이다. $\blacksquare$ **검산.** 끝 모양에 $\sim$가 남아 있지 않고, 화살표도 남아 있지 않다(조건문은 부정 뒤에 $\wedge$가 된다). 자격 두 개가 그대로 있다. 세 조건이 모두 충족되면 완성이다. ### 문제 12 **접근.** "정의가 아니다"를 보이려면 홀수의 원정의가 무엇인지부터 확정해야 한다. 원정의는 "$n = 2k+1$인 정수 $k$가 존재한다"이므로, "짝수가 아니다"는 그 원정의와 다른 조건이고 따라서 동치를 증명해야 쓸 수 있다. 동치 증명은 두 방향이고, 각 방향이 서로 다른 성질을 쓴다. **풀이.** 이것이 정의가 아닌 이유: 홀수의 정의는 "$n = 2k+1$ 꼴"이라는 **존재 조건**으로 약속되어 있고, "짝수가 아니다"는 그 약속에 들어 있지 않은 부정형 조건이다. 두 조건이 같은 정수를 걸러 낸다는 것은 증명해야 얻는 사실이므로, "홀수 = 짝수가 아닌 정수"는 정의가 아니라 특성화다. ($\Rightarrow$ 배타성) $n = 2k+1$인 정수 $k$가 존재한다고 하자. $n$이 짝수라면 $n = 2m$인 정수 $m$도 존재하므로 $2m = 2k+1$이고 $1 = 2(m-k)$가 된다. 그러면 $2 \mid 1$인데 1의 약수는 $1$과 $-1$뿐이므로(1권 22주차 보조 명제 22.A) 모순이다. 따라서 $n$은 짝수가 아니다. 같은 논증이 1권 22주차 문제 5다. ($\Leftarrow$ 전수성) $n$이 짝수가 아니라 하자. 모든 정수는 짝수이거나 홀수이므로 (1권 17주차, 나눗셈 정리) $n$은 홀수이고, 홀수의 정의에 의해 $n = 2k+1$인 정수 $k$가 존재한다. 두 방향을 합쳐 특성화가 확립된다. $\blacksquare$ **복기.** 한 방향은 배타성(짝수이면서 홀수일 수 없다), 다른 방향은 전수성(둘 중 하나이긴 하다)을 쓴다. 두 성질이 각각 다른 주차에서 증명된 사실이므로, 이 특성화를 인용할 때는 두 출처를 함께 대는 것이 정확하다. ### 문제 13 **접근.** 명제는 하나이고 무대만 바뀐다. §1.3의 조각 해부에서 본 대로 무대는 진리값을 결정하는 조각이므로, 각 무대에서 증인이 그 무대 **안에** 있는지만 판정하면 된다. 증인 후보는 어느 무대에서나 $\sqrt2$로 같다. **풀이.** (a) $\mathbb{N}$에서 **거짓**. $1^2 = 1 < 2$이고 $2^2 = 4 > 2$이며, 1과 2 사이에 자연수가 없다. 자연수는 커질수록 제곱이 커지므로 $n \ge 2$이면 $n^2 \ge 4 > 2$이다. 따라서 $n^2 = 2$인 자연수는 없다. (b) $\mathbb{Q}$에서 **거짓**. $x^2 = 2$인 양수는 $\sqrt2$뿐인데 $\sqrt2$는 무리수이므로 (1권 21주차에서 귀류법으로 증명) 유리수 무대 안에 증인이 없다. 음수 쪽도 $-\sqrt2$가 무리수이므로 마찬가지다. (c) $\mathbb{R}$에서 **참**. 증인 $x = \sqrt2$. 검증: $\sqrt2 \in \mathbb{R}$이고 $(\sqrt2)^2 = 2$이다. (d) $\mathbb{C}$에서 **참**. 증인은 그대로 $\sqrt2$다. 검증: $\mathbb{R} \subseteq \mathbb{C}$이므로 $\sqrt2 \in \mathbb{C}$이고 $(\sqrt2)^2 = 2$이다. **복기.** 존재 명제는 무대가 커질수록 참이 되기 쉽다 — 후보가 늘기 때문이다. 전칭 명제는 정반대로 무대가 커질수록 거짓이 되기 쉽다. 명제를 옮겨 적을 때 무대를 빠뜨리면 이 방향성 자체가 사라진다. ### 문제 14 **접근.** 조건 세 개를 한 줄로 잇는 대신 두 쌍으로 나눠 각각 양방향으로 증명한다. 집합의 상등은 두 포함으로 쪼개고(1권 27주차), 포함은 원소 하나를 잡아 추적한다. **풀이.** **쌍 1: $A \subseteq B \iff A \cup B = B$.** ($\Rightarrow$) $A \subseteq B$라 하자. $B \subseteq A \cup B$는 합집합의 정의로 항상 성립한다. 거꾸로 $x \in A \cup B$라 하면 $x \in A$이거나 $x \in B$인데, 앞의 경우 가정에 의해 $x \in B$이고 뒤의 경우도 $x \in B$이므로 $A \cup B \subseteq B$이다. 두 포함으로 $A \cup B = B$이다. ($\Leftarrow$) $A \cup B = B$라 하자. $x \in A$이면 $x \in A \cup B = B$이므로 $A \subseteq B$이다. **쌍 2: $A \subseteq B \iff A \cap B = A$.** ($\Rightarrow$) $A \subseteq B$라 하자. $A \cap B \subseteq A$는 교집합의 정의로 항상 성립한다. 거꾸로 $x \in A$이면 가정에 의해 $x \in B$이므로 $x \in A \cap B$이고, 따라서 $A \subseteq A \cap B$이다. 두 포함으로 $A \cap B = A$이다. ($\Leftarrow$) $A \cap B = A$라 하자. $x \in A = A \cap B$이면 $x \in B$이므로 $A \subseteq B$이다. 두 쌍이 모두 $A \subseteq B$를 거치므로 세 조건이 서로 동치다. $\blacksquare$ 편의: 원소 하나를 따라가는 논증에는 정의 "$A \subseteq B$"가 편하고, 집합 대수로 식을 변형하는 계산에는 등식 꼴인 "$A \cup B = B$"나 "$A \cap B = A$"가 편하다 — 등식은 다른 식에 그대로 대입할 수 있기 때문이다. **복기.** 세 조건을 잇는 데 동치 두 개면 충분했다. iff의 추이성 덕분이고, 이것이 특성화를 여러 개 모아 두는 값이다 — 상황마다 가장 가까운 표현으로 한 번에 건너뛴다. ### 문제 15 **접근.** 세 겹이지만 안쪽 두 겹은 $m$이 정해진 뒤의 문제다. $\exists n$이 $\forall m$의 안쪽에 있으므로 $n$을 $m$의 식으로 둘 수 있다 — 가장 게으른 선택부터 시험한다. 부정을 유도할 때는 맨 안쪽 조건문 하나가 남는 것에 주의한다. **풀이.** 명제는 **참**이다. 자연수 $m$이 주어지면 $n = m$으로 둔다. 그러면 안쪽 문장은 "$\forall k \in \mathbb{N},\ (k \le m \Rightarrow k \le m)$"이 되고, 이는 임의의 $k$에 대해 가정과 결론이 같은 항진 조건문이므로 참이다. 맞춤 증인 $n = m$이 통과한다. 부정을 유도한다. 바깥부터 세 걸음과 조건문 부정 한 걸음이다. $$ \exists m \in \mathbb{N},\ \forall n \in \mathbb{N},\ \exists k \in \mathbb{N},\ (k \le m \ \wedge\ k > n) $$ 이 부정이 거짓임을 확인한다. 어떤 $m$을 잡더라도, $n = m$으로 두면 $k \le m$이면서 $k > m$인 자연수 $k$는 존재하지 않는다($k \le m$과 $k > m$은 동시에 성립할 수 없다). 따라서 안쪽 $\exists k$가 실패하고, $\forall n$ 층에서 반례 $n = m$이 나오므로 부정은 거짓이다. 부정이 거짓이므로 원명제가 참임이 다시 확인된다. $\blacksquare$ **복기.** 원명제를 직접 판정한 것과 부정이 거짓임을 보인 것이 서로 검산이 된다. 두 경로에서 같은 값($n = m$)이 각각 증인과 반례로 쓰인 것도 문제 2의 검산과 같은 구조다. ### 문제 16 **접근.** (a)는 순환소수를 급수로 펼치는 계산이다. 공비를 먼저 확정해야 공식이 적용된다. $0.2727\ldots$은 두 자리씩 반복되므로 각 항이 앞 항의 $\frac{1}{100}$이다. (b)는 §1.7의 삭제 실험을 유리수에 적용하는 문제다 — 유리수의 정의가 무엇이었는지부터 적는다. **풀이.** (a) $0.2727\ldots$을 급수로 펼치면 다음과 같다. $$ 0.2727\ldots = \frac{27}{100} + \frac{27}{100^2} + \frac{27}{100^3} + \cdots $$ 첫항 $a = \frac{27}{100}$, 공비 $r = \frac{1}{100}$인 무한등비급수이고 $\lvert r \rvert < 1$이므로 합은 $\dfrac{a}{1-r} = \dfrac{27/100}{1 - 1/100} = \dfrac{27/100}{99/100} = \dfrac{27}{99} = \dfrac{3}{11}$이다. 합 공식 $\frac{a}{1-r}$은 1권 46주차 문제 17에서 부분합 $\frac{1-r^{n+1}}{1-r}$과 $r^{n+1} \to 0$으로 증명했다(근거 ④). 분자와 분모가 모두 정수이고 분모가 0이 아니므로 이 값은 유리수다. 같은 계산이 임의의 순환 마디에 대해 작동한다 — 마디의 길이가 $d$이면 공비가 $\frac{1}{10^d}$이 되고, 합은 언제나 정수 나누기 정수의 꼴로 나온다. 유한 소수는 마디가 없는 경우이므로 $\frac{(\text{정수})}{10^d}$ 꼴이라 곧바로 유리수다. 순환 마디 앞에 비순환 부분이 $p$자리 붙어 있는 경우도 같은 틀로 들어온다. $r = (\text{유한 소수}) + 10^{-p} \times (\text{순수 순환 소수})$로 쪼개면 앞은 $\frac{(\text{정수})}{10^p}$ 꼴이라 유리수이고 뒤는 위 계산으로 유리수이므로, 유리수의 덧셈 닫힘성(근거 ②)에 의해 합도 유리수다. 예를 들어 $0.1666\ldots = \frac{1}{10} + \frac{1}{10}\cdot\frac{6/10}{1 - 1/10} = \frac{1}{10} + \frac{1}{15} = \frac{1}{6}$이다. (b) 유리수의 정의는 "$r = \frac{a}{b}$인 정수 $a$와 0이 아닌 정수 $b$가 존재한다"이고, 십진 전개에 대한 언급은 정의에 들어 있지 않다. "유한하거나 순환한다"는 그 정의와 동치임이 증명된 특성화이지 정의 자체가 아니다. 이것을 정의로 삼으면 두 가지가 무너진다. 첫째, (a)에서 쓴 급수 합 계산이 근거를 잃는다 — 그 계산의 결론이 바로 "정수 나누기 정수"라는 원정의 꼴이었기 때문이다. 둘째, 십진 전개를 정의로 두면 십진법이라는 표기 약속이 수의 성질을 정하게 되어, 표기를 바꿀 때마다 유리수의 범위를 다시 증명해야 한다. **복기.** (b)가 §1.7의 셋째 조각이 막는 두 붕괴 중 순환 쪽 사례다. 증명되지 않은 동치를 정의 자리에 놓으면, 그 동치를 증명하는 데 쓰던 사실이 근거를 잃는다. ### 문제 17 **접근.** 참인 쪽은 맞춤 증인을 제시하면 끝난다. 거짓인 쪽은 만능 증인 $y_0$이 있다고 가정한 뒤 그 $y_0$을 무너뜨리는 $x$를 만든다 — $y_0$ 자신을 $x$ 자리에 넣는 것이 가장 짧다. 마지막 물음은 참인 쪽의 증인이 왜 만능이 될 수 없는지를 적는 것이다. **풀이.** (참) $\forall x \in \mathbb{R},\ \exists y \in \mathbb{R},\ y > x$. 실수 $x$가 주어지면 $y = x + 1$로 둔다. 검증: $x + 1 \in \mathbb{R}$이고 $(x+1) - x = 1 > 0$이므로 $y > x$이다. $\exists y$가 안쪽이므로 $y$를 $x$의 식으로 두는 것이 합법이다. (거짓) $\exists y \in \mathbb{R},\ \forall x \in \mathbb{R},\ y > x$. 만능 증인 $y_0$이 있다고 하자. 안쪽 $\forall x$는 모든 실수 $x$를 훑으므로 $x = y_0$도 대입할 수 있고, 그러면 $y_0 > y_0$이 되어 부등호의 비반사성에 어긋난다. 모순이므로 그런 $y_0$은 존재하지 않는다. $\blacksquare$ 역이 성립하지 않는 이유: 한 방향 교환 정리는 만능 증인이 있을 때 그것을 각 $x$에 재사용하는 것이므로 $\exists\forall$에서 $\forall\exists$로만 간다. 여기서 참인 쪽의 증인 $y = x+1$은 식 안에 $x$가 들어 있어 $x$가 정해지기 전에는 제시할 수 없다 — 맞춤 증인이지 만능 증인이 아니므로 거꾸로 올라갈 수 없다. **복기.** 만능 증인을 무너뜨리는 표준 수법은 "증인 자신을 안쪽 변수에 대입하기"다. $y_0 > y_0$처럼 즉시 모순이 나오는 값을 고르는 것이고, 같은 수법을 S8주차의 반증 문제에서도 쓴다. ### 문제 18 **접근.** 세 오류가 서로 다른 걸음에서 났다. 각각을 §1.5의 다섯 걸음 표에 대 보고 어느 칸이 비었는지 지목한다. 진단이 끝나면 반드시 올바른 부정까지 적는다 — 오류만 지적하고 수정본을 쓰지 않으면 절반만 제출한 것이다. **풀이.** (a) 걸음 ②를 어겼다 — 양화사를 반전하지 않고 $\exists$를 그대로 두었다. 본체만 뒤집힌 문장은 원문과 진리값이 반대라는 보장이 없다. 올바른 부정: $\forall x,\ \sim P(x)$. 확인: "$P(x)$인 $x$가 있다"의 실패는 "전원이 $P$를 만족하지 않는다"이다. (b) 역시 걸음 ②를 어겼다 — 두 층 모두 반전되지 않았다. 올바른 부정: $\exists x\, \forall y,\ \sim P(x,y)$. 바깥 $\forall x$가 $\exists x$로, 안쪽 $\exists y$가 $\forall y$로 각각 제자리에서 뒤집히고 층의 배치는 그대로다. (c) 걸음 ③을 어겼다 — 무대 $\mathbb{N}$을 부정해 $n \notin \mathbb{N}$으로 바꿨다. 올바른 부정: $\exists n \in \mathbb{N},\ n < 1$. 원명제 "모든 자연수는 1 이상이다"는 참이고 이 부정은 거짓이므로 진리값이 반대다. 제시된 문장은 $n = 0$ 같은 것을 증인으로 삼아 참이 되므로, 원문도 참이고 부정도 참인 붕괴가 일어난다. **복기.** 세 오류 모두 "본체만 보고 껍질을 안 봤다"는 하나의 습관에서 나온다. 부정 절차의 걸음 ②와 ③은 껍질(양화사와 무대)을 다루는 두 걸음이고, 둘 중 하나만 빠져도 부정이 아니게 된다. ### 문제 19 **접근.** $10a + b$를 그대로 3으로 나누려 하면 $a$와 $b$의 값을 알아야 한다. 대신 계수 10을 "3의 배수 + 나머지"로 쪼갠다. 쪼갠 뒤 3의 배수 부분을 옆으로 밀어내면 남는 것이 자리합이고, 그러면 $n$의 3 나누어떨어짐이 자리합의 그것과 같아진다. **풀이.** 두 자리 수 $n$을 $n = 10a + b$라 하자($a$는 십의 자리, $b$는 일의 자리이고 둘 다 정수). 10을 $9 + 1$로 쪼개면 다음이 성립한다. $$ n = 10a + b = 9a + a + b = 9a + (a + b) $$ $9a = 3(3a)$이고 $3a$는 정수이므로 $9a$는 3의 배수다. ($\Rightarrow$) $n$이 3의 배수라 하자. $n = 3t$인 정수 $t$가 존재하므로 $a + b = n - 9a = 3t - 9a = 3(t - 3a)$이고 $t - 3a$는 정수이므로 자리합 $a+b$는 3의 배수다. ($\Leftarrow$) $a + b$가 3의 배수라 하자. $a + b = 3s$인 정수 $s$가 존재하므로 $n = 9a + 3s = 3(3a + s)$이고 $3a + s$는 정수이므로 $n$은 3의 배수다. 두 방향을 합쳐 특성화가 확립된다. $\blacksquare$ 편의: 판정 대상이 작아진다. $n = 51$을 3으로 직접 나누는 대신 자리합 $5 + 1 = 6$이 3의 배수인지만 보면 되고, 6은 곧바로 판정된다. 자릿수가 늘수록 이 차이가 커진다 — 여섯 자리 수의 나눗셈 한 번보다 한 자리 수 여섯 개의 덧셈이 훨씬 싸다. **검산.** $51 = 3 \times 17$이므로 3의 배수이고, 자리합 $6 = 3 \times 2$도 3의 배수다. $52$는 3의 배수가 아니고 자리합 $7$도 아니다. 두 사례가 양방향을 각각 확인한다. (세 자리 이상은 $10^k$를 $(10^k - 1) + 1$로 쪼개고 $10^k - 1$이 3의 배수임을 귀납으로 보이면 같은 논증이 그대로 작동한다 — 합동 산술은 C6주차, 귀납은 C8주차에서 정식으로 다룬다.) ### 문제 20 **접근.** (a)는 예제 2.2의 네 줄을 근거로 삼아 세 문장을 만드는 문제다. 어느 줄이 S8주차의 무엇이고 어느 줄이 S10주차의 무엇인지 대응을 먼저 적어 두면 문장이 나온다. (b)는 예제 2.3의 세 표현 중 길이 차이가 어디서 왔는지를 한 문장으로 압축하는 문제다. **풀이.** (예시 답안) (a) 예제 2.2에서 수렴의 세 겹을 부정할 때, 가장 바깥 층 하나만 처리하고 남은 안쪽을 한 겹 줄어든 새 문제로 삼는 S8주차의 절차와, 양화사를 반전하고 본체만 뒤집는 S10주차의 규칙이 각 줄에서 그대로 작동했다. 이번 주가 더한 것은 기법이 아니라 그 두 가지가 $\sim(\forall \cdots) \equiv \exists \cdots \sim$이라는 논리 동치의 반복 적용이라는 확인이다. 자격 보존이 핵심인 이유는, 자격을 뒤집으면 원명제가 심사하지 않던 대상이 들어와 원문과 부정이 동시에 참이 될 수 있고, 그 순간 부정이라는 이름의 자격 자체가 무너지기 때문이다. (b) 예제 2.3에서 과녁 "$n^2 + n$이 짝수"를 연속한 두 정수의 곱이라는 기증명 정리와 법 2의 합동이라는 특성화 쪽으로 옮기자 경우 나누기 두 벌이 한 줄로 줄었고, 이는 S4주차가 "사실 목록과 과녁의 겉모양에 가까운 표현을 고른다"는 조준 규칙으로 이미 쓰던 일이다. 원서 2.11절은 그 표현들에 특성화라는 이름과 사용 자격을 붙여, 언제 갈아 끼울 수 있는지를 "동치가 증명됐을 때"로 못 박는다. 특성화는 표현을 고를 자유를 주지만, 그 자유는 동치를 증명해 둔 만큼만 주어지므로 인용할 때마다 어디서 증명됐는지를 댈 책임이 따른다. --- **다음 주 예고 (C5주차):** Chartrand 3장 — 직접 증명과 대우 증명에 더해, 이 책만의 두 도구를 얻는다. **자명한 증명과 공허한 증명**(결론이 항상 참이거나 가정이 항상 거짓이라 조건문이 자동으로 참이 되는 경우)과, **증명 평가**(제출된 증명을 읽고 옳은지 판정하는 훈련)다. 1학기 내내 진단이라 부르던 작업이 여기서 정식 과제가 되고, 이번 주의 양화 작업 3단 뼈대가 그 판정의 첫 걸음으로 쓰인다. 원서 3장을 통독하고 온다.