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\)가 남지 않은 끝 모양 |
확인 14. 목표 칸의 진위 쪽 빈칸을 채워 보자. §1.4의 비대칭 표에 따르면, 참일 때와 거짓일 때 각각 무엇을 제출해야 하는가.
답
\(\forall\) 명제라면 참일 때 일반 논증, 거짓일 때 반례와 검증 계산. \(\exists\) 명제라면
참일 때 증인과 검증 계산, 거짓일 때 전원 탈락의 일반 논증. 어느 칸이든 값만으로는
제출물이 되지 않고 검증 계산까지가 제출물이다.
1단계 — \(A\)를 판정한다. 바깥 층이 \(\forall\)이므로 참을 주장하려면 문자를 잡은 일반 논증이 필요하다.
확인 15. \(A\)가 참임을 보이는 한 줄을 적어 보자. 어떤 사실을 인용하는가.
답
“임의의 실수 \(x\)에 대해 \(x^2 \ge 0\)이다 — 실수의 제곱은 음이 아니다(1권 16주차의
실수 기본 성질).” 특정한 \(x\)를 넣어 확인한 것이 아니라 임의의 \(x\)를 문자로 잡은
논증이므로 \(\forall\)의 참 칸을 채운다. \(A\)는 참이다.
2단계 — \(B\)를 판정한다. 바깥 층이 \(\exists\)이므로 증인 하나와 검증 계산이면 끝난다.
확인 16. \(B\)의 증인을 제시하고 검증까지 적어 보자.
답
증인 \(x = \sqrt2\). 검증: \(\sqrt2 \in \mathbb{R}\)이고 \((\sqrt2)^2 = 2\)이므로 열린
문장 “\(x^2 = 2\)”를 통과한다. \(B\)는 참이다. 무대가 \(\mathbb{Q}\)였다면 이 증인이
무대 밖이라 쓸 수 없고 명제는 거짓이 된다 — §1.3의 무대 표 그대로다.
3단계 — \(C\)를 판정한다. 두 겹이므로 순서부터 읽는다. \(\exists y\)가 \(\forall x\) 안쪽에 있으므로 증인은 맞춤이어도 된다.
확인 17. \(C\)의 증인을 \(x\)의 식으로 제시하고 검증까지 적어 보자.
답
\(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\)가 바깥이므로 만능 증인이 필요하다. 만능 증인을 요구하는 쪽은 훨씬 강한 주장이라 대개 거짓이지만, 이 명제는 예외다.
확인 18. \(D\)의 만능 증인을 제시하고, 그것이 만능임을 검증해 보자.
답
\(y = 0\). 검증: \(0 \in \mathbb{R}\)이고 모든 실수 \(x\)에 대해 \(x \cdot 0 = 0\)이다.
이 증인의 식에 \(x\)가 한 번도 나오지 않으므로 만능 증인이다. \(D\)는 참이다.
\(C\)와 \(D\)가 둘 다 참인 것은 \(D\)의 증인이 우연히 \(x\)에 무관하기 때문이고, 그런
상수 증인을 잡을 수 있을 때만 순서를 바꿔도 진위가 유지된다.
5단계 — 네 부정을 만든다. §1.5의 절차를 바깥 층부터 한 겹씩 적용한다. 무대 \(\mathbb{R}\)은 네 줄 모두에서 그대로 남는다.
확인 19. 네 명제의 부정을 각각 적어 보자. \(C\)와 \(D\)는 두 겹이므로 두 걸음이다.
답
\(\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\)”의 부정을 유도하시오.
이번에는 설계만 함께 하고, 본문은 완성본으로 본다.
확인 20. 번역표를 채워 보자.
출발점: 층이 \(\underline{\quad}\)겹이고, 각 층에 붙은 자격은 \(\underline{\quad}\)과 \(\underline{\quad}\)이다.
도착점: \(\sim\)가 \(\underline{\qquad}\)까지 흡수된 끝 모양.
답
세 겹이고, 자격은 “\(\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\)은 짝수이다”를 정의로 한 번, 이미 증명된 정리로 한 번, 특성화로 한 번 증명하고, 어느 것이 가장 짧은지 보시오.
이번에는 설계부터 스스로 해 보자.
확인 21. 번역표를 채워 보자. 목표 “\(n^2 + n\)이 짝수”를 정의로 번역하면 무엇을 만들어야 하는가. 그리고 정의 대신 쓸 수 있는 재료로 무엇이 손에 있는가.
답
정의로 번역하면 \(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}\) |
확인 22. 빈칸 (1)~(3)을 채워 보자.
답
(1) “\(n^2 + n\)이 짝수”를 정의로 펴서 “\(n^2 + n = 2k\)인 정수 \(k\)가 존재한다”는
존재 명제로 적는다. (2) 바깥 층부터 반전 규칙을 한 겹씩 적용한다. (3) 인용한
정리나 동치가 증명된 것인지, 출처를 댈 수 있는지 확인한다.
확인 23. 세 예제에서 공통으로 반복된 순서를 세 걸음으로 적어 보자. 순서를 바꾸면 무엇이 어긋나는가.
답
① 층을 분해해 양화사\(\cdot\)무대\(\cdot\)열린 문장을 분리한다 \(\to\) ② 바깥 층부터 규칙 하나씩
처리한다 \(\to\) ③ 끝 모양이 제출 조건을 만족하는지 판정한다.
①을 건너뛰면 뒤집거나 갈아 끼울 대상이 문면에 없어 ②가 시작되지 않는다(§1.5의
걸음 ①). ③을 건너뛰면 증인만 적고 검증을 빠뜨리거나(§1.4), \(\sim\)가 남은 중간
상태에서 멈추거나(확인 8), 증명되지 않은 동치를 인용하게 된다(§1.7의 삭제 실험).
방금 확인한 뼈대에 이름을 붙인다.
백지 암기 대상
양화 작업의 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\) 그래도 안 되면 풀이를 읽는다. 이 순서가 답지 암기 습관을 끊는 장치다.
이번 주의 채점 기준
답이 아니라 근거가 점수다. 이번 주의 근거는 세 가지 형태로 제출된다. ① 진위 판정 문제에서는 값이 아니라 검증 계산이 점수다 — “증인은 \(\sqrt2\)”는 절반이고 “\((\sqrt2)^2 = 2\)이므로 통과한다”까지가 만점이다. ② 부정 문제에서는 끝 모양이 점수다 — \(\sim\)가 양화사 밖에 남아 있으면 중간 상태이고, 자격이나 무대가 뒤집혀 있으면 그 순간 다른 명제가 된다. ③ 특성화를 인용하는 문제에서는 출처가 점수다 — “특성화에 의해”만 적으면 어디서 증명됐는지 검사할 수 없다. 힌트 상자는 5분 이상 막힌 뒤에만 연다.
기본 ●○○#
1. [백지] 양화사의 정의, 부정 규칙(양화사 반전과 무대\(\cdot\)자격 보존), 중첩 양화사의 순서 차이, 특성화의 정의(증명된 iff)를 쓰시오.
힌트
네 항목을 한 줄씩 떠올리려 하면 중간에서 끊긴다. 두 묶음으로 나눈다 — 문장을
닫는 층(정의 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\)
힌트
네 문제 모두 층 분해부터 한다. (a)(b)는 한 겹, (c)(d)는 두 겹이다. 두 겹짜리는
안쪽 \(\exists\)가 맞춤인지 만능인지부터 판정하고, 맞춤이면 증인을 바깥 변수의
식으로 써 보고, 만능이면 상수 후보를 하나 잡아 무너지는지 시험한다.
(c)에서 \(x = 0\)을 넣어 보면 무엇이 걸리는가.
3. 문제 2의 각 명제의 부정을 양화사로 쓰시오.
힌트
진위를 몰라도 부정은 쓸 수 있다 — 부정은 규칙의 적용이지 판정이 아니다.
두 겹짜리는 바깥부터 두 걸음이고, 층의 배치는 바뀌지 않는다. 맨 안쪽에서
\(>\)의 부정은 \(\ge\)가 아니라 \(\le\), \(=\)의 부정은 \(\neq\)다.
4. §3의 훈련 1~3을 백지에서 완성하시오.
힌트
훈련 3이 막히면 ①만 먼저 판정한다. 두 방향 중 가정이 \(n\) 자체의 성질인 쪽이
정의로 곧장 풀리고, 가정이 \(n^2\)의 성질인 쪽이 §1.7의 시도처럼 막힌다.
막히는 쪽은 1권 19주차가 쓴 기법으로 돌린다.
5. 예제 2.2(수렴의 부정)를 백지에서 재현하시오 — 세 겹 뒤집기.
힌트
정의를 먼저 정확히 적는 것이 절반이다. 층 세 개와 자격 두 개, 무대 \(\mathbb{N}\)을
종이에 나열한 뒤 걸음 ②를 세 번 돌린다. 옮겨 적을 때 “\(> 0\)”과 “\(> N\)”,
그리고 \(\in \mathbb{N}\)이 그대로 따라오는지 매 줄 확인한다.
6. 특성화의 예 세 개를 드시오 (짝수\(\cdot\)부분집합\(\cdot\)단사 중에서 — 각각 정의와 동치인 조건).
힌트
각 예에서 정의가 무엇인지부터 적고, 그 옆에 동치인 조건을 적는다. 짝수는 §1의
확인 12, 부분집합은 S4주차 문제 13, 단사는 정의의 대우 형태에서 재료를 얻는다.
세 예 모두 “이 동치는 어디서 증명됐는가”를 한 줄로 함께 적어야 완결이다.
표준 ●●○#
7. 명제 “\(\forall x \in \mathbb{R},\ x^2 \ge x\)”의 진위를 판정하고, 거짓이면 반례를, 참이면 증명을 제시하시오. 이어서 그 부정을 쓰고, 부정이 참임을 증인으로 보이시오.
힌트
\(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\)도 짝수이다”를 짧게 증명하시오.
힌트
두 방향의 난이도가 다르다. 한 방향은 정의를 풀어 제곱하면 끝나고, 다른 방향은
§1.7의 시도처럼 막힌다. 막히는 방향은 대우로 돌린다 — 대우의 가정이 \(n\) 자체의
성질이 되어 정의가 즉시 풀린다 (1권 19주차 §1.5의 판정 표).
10. 다음 부정을 진단하시오.
“’\(\forall x > 0,\ x^2 > 0\)’의 부정은 ‘\(\exists x \le 0,\ x^2 \le 0\)’이다.”
힌트
원명제와 그 “부정”의 진위를 각각 판정해 나란히 놓아 본다. 둘이 동시에 참이면
부정의 자격이 무너진 것이고, 무너진 자리는 §1.5의 다섯 걸음 중 하나다.
새 도구 — 양화사 층 안에 조건문이 있을 때
문제 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\)에서 연속이라는 정의)의 부정을 유도하시오.
힌트
네 걸음이다 — 양화사 세 층을 바깥부터 뒤집고, 마지막에 조건문 하나를 처리한다.
자격 “\(\varepsilon > 0\)”과 “\(\delta > 0\)”은 네 걸음 내내 그대로 따라온다.
완성된 문장을 말로 옮겨 “어떤 오차 폭이 있어서 …”로 읽어 보면 검산이 된다.
12. 특성화와 정의: “홀수 = 짝수가 아닌 정수”라고 쓸 때, 이것이 정의가 아니라 증명이 필요한 특성화인 이유를 설명하시오. 그리고 “\(n = 2k+1\) 꼴”과 “짝수가 아님”이 동치임을 보이시오.
힌트
동치를 보이려면 두 방향이다. 한 방향은 “\(2k+1\) 꼴이면 짝수가 아니다”이고 귀류로
처리한다. 다른 방향은 “짝수가 아니면 \(2k+1\) 꼴이다”인데, 여기서 인용하는 사실이
1권 17주차의 그것이다. 두 방향이 각각 어떤 성질(배타성\(\cdot\)전수성)을 쓰는지 이름을
붙여 두면 답이 정리된다.
이 문제가 빌려 쓰는 사실 — 무대와 \(\sqrt2\)
문제 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\)”. 각 동치를 원소 추적 또는 집합 대수로 증명하시오.
힌트
셋을 두 쌍으로 나눠 각각 양방향으로 증명하면 세 개의 동치가 전부 이어진다.
집합의 상등은 두 포함으로 쪼갠다(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)\)”의 진위를 판정하시오. 부정을 유도하고, 그 부정이 왜 거짓인지 확인하시오.
힌트
세 겹이지만 안쪽 두 겹은 \(m\)이 정해진 뒤의 문제다. \(\exists n\)이 \(\forall m\)의
안쪽에 있으므로 \(n\)을 \(m\)의 식으로 둘 수 있다 — 가장 게으른 선택을 시험해 본다.
부정을 유도할 때 마지막 조건문 하나가 남는 것에 주의한다.
이 문제가 빌려 쓰는 사실 — 무한등비급수의 합
문제 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) 이 특성화를 정의로 쓰면 왜 안 되는지 쓰시오.
힌트
(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\)”는 거짓임을 증명하시오. 그리고 한 방향 교환 정리가 이 경우 역으로 가지 않는 이유를 쓰시오.
힌트
거짓 쪽은 만능 증인 \(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\)’.”
힌트
세 오류가 서로 다른 걸음에서 났다. 각각을 §1.5의 다섯 걸음 표에 대 보고,
어느 칸이 비었는지 지목한다. 진단이 끝나면 반드시 올바른 부정까지 적는다 —
오류만 지적하고 수정본을 쓰지 않으면 절반만 제출한 것이다.
19. “정수 \(n\)이 3의 배수 \(\iff\) 각 자리 숫자의 합이 3의 배수”를 두 자리 수 \(n = 10a + b\)에 대해 증명하시오. 그리고 이 특성화가 “3으로 직접 나눠 보기”보다 편한 이유를 쓰시오.
힌트
\(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\)로 바꾸면 다음이 끝 모양이다.
말로 옮기면 “어떤 오차 폭 \(\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\)가 존재한다. 그러면
이고 \(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\)”은 네 걸음 내내 그대로 따라온다.
풀이. 부정할 대상은 다음과 같다.
첫 걸음(\(\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\)):
말로 옮기면 “어떤 오차 폭 \(\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\)이 통과한다. 부정을 유도한다. 바깥부터 세 걸음과 조건문 부정 한 걸음이다.
이 부정이 거짓임을 확인한다. 어떤 \(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\)을 급수로 펼치면 다음과 같다.
첫항 \(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\)로 쪼개면 다음이 성립한다.
\(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장을 통독하고 온다.