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

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

예제 — 부정을 게임으로 바꾸며#

완성된 증명을 먼저 보이지 않는다. 예제 2.1은 설계부터 한 줄씩 함께 만들고, 예제 2.2는 설계만 함께 하고, 예제 2.3은 설계부터 스스로 한 뒤 표 없이 산문으로 적는다. 지지대가 한 예제마다 하나씩 빠진다.

예제 2.1 — 기계 적용: “증가함수가 아니다”의 정체#

명제. \(f(x) = x^2\) (\(f : \mathbb{R} \to \mathbb{R}\))은 증가함수가 아니다.

설계 — 쓰기 전에 정하는 두 가지. 가정이 주는 것(출발점)과 만들어야 할 것(도착점)을 먼저 정한다.

말

전개로 번역

가정 (출발점)

없음 — \(f(x) = x^2\)이라는 대응 규칙뿐

무대: 실수 전체

목표 (도착점)

\(f\)는 증가함수가 아니다

\(\underline{\quad(?)\quad}\)

확인 10. 목표 칸을 채우기 전에 반드시 먼저 해야 하는 일이 하나 있다. 무엇인가.

답

증가함수의 정의를 펴는 것이다(걸음 ①). 목표가 부정문이므로, 부정할 원문이 먼저

정확한 양화사 문장으로 있어야 한다. 부정은 원문의 겉모양에만 작동한다.

정의 — 증가함수 (increasing function)

\(f : \mathbb{R} \to \mathbb{R}\)가 증가함수라는 것은, 모든 실수 \(x_1, x_2\)에 대해

\(x_1 < x_2\)이면 \(f(x_1) < f(x_2)\)라는 뜻이다. 기호로 적으면

\(\forall x_1 \forall x_2\,[\,x_1 < x_2 \Rightarrow f(x_1) < f(x_2)\,]\)이다.

이 진술은 1권 41주차 문제 13과 1권 42주차 문제 12 앞 상자에서 쓴 것과 같다. 1권에 번호가 붙은 정의 상자로는 나오지 않았으므로, 이번 주는 그 두 자리의 진술을 그대로 받아 쓴다.

걸음 ① — 정의 노출.

확인 11. 명제를 \(\neg\)가 앞에 붙은 한 줄로 적어 보자.

답

\(\neg\big[\,\forall x_1 \forall x_2\,(x_1 < x_2 \Rightarrow f(x_1) < f(x_2))\,\big]\).

이 줄을 적는 순간 뒤집을 대상이 문면에 드러난다. 여기서부터 기계가 돈다.

걸음 ② — 겹 벗기기.

확인 12. 가장 바깥 겹은 무엇이고 어느 규칙을 쓰는가. 한 번 적용한 결과를 적고, 이어서 한 번 더 적용해 보자.

답

가장 바깥은 \(\forall x_1\)이므로 N5:

\(\exists x_1\ \neg\big[\forall x_2\,(x_1 < x_2 \Rightarrow f(x_1) < f(x_2))\big]\).

남은 바깥은 \(\forall x_2\)이므로 다시 N5:

\(\exists x_1 \exists x_2\ \neg\big(x_1 < x_2 \Rightarrow f(x_1) < f(x_2)\big)\).

두 번 다 한 겹씩만 벗겼다. 두 겹을 한꺼번에 뒤집으면 §1.3의 삭제 실험 1이 된다.

확인 13. 남은 \(\neg\)는 조건문 앞에 있다. 어느 규칙이고, 적용 후 걸음 ③까지 마치면 최종 전개문은 무엇인가.

답

N4: \(\exists x_1 \exists x_2\ \big(x_1 < x_2\ \wedge\ \neg(f(x_1) < f(x_2))\big)\).

걸음 ③ 본체 도달 — \(\neg(<)\)는 \(\ge\)이므로, 최종 전개문은

\(\exists x_1 \exists x_2\ \big(x_1 < x_2\ \wedge\ f(x_1) \ge f(x_2)\big)\)이다.

여기에 \(\ge\)가 나오는 것이 중요하다. \(>\)로 좁히면 §1.3의 삭제 실험 2가 된다.

전개가 끝났다. 최종 전개문을 자기 줄에 다시 적어 둔다.

\[ \exists x_1 \exists x_2\ \big(x_1 < x_2\ \wedge\ f(x_1) \ge f(x_2)\big) \]

걸음 ④ — 게임 판독.

확인 14. 이 전개문의 겉모양은 네 칸 표의 어느 칸인가. 답안이 제시해야 하는 것은 무엇이고, 검증할 조각은 몇 개인가.

답

가장 바깥이 \(\exists x_1\)이고 이것은 **결론의 \(\exists\)**이므로 구성법(S5주차)이다. 안쪽

\(\exists x_2\)도 같다. 제시할 것은 실수의 쌍 하나다.

검증은 세 조각이다 — 자격(두 수가 실수인가), 사건 1(\(x_1 < x_2\)), 사건 2

(\(f(x_1) \ge f(x_2)\)). 본체가 \(\wedge\)이므로 사건은 둘 다 확인해야 한다. 하나라도

빠지면 증인이 성립하지 않는다.

확인 15. 증인 후보를 어떻게 찾는가. 후보를 하나 제시하고, 그것이 유일한 후보인지 판단해 보자.

답

본체를 만족하는 쌍을 역산해 찾는다. \(f(x) = x^2\)은 음수 쪽에서 값이 줄어들므로,

음수 하나와 그보다 큰 수 하나를 잡으면 된다. \(x_1 = -1\), \(x_2 = 0\)이면

\(-1 < 0\)이고 \(f(-1) = 1 \ge 0 = f(0)\)이다.

유일하지 않다. \(x_1 = -1\), \(x_2 = 1\)도 증인이다 — \(-1 < 1\)이고

\(f(-1) = 1 \ge 1 = f(1)\)로 등호로 성립한다. 걸음 ③에서 \(\ge\)를 지켰기 때문에

이 쌍이 살아 있다. 증인은 하나만 제시하면 되므로 어느 쪽이든 답안이 된다.

완성본. 방금 만든 문장을 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 “왜?”에 스스로 답해 본다.

증명의 한 줄

왜 이 줄을 쓰는가?

증가함수의 정의에 의해, 보일 것은 \(\exists x_1 \exists x_2\,(x_1 < x_2 \wedge f(x_1) \ge f(x_2))\)이다 [N5, N5, N4].

걸음 ①~③의 결과를 한 줄로 선언한다. 이 줄이 없으면 아래의 검증들이 무엇을 향한 것인지 확정되지 않는다. 규칙 번호가 이 줄의 근거다.

\(x_1 = -1\), \(x_2 = 0\)으로 두자 [구성].

걸음 ④의 지시 — 전개문의 바깥이 결론의 \(\exists\)이므로 구성법(S5주차)이고, 증인은 쌍 하나다.

자격: \(-1\)과 \(0\)은 실수이다.

증인이 무대의 대상인지 밝힌다. 이 줄이 빠지면 증인이 어디서 온 것인지 확정되지 않는다.

사건 1: \(-1 < 0\)이다.

본체의 왼쪽 조각 \(x_1 < x_2\)의 검증.

사건 2: \(f(-1) = (-1)^2 = 1\)이고 \(f(0) = 0\)이므로 \(f(-1) \ge f(0)\)이다.

본체의 오른쪽 조각 검증. 본체가 \(\wedge\)이므로 두 조각을 모두 확인해야 한다.

따라서 전개문이 성립하고, 그 전개문은 “\(f\)는 증가함수가 아니다”와 같은 말이므로 \(f\)는 증가함수가 아니다. \(\blacksquare\)

전개문과 원명제를 다시 잇는 마무리. 부정을 전개해 증명한 답안은 이 줄로 닫는다.

관찰. 처음에 손잡이가 없던 결론이 세 걸음 뒤에 “쌍 하나 내놓기”가 되었다. 바뀐 것은 명제가 아니라 NOT의 위치뿐이다. 부정형 결론의 어려움은 대개 전개 이전의 자리에 있고, 전개 이후의 수학은 S5주차의 구성법 그대로다.

예제 2.2 — 처방 ①의 다른 갈래: 특성화로 갈아타기#

명제. 모든 정수 \(n\)에 대해, \(n^2 + n + 1\)은 짝수가 아니다.

이번에는 설계까지만 함께 하고 본문은 완성본으로 본다.

확인 16. 번역표를 채워 보자. 목표 칸은 걸음 ①~③까지 밀어 본 결과를 적는다.

답

가정 (출발점): \(n\)은 정수 — 무대는 정수 전체이고, 풀 정의는 없다.

목표 (도착점): 짝수의 정의는 \(\exists k \in \mathbb{Z}:\ n^2 + n + 1 = 2k\)이므로,

부정은 N6로 \(\forall k \in \mathbb{Z}:\ \neg(n^2+n+1 = 2k)\), 곧

\(\forall k \in \mathbb{Z}:\ n^2 + n + 1 \neq 2k\)이다.

확인 17. 그 전개문을 그대로 증명하려면 무엇을 해야 하는가. 더 짧은 길은 없는가.

답

전개문의 바깥은 결론의 \(\forall\)이므로 선택법이다 — 정수 \(k\)를 임의로 잡고

\(n^2 + n + 1 \neq 2k\)를 보여야 하는데, 이 결론 \(\neq\)가 또 부정형이라 겹이 하나 더

남는다. 밀어 넣기만으로는 짧아지지 않는 경우다.

더 짧은 길은 처방 ①의 다른 갈래인 특성화 갈아타기다. “짝수가 아니다”를

“홀수이다”로 바꿔도 되는 자격은 두 사실이 준다 — 전수성(모든 정수는 짝수이거나

홀수이다, 1권 33주차 예제 2.2의 따름정리)과 배타성(어떤 정수도 짝수이면서 동시에

홀수일 수 없다, 1권 22주차 문제 5). 갈아타면 결론이 긍정형이 되고, 1권 15주차

문제 12에서 이미 한 계산이 그대로 재사용된다.

갈아타기는 공짜가 아니다. 증명된 배타성과 전수성의 인용이고, 답안에 그 인용

줄이 실제로 있어야 한다.

증명의 한 줄

왜 이 줄을 쓰는가?

정수 \(n\)을 임의로 잡자 [선택].

결론이 “모든 정수 \(n\)에 대해”이므로 결론의 \(\forall\) — 선택법(S6주차).

\(n^2 + n = n(n+1)\)은 연속한 두 정수의 곱이므로 짝수이다 [1권 1주차 문제 16].

인용으로 한 줄에 끝낸다 — 근거 ④. 인용한 명제의 가정(“연속한 두 정수”)이 충족됨을 같은 줄에서 밝힌다.

짝수의 정의에 의해 \(n^2 + n = 2m\)인 정수 \(m\)이 존재한다. 그런 \(m\)을 잡자 [수령].

인용해 얻은 사실이 존재 진술이므로 이름을 붙여 받는다(S8주차 §1.7). 여기서 등식이 손에 들어온다.

그러면 \(n^2 + n + 1 = 2m + 1\)이고, \(m\)은 정수이므로 \(n^2 + n + 1\)은 홀수이다.

홀수의 정의 꼴 \(2 \times (\text{정수}) + 1\)을 만들어 제시한다 — 근거 ①. 여기까지가 갈아탄 긍정형 명제의 증명이다.

홀짝의 배타성에 의해 [1권 22주차 문제 5] \(n^2 + n + 1\)은 짝수가 아니다.

갈아탄 결론에서 원래 결론으로 돌아오는 다리. 이 줄이 빠지면 증명한 것(“홀수이다”)과 요구된 것(“짝수가 아니다”)이 서로 다른 명제로 남는다.

\(n\)이 임의였으므로 모든 정수 \(n\)에 대해 성립한다. \(\blacksquare\)

선택법의 마무리 선언(S6주차).

관찰. 이 답안에서 부정을 실제로 처리한 줄은 마지막에서 두 번째 줄 하나다. 나머지는 전부 긍정형 명제의 증명이다. 갈아타기의 값은 여기 있다 — 부정을 한 줄로 몰아넣고 나머지를 아는 게임으로 만든다. 다만 그 한 줄이 인용 없이 비면 증명이 닫히지 않는다.

예제 2.3 — 전개 사고 진단 3건#

세 개의 전개가 있다. 각각이 왜 부정이 아닌지 판정한다. 이번에는 설계부터 스스로 한 뒤 표 없이 산문으로 읽는다.

확인 18. 전개가 틀렸다고 판정하려면 무엇을 보여야 하는가. 진단의 서식을 세 조각으로 적어 보자.

답

① 어긴 규칙의 지목(N1~N6 중 어느 것인지), ② 올바른 전개, ③ 목격자 — 원문과

사고 전개의 진리값이 반대가 아님을 보이는 구체적 사례 하나.

판정을 내리는 조각은 ③이다. ①②만 적으면 “다르다”까지고, 왜 부정이 아닌지는

③이 말한다. 판정 기준은 1권 11주차 §1.3의 부정의 자격 — 원문과 부정은 어떤

상황에서도 진리값이 정확히 반대다.

사고 1. “\(\neg(P \wedge Q)\)는 \(\neg P \wedge \neg Q\)이다.”

N2 위반이다. “둘 다”의 실패는 “둘 다 실패”가 아니라 “한쪽이라도 실패”이므로 결과는 \(\vee\)여야 한다. 목격자는 \(P\)가 참이고 \(Q\)가 거짓인 경우다. 이때 \(P \wedge Q\)는 거짓이므로 \(\neg(P \wedge Q)\)는 참인데, \(\neg P\)는 거짓이므로 \(\neg P \wedge \neg Q\)는 거짓이다. 두 문장의 진리값이 같지 않으므로 사고 전개는 부정이 아니다. 1권 9주차의 진리표로 네 행을 채우면 즉시 확인된다.

사고 2. “\(\neg(P \Rightarrow Q)\)는 \(\neg P \Rightarrow \neg Q\)이다.”

N4 위반이다. 오른쪽 문장은 1권 9주차의 용어로 이(inverse)이고, 이는 원명제와 동치가 아니다(1권 9주차 문제 13에서 증명했다). 조건문의 부정은 조건문이 아니라 \(\wedge\)이다 — “\(P\)인데 \(Q\)가 아니다”. 목격자는 \(P\)도 거짓이고 \(Q\)도 거짓인 경우다. 이때 \(P \Rightarrow Q\)는 참(전건이 거짓이므로)이라 \(\neg(P \Rightarrow Q)\)는 거짓인데, \(\neg P \Rightarrow \neg Q\)는 참인 전건에 참인 후건이라 참이다. 이 사고가 특히 위험한 것은 S11주차의 귀류에서 \(\neg B\)를 만들 때 \(B\)가 조건문이면 이 규칙이 곧바로 쓰이기 때문이다 — 여기서 틀리면 가정 자리에 들어가는 문장 자체가 잘못된 것이 된다.

사고 3. “\(\neg\)(모든 양수 \(x\)에 대해 \(x + \frac1x \ge 2\))는 ‘어떤 \(x\)는 양수가 아니거나 \(x + \frac1x < 2\)이다’이다.”

자격 부정 사고다(§1.4). 올바른 전개는 “어떤 양수 \(x\)에 대해 \(x + \frac1x < 2\)이다”이고, 자격 “양수”는 그대로 남는다. 목격자는 \(x = -1\)이다. 원명제는 참인데(\(x > 0\)일 때 \(x + \frac1x - 2 = \frac{(x-1)^2}{x} \ge 0\)), 사고 전개도 \(x = -1\)이 “양수가 아니다”를 만족시켜 참이 된다. 둘 다 참이므로 진리값이 반대가 아니다. 자격을 부정하면 원명제의 무대에 애초에 들어오지 않는 대상이 증인 자리에 앉는다. \(\blacksquare\)

관찰 — 같은 뼈대#

예제 2.1, 예제 2.2, 그리고 §3의 훈련 1은 소재가 다르지만 걸음의 배치가 같다. 대응표의 빈칸을 채워 보자(훈련 1의 명제는 “\(f(x) = x^2\)은 단사가 아니다”이다).

걸음

예제 2.1

예제 2.2

훈련 1

표면 NOT의 낱말

증가함수가 아니다

짝수가 아니다

\(\underline{\quad(1)\quad}\)

걸음 ① 정의 노출의 결과

\(\forall x_1 \forall x_2[\,x_1 < x_2 \Rightarrow f(x_1) < f(x_2)\,]\)

\(\exists k \in \mathbb{Z}:\ n^2+n+1 = 2k\)

\(\underline{\quad(2)\quad}\)

걸음 ②③에서 쓴 규칙의 순서

N5, N5, N4

N6

\(\underline{\quad(3)\quad}\)

걸음 ④ 판독이 지정한 기법

구성법

갈아타기로 우회

\(\underline{\quad(4)\quad}\)

답안이 제시하는 것

쌍 \((-1, 0)\)

홀수 표현 \(2m+1\)

\(\underline{\quad(5)\quad}\)

확인 19. 빈칸 (1)~(5)를 채우고, 세 경우에서 공통으로 반복된 순서를 네 걸음으로 적어 보자.

답

(1) 단사가 아니다 (2) \(\forall x_1 \forall x_2[\,f(x_1) = f(x_2) \Rightarrow x_1 = x_2\,]\)

(3) N5, N5, N4 (4) 구성법 (5) 쌍 \((-1, 1)\) (또는 \(f\)의 값이 같은 서로 다른 두 수의 쌍)

공통 순서: ① 낱말을 정의로 펴서 뒤집을 대상을 드러낸다 \(\to\) ② 바깥부터 한 겹씩 규칙을

적용한다 \(\to\) ③ 본체까지 밀어 부등호\(\cdot\)등호\(\cdot\)소속을 뒤집는다 \(\to\) ④ 전개문의 겉모양을

네 칸 표에 넣어 기법을 정하고 답안을 쓴다.

예제 2.2가 ④에서 우회한 것도 같은 절차의 결과다 — 판독해 보니 전개문이 여전히

부정을 품고 있어서, 그 판독을 근거로 갈아타기를 골랐다.

방금 확인한 뼈대에 이름을 붙인다.

백지 암기 대상

부정 증명 4단 서식

① 전개 — 낱말을 정의로 펴고(걸음 ①), NOT을 바깥부터 한 겹씩 밀어(걸음 ②) 본체까지 보낸다(걸음 ③). 줄마다 규칙 번호를 단다.

② 판독 — 전개문의 가장 바깥 겹을 네 칸 표에 넣어 기법을 정한다. 전개문이 여전히 부정형이면 §1.5의 처방 ②③으로 갈아탈지 여기서 판단한다.

③ 설계 — 정해진 기법의 첫 문장을 적는다. 증인이 필요하면 본체에서 역산해 후보를 찾는다.

④ 답안 — 증인 제시와 검증을 전수로 적고, 전개문이 원명제의 부정이라는 것을 선언하며 닫는다.

빈칸 사다리 — 지지대를 하나씩 빼며#

필사에서 자립으로 넘어가는 다리다. 베끼지 말고 빈칸만 스스로 채운다. 답은 §6에 있다. 훈련이 진행될수록 빈칸이 커진다.

훈련 1 ●○○ — 수식과 절차의 빈칸#

명제. \(f(x) = x^2\) (\(f : \mathbb{R} \to \mathbb{R}\))은 단사가 아니다. (단사의 정의 — 1권 정의 41.1: \(\forall x_1 \forall x_2\,[\,f(x_1) = f(x_2) \Rightarrow x_1 = x_2\,]\))

전개. 정의를 편 뒤 N5를 두 번 적용하고, 이어 \(\underline{\quad(1)\quad}\)을 적용하면

\[ \exists x_1 \exists x_2\ \big(f(x_1) = f(x_2)\ \underline{\quad(2)\quad}\ x_1 \neq x_2\big) \]

이다.

판독. 가장 바깥이 결론의 \(\exists\)이므로 \(\underline{\quad(3)\quad}\)법이다 — 증인 쌍을 제시한다.

답안. \(x_1 = \underline{\quad(4)\quad}\), \(x_2 = \underline{\quad(5)\quad}\)으로 두자. 자격: 둘 다 실수 ✓. 사건 1: \(f(x_1) = f(x_2) = \underline{\quad(6)\quad}\) ✓. 사건 2: \(x_1 \neq x_2\) ✓. 따라서 \(f\)는 단사가 아니다. \(\blacksquare\)

연결. 이 결과는 1권 41주차 문제 4의 판정과 같은 내용이다. 그때 쓴 “서로 다른 두 입력이 같은 출력을 갖는다” 서식의 논리적 정체는 \(\underline{\quad(7)\quad}\) 전개와 구성법이었다.

훈련 2 ●●○ — 수식과 근거를 함께#

이번에는 근거 문장도 빈칸이다.

명제. \(m\)과 \(n\)이 모두 홀수이면 \(mn\)은 짝수가 아니다.

판단. 결론 “짝수가 아니다”를 기계로 밀면 \(\underline{\quad(1)\quad}\)이 되어 결론의 \(\forall\)가 하나 더 생긴다. 대신 처방 ①의 갈아타기를 쓴다 — “짝수가 아니다”를 “\(\underline{\quad(2)\quad}\)”로 교체할 자격은 \(\underline{\quad(3)\quad}\)이 준다.

답안. \(m\)과 \(n\)을 홀수라 하자. 정의에 의해 \(m = \underline{\quad(4)\quad}\), \(n = 2b + 1\)인 정수 \(a, b\)가 존재한다. 그러면

\[ mn = (2a+1)(2b+1) = 4ab + 2a + 2b + 1 = 2\big(\underline{\quad(5)\quad}\big) + 1 \]

이고, \(\underline{\quad(6)\quad}\)이므로 괄호 안은 정수이다. 따라서 \(mn\)은 홀수이고, \(\underline{\quad(7)\quad}\)에 의해 \(mn\)은 짝수가 아니다. \(\blacksquare\)

훈련 3 ●●● — 뼈대만 남기고#

이번에는 전개부터 스스로 한다.

명제. \(A = \{n \in \mathbb{Z} : 3 \mid n\}\)과 \(B = \{n \in \mathbb{Z} : 6 \mid n\}\)에 대해 \(A \neq B\)이다.

증명의 뼈대. 4단 서식의 각 칸을 문장으로 통째로 채운다.

  • ① 전개 — 상등의 판정 기준(1권 정의 27.1)을 펴고 부정을 밀어 넣는다: \(\underline{\quad(1)\quad}\)

  • ② 판독 — 전개문의 겉모양과 지정된 기법: \(\underline{\quad(2)\quad}\)

  • ③ 설계 — 증인 후보와 그것을 찾는 방법: \(\underline{\quad(3)\quad}\)

  • ④ 답안 — 자격과 검증 두 조각을 전수로: \(\underline{\quad(4)\quad}\)

(이 훈련이 문제 10의 예행연습이다.)

연습문제 (20문항)#

해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 접근까지만 읽고 다시 시도한다.

이번 주의 채점 기준

답이 아니라 근거가 점수다. 이번 주의 제출 규격은 네 가지다: ① 전개의 각 걸음에 붙은 규칙 번호(N1~N6) ② 전개가 본체까지 닿았다는 표시 — 등호\(\cdot\)부등호\(\cdot\)소속이 뒤집힌 줄 ③ 전개문의 겉모양이 지정한 기법의 이름 ④ 증인을 제시했다면 자격과 사건의 전수 검증. 결론이 맞아도 ①이 없으면 그 문장이 어느 규칙으로 나왔는지 확정되지 않으므로 전개로 읽히지 않는다. 힌트 상자는 5분 이상 막힌 뒤에만 연다.

전개 문제는 한 겹씩 줄을 나누어 쓰고 각 걸음에 규칙 번호를 단다. 증명 문제는 전개 \(\to\) 판독 \(\to\) 설계 \(\to\) 답안의 순서로 쓴다.

기본 ●○○#

1. [백지] 기계 6칙 + 적용 규칙 + 자격 보존 함정 + 부정형 결론의 3처방을 쓰시오.

힌트

§1.3의 표와 적용 규칙 상자, §1.4의 두 줄, §1.5의 상자다. 6칙은 “이중부정 하나,

드모르간 둘, 조건문 하나, 양화사 둘”로 세어 두면 빠뜨리지 않는다.

2. 다음을 본체까지 전개하시오 (규칙 번호 표기). (a) \(\neg\)(모든 짝수 \(n\)에 대해 \(n^2\)은 4의 배수이다) (b) \(\neg\)(\(x > 0\)이고 \(y > 0\)) (c) \(\neg\)(어떤 실수 \(x\)에 대해 \(x^2 = -1\)) (d) \(\neg\)(\(a \mid b\) 또는 \(a \mid c\))

힌트

네 문항 모두 한 걸음이면 규칙이 끝나고, 그다음 본체를 뒤집는 걸음이 남는다.

(a)에서 자격 “짝수”를 건드리지 않았는지 마지막에 확인한다.

3. 다음 숨은 NOT을 노출하고 전개하시오. (a) “\((a_n)\)은 위로 유계가 아니다” (유계의 정의: \(\exists M\ \forall n:\ a_n \le M\)) (b) “\(m\)과 \(n\)은 같은 홀짝이 아니다” (c) “\(f\)는 상수함수가 아니다” (상수함수의 정의: \(\exists c\ \forall x:\ f(x) = c\))

힌트

세 문항 모두 걸음 ①이 절반이다. (b)는 “같은 홀짝”을 먼저

“(둘 다 짝수) 또는 (둘 다 홀수)”로 편 뒤 시작한다.

4. §3의 빈칸 사다리 훈련 1~3을 백지에서 완성하시오.

힌트

훈련 셋은 지지대만 다르고 서식은 하나다. 백지에서 가장 자주 빠지는 줄은 훈련 2의

마지막 인용(배타성)과 훈련 3의 검증 2다.

5. 예제 2.1을 백지 재현하시오 — 전개 3걸음의 규칙 번호 포함.

힌트

규칙 번호는 세 개이고 순서가 있다. 정의를 편 직후의 가장 바깥이 무엇인지부터

확인하면 순서가 저절로 정해진다.

6. 예제 2.3의 세 사고를 재현하고, 각각의 “목격자”(사고 전개와 올바른 전개가 갈라지는 사례)를 하나씩 드시오.

힌트

목격자는 두 문장의 진리값이 갈라지는 구체적 인스턴스다. 사고 1과 2는 \(P\), \(Q\)에

참\(\cdot\)거짓을 배정하는 네 경우를 훑으면 나오고, 사고 3은 자격을 위반하는 수 하나면 된다.

표준 ●●○#

7. 명제 “모든 실수 \(x\)에 대해 \(x^2 + 1 \neq 0\)”을 증명하시오.

힌트

\(\neq\)를 직접 다루려 하면 \(\forall\) 하나가 더 생긴다. 대신 순서로 강화한다 —

\(x^2 + 1\)이 0보다 크다는 것을 보이면 0이 아니라는 것은 따라온다.

\(x^2 \ge 0\)의 근거는 1권 16주차의 (W1)이다.

8. 명제 “\(f(x) = 3x + 1\)은 상수함수가 아니다”를 증명하시오.

힌트

문제 3(c)의 전개를 그대로 쓴다 — \(\forall c\ \exists x:\ f(x) \neq c\). 바깥이 결론의 \(\forall\)이므로

후보 \(c\)를 임의로 잡는 것이 첫 문장이고, 그 \(c\)를 배반하는 \(x\)를 만드는 것이 둘째

문장이다. 두 가지 길이 있다: \(f\)의 서로 다른 두 값을 먼저 확보해 두는 지름길과,

\(c\)의 식으로 증인을 직접 만드는 길이다.

이 문제들이 다시 쓰는 부품 — 천장 함수

문제 9와 문제 15는 임의로 받은 실수 \(M\)보다 큰 대상을 만들어야 한다. 부품은 S5주차

문제 14에서 채택한 천장의 성질이다: 실수 \(t\)에 대해 \(\lceil t \rceil\)은 정수이고

\(\lceil t \rceil \ge t\)이다. 그리고 1권 17주차 문제 5의 \(t \le \lvert t \rvert\)를 함께 쓰면

\(M\)의 부호를 나누지 않고 한 번에 처리할 수 있다.

9. 명제 “자연수 집합 \(\mathbb{N}\)은 위로 유계가 아니다”를 증명하시오.

힌트

문제 3(a)의 전개가 그대로 쓰인다 — \(\forall M\ \exists n \in \mathbb{N}:\ n > M\).

증인은 \(M\)의 식이어도 된다(S8주차의 의존성의 문법). \(M\)이 음수일 수도 있으므로

절댓값을 한 번 거치면 자격 검증이 한 줄로 끝난다.

10. 집합 상등의 부정: \(A = \{n \in \mathbb{Z} : 2 \mid n\}\), \(B = \{n \in \mathbb{Z} : 4 \mid n\}\)에 대해 \(A \neq B\)임을 증명하시오.

힌트

상등을 1권 정의 27.1(양방향 포함)로 펴는 것이 걸음 ①이다. 전개하면 “한쪽에만

속하는 원소가 존재한다”가 되고, 갈래 하나를 지목해 증인 하나를 제시하면 된다. 검증 2(”\(B\)에 속하지 않는다”)는 그 자체가 작은

부정 증명이므로 같은 기계를 한 번 더 돌린다.

11. 명제 “\(\forall n \in \mathbb{N}: 2^n \ge n^2\)”은 거짓이다 — 반례의 문법(N5와 N4)으로 부정을 전개하고 증명하시오. 이어서 참이 되도록 자격을 수리한 명제(\(n = 1\) 또는 \(n \ge 4\))를 진술만 하시오.

힌트

전개하면 \(\exists n \in \mathbb{N}:\ 2^n < n^2\)이다. 증인 정찰은 작은 수부터

\(n = 1, 2, 3, 4\)를 표로 계산하면 끝난다. 위반이 일어나는 구간이 좁다는 것도 함께 본다.

12. 다음 전개를 진단하시오 (사고 유형 지목 + 올바른 전개). (a) “\(\neg(\forall \varepsilon > 0\ \exists N\ \forall n > N:\ \lvert a_n \rvert < \varepsilon)\)은 \(\exists \varepsilon \le 0\ \forall N\ \exists n > N:\ \lvert a_n \rvert \ge \varepsilon\)이다” (b) “’\(f\)가 단사가 아니다’는 ‘모든 \(x_1 \neq x_2\)에 대해 \(f(x_1) = f(x_2)\)’이다” (c) “\(\neg\)(\(p\)는 소수이고 \(p > 2\))는 ‘\(p\)는 소수가 아니고 \(p \le 2\)’이다”

힌트

세 문항의 사고 유형이 서로 다르다 — 하나는 §1.4, 하나는 걸음 ②의 규칙 누락,

하나는 N2의 방향이다. 각각에 목격자를 붙이면 진단이 판정이 된다.

13. “\(x \notin A \cup B\)”를 전개해 “\(x \notin A\) 그리고 \(x \notin B\)”를 얻는 과정(\(\cup\)의 정의 노출 후 N3)을 쓰고, 이것이 S6주차 문제 15에서 실제로 쓰였던 지점을 지목하시오. 이어서 “\(x \notin A \cap B\)”의 전개도 쓰시오 — 결과가 \(\vee\)라서 케이스 신호임을 명시하시오.

힌트

두 전개의 차이는 정의가 \(\vee\)인가 \(\wedge\)인가 하나뿐이고, 그 하나가 결과를

\(\wedge\)와 \(\vee\)로 갈라 놓는다. S6주차 문제 15는 \(A - (B \cup C) = (A-B) \cap (A-C)\)였다.

14. 명제 “\((a_n) = ((-1)^n)\)은 위로 유계이다 — 그러나 수렴하지는 않는다”에서 뒤 절반의 완전한 전개(\(\neg \exists L:\ a_n \to L\))를 쓰고, S8주차 문제 15가 증명한 것(“0으로 수렴하지 않는다”)과 이번 전개(“어떤 \(L\)로도 수렴하지 않는다”)의 차이를 한 문장으로 밝히시오. (증명은 S8주차 문제 15 해설 끝의 스케치 인용으로 갈음한다.)

힌트

정의 45.1이 세 겹이고 그 바깥에 \(\exists L\)이 하나 더 붙으므로 전부 네 겹이다.

규칙을 네 번 적용하는 동안 겹이 하나씩 뒤집히는 것을 줄을 나누어 적는다.

도전 ●●●#

15. 명제 “\(f(x) = x^3 + x\)는 위로 유계가 아니다”를 증명하시오.

힌트

전개는 \(\forall M\ \exists x:\ f(x) > M\)이다. 증인을 \(\lvert M \rvert + 1\)로 두면

\(x \ge 1\)이 확보되고, 그 조건에서 \(x^3\)의 부호가 정해진다. 근거는 1권 16주차의 (W4)다.

이 문제가 쓰는 새 낱말 — 정수의 서로소

1권 5주차의 “서로소”는 두 집합의 교집합이 공집합이라는 뜻이었다. 문제 16의 “서로소”는

같은 낱말을 쓰는 다른 개념이다 — 두 정수가 1보다 큰 공약수를 갖지 않는다는 뜻이고,

문제 안에 정의가 함께 주어져 있다. 이 개념의 본격적인 전개(최대공약수, 유클리드

호제법)는 C15주차에서 다룬다. 지금 다루는 것은 이 정의가 부정형이라는 사실 하나다.

16. “서로소”의 부정: 정수 \(a, b\)가 서로소라 함은 \(\gcd(a,b) = 1\), 곧 “1보다 큰 공약수가 없다”(\(\neg\exists d > 1:\ d \mid a \wedge d \mid b\))이다. (a) “서로소가 아니다”를 전개하시오. (b) 91과 65가 서로소가 아님을 구성법으로 증명하시오. (c) “서로소”라는 긍정형 낱말이 사실 부정형 정의임을 지적하고, 서로소라는 사실이 가정 쪽에 주어졌을 때 그것이 왜 다루기 어려운지를 두 문장으로 쓰시오.

힌트

(a)는 원정의가 이미 \(\neg \exists\) 꼴이라는 데서 시작한다 — 그 앞에 \(\neg\)를 하나 더

붙이면 N1이 작동한다. (c)는 (a)와 반대 방향으로 한 번 더 전개해 보면 답이 나온다.

17. 삼중 전개 종합: “\(f\)가 \(x = a\)에서 연속이 아니다”를 전개하시오 (연속의 정의 — 1권 정의 47.2: \(\forall \varepsilon > 0\ \exists \delta > 0\ \forall x\,[\,\lvert x - a \rvert < \delta \Rightarrow \lvert f(x) - f(a) \rvert < \varepsilon\,]\)). 그리고 계단함수 \(g(x) = 0\) (\(x < 0\)), \(g(x) = 1\) (\(x \ge 0\))이 \(x = 0\)에서 연속이 아님을 전개식대로 증명하시오.

힌트

규칙을 네 번 적용한다 — 양화사 셋과 조건문 하나다. 전개가 끝나면 \(\varepsilon\)과 \(x\)는

이쪽이 고르고 \(\delta\)는 저쪽이 주는 배치가 된다(S8주차 예제 2.2와 정확히 뒤집힌 모양).

\(\varepsilon\)은 \(g\)의 두 값의 차이보다 작게 잡고, \(x\)는 \(\delta\)의 식으로 만든다.

이 문제들이 미리 쓰는 도구 — 귀류와 대우

문제 18과 19는 처방 ③(귀류)과 처방 ②(대우)를 실제로 사용한다. 두 기법 자체는

1권 19\(\cdot\)21주차에서 이미 익힌 것이므로 지금 인정하고 쓴다. 다만 “무엇을 얻고 무엇을

잃는 거래인가”라는 Solow의 관점에서의 재정의는 S11주차와 S12주차에서 정면으로 다룬다.

이번 주에 확인할 것은 하나다 — 두 기법 모두 \(\neg B\)를 정확히 만드는 데서 시작하므로,

이번 주의 기계가 그 둘의 부품이라는 것이다.

18. (진단 종합) 다음 답안의 결함을 모두 찾으시오. 그리고 올바른 증명을 완성하시오.

“명제: \(\sqrt2 + \frac12\)은 무리수이다. 증명: \(\sqrt2\)는 무리수이다(1권 21주차). 무리수에 유리수를 더한 것은 무리수처럼 보이므로 \(\sqrt2 + \frac12\)도 무리수이다.”

힌트

결함은 근거의 문제만이 아니다. 결론이 부정 신호(“무리수”)인데 이 답안에는 전개도

처방 선택도 한 줄이 없다는 것부터 짚는다. 올바른 증명은 처방 ③이고, 인용할 닫힘은

1권 15주차 문제 9다.

19. (전개 \(\to\) 판독 \(\to\) 증명 풀코스) 명제 “임의의 실수 \(x\)에 대해, \(x\)가 무리수이면 \(-x\)도 무리수이다”를 증명하시오. 대우 공략과 귀류 공략을 모두 쓰고, 어느 쪽이 짧은지 평가하시오.

힌트

가정과 결론이 둘 다 부정 신호다. 대우를 잡으면 두 NOT이 동시에 벗겨져 양쪽이 다

긍정형이 된다. 귀류 쪽은 조건문의 부정이므로 N4가 먼저 작동한다 — 무엇과 무엇이

\(\wedge\)로 손에 들어오는지 먼저 적는다.

20. (서술) (a) “부정은 위치의 문제다”라는 이번 주의 핵심 문장을 예제 2.1의 3단(표면 NOT \(\to\) 본체 \(\ge\))으로 세 문장 이내로 해설하시오. (b) 반례 제작(1권 29주차), 만능 증인 격파(S8주차 예제 2.1(b)), “단사가 아님” 증명(훈련 1) — 셋이 모두 같은 골격(부정 전개 + 구성법)임을 두 문장으로 통합하시오.

힌트

(a)는 “같은 정보인데 NOT의 위치가 다르다”는 대비로 쓴다. (b)는 셋의 원명제 겉모양을

먼저 나란히 적어 본다 — 둘은 \(\neg\forall\)이고 하나는 \(\neg\exists\forall\)이라 겹 수가

다르다. 그래도 전개가 끝난 자리에서 겹치는 것이 하나 있다. §2의 관찰 표가 준비다.

백지 재현 — 복습 프로토콜#

이번 주의 5일 루틴. 원서와 교안을 번갈아 쓰는 순서다.

요일

할 일

1일차

원서 Solow 8장 통독 (모르는 문장은 표시만 하고 통과)

2일차

교안 §0~§2 — 개념과 예제. 확인 상자는 연필로 먼저 답한다

3일차

원서 재독 — 1일차에 표시한 문장을 해결하고, 원서 8장의 연습문제 몇 개를 직접 시도

4일차

교안 §3 빈칸 사다리 + §4 연습문제 20문항

5일차

백지 재현 1차(틀 카드)\(\cdot\)2차(완전 백지) + 체크리스트

3일차의 재독에서 볼 것이 정해져 있다. 원서 8장은 부정 규칙을 표로 제시한 뒤 곧바로 예제로 넘어가므로, 교안의 4단 서식(§2 관찰)과 걸음 삭제 실험(§1.3)을 손에 쥐고 다시 읽으면 원서 예제의 각 줄이 걸음 ①~④ 중 어느 것인지 짚을 수 있다. 특히 원서가 한 줄에 압축한 자리에서 규칙이 몇 개 적용되었는지 세어 보는 것이 이번 주의 재독 과제다.

1차 시도 — 틀 카드 허용. 다음 두 상자만 옮겨 적은 카드를 펴 놓는다: 기계 6칙과 적용 규칙(§1.3), 부정형 결론의 3처방(§1.5). 그 상태에서 예제 2.1을 전개부터 답안까지 적는다. 예제 본문과 확인 상자는 보지 않는다.

2차 시도 — 완전 백지. 아무것도 보지 않고 수행한다.

  • 기계 6칙을 규칙 번호와 함께 쓰고, 적용 규칙(바깥부터 한 겹씩, 본체까지)을 적었다.

  • 걸음 ①~④의 절차 해부 표를 재현하고, 걸음 ②의 “한 겹씩”과 걸음 ③의 \(\ge\)를 각각 지우면 무엇이 무너지는지 사례와 함께 적었다.

  • 자격 보존을 쓰고, 자격을 부정한 문장이 왜 부정이 아닌지 목격자 하나로 보였다.

  • 부정형 결론의 3처방을 쓰고, 세 결론(단사 아님 / 무리수 / 대우형)에 각각 어느 처방이 먼저 후보인지 답했다.

  • 예제 2.1을 전개 3걸음(N5, N5, N4)과 검증 세 조각까지 재현했다.

  • 예제 2.2의 갈아타기를 재현했고, 배타성 인용 줄이 빠지면 무엇이 닫히지 않는지 말할 수 있다.

  • 훈련 1(단사 아님)과 훈련 3(집합 상등의 부정)을 전개부터 답안까지 재현했다.

  • “반증은 부정 전개와 구성법이다”를 문제 11로 실증했다.

  • 원서 8장을 두 번 읽었고, 1일차에 표시한 문장이 전부 해결되었다.

막힌 지점별 처방. 막힌 지점이 무엇을 다시 볼지 알려 준다.

막힌 지점

처방

첫 문장부터 나오지 않는다

§1.1과 걸음 ① — 낱말을 정의로 펴기 전에는 어떤 규칙도 적용되지 않는다

규칙 이름은 아는데 어느 것부터 쓸지 모르겠다

§1.3 적용 규칙 — 결정하는 것은 취향이 아니라 가장 바깥에 무엇이 있는가다

전개는 했는데 답안이 시작되지 않는다

걸음 ④와 §2 확인 14 — 전개문의 바깥 겹을 네 칸 표에 넣어야 첫 문장이 나온다

전개한 문장이 여전히 부정형이다

§1.5 — 처방 ①의 밀어넣기가 안 되는 경우다. 갈아타기 또는 처방 ②③을 판단한다

자격을 부정해야 하는지 아닌지 헷갈린다

§1.4의 N5 \(\to\) N4 계산 — 자격은 \(\wedge\)의 한쪽으로 살아남는다

증인은 찾았는데 검증이 비어 있다

예제 2.1의 완성본 셋째~다섯째 줄 — 자격 하나와 사건 두 조각이 전부 답안의 문장이다

\(\ge\)인지 \(>\)인지 매번 흔들린다

§1.3의 삭제 실험 2 — 상수함수를 넣어 보면 어느 쪽이 부정인지 한 번에 갈린다

전개가 옳은지 확신이 없다

부정의 자격으로 검산한다 — 원문이 참인 사례를 하나 넣어 전개문이 거짓이 되는지 본다

하나라도 실패하면 그 항목만 다시 적고 다음날 재시도한다.

해설#

각 해설은 접근(문제 앞에서 무엇을 생각하는가)과 풀이로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다.

빈칸 사다리 — 훈련 1#

(1) N4 (2) \(\wedge\) (그리고) (3) 구성 (4) \(-1\) (5) \(1\) (6) \(1\) (7) 부정

※ (4)(5)는 순서가 바뀌어도 되고, \(-2\)와 \(2\)처럼 절댓값이 같은 다른 쌍이어도 된다. 핵심은 \(f(x_1) = f(x_2)\)이면서 \(x_1 \neq x_2\)인 쌍이라는 것이다. (1)에서 N4가 필요한 이유는 정의의 본체가 조건문이기 때문이고, N4를 빠뜨리면 조건문이 남아 §1.3의 삭제 실험 1이 재연된다.

빈칸 사다리 — 훈련 2#

(1) \(\forall k \in \mathbb{Z}:\ mn \neq 2k\) (2) 홀수이다 (3) 홀짝의 전수성(1권 33주차 예제 2.2의 따름정리)과 배타성(1권 22주차 문제 5) (4) \(2a + 1\) (5) \(2ab + a + b\) (6) 정수의 곱과 합은 정수이므로 (근거 ②) (7) 홀짝의 배타성

※ (3)에서 두 사실이 모두 필요하다. 전수성이 없으면 “짝수가 아니다”에서 “홀수이다”로 갈 수 없고(제3의 부류가 있을 수 있다), 배타성이 없으면 “홀수이다”에서 “짝수가 아니다”로 돌아올 수 없다(둘 다일 수 있다). 갈아타기는 두 방향 모두에 근거가 필요하다.

빈칸 사다리 — 훈련 3#

(1) 상등의 판정 기준은 1권 정의 27.1이다 — \(A = B \iff (A \subseteq B) \wedge (B \subseteq A)\). \(\subseteq\)의 정의(1권 정의 4.1)를 마저 펴면 \(A = B\)는

\[ \forall x\,(x \in A \Rightarrow x \in B)\ \wedge\ \forall x\,(x \in B \Rightarrow x \in A) \]

이다. 그 앞에 \(\neg\)를 붙이고 바깥부터 민다. 가장 바깥은 \(\wedge\)이므로 \(\leadsto\) [N2] \(\neg\forall x\,(x \in A \Rightarrow x \in B)\ \vee\ \neg\forall x\,(x \in B \Rightarrow x \in A)\) \(\leadsto\) [N5 두 번] \(\exists x\,\neg(x \in A \Rightarrow x \in B)\ \vee\ \exists x\,\neg(x \in B \Rightarrow x \in A)\) \(\leadsto\) [N4 두 번] \(\exists x\,(x \in A \wedge \neg(x \in B))\ \vee\ \exists x\,(x \in B \wedge \neg(x \in A))\) \(\leadsto\) [본체] \(\exists x\,(x \in A \wedge x \notin B)\ \vee\ \exists x\,(x \in B \wedge x \notin A)\). 읽으면 “\(A\)에만 속하는 원소가 있거나, \(B\)에만 속하는 원소가 있다” — 곧 “한쪽에만 속하는 원소가 존재한다”는 뜻이다. 두 갈래가 \(\vee\)로 이어져 있으므로 갈래마다 규칙을 한 번씩 적용했고, 그것이 “두 번” 표기의 뜻이다. (2) 가장 바깥은 \(\vee\)다. 결론의 \(\vee\)는 어느 쪽이 참인지 지목할 수 있으면 그 갈래 하나만 증명하면 닫힌다(지목이 안 될 때 막히는 자리가 1권 19주차 예제 2.3이었다). 여기서는 지목이 된다 — 6의 배수는 전부 3의 배수이므로 오른쪽 갈래에는 증인이 없고, 왼쪽 갈래 \(\exists x\,(x \in A \wedge x \notin B)\)만 남는다. 고르고 나면 겉모양이 결론의 \(\exists\)이므로 구성법이다 — 그런 원소 하나를 제시하고 검증한다. (3) 3의 배수이면서 6의 배수가 아닌 정수를 찾는다. 가장 작은 후보는 3이다. (4) \(x = 3\)으로 두자 [구성]. 자격: 3은 정수 ✓. 검증 1: \(3 = 3 \cdot 1\)이므로 \(3 \mid 3\), 곧 \(3 \in A\) ✓. 검증 2: \(3 \in B\)라면 \(3 = 6k\)인 정수 \(k\)가 있어야 한다. \(k \le 0\)이면 \(6k \le 0 < 3\)이고 \(k \ge 1\)이면 \(6k \ge 6 > 3\)이므로 그런 정수 \(k\)는 없다 — \(3 \notin B\) ✓. 왼쪽 갈래 \(\exists x\,(x \in A \wedge x \notin B)\)가 성립했으므로 전개문의 \(\vee\)가 성립하고, 곧 \(A \neq B\)이다. \(\blacksquare\)

※ 검증 2가 그 자체로 작은 부정 증명이다. “\(3 \notin B\)”는 \(\neg \exists k\) 꼴이므로 N6로 \(\forall k\)가 되고, 그 \(\forall k\)를 \(k \le 0\)과 \(k \ge 1\)의 두 경우로 전수 처리했다. 부정 안의 부정도 같은 기계로 돈다.

문제 1#

접근. 네 상자를 재현하는 문항이지만 순서가 있다. 6칙은 규칙표이고, 적용 규칙은 그 규칙표를 어떤 순서로 쓰는지의 지시이며, 자격 보존은 그 순서를 지켜도 틀릴 수 있는 한 자리의 경고이고, 3처방은 전개가 끝난 뒤의 갈림길이다. 이 넷의 관계를 함께 적어야 백지에서 하나를 잊었을 때 나머지에서 복구할 수 있다.

풀이. 채점 항목은 다음과 같다.

6칙: N1 \(\neg\neg P \leadsto P\) / N2 \(\neg(P \wedge Q) \leadsto \neg P \vee \neg Q\) / N3 \(\neg(P \vee Q) \leadsto \neg P \wedge \neg Q\) / N4 \(\neg(P \Rightarrow Q) \leadsto P \wedge \neg Q\) / N5 \(\neg\forall x \in S, P(x) \leadsto \exists x \in S, \neg P(x)\) / N6 \(\neg\exists x \in S, P(x) \leadsto \forall x \in S, \neg P(x)\).

적용 규칙: NOT이 본체(등호\(\cdot\)부등호\(\cdot\)소속)에 닿을 때까지 바깥부터 한 겹씩 밀고, 한 걸음에 규칙 하나만 쓴다. 본체에 닿으면 \(\neg(a = b)\)는 \(a \neq b\), \(\neg(a < b)\)는 \(a \ge b\), \(\neg(x \in A)\)는 \(x \notin A\)로 적는다.

자격 보존: 양화사에 붙은 자격(\(\in S\), “양수”, “\(n > N\)”)은 부정되지 않는다. N5와 N4를 차례로 쓰면 자격이 \(\wedge\)의 한쪽으로 살아남는 것이 계산으로 나온다.

3처방: ① 긍정형 재표현(밀어넣기 또는 특성화 갈아타기) ② 대우 ③ 귀류. 셋 다 첫 동작은 정확한 전개다.

복기. 자가 채점에서 볼 것은 여섯 줄을 다 썼는가가 아니라, 각 줄이 어디서 나왔는지 댈 수 있는가다. N2\(\cdot\)N3\(\cdot\)N1은 1권 9주차 동치 목록, N4는 1권 9주차 문제 7, N5\(\cdot\)N6은 1권 10주차의 판정 기준이다. 출처를 대면 잊었을 때 그 자리에서 다시 만들 수 있다.

문제 2#

접근. 네 문항 모두 규칙 한 걸음과 본체 도달 한 걸음, 합쳐 두 걸음이다. 시작 전에 가장 바깥이 무엇인지(양화사인가 연결사인가)부터 확정한다. (a)는 자격이 붙은 전칭이므로 §1.4가 그대로 걸린다.

풀이.

(a) 가장 바깥은 \(\forall\)이므로 [N5] “어떤 짝수 \(n\)에 대해 \(\neg\)(\(n^2\)은 4의 배수이다)”이고, 본체 도달까지 가면 “어떤 짝수 \(n\)에 대해 \(n^2\)은 4의 배수가 아니다”이다. 자격 “짝수”는 그대로 남는다. 참고로 이 부정은 거짓이다 — \(n = 2k\)이면 \(n^2 = 4k^2\)이므로 원명제가 참이기 때문이고, 그래야 부정의 자격이 지켜진다.

(b) 가장 바깥은 \(\wedge\)이므로 [N2] \(\neg(x > 0) \vee \neg(y > 0)\)이고, 본체 도달까지 가면 “\(x \le 0\) 또는 \(y \le 0\)”이다. \(\vee\)가 나왔으므로 이 문장을 가정으로 받으면 케이스 신호가 된다.

(c) 가장 바깥은 \(\exists\)이므로 [N6] “모든 실수 \(x\)에 대해 \(\neg(x^2 = -1)\)”이고, 본체 도달까지 가면 “모든 실수 \(x\)에 대해 \(x^2 \neq -1\)”이다. 자격 “실수”는 그대로다.

(d) 가장 바깥은 \(\vee\)이므로 [N3] \(\neg(a \mid b) \wedge \neg(a \mid c)\)이고, 본체 도달까지 가면 “\(a \nmid b\) 그리고 \(a \nmid c\)”이다.

복기. (b)와 (d)가 서로 뒤집힌 쌍이다 — \(\wedge\)의 부정은 \(\vee\), \(\vee\)의 부정은 \(\wedge\). 방향을 외우지 말고 뜻으로 확인한다: “둘 다”가 실패하려면 한쪽만 실패해도 되고, “하나라도”가 실패하려면 둘 다 실패해야 한다.

문제 3#

접근. 세 문항 모두 걸음 ①(정의 노출)이 절반이다. 정의를 편 뒤에는 바깥부터 규칙을 차례로 적용하는 기계적 작업만 남는다. (b)는 “같은 홀짝”이라는 낱말 자체를 먼저 풀어야 하고, 풀면 \(\vee\)가 나오므로 N3부터 시작한다.

풀이.

(a) 정의 노출: 위로 유계는 \(\exists M\ \forall n:\ a_n \le M\)이다. \(\neg\big(\exists M\ \forall n:\ a_n \le M\big)\) \(\leadsto\) [N6] \(\forall M\ \neg\big(\forall n:\ a_n \le M\big)\) \(\leadsto\) [N5] \(\forall M\ \exists n:\ \neg(a_n \le M)\) \(\leadsto\) [본체] \(\forall M\ \exists n:\ a_n > M\). 읽으면 “어떤 문턱을 제시해도 그것을 넘는 항이 있다”이다.

(b) 정의 노출: “같은 홀짝”은 (\(m\) 짝수 \(\wedge\) \(n\) 짝수) \(\vee\) (\(m\) 홀수 \(\wedge\) \(n\) 홀수)이다. [N3] \(\neg\)(\(m\) 짝수 \(\wedge\) \(n\) 짝수) \(\wedge\) \(\neg\)(\(m\) 홀수 \(\wedge\) \(n\) 홀수) \(\leadsto\) [N2 두 번] (\(m\) 홀수 \(\vee\) \(n\) 홀수) \(\wedge\) (\(m\) 짝수 \(\vee\) \(n\) 짝수). (여기서 \(\neg\)(\(m\) 짝수)를 “\(m\) 홀수”로 적은 것은 전수성과 배타성의 인용이다.) 정리하면 다음과 같다. \(m\)이 홀수라 하자. 둘째 괄호에서 \(m\) 짝수 또는 \(n\) 짝수인데 \(m\)은 배타성에 의해 짝수가 아니므로 \(n\)이 짝수다. \(m\)이 홀수가 아니라면 전수성에 의해 \(m\)은 짝수이고, 첫째 괄호에서 \(m\) 홀수 또는 \(n\) 홀수인데 \(m\)은 홀수가 아니므로 \(n\)이 홀수다. 어느 경우든 하나는 짝수이고 다른 하나는 홀수다.

(c) 정의 노출: 상수함수는 \(\exists c\ \forall x:\ f(x) = c\)이다. \(\leadsto\) [N6] \(\forall c\ \neg\big(\forall x:\ f(x) = c\big)\) \(\leadsto\) [N5] \(\forall c\ \exists x:\ \neg(f(x) = c)\) \(\leadsto\) [본체] \(\forall c\ \exists x:\ f(x) \neq c\). 읽으면 “어떤 후보 상수를 제시해도 그것을 배반하는 입력이 있다”이다.

복기. (a)와 (c)의 전개문이 같은 모양(\(\forall\ \exists\))이다. 겉모양이 같으므로 답안의 문장 배치도 같다 — 임의로 받고, 그 문자의 식으로 증인을 만든다. 문제 8과 문제 9가 각각 (c)와 (a)의 실전이고, 두 답안이 같은 순서로 흘러간다.

문제 4#

접근. 세 훈련은 지지대만 다르고 서식은 하나(4단 서식)다. 백지에서는 지지대가 전부 없으므로, 훈련 1을 먼저 전개부터 다시 만들고 그 골격을 훈련 2\(\cdot\)3에 옮기는 순서가 빠르다.

풀이. 답은 위의 “빈칸 사다리 — 훈련 1/2/3” 항목과 대조한다. 백지에서 특히 자주 빠지는 줄이 셋 있으니 그 셋을 따로 점검한다.

첫째, 훈련 1에서 규칙 번호(N5, N5, N4)를 빠뜨리는 경우다. 전개문만 맞게 적어도 채점 기준 ①을 만족하지 못한다.

둘째, 훈련 2의 마지막 인용이다. “\(mn\)은 홀수이다”까지 쓰고 끝내면 증명한 명제와 요구된 명제가 다르다 — 배타성 인용 줄이 있어야 “짝수가 아니다”에 도달한다.

셋째, 훈련 3의 검증 2다. “\(3 \notin B\)”를 “\(3\)은 6의 배수가 아니니까”로 적고 넘어가는 경우가 많은데, 그것은 검증이 아니라 결론의 반복이다. \(6k = 3\)인 정수 \(k\)가 없음을 \(k \le 0\)과 \(k \ge 1\)로 나누어 실제로 보여야 한다.

복기. 세 누락의 공통점은 전부 “마지막 한 줄”이라는 것이다. 부정 증명은 원명제로 돌아오는 줄에서 닫히므로, 답안을 덮기 전에 마지막 줄이 원명제의 낱말을 다시 쓰고 있는지 확인하는 습관이 유효하다.

문제 5#

접근. 재현 문항이지만 채점 대상은 답안이 아니라 전개다. 정의를 편 직후 가장 바깥이 \(\forall x_1\)이라는 것만 확정하면 규칙 순서가 저절로 정해지고, 나머지는 구성법의 표준 서식이다.

풀이. 재현 결과는 다음과 같아야 한다.

전개. 걸음 ① — 증가함수의 정의를 펴면 \(\forall x_1 \forall x_2\,[x_1 < x_2 \Rightarrow f(x_1) < f(x_2)]\)이고, 명제는 그 앞에 \(\neg\)가 붙은 것이다. 걸음 ② — [N5] \(\exists x_1 \neg[\forall x_2(\dots)]\), 다시 [N5] \(\exists x_1 \exists x_2 \neg(x_1 < x_2 \Rightarrow f(x_1) < f(x_2))\), 이어 [N4] \(\exists x_1 \exists x_2 (x_1 < x_2 \wedge \neg(f(x_1) < f(x_2)))\). 걸음 ③ — 본체 도달:

\[ \exists x_1 \exists x_2\ \big(x_1 < x_2\ \wedge\ f(x_1) \ge f(x_2)\big) \]

답안. 걸음 ④ 판독으로 결론의 \(\exists\) — 구성법이 지정된다. \(x_1 = -1\), \(x_2 = 0\)으로 두자. 자격: 둘 다 실수 ✓. 사건 1: \(-1 < 0\) ✓. 사건 2: \(f(-1) = 1\)이고 \(f(0) = 0\)이므로 \(f(-1) \ge f(0)\) ✓. 따라서 전개문이 성립하고, \(f\)는 증가함수가 아니다. \(\blacksquare\)

검산. 증가함수인 \(f(x) = x\)에 같은 전개문을 대 보면 \(x_1 < x_2\)인 모든 쌍에서 \(f(x_1) < f(x_2)\)이므로 전개문이 거짓이다 — 원문이 참일 때 전개문이 거짓이라는 것이 부정의 자격이 지켜졌다는 표시다.

문제 6#

접근. 목격자는 두 문장의 진리값이 갈라지는 구체적 인스턴스다. 사고 1과 2는 \(P\)와 \(Q\)에 참\(\cdot\)거짓을 배정하는 네 경우를 훑으면 반드시 하나가 나오고, 사고 3은 자격을 위반하는 수 하나면 된다. 진리값을 실제로 계산해 적는 것까지가 답이다.

풀이.

사고 1 (\(\neg(P \wedge Q)\)를 \(\neg P \wedge \neg Q\)로). 목격자: \(P\) 참, \(Q\) 거짓. 좌변 — \(P \wedge Q\)가 거짓이므로 \(\neg(P \wedge Q)\)는 참. 우변 — \(\neg P\)가 거짓이므로 \(\neg P \wedge \neg Q\)는 거짓. 진리값이 다르므로 사고 전개는 부정이 아니다.

사고 2 (\(\neg(P \Rightarrow Q)\)를 \(\neg P \Rightarrow \neg Q\)로). 목격자: \(P\) 거짓, \(Q\) 거짓. 좌변 — 전건이 거짓이면 조건문은 참이므로 \(P \Rightarrow Q\)는 참이고 \(\neg(P \Rightarrow Q)\)는 거짓. 우변 — \(\neg P\) 참, \(\neg Q\) 참이므로 \(\neg P \Rightarrow \neg Q\)는 참. 갈라진다.

사고 3 (자격까지 부정). 목격자: \(x = -1\). 원명제 “모든 양수 \(x\)에 대해 \(x + \frac1x \ge 2\)”는 참이다(\(x > 0\)일 때 \(x + \frac1x - 2 = \frac{(x-1)^2}{x} \ge 0\) — (W1)과 (W5)). 사고 전개 “어떤 \(x\)는 양수가 아니거나 \(x + \frac1x < 2\)이다”도 \(x = -1\)이 “양수가 아니다”를 만족시키므로 참이다. 원문과 부정은 진리값이 반대여야 하는데 둘 다 참이므로 부정이 아니다.

복기. 세 목격자를 찾는 방법이 같다 — 두 문장을 나란히 놓고, 한쪽만 참이 되게 하는 가장 단순한 배정을 고른다. 사고 1은 \(\wedge\)의 한쪽만 무너뜨리면 되고, 사고 2는 조건문이 공허하게 참이 되는 자리를 고르면 되며, 사고 3은 자격 밖의 대상을 고르면 된다. 이 검산은 전개를 마친 뒤 스스로에게도 그대로 쓸 수 있다.

문제 7#

접근. 결론이 \(\neq\)이므로 부정 신호다. 그대로 밀면 짝수 정의를 부정할 때처럼 \(\forall\)이 하나 더 생겨 길어진다. 처방 ①의 다른 갈래를 쓴다 — 순서로 강화한다. “0이 아니다”는 “0보다 크다”에서 따라오므로, 더 강한 것을 증명하면 원래 결론은 공짜로 나온다.

풀이. 증명. 실수 \(x\)를 임의로 잡자 [선택]. 1권 16주차의 (W1)에 의해 \(x^2 \ge 0\)이다. 양변에 1을 더하면 (W2)에 의해 \(x^2 + 1 \ge 1\)이고, \(1 > 0\)이므로 (W6) 추이성에 의해 \(x^2 + 1 > 0\)이다. 0보다 큰 수는 0이 아니므로 \(x^2 + 1 \neq 0\)이다. \(x\)가 임의였으므로 모든 실수 \(x\)에 대해 성립한다. \(\blacksquare\)

복기. “\(\neq\)는 직접 다루지 말고 순서로 강화해 이긴다”가 부등식 세계에서의 처방 ①이다. 같은 수가 문제 15에서도 쓰인다 — 거기서도 \(f(x) > M\)을 보이는 것이 “\(f(x) \le M\)이 아니다”를 보이는 것보다 짧다. 부정형 결론을 더 강한 긍정형 결론으로 바꿀 수 있는지 먼저 살피는 것이 이 수의 요점이다.

검산. \(x = 0\)을 넣으면 \(x^2 + 1 = 1 \neq 0\) ✓. \(x = 3\)이면 \(10 \neq 0\) ✓.

문제 8#

접근. 문제 3(c)의 전개 \(\forall c\ \exists x:\ f(x) \neq c\)가 출발점이다. 바깥이 결론의 \(\forall\)이므로 후보 \(c\)를 임의로 받는 것이 첫 문장이고, 안쪽이 결론의 \(\exists\)이므로 그 \(c\)를 배반하는 \(x\)를 만드는 것이 둘째 문장이다. 증인은 \(c\)의 식이어도 된다 — S8주차의 의존성의 문법이 그것을 허락한다. 두 가지 길이 있고 둘 다 정답이다.

풀이 1 (서로 다른 두 값의 확보). 실수 \(c\)를 임의로 잡자 [선택]. \(f(0) = 1\)이고 \(f(1) = 4\)이다. \(1 \neq 4\)이므로 \(c\)는 1과 4 중 많아야 하나와 같다. \(c \neq 1\)이면 \(x = 0\)으로 두자 — \(f(0) = 1 \neq c\) ✓. \(c = 1\)이면 \(c \neq 4\)이므로 \(x = 1\)로 두자 — \(f(1) = 4 \neq c\) ✓. 어느 경우든 \(f(x) \neq c\)인 실수 \(x\)가 존재한다. \(c\)가 임의였으므로 \(f\)는 상수함수가 아니다. \(\blacksquare\)

풀이 2 (맞춤 증인 직접 구성). 실수 \(c\)를 임의로 잡자 [선택]. \(x = \dfrac{c + 2}{3}\)으로 두자 [구성]. 자격: \(c\)가 실수이므로 \(x\)도 실수 ✓. 사건:

\[ f(x) = 3 \cdot \frac{c+2}{3} + 1 = (c + 2) + 1 = c + 3 \]

이고 \(3 \neq 0\)이므로 \(c + 3 \neq c\), 곧 \(f(x) \neq c\)이다 ✓. \(c\)가 임의였으므로 \(f\)는 상수함수가 아니다. \(\blacksquare\)

복기. 풀이 1은 “모든 후보”를 두 값의 확보로 한 번에 처리하는 지름길이고 — S8주차 예제 2.1(b)에서 만능 증인을 두 값의 충돌로 무너뜨린 것과 같은 수다 — 풀이 2는 증인을 \(c\)의 식으로 직접 만드는 정석이다. 증인을 만들 수 있으면 풀이 2가 짧고, 만들기 어려우면 풀이 1의 두 값 확보가 통한다.

검산. 풀이 2에서 \(c = 0\)이면 \(x = \frac23\)이고 \(f(\frac23) = 3 \neq 0\) ✓. \(c = 7\)이면 \(x = 3\)이고 \(f(3) = 10 \neq 7\) ✓.

문제 9#

접근. 문제 3(a)의 전개 \(\forall M\ \exists n \in \mathbb{N}:\ n > M\)이 출발점이다. \(M\)을 임의로 받고 그보다 큰 자연수를 만들면 된다. \(M\)이 음수일 수도 있으므로 절댓값을 한 번 거치면 부호를 나누지 않고 자격 검증이 한 줄로 끝난다. 부품은 천장의 성질(S5주차 문제 14)과 \(M \le \lvert M \rvert\)(1권 17주차 문제 5)이다.

풀이. 증명. 실수 \(M\)을 임의로 잡자 [선택]. \(n = \lceil \lvert M \rvert \rceil + 1\)로 두자 [구성].

자격 검증: \(\lvert M \rvert \ge 0\)이고 천장의 성질에 의해 \(\lceil \lvert M \rvert \rceil\)은 \(\lvert M \rvert\) 이상인 정수이므로 \(\lceil \lvert M \rvert \rceil \ge 0\)이고, 따라서 \(n \ge 1\)이다. \(n\)은 정수이고 1 이상이므로 자연수다 ✓.

사건 검증: 천장의 성질에서 \(\lceil \lvert M \rvert \rceil \ge \lvert M \rvert\)이고, 1권 17주차 문제 5에서 \(\lvert M \rvert \ge M\)이다. 따라서

\[ n = \lceil \lvert M \rvert \rceil + 1 > \lceil \lvert M \rvert \rceil \ge \lvert M \rvert \ge M \]

이므로 (W6) 추이성에 의해 \(n > M\)이다 ✓. 곧 “모든 자연수는 \(M\) 이하이다”가 위반된다.

\(M\)이 임의였으므로 어떤 실수도 \(\mathbb{N}\)의 상계가 아니고, \(\mathbb{N}\)은 위로 유계가 아니다. \(\blacksquare\)

복기. 증인이 임의로 받은 \(M\)의 식이라는 점이 이 답안의 핵심이다. \(M\)이 먼저 무대에 올랐기 때문에 합법이고, 순서를 바꾸어 \(n\)을 먼저 정하면 만능 증인을 주장한 것이 되어 곧바로 무너진다(S8주차 문제 18의 결함이 그것이었다). 이 명제는 아르키메데스 성질 (S5주차 문제 14)의 다른 얼굴이다.

검산. \(M = 3.2\)이면 \(n = \lceil 3.2 \rceil + 1 = 5 > 3.2\) ✓. \(M = -7\)이면 \(n = \lceil 7 \rceil + 1 = 8 > -7\) ✓.

문제 10#

접근. 걸음 ①은 상등을 판정 기준으로 펴는 것이다 — 1권 정의 27.1에 의해 \(A = B\)는 \((A \subseteq B) \wedge (B \subseteq A)\)이고, \(\subseteq\)를 마저 펴면 \(\forall\) 문장 두 개의 \(\wedge\)가 된다. 부정하면 N2\(\cdot\)N5\(\cdot\)N4가 차례로 작동해 \(\vee\)로 이어진 두 존재 진술이 되고, 갈래 하나를 지목하면 결론의 \(\exists\)이므로 구성법이 지정된다. 증인 후보는 “2의 배수이지만 4의 배수가 아닌 정수”이고 가장 작은 것이 2다. 검증 2가 그 자체로 작은 부정 증명이라는 점이 이 문제의 무게다.

풀이. 전개. 1권 정의 27.1과 부분집합의 정의(1권 정의 4.1)에 의해 \(A = B\)는 \(\forall x\,(x \in A \Rightarrow x \in B)\ \wedge\ \forall x\,(x \in B \Rightarrow x \in A)\)이다. 그 앞에 \(\neg\)를 붙이고 바깥부터 민다.

\(\leadsto\) [N2] \(\neg\forall x\,(x \in A \Rightarrow x \in B)\ \vee\ \neg\forall x\,(x \in B \Rightarrow x \in A)\)

\(\leadsto\) [N5 두 번] \(\exists x\,\neg(x \in A \Rightarrow x \in B)\ \vee\ \exists x\,\neg(x \in B \Rightarrow x \in A)\)

\(\leadsto\) [N4 두 번] \(\exists x\,(x \in A \wedge \neg(x \in B))\ \vee\ \exists x\,(x \in B \wedge \neg(x \in A))\)

\(\leadsto\) [본체] \(\exists x\,(x \in A \wedge x \notin B)\ \vee\ \exists x\,(x \in B \wedge x \notin A)\)

읽으면 “한쪽에만 속하는 원소가 존재한다”이다. 판독: 가장 바깥이 \(\vee\)이므로 지목이 가능한 갈래 하나를 고른다. 여기서는 \(4 \mid n\)이면 \(2 \mid n\)이므로 오른쪽 갈래는 증인이 없다 — 왼쪽 갈래 \(\exists x\,(x \in A \wedge x \notin B)\)를 고르면 결론의 \(\exists\)이므로 구성법이다.

증명. \(x = 2\)로 두자 [구성]. 자격: 2는 정수 ✓.

검증 1 (\(2 \in A\)): \(2 = 2 \cdot 1\)이고 \(1\)은 정수이므로 \(2 \mid 2\)이다. 따라서 \(2 \in A\) ✓.

검증 2 (\(2 \notin B\)): \(2 \in B\)라고 하면 \(2 = 4k\)인 정수 \(k\)가 존재해야 한다. 이 \(\neg\exists\)를 전개하면 [N6] “모든 정수 \(k\)에 대해 \(4k \neq 2\)”를 보이면 되고, 정수 \(k\)를 임의로 잡아 두 경우로 나눈다. \(k \le 0\)이면 \(4k \le 0 < 2\)이고, \(k \ge 1\)이면 \(4k \ge 4 > 2\)이다. 모든 정수는 \(k \le 0\)이거나 \(k \ge 1\)이므로 두 경우가 전부를 덮고, 어느 경우든 \(4k \neq 2\)이다. 따라서 \(2 \notin B\) ✓.

\(2\)는 \(A\)에 속하고 \(B\)에는 속하지 않으므로 왼쪽 갈래 \(\exists x\,(x \in A \wedge x \notin B)\)가 성립하고, 따라서 전개문의 \(\vee\)가 성립한다. 곧 한쪽에만 속하는 원소가 존재하므로 \(A \neq B\)이다. \(\blacksquare\)

복기. 검증 2를 “\(\frac12\)은 정수가 아니므로”로 한 줄에 끝내고 싶어지지만, 그것은 \(4k = 2\)의 실수 해가 하나뿐이라는 사실을 암묵적으로 쓴 것이다. 위처럼 두 경우로 나누면 쓰는 근거가 부등식의 기본 성질뿐이므로 근거 목록 안에서 닫힌다. 부정 안의 부정을 만났을 때 같은 기계를 한 번 더 돌리면 된다는 것이 이 문제의 이식 가능한 부분이다.

검산. \(4 \in A\)이고 \(4 \in B\)이다 — 공통 원소가 있다는 것은 \(A \neq B\)와 모순되지 않는다. 상등의 부정에 필요한 것은 “한쪽에만 속하는 원소 하나”이지 “공통 원소가 없다”가 아니다.

문제 11#

접근. 반례의 문법(§1.6)이 그대로 적용된다. 원명제가 \(\forall n\ [P(n)]\) 꼴이므로 부정은 [N5] \(\exists n\ [\neg P(n)]\)이고, 결론의 \(\exists\)이므로 구성법 — 위반자 하나를 찾아 검증한다. 증인 정찰은 작은 수부터 표로 계산하는 것이 가장 빠르다.

풀이. 전개: \(\neg\big(\forall n \in \mathbb{N}:\ 2^n \ge n^2\big) \leadsto\) [N5] \(\exists n \in \mathbb{N}:\ \neg(2^n \ge n^2) \leadsto\) [본체] \(\exists n \in \mathbb{N}:\ 2^n < n^2\).

정찰:

\(n\)

\(2^n\)

\(n^2\)

\(2^n \ge n^2\)

1

2

1

성립

2

4

4

성립 (등호)

3

8

9

위반

4

16

16

성립 (등호)

5

32

25

성립

증명(반증). \(n = 3\)으로 두자 [구성]. 자격: 3은 자연수 ✓. 사건: \(2^3 = 8\)이고 \(3^2 = 9\)이며 \(8 < 9\)이다 ✓. 따라서 \(\exists n \in \mathbb{N}:\ 2^n < n^2\)이 성립하고, 원명제는 거짓이다. \(\blacksquare\)

수리된 명제(진술만): “모든 자연수 \(n\)에 대해, \(n = 1\)이거나 \(n \ge 4\)이면 \(2^n \ge n^2\)이다.” (더 강한 형태로는 “모든 자연수 \(n \ge 5\)에 대해 \(2^n > n^2\)이다” — 등호가 사라진다.)

복기. 위 표에서 확인되는 위반은 \(n = 3\) 하나이고, \(n \ge 4\)에서 다시 성립한다는 것은 귀납법(S14주차)이 증명한다 — 표 다섯 줄만으로는 거기까지 오지 않는다. 그 사실까지 받아들이면 유일한 위반자가 \(n = 3\)이므로, 자격을 가장 정확히 수리하면 “\(n \neq 3\)”이다. 그런데도 관례적으로 “\(n \ge 4\)”나 “\(n \ge 5\)”로 적는 이유는 그 꼴이 귀납법으로 증명하기 좋기 때문이다 — 자격의 수리는 참이기만 하면 되는 것이 아니라 증명 가능한 꼴로 하는 것이 실용적이다. 1권 29주차 예제 2.3 뒤 상자(“반례는 명제를 수선하기도 한다”)의 습관에 한 가지가 더해지는 자리다. 29주차가 \(3^n > n^3\)의 경계를 \(n \ge 4\)로 수리한 것이 바로 이 자리이고, 거기서도 수리된 명제의 증명은 귀납법으로 미뤄 두었다.

검산. \(n = 4\): \(16 \ge 16\) ✓. \(n = 5\): \(32 > 25\) ✓. 수리된 명제의 경계가 실제로 맞다.

문제 12#

접근. 세 문항의 사고 유형이 서로 다르다. (a)는 자격을 뒤집었고, (b)는 규칙을 빠뜨린 채 양화사만 바꿨으며, (c)는 N2의 방향을 반대로 썼다. 각각에 목격자를 붙여야 진단이 판정이 된다.

풀이.

(a) 자격 부정 사고다. \(\varepsilon\)에 붙은 “\(> 0\)”은 심사 범위의 선언이므로 부정되지 않는다. 올바른 전개는 \(\exists \varepsilon > 0\ \forall N\ \exists n > N:\ \lvert a_n \rvert \ge \varepsilon\)이다 (\(n > N\)이라는 자격도 같은 이유로 보존된다). 목격자: 사고 전개대로라면 \(\varepsilon \le 0\)을 골라도 되는데, 절댓값은 항상 0 이상이므로 \(\lvert a_n \rvert \ge \varepsilon\)이 모든 \(n\)에서 자동으로 성립한다. 곧 사고 전개는 어떤 수열에 대해서도 참이고, 0으로 수렴하는 수열 \(a_n = \frac1n\)에 대해서도 참이다. 원명제가 참인데 부정도 참이므로 부정의 자격이 무너진다.

(b) 규칙 누락과 양화사 뒤바뀜이다. 단사의 정의는 \(\forall x_1 \forall x_2\,[f(x_1) = f(x_2) \Rightarrow x_1 = x_2]\)이고, 부정은 [N5, N5, N4] \(\exists x_1 \exists x_2\,[\,f(x_1) = f(x_2) \wedge x_1 \neq x_2\,]\)이다. 제시된 문장은 \(\forall\)을 그대로 두었고 조건문의 부정(N4)도 하지 않았다. 목격자: \(f(x) = x^2\)은 단사가 아니지만, \(x_1 = 1\), \(x_2 = 2\)는 \(x_1 \neq x_2\)인데 \(f(1) = 1 \neq 4 = f(2)\)이므로 제시된 문장은 거짓이다. 원명제의 부정이 참이어야 하는 자리에서 거짓이 나왔으므로 부정이 아니다. (덧붙이면 제시된 문장 \(\forall x_1 \forall x_2\,[\,x_1 \neq x_2 \Rightarrow f(x_1) = f(x_2)\,]\)을 만족하는 함수는 상수함수뿐이다 — 문제 3(c)의 정의 \(\exists c\ \forall x: f(x) = c\)와 같은 조건이며, 훨씬 강한 다른 명제다.)

(c) N2의 방향 사고다. \(\wedge\)의 부정은 \(\vee\)이므로 올바른 전개는 “\(p\)는 소수가 아니거나 \(p \le 2\)이다”이다. 목격자: \(p = 4\)를 보자. 원문 “\(p\)는 소수이고 \(p > 2\)”는 거짓이므로 그 부정은 참이어야 한다. 올바른 전개는 “4는 소수가 아니다”에서 참이 된다. 사고 전개는 “4는 소수가 아니고 \(4 \le 2\)”인데 뒤쪽이 거짓이므로 전체가 거짓이다. 진리값이 갈라진다.

복기. 세 진단의 서식이 같다 — 규칙 지목, 올바른 전개, 목격자. 자기 답안을 검열할 때도 같은 순서로 훑으면 된다. 특히 목격자 찾기는 전개를 마친 뒤 언제나 할 수 있는 검산이므로, 전개가 길수록 반드시 한 번 돌린다.

문제 13#

접근. 두 전개의 차이는 정의가 \(\vee\)인가 \(\wedge\)인가 하나뿐이고, 그 하나가 결과를 \(\wedge\)와 \(\vee\)로 갈라 놓는다. 결과가 \(\vee\)이면 어느 쪽인지 모르는 채로 손에 들어오므로 케이스 신호가 된다는 것까지가 이 문제의 목적이다.

풀이. 합집합 쪽. \(\cup\)의 정의에 의해 \(x \in A \cup B\)는 \(x \in A \vee x \in B\)이다. 따라서 \(x \notin A \cup B\)는 \(\neg(x \in A \vee x \in B)\)이고, [N3] \(\neg(x \in A) \wedge \neg(x \in B)\), 본체 도달까지 가면 \(x \notin A\) 그리고 \(x \notin B\)이다.

S6주차 문제 15(\(A - (B \cup C) = (A-B) \cap (A-C)\))의 \(\subseteq\) 방향에서, 원소 \(x\)를 임의로 잡아 \(x \in A - (B \cup C)\)를 풀면 “\(x \in A\)이고 \(x \notin B \cup C\)”가 나온다. 그 두 번째 조각을 “\(x \notin B\)이고 \(x \notin C\)”로 쪼갠 걸음이 정확히 이 전개다. 그 순간부터 \(x \in A - B\)와 \(x \in A - C\)를 각각 조립할 수 있게 된다.

교집합 쪽. \(\cap\)의 정의에 의해 \(x \in A \cap B\)는 \(x \in A \wedge x \in B\)이므로, \(x \notin A \cap B\)는 [N2] \(x \notin A\) 또는 \(x \notin B\)이다.

결과가 \(\vee\)라는 것이 중요하다. 이 사실을 가정으로 받으면 어느 쪽이 성립하는지 알 수 없으므로, 두 경우를 각각 처리해야 한다 — 케이스 신호다(1권 17주차의 경우 나누기; 소거법을 포함한 체계적 처리는 S15주차에서 다룬다).

복기. 전개의 결과가 \(\wedge\)인지 \(\vee\)인지가 다음 걸음을 결정한다. \(\wedge\)면 두 조각을 모두 손에 쥔 것이고, \(\vee\)면 두 갈래로 나누어 각각 완결해야 한다. 전개를 마친 뒤 연결사를 먼저 보는 습관이 여기서 만들어진다.

문제 14#

접근. 수렴의 정의(1권 정의 45.1)가 세 겹이고 그 바깥에 \(\exists L\)이 하나 더 붙으므로 전부 네 겹이다. 규칙을 네 번 적용하는 동안 겹이 하나씩 뒤집히므로, 줄을 나누어 적고 각 줄에 규칙 번호를 단다.

풀이. 전개. “수렴한다”는 \(\exists L \in \mathbb{R}\ \big[\forall \varepsilon > 0\ \exists N\ \forall n > N:\ \lvert a_n - L \rvert < \varepsilon\big]\)이다.

\(\leadsto\) [N6] \(\forall L\ \neg\big[\forall \varepsilon > 0\ \exists N\ \forall n > N:\ \lvert a_n - L \rvert < \varepsilon\big]\)

\(\leadsto\) [N5] \(\forall L\ \exists \varepsilon > 0\ \neg\big[\exists N\ \forall n > N:\ \lvert a_n - L \rvert < \varepsilon\big]\)

\(\leadsto\) [N6] \(\forall L\ \exists \varepsilon > 0\ \forall N\ \neg\big[\forall n > N:\ \lvert a_n - L \rvert < \varepsilon\big]\)

\(\leadsto\) [N5] \(\forall L\ \exists \varepsilon > 0\ \forall N\ \exists n > N:\ \neg\big(\lvert a_n - L \rvert < \varepsilon\big)\)

\(\leadsto\) [본체] \(\forall L\ \exists \varepsilon > 0\ \forall N\ \exists n > N:\ \lvert a_n - L \rvert \ge \varepsilon\).

자격 “\(\varepsilon > 0\)”과 “\(n > N\)”은 네 걸음 내내 그대로 남는다.

차이. S8주차 문제 15는 바깥의 \(\forall L\) 없이 \(L = 0\) 한 점만 격파한 것이고, 이번 전개의 “수렴하지 않는다”는 모든 후보 극한을 격파하는 것이므로 겹이 하나 더 있다.

증명은 S8주차 문제 15 해설 끝의 스케치를 인용한다: 임의의 \(L\)에 대해 \(\varepsilon = \frac12\)로 두면, 삼각부등식에서 \(\lvert 1 - L \rvert + \lvert -1 - L \rvert \ge \lvert (1-L) - (-1-L) \rvert = 2\)이므로 두 값 중 적어도 하나는 1 이상이고, 그 쪽에 해당하는 홀수 또는 짝수 \(n\)을 \(N\)보다 크게 고르면 \(\lvert a_n - L \rvert \ge 1 > \frac12\)이 된다.

복기. 겹이 하나 늘 때마다 기법이 하나씩 바뀐다. 전개문의 배치는 [선택 \(L\)] \(\cdot\) [구성 \(\varepsilon\)] \(\cdot\) [선택 \(N\)] \(\cdot\) [구성 \(n\)]이고, 수렴 증명의 [선택] \(\cdot\) [구성] \(\cdot\) [선택]과 정확히 뒤집힌 모양이다. 부정이 의무와 권리를 전부 맞바꾼다는 S8주차 문제 14의 관찰이 여기서 한 겹 더 확장된다.

문제 15#

접근. “위로 유계가 아니다”의 전개는 문제 3(a)와 같은 꼴이다 — \(\forall M\ \exists x \in \mathbb{R}:\ f(x) > M\). \(M\)을 임의로 받고 \(M\)보다 큰 값을 내는 \(x\)를 만든다. 증인을 \(\lvert M \rvert + 1\)로 두면 \(x \ge 1\)이 확보되고, 그 조건에서 \(x^3\)의 부호가 정해진다.

풀이. 증명. 실수 \(M\)을 임의로 잡자 [선택]. \(x = \lvert M \rvert + 1\)로 두자 [구성].

자격 검증: \(M\)이 실수이므로 \(\lvert M \rvert\)도 \(x\)도 실수다 ✓.

사건 검증: \(\lvert M \rvert \ge 0\)이므로 \(x \ge 1\)이고, 따라서 \(x > 0\)이다. (W4)에 의해 \(x \cdot x = x^2 > 0\)이고 다시 (W4)에 의해 \(x^2 \cdot x = x^3 > 0\)이다. (W2)에 의해 양변에 \(x\)를 더하면 \(x^3 + x > 0 + x = x\)이다. 그러므로

\[ f(x) = x^3 + x > 0 + x = x = \lvert M \rvert + 1 > \lvert M \rvert \ge M \]

이고, (W6) 추이성에 의해 \(f(x) > M\)이다 ✓ (마지막 부등식은 1권 17주차 문제 5). 곧 \(M\)은 상계 조건 “\(f(x) \le M\)”을 만족시키지 못한다.

\(M\)이 임의였으므로 어떤 실수도 \(f\)의 상계가 아니고, \(f\)는 위로 유계가 아니다. \(\blacksquare\)

복기. 이 답안과 문제 9의 답안이 같은 골격이다 — 임의의 \(M\)을 받고, \(\lvert M \rvert\)을 거쳐 부호를 없앤 뒤, 1을 더해 여유를 만든다. \(\lvert M \rvert\)을 쓰는 이유는 \(M\)이 음수일 때를 따로 나누지 않기 위해서다. “임의로 받은 문턱을 넘는 대상을 만든다”는 이 서식은 유계가 아님을 보이는 모든 증명에 그대로 옮겨진다.

검산. \(M = 10\)이면 \(x = 11\)이고 \(f(11) = 1331 + 11 = 1342 > 10\) ✓. \(M = -5\)이면 \(x = 6\)이고 \(f(6) = 216 + 6 = 222 > -5\) ✓.

문제 16#

접근. (a)의 요점은 원정의가 이미 \(\neg\exists\) 꼴이라는 것이다. 그 앞에 \(\neg\)를 하나 더 붙이면 N1이 작동해 NOT이 통째로 사라진다. (b)는 (a)의 결과가 \(\exists\)이므로 구성법 — 공약수 하나를 제시하면 된다. (c)는 (a)와 반대 방향으로 한 번 더 전개해 보면 답이 나온다.

풀이.

(a) 서로소의 정의는 \(\neg\exists d\,[\,d > 1 \wedge d \mid a \wedge d \mid b\,]\)이다. 따라서 “서로소가 아니다”는 \(\neg\neg\exists d\,[\dots]\)이고, [N1]에 의해

\[ \exists d\,[\,d > 1\ \wedge\ d \mid a\ \wedge\ d \mid b\,] \]

이다. 곧 “1보다 큰 공약수가 존재한다”는 긍정형 구성 게임이 된다.

(b) 증명. \(d = 13\)으로 두자 [구성]. 자격: 13은 정수 ✓. 검증 1: \(13 > 1\) ✓. 검증 2: \(91 = 13 \cdot 7\)이고 7은 정수이므로 \(13 \mid 91\) ✓. 검증 3: \(65 = 13 \cdot 5\)이고 5는 정수이므로 \(13 \mid 65\) ✓. 본체가 \(\wedge\) 두 개로 이어져 있으므로 세 조각을 모두 확인했다. 따라서 91과 65는 서로소가 아니다. \(\blacksquare\)

(c) “서로소”는 낱말이 긍정형이지만 정의는 \(\neg\exists\) 꼴이다. 이 사실이 주어졌을 때 전개하면 [N6] \(\forall d\ \neg[\,d > 1 \wedge d \mid a \wedge d \mid b\,]\)가 되고, 본체가 세 항 연언이므로 [N2 두 번] \(\forall d\,[\,d \le 1 \vee d \nmid a \vee d \nmid b\,]\)이다. 이 꼴에서 \(d \le 1 \vee X\)를 조건문 분해(\(P \Rightarrow Q \equiv \neg P \vee Q\), 1권 9주차 동치 목록)로 되읽으면 자격이 양화사 쪽으로 돌아와

\[ \forall d > 1\,[\,d \nmid a\ \vee\ d \nmid b\,] \]

가 되고, 이 자격 보존형이 주 답이다 — 곧 결론이 아니라 가정 쪽에 놓인 \(\forall\) 문장이다. 두 꼴은 같은 문장이다. 앞 꼴에 \(d \le 1\)이 나온 것은 자격을 부정한 것이 아니라 문제 진술의 정의가 \(d > 1\)을 본체의 연언으로 적어 두었기 때문이다. 본체로 옮겨 적힌 조각은 본체이므로 뒤집히고, §1.4가 금지하는 것은 양화사에 붙은 채로 있는 자격을 뒤집는 일이다 — 두 자리를 구별해야 문제 12(a)의 \(\varepsilon > 0\) 사고와 섞이지 않는다.

가정의 \(\forall\)을 쓰는 법은 특수화(S7주차)이므로, 서로소라는 사실을 쓰려면 의심 가는 공약수 후보 \(d\)를 이쪽이 지목해 투입해야 한다. 1권 21주차의 \(\sqrt2\) 증명이 정확히 그렇게 했다 — 기약분수 조건(정의 21.2, 공통 약수가 \(\pm 1\)뿐)에 \(d = 2\)를 투입해 모순을 얻었다. 무엇을 투입할지 고르는 것이 이런 증명의 기술이고, 그 기술의 체계화가 C15주차의 정수론이다.

복기. 낱말의 겉모양과 정의의 겉모양이 다를 수 있다는 것이 이 문제의 이식 가능한 부분이다. “서로소”, “무리수”, “단사”는 모두 긍정형 낱말인데 정의는 부정형이거나 \(\forall\) 꼴이다. 부정 신호를 감지할 때는 낱말이 아니라 정의를 펴 본 뒤의 모양으로 판단한다.

검산. \(91 = 7 \cdot 13\), \(65 = 5 \cdot 13\)이므로 두 수의 공약수는 1과 13(과 부호 반전)이다. \(\gcd(91, 65) = 13 \neq 1\) ✓.

문제 17#

접근. 규칙을 네 번 적용한다 — 양화사 셋과 조건문 하나다. 전개가 끝나면 \(\varepsilon\)과 \(x\)는 이쪽이 고르고 \(\delta\)는 저쪽이 주는 배치가 되어, 수렴 증명(S8주차 예제 2.2)의 배치와 정확히 뒤집힌다. \(\varepsilon\)은 \(g\)의 두 값의 차이보다 작게 잡고, \(x\)는 \(\delta\)의 식으로 만든다.

풀이. 전개. 연속의 정의는 \(\forall \varepsilon > 0\ \exists \delta > 0\ \forall x\,[\,\lvert x - a \rvert < \delta \Rightarrow \lvert f(x) - f(a) \rvert < \varepsilon\,]\)이다.

\(\leadsto\) [N5] \(\exists \varepsilon > 0\ \neg\big[\exists \delta > 0\ \forall x(\dots)\big]\)

\(\leadsto\) [N6] \(\exists \varepsilon > 0\ \forall \delta > 0\ \neg\big[\forall x(\dots)\big]\)

\(\leadsto\) [N5] \(\exists \varepsilon > 0\ \forall \delta > 0\ \exists x\ \neg\big[\lvert x - a \rvert < \delta \Rightarrow \lvert f(x) - f(a) \rvert < \varepsilon\big]\)

\(\leadsto\) [N4, 본체] \(\exists \varepsilon > 0\ \forall \delta > 0\ \exists x\,\big[\,\lvert x - a \rvert < \delta\ \wedge\ \lvert f(x) - f(a) \rvert \ge \varepsilon\,\big]\).

규칙 순서는 N5, N6, N5, N4이다. 자격 “\(\varepsilon > 0\)”과 “\(\delta > 0\)”은 보존된다.

증명. \(g(0) = 1\)이다. \(\varepsilon = \frac12\)로 두자 [구성 — 자격: \(\frac12 > 0\) ✓]. \(\delta > 0\)을 임의로 잡자 [선택]. \(x = -\dfrac{\delta}{2}\)로 두자 [구성 — \(\delta\)가 이미 확정된 뒤이므로 \(\delta\)의 식이어도 된다].

자격: \(\delta\)가 실수이므로 \(x\)도 실수 ✓.

검증 1: \(\lvert x - 0 \rvert = \left\lvert -\frac{\delta}{2} \right\rvert = \frac{\delta}{2}\)이고 \(\delta > 0\)이므로 \(\frac{\delta}{2} < \delta\)이다 ✓.

검증 2: \(\delta > 0\)이므로 \(x = -\frac{\delta}{2} < 0\)이고, 따라서 \(g(x) = 0\)이다. \(g(0) = 1\)이므로 \(\lvert g(x) - g(0) \rvert = \lvert 0 - 1 \rvert = 1 \ge \frac12 = \varepsilon\)이다 ✓.

\(\delta\)가 임의였으므로 전개문이 성립하고, \(g\)는 \(x = 0\)에서 연속이 아니다. \(\blacksquare\)

복기. 부정이 네 칸 표의 배치를 전부 뒤집는다는 것이 이 문제의 요점이다. 연속 증명에서는 \(\varepsilon\)을 받고 \(\delta\)를 만들었는데, 불연속 증명에서는 \(\varepsilon\)을 만들고 \(\delta\)를 받는다. 전개문을 정확히 적어 두면 누가 무엇을 고르는지가 자동으로 정해지므로, 답안의 문장 순서를 고민할 필요가 없어진다. 1권 47주차에서 서식으로 익힌 \(\varepsilon\)-\(\delta\)의 부정판이 여기서 유도로 회수된다.

검산. \(\delta = 0.1\)이면 \(x = -0.05\)이고 \(\lvert x \rvert = 0.05 < 0.1\) ✓, \(\lvert g(-0.05) - g(0) \rvert = 1 \ge 0.5\) ✓. \(\delta\)를 아무리 작게 잡아도 \(-\frac{\delta}{2}\)은 여전히 음수이므로 같은 논증이 그대로 돈다.

문제 18#

접근. 결함은 근거의 문제만이 아니다. 결론 “무리수이다”가 부정 신호인데 이 답안에는 전개도 처방 선택도 한 줄이 없다는 것부터 짚는다. 올바른 증명은 처방 ③(귀류)이고, 인용할 닫힘은 1권 15주차 문제 9(두 유리수의 차는 유리수)다.

풀이. 결함은 셋이다.

① “무리수처럼 보이므로”는 근거가 아니다. 허용 근거 목록(①정의 ②닫힘성\(\cdot\)기본 성질 ③등식의 성질 ④이미 증명한 명제) 어디에도 “보인다”는 항목이 없다. S1주차 문제 13에서 다룬 가짜 근거 반입과 같은 유형이다.

② 인용하려는 사실 “무리수에 유리수를 더하면 무리수이다”는 참인 정리이지만, 이 자리는 그 정리의 특수한 경우를 증명하도록 요구받은 맥락이다. 증명해야 할 것을 근거로 쓰면 아무것도 증명되지 않는다.

③ 결론이 부정 신호인데 전개가 없다. “무리수”는 정의 15.1에 의해 \(\neg\)(유리수)이므로, 답안의 첫 줄은 세 처방 중 무엇을 고르는지의 선언이어야 한다. 그 줄이 없어 답안이 어디로 가는지 정해지지 않았다.

올바른 증명. \(\sqrt2 + \frac12\)이 유리수라고 가정하자 [처방 ③ — 귀류. “무리수”의 부정은 “유리수”이고, 이것은 정의를 펼 수 있는 긍정형 진술이다]. \(\frac12\)도 유리수이므로, 두 유리수의 차는 유리수라는 사실에 의해 [1권 15주차 문제 9]

\[ \left(\sqrt2 + \frac12\right) - \frac12 = \sqrt2 \]

은 유리수다. 그런데 \(\sqrt2\)는 무리수이다 [1권 21주차]. 한 실수가 유리수이면서 무리수일 수는 없으므로 모순이다. 따라서 가정이 틀렸고, \(\sqrt2 + \frac12\)은 무리수이다. \(\blacksquare\)

복기. 무리수, \(\notin\), \(\neq\)처럼 정의가 부정형인 결론에서는 처방 ③이 표준이다. 이유는 기계로 설명된다 — \(\neg B\)를 가정으로 받는 순간 N1이 작동해 NOT이 벗겨지고, 정의를 펼 수 있는 긍정문이 손에 들어오기 때문이다. 이 관찰이 S11주차의 중심 주제다.

문제 19#

접근. 가정과 결론이 둘 다 부정 신호다. 대우를 잡으면 두 NOT이 동시에 벗겨져 양쪽이 모두 긍정형이 된다 — 처방 ②가 이 자리의 정확한 수다. 귀류 쪽은 조건문의 부정이므로 N4가 먼저 작동하고, 무엇과 무엇이 \(\wedge\)로 손에 들어오는지 먼저 적어야 한다.

풀이.

대우 공략. 원명제는 “\(x\)가 무리수이면 \(-x\)도 무리수이다”이다. 대우는 “\(-x\)가 유리수이면 \(x\)는 유리수이다”이다 — 양쪽의 NOT이 동시에 벗겨졌다.

증명. 실수 \(x\)를 임의로 잡고, \(-x\)가 유리수라 하자 [전진면]. 정의 15.1에 의해 \(-x = \frac ab\)인 정수 \(a, b\) (\(b \neq 0\))가 존재한다. 양변에 \(-1\)을 곱하면

\[ x = -\frac ab = \frac{-a}{b} \]

이고, \(-a\)는 정수이며 \(b\)는 0이 아닌 정수이므로 \(x\)는 유리수의 정의를 만족한다 [후진면]. 따라서 \(x\)는 유리수이다. 대우가 원명제와 동치이므로 [1권 9주차\(\cdot\)19주차] 원명제가 성립한다. \(\blacksquare\)

귀류 공략. 원명제의 부정을 먼저 전개한다. 조건문의 부정이므로 [N4] “\(x\)는 무리수이고 \(-x\)는 무리수가 아니다”, 곧 “\(x\)는 무리수이고 \(-x\)는 유리수이다”이다. 이것을 가정하자 [처방 ③]. \(-x\)가 유리수이므로 \(-x = \frac ab\)인 정수 \(a, b\) (\(b \neq 0\))가 존재하고, \(x = \frac{-a}{b}\)이므로 \(x\)도 유리수다. 그런데 가정의 다른 조각은 \(x\)가 무리수라고 한다 — 모순이다. 따라서 원명제가 성립한다. \(\blacksquare\)

평가. 길이는 비슷하다. 차이는 설계 부담에 있다. 대우판은 가정도 결론도 유리수여서 처음부터 끝까지 긍정형 게임이고, 전진면과 후진면이 곧바로 맞물린다. 귀류판은 시작 전에 N4 전개를 정확히 해야 하고, 게다가 과녁이 “아무 모순”이라 어디로 갈지가 답안을 쓰는 동안 정해지지 않는다. NOT이 가정과 결론에 모두 낀 조건문은 대우로 뒤집으면 NOT이 양쪽에서 동시에 사라지는 경우가 많으므로, 그런 꼴에서는 처방 ②가 먼저 후보다. 이 감각의 체계화가 S12주차다.

검산. \(x = \sqrt2\)이면 \(-x = -\sqrt2\)이고, \(-\sqrt2\)가 유리수라면 위 계산으로 \(\sqrt2\)도 유리수가 되어 1권 21주차와 충돌한다 — 명제가 실제로 작동한다.

문제 20#

접근. (a)는 예제 2.1의 세 걸음을 “같은 정보인데 NOT의 위치가 다르다”는 대비로 다시 쓰는 문항이다. (b)는 셋의 부정 대상이 서로 다르다는 것부터 확인한 뒤, 그런데도 전개가 끝난 자리에서 무엇이 같아지는지를 말하면 된다 — §2의 관찰 표가 그 준비였다.

풀이. (예시 답안)

(a) “증가함수가 아니다”라는 표면의 NOT 앞에서는 네 칸 표를 펼 겉모양이 보이지 않아 어떤 기법도 발동하지 않는다. 기계를 돌려 NOT을 \(\forall\) 두 겹 안으로, 다시 조건문 안으로 밀어 넣으면 마지막에 남는 것은 \(\neg(<)\)가 \(\ge\)로 바뀐 본체 하나뿐인데, 그것은 부정이 아니라 그냥 다른 부등식이다. 정보는 처음과 끝이 같고 달라진 것은 NOT의 위치뿐인데, 표면에 있으면 손잡이가 없고 본체에 있으면 평범한 구성 문제가 된다 — 그래서 부정은 내용이 아니라 위치의 문제다.

(b) 반례 제작과 “단사가 아님”은 \(\neg\forall[\dots \Rightarrow \dots]\) 꼴이므로 N5\(\cdot\)N4를 거쳐 \(\exists[\dots \wedge \dots]\)가 되어 전개 후의 겉모양이 서로 같지만, 만능 증인 격파는 \(\neg\exists\forall\)이라 \(\forall\exists\)가 되어 바깥에 선택이 한 겹 더 붙는다(S8주차 예제 2.1(b)의 반증이 귀류와 특수화로 그 겹을 처리한 자리다). 셋의 공통점은 겉모양이 아니라 마무리다 — 전개가 끝나면 **가장 안쪽이 결론의 \(\exists\)**가 되고, 그래서 셋 다 증인 제시와 검증으로 닫힌다.

복기. (b)에서 확인한 통합이 이번 주가 남기는 가장 이식 가능한 것이다. 앞으로 부정형 결론을 만나면 기법 이름을 떠올리기 전에 전개부터 하고, 전개문의 겉모양이 무엇을 지정하는지 본다. 기법은 그다음에 정해진다.

다음 주 예고 (S11주차): 부정 3부작의 둘째 — 귀류법을 Solow의 시선으로 다시 본다. 1권 21\(\cdot\)22주차에서 익힌 귀류를 “무엇을 얻고 무엇을 잃는 거래인가”로 재정의한다: \(\neg B\)라는 사실을 가정 자리에 하나 더 받는 대신 과녁이 “아무 모순”으로 흐려지는 거래, 그래서 후진 과정이 사라지고 전진만 남는 기법이라는 것, 이 거래가 이득인 조건 (결론이 부정형이거나 “없다”이거나 “무한하다”일 때), 그리고 이번 주의 기계가 \(\neg B\)를 정확히 만드는 필수 부품이라는 것을 확인한다. 1일차에 원서 9장을 통독하고 온다.