S19주차 · 강의 — 예제 · 연습 · 해설#
예제 — 만드는 일을 함께 해 보기#
완성된 결과를 먼저 보이지 않는다. 예제 2.1은 설계부터 한 줄씩 함께 만들고, 예제 2.2는 설계만 함께 하고, 예제 2.3은 설계부터 스스로 한 뒤 표 없이 산문으로 적는다. 지지대가 예제마다 하나씩 빠진다.
예제 2.1 — 정의 짓기: 삼각수#
과제. “정수 \(n\)이 삼각수(triangular)”를 정의하고 좋은 정의의 조건을 점검하라.
설계 — 쓰기 전에 정하는 두 가지. 증명을 쓸 때와 순서가 같다. 손에 든 것(출발점)과 만들어야 할 것(도착점)을 먼저 적는다.
말 |
제작 번역 |
|
|---|---|---|
출발점 (쓸 수 있는 것) |
이미 정의된 용어들 |
정수, 곱, 나눗셈, 존재한다 — 전부 삼각수보다 아래층 |
도착점 (만들 것) |
삼각수의 정의 |
“\(n\)이 삼각수 \(\iff\) \(\underline{\quad(?)\quad}\)” 꼴의 한 문장과, 네 조건의 점검 |
확인 14. 도착점 칸의 빈칸을 채우려면 먼저 무엇을 해야 하는가. \(1, 3, 6, 10, 15\)를 늘어놓고 각각을 하나의 식으로 적어 보자.
답
먼저 사례를 늘어놓고 공통의 꼴을 찾아야 한다.
\(1 = \frac{1 \cdot 2}2\), \(3 = \frac{2 \cdot 3}2\), \(6 = \frac{3 \cdot 4}2\),
\(10 = \frac{4 \cdot 5}2\), \(15 = \frac{5 \cdot 6}2\).
공통의 꼴은 \(\frac{k(k+1)}2\)이고, 위 다섯 줄에서 \(k\)는 각각
\(1, 2, 3, 4, 5\)다. 1권 1주차 §1.2에서 짝수를 \(2 \times (\text{무엇})\) 꼴로
적어 본 것과 같은 걸음이다 — 정의는 사례에서 꼴을 뽑아 굳힌 것이다.
1단계 — 조건을 iff 문장으로 적는다. 뽑아낸 꼴을 정의의 형식에 넣는다. 이때 \(k\)의 자격을 반드시 붙인다 — 1권 1주차 §1.3의 조각 삭제 실험이 보인 대로, 자격이 빠지면 정의가 무너진다.
확인 15. 정의 문장을 완성해 보자: “양의 정수 \(n\)이 삼각수라 함은, \(n = \underline{\quad}\)인 \(\underline{\quad}\) \(k\)가 존재하는 것이다.”
답
“양의 정수 \(n\)이 삼각수라 함은, \(n = \frac{k(k+1)}2\)인 양의 정수 \(k\)가
존재하는 것이다.”
자격을 “정수”까지 넓혀도 정의되는 것은 전혀 달라지지 않는다. 무대가 양의
정수로 고정돼 있으므로 \(n = 0\)을 주는 \(k = 0\)과 \(k = -1\)은 애초에 판정 대상이
아니고, \(k \le -2\)인 정수 \(k\)에는 \(k' = -k-1 \ge 1\)을 대응시키면
\(\frac{k'(k'+1)}2 = \frac{k(k+1)}2\)이므로 같은 \(n\)이 나온다. 곧 삼각수인 양의
정수의 모임은 그대로다. 실제로 무너지는 것은 자격을 아예 빼는 쪽이다 —
\(k\)를 실수로 잡으면 \(k = \frac{-1 + \sqrt{1 + 8n}}2\)이 늘 존재하므로 임의의 양의
정수 \(n\)이 삼각수가 된다. 이것이 §1.4 조건 삭제 실험 표의 ④ 비자명 붕괴다.
따라서 자격을 좁히는 실질적 이유는 정수성이지 양수성이 아니다.
2단계 — 조건 ① 명확성을 점검한다. 조건 안에 판정할 수 없는 낱말이 있는지 읽는다.
확인 16. 조건 “\(n = \frac{k(k+1)}2\)인 양의 정수 \(k\)가 존재한다”에 애매한 낱말이 있는가. 그리고 이 조건은 어떤 양화사 꼴인가.
답
없다. “양의 정수”, “\(=\)”, “존재한다”는 모두 아래층에서 판정이 정해진 낱말이다.
이름도 조건과 어긋나지 않는다 — \(\frac{k(k+1)}2\)은 점을 삼각형 꼴로 \(k\)줄까지
쌓았을 때의 개수이므로 “삼각수”라는 이름이 조건이 가리키는 것과 맞는다.
양화사 꼴은 \(\exists\)이므로, 이 정의의 후진면(S4주차 §1.4)은 구성법이 된다 —
삼각수임을 보이려면 \(k\)를 하나 제시하면 끝난다. 조건 ①의 점검은 이렇게
양화사 구조를 드러내는 일까지 포함한다.
3단계 — 조건 ② 무순환을 점검한다. 조건에 쓰인 용어를 나열하고 각각이 피정의어보다 아래층인지 확인한다.
확인 17. 조건에 쓰인 용어를 전부 나열하고, 그중 “삼각수”를 직접 또는 간접으로 쓰는 것이 있는지 확인해 보자.
답
용어는 “양의 정수”, “곱”, “합”, “나누기 2”, “등호”, “존재한다”의 여섯이다.
어느 것도 삼각수를 쓰지 않고, 어느 것도 삼각수를 쓰는 용어를 쓰지 않는다.
간접 순환까지 보려면 한 단계 더 내려가면 되는데, 여섯 용어는 전부 산술과
논리의 층에서 이미 확정되어 있으므로 더 내려갈 것이 없다. 무순환 통과다.
4단계 — 조건 ③ well-defined를 점검한다. 정의 19.3의 서식을 걸기 전에, 이 정의가 값을 주는지 성질을 주는지부터 가른다.
확인 18. 이 정의에 well-defined 검사 서식을 실제로 걸어야 하는가.
답
걸 필요가 없다. 이 정의가 \(n\)에 주는 것은 “삼각수인가 아닌가”라는 참\(\cdot\)거짓이지
값이 아니다. 대표원을 골라 값을 계산하는 자리가 없으므로 표현 선택이 개입할
자리도 없다 — \(6\)을 어떻게 적든 삼각수인지 아닌지는 그대로다.
확인 9에서 정리한 갈림이 여기 적용된다 — **성질을 정하는 정의는 자동 통과,
대표원을 골라 값이나 연산을 계산하는 정의는 검사 필수.** 다만 답안에는 “성질 정의이므로 자동
통과”라는 한 줄을 적는다. 점검하지 않은 것과 점검해서 통과한 것은 다르다.
5단계 — 조건 ④ 비공허\(\cdot\)비자명을 점검한다. 대상 하나와 비대상 하나를 실제로 만들어 낸다.
확인 19. 비공허의 근거로 삼각수 하나를, 비자명의 근거로 삼각수가 아닌 양의 정수 하나를 제시하고 각각 검증해 보자.
답
비공허: \(6\)은 삼각수다 — \(k = 3\)에서 \(\frac{3 \cdot 4}2 = 6\)이고 \(3\)은 양의
정수다. 비자명: \(5\)는 삼각수가 아니다 — \(k = 1, 2, 3\)에서 값이 각각
\(1, 3, 6\)이고 \(k \ge 3\)이면 \(\frac{k(k+1)}2 \ge 6 > 5\)이므로 남은 후보가 없다.
비자명 쪽에는 “후보를 다 훑었다”는 한 줄이 필요하다. 그 줄이 없으면 “아직 못
찾았다”와 “없다”가 구별되지 않는다.
완성본. 다섯 걸음을 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 “왜”에 스스로 답해 본다.
증명의 한 줄 |
왜 이 줄을 쓰는가? |
|---|---|
정의. 양의 정수 \(n\)이 삼각수라 함은, \(n = \frac{k(k+1)}2\)인 양의 정수 \(k\)가 존재하는 것이다. |
사례에서 뽑은 꼴을 iff 형식으로 굳힌다. \(k\)의 자격을 붙이는 것이 조각 삭제 실험을 견디는 조건이다 |
① 명확성. 조건 “\(\exists k\)(양의 정수): \(n = \frac{k(k+1)}2\)”에 애매어가 없고, 이름도 조건과 어긋나지 않으며, 양화사는 \(\exists\)이다. |
조건이 판정 가능하고 이름이 조건과 맞음을 보이고, 동시에 이 정의의 후진면이 구성법임을 드러낸다 |
② 무순환. 조건이 쓰는 용어는 양의 정수\(\cdot\)곱\(\cdot\)합\(\cdot\)나누기 2\(\cdot\)등호\(\cdot\)존재뿐이고, 어느 것도 삼각수를 쓰지 않는다. |
정의 19.1의 층위를 지켰음을 보인다. 용어 목록을 실제로 나열하는 것이 점검이다 |
③ well-defined. 이 정의는 값이 아니라 성질을 주고 대표원을 골라 계산하는 자리가 없으므로 자동 통과한다. |
점검했음을 남긴다. 성질 정의와 연산 정의의 갈림이 여기서 갈린다 |
④ 비공허\(\cdot\)비자명. \(6 = \frac{3 \cdot 4}2\)이므로 비공허, \(5\)는 \(k \le 2\)에서 미달하고 \(k \ge 3\)에서 초과하므로 비자명이다. |
이름이 무언가를 가리키고 또 무언가를 배제함을 실물로 보인다 |
검산. \(k = 1\)부터 \(6\)까지 넣으면 \(1, 3, 6, 10, 15, 21\)이 나오고, 이웃한 두 값의 차가 \(2, 3, 4, 5, 6\)으로 하나씩 커진다. 정의가 뽑아낸 꼴이 사례의 규칙과 일치한다.
예제 2.2 — well-defined 검증: 연산 정의의 함정#
과제. 유리수에 연산 \(\oplus\)를 \(\frac ab \oplus \frac cd = \frac{a + c}{b + d}\)로 정의하려 한다. well-defined인가?
이번에는 설계만 함께 하고, 본문은 완성본으로 본다.
확인 20. 정의 19.3의 검사 서식 세 걸음에 무엇을 넣을지 설계표를 채워 보자. ① 잡을 두 표현: \(\underline{\quad}\) / ② 같음의 등식: \(\underline{\quad}\) / ③ 비교할 두 값: \(\underline{\quad}\)
답
① 한 입력만 표현을 바꾸면 충분하다. 첫 입력을 \(\frac12\)과 \(\frac24\)로 잡고
둘째 입력은 \(\frac13\)으로 고정한다.
② \(1 \cdot 4 = 2 \cdot 2\)이므로 \(\frac12 = \frac24\)이다.
③ \(\frac12 \oplus \frac13\)과 \(\frac24 \oplus \frac13\)을 각각 계산해 비교한다.
입력이 둘인 연산에서 **한쪽만 바꾸는 것으로 충분한 것은 ill-defined를 주장할
때뿐이다** — 값이 갈리는 쌍 하나면 불통과가 확정되기 때문이다. 반대로
well-defined를 주장하려면 두 입력 모두에서 표현 무관을 보여야 한다(훈련 1과
문제 8이 그 자리다).
확인 21. 두 값을 계산하기 전에, 두 값이 같은지 다른지를 무엇으로 판정할 것인지 미리 정해 보자.
답
교차곱이다. \(\frac pq = \frac rs\)의 판정은 \(ps = qr\)이고, 이것이 정의 19.3
번역표의 첫째 줄이다. 소수로 바꿔 어림하지 않는다 — 어림은 근거 목록에 없다.
검증. \(\frac12 = \frac24\)이다 (\(1 \cdot 4 = 4 = 2 \cdot 2\)). 두 표현을 각각 넣으면
이고, 교차곱으로 비교하면 \(2 \cdot 7 = 14\)이고 \(5 \cdot 3 = 15\)이므로 \(\frac25 \neq \frac37\)이다. 같은 입력에 다른 출력이 나왔으므로 \(\oplus\)는 ill-defined이고, 이 문장은 유리수 위의 연산의 정의로 성립하지 않는다. \(\blacksquare\)
어디서 어긋났는가. \(\oplus\)의 계산은 분자와 분모를 각각 더한다 — 곧 유리수 자체가 아니라 그 유리수를 적은 분수 표현을 조작한다. 표현을 조작하는 규칙은 표현을 바꾸면 결과가 흔들리므로 값의 연산이 될 수 없다. 이 규칙이 아무 쓸모가 없다는 뜻은 아니다. 분수 쌍에 붙는 연산으로 보면 통계와 수열에서 의미를 갖는다. 어긋난 것은 규칙 자체가 아니라 그 규칙을 유리수 위의 연산으로 선언한 것이다.
예제 2.3 — 공리계 세우기: 순서 공리계#
과제. 작은 공리계를 세우고 세 덕목을 점검하라.
순서 공리계
무정의 용어: 집합 \(S\)와 \(S\) 위의 관계 \(\prec\).
공리 A1 (비반사): 모든 \(x\)에 대해 \(x \not\prec x\)이다.
공리 A2 (추이): \(x \prec y\)이고 \(y \prec z\)이면 \(x \prec z\)이다.
공리 A3 (삼분): 임의의 \(x, y\)에 대해 \(x \prec y\), \(x = y\), \(y \prec x\) 중 정확히 하나가 성립한다.
이번에는 설계부터 스스로 해 보자. 정의 19.4의 검사법 두 줄 — 무모순성은 모형 하나, 독립성은 공리마다 반례 모형 하나 — 을 노트에서 먼저 실행한 뒤 아래를 읽고 대조한다.
점검. 무모순성부터 본다. \(S = \mathbb{R}\)로 두고 \(\prec\)을 \(<\)로 읽으면, A1은 “\(x < x\)가 거짓”이므로 참이고, A2는 실수 부등호의 추이성이므로 참이고, A3은 임의의 두 실수가 크거나 같거나 작음 중 정확히 하나를 만족하므로 참이다. 세 공리를 전부 만족하는 대상이 존재하므로 이 공리계는 무모순이다.
다음은 A3의 독립성이다. \(S = \{a, b\}\)로 두고 \(\prec\)을 어떤 쌍에도 성립하지 않는 관계로 두면, A1은 어느 \(x\)에 대해서도 \(x \prec x\)가 성립하지 않으므로 참이고, A2는 전건을 만족하는 \(x, y, z\)가 없으므로 공허 참이며, A3은 \(a\)와 \(b\)에 대해 세 경우가 모두 거짓이므로 위배된다. A3만 거짓이고 나머지가 참인 모형이 존재하므로 A3은 A1과 A2에서 유도되지 않는다. 곧 A3은 독립이다.
다음은 A2의 독립성이다. \(S = \{a, b, c\}\)로 두고 \(\prec\)을 \(a \prec b\), \(b \prec c\), \(c \prec a\)의 세 쌍에서만 성립하는 관계로 두자. A1은 어느 \(x\)에 대해서도 \(x \prec x\)가 목록에 없으므로 참이고, A3은 세 쌍 \(\{a,b\}\), \(\{b,c\}\), \(\{c,a\}\) 각각에서 한 방향만 성립하고 서로 다른 두 원소이므로 “정확히 하나”가 지켜지며 \(x = y\)인 경우에도 \(x \prec x\)가 없으므로 지켜진다. 그러나 \(a \prec b\)이고 \(b \prec c\)인데 \(a \prec c\)는 성립하지 않으므로 A2는 위배된다. A2만 거짓이고 나머지가 참인 모형이 존재하므로 A2도 독립이다.
남은 것은 A1의 독립성인데, 여기서는 반례 모형을 만들 수 없다. A3에 \(y = x\)를 넣으면 “\(x \prec x\), \(x = x\), \(x \prec x\) 중 정확히 하나가 성립한다”가 되고, \(x = x\)가 참이므로 나머지는 거짓이어야 하며 곧 \(x \not\prec x\)다. 이것이 A1이므로 A1은 A3에서 유도된다. A3이 참이면서 A1이 거짓인 모형은 존재할 수 없으므로, 이 공리계는 정의 19.4의 ② 독립성을 만족하지 않는다.
곧 이 공리계는 무모순이지만 최소가 아니다. 고치는 방법은 둘이다 — ㄱ. A1을 공리 목록에서 내려 A3의 정리로 둔다. ㄴ. A3을 “\(x \prec y\), \(x = y\), \(y \prec x\) 중 둘 이상은 성립하지 않는다”로 약화해 A1이 유도되지 않게 한 뒤 A1을 공리로 남긴다. 어느 쪽이든 목록에 남는 것은 서로에게서 유도되지 않는 것뿐이다. §1.5의 덕목 삭제 실험이 말한 일이 여기서 실물로 나온다 — 유도되는 것을 목록에 남겨 두면 읽는 사람은 그것을 별도의 요구로 읽는다.
완전성은 요구하지 않는다. 이 공리계는 실수의 순서 말고도 자연수의 순서, 유한 집합의 순서 등 서로 다른 모형을 여럿 갖고, 그 모형들에서 참\(\cdot\)거짓이 갈리는 명제가 있기 때문이다. 예를 들어 “가장 작은 원소가 존재한다”는 자연수 모형에서는 참이고 실수 모형에서는 거짓이므로, 공리들만으로는 증명도 반증도 되지 않는다. \(\blacksquare\)
같은 방법이 어디에서 쓰였는가. A3의 독립성을 보인 논법이 그대로 유클리드 기하의 평행선 공리에 걸린다 — 나머지 공리는 지키면서 평행선 공리만 다르게 놓은 모형(구면 기하와 쌍곡 기하)이 존재하므로 평행선 공리는 독립이다. 독립인 공리를 다르게 놓으면 각각 완결된 새 이론이 나온다. 문제 13이 그것이다.
관찰 — 같은 뼈대#
세 예제는 소재가 다르지만 걸음의 배치가 같다. 대응표의 빈칸을 채워 보자.
항목 |
예제 2.1 |
예제 2.2 |
예제 2.3 |
|---|---|---|---|
만든 것 |
정의 하나 |
판정 하나 |
\(\underline{\quad(1)\quad}\) |
적용한 검사 목록 |
정의 19.2의 네 조건 |
정의 19.3의 검사 서식 |
\(\underline{\quad(2)\quad}\) |
검사의 재료 |
예 하나와 비예 하나 |
같은 대상의 두 표현 |
\(\underline{\quad(3)\quad}\) |
결과 |
네 조건 통과 — 정의로 성립 |
값이 갈림 — 정의로 불성립 |
무모순이고 A2\(\cdot\)A3은 독립이나 A1이 A3에서 유도되어 최소가 아니다 |
빠뜨리면 무엇이 무너지는가 |
비자명 붕괴 (모든 수가 이름을 받는다) |
\(\underline{\quad(4)\quad}\) |
모순된 공리계 (모든 명제가 증명된다) |
확인 22. 빈칸 (1)~(4)를 채우고, 세 예제가 공통으로 지킨 순서를 네 걸음으로 적어 보자.
답
(1) 공리계 하나.
(2) 정의 19.4의 세 덕목.
(3) 모형 — 무모순성에는 전부 만족하는 모형 하나, 독립성에는 그 공리만 어기는
모형 하나.
(4) \(\frac25 = \frac37\), 곧 \(14 = 15\)가 유도되어 산술 전체가 무너진다(무게 \(w\)의
\(3 = 6\)과 같은 꼴이다).
공통 순서: ① 만들 것이 정의인지 공리계인지 정하고 무정의 용어를 명시한다 \(\to\)
② 해당하는 검사 목록을 고른다(정의면 19.2의 네 조건, 공리계면 19.4의 세
덕목) \(\to\) ③ 목록의 항목마다 재료를 실제로 만들어 낸다(예\(\cdot\)비예 또는 두 표현
또는 모형) \(\to\) ④ 통과\(\cdot\)불통과를 항목별로 선언한다.
방금 확인한 순서에 제출 형식의 이름을 붙인다.
백지 암기 대상
제작 보고의 서식
① 무정의 용어와 만들 것의 종류 — 정의인가 공리계인가
② 본문 — 정의 한 문장 또는 공리 목록
③ 검사 — 정의면 네 조건을 순서대로, 공리계면 무모순성 모형과 공리별 독립성 모형
④ 통과\(\cdot\)불통과의 선언 — 불통과면 어느 항목에서 무엇이 갈렸는지까지
네 줄 중 어느 하나라도 빠지면 보고가 아니라 선언이다. 특히 ③이 없으면 읽는 사람은 그 정의를 검사된 것으로 읽는다.
빈칸 사다리 — 지지대를 하나씩 빼며#
필사에서 자립으로 넘어가는 다리다. 베끼지 말고 빈칸만 스스로 채운다. 답은 §6에 있다. 훈련이 진행될수록 빈칸이 커진다.
훈련 1 ●○○ — 수식과 절차의 빈칸#
과제. 연산 \(\frac ab \odot \frac cd = \frac{ac}{bd}\)(분수 곱셈)이 well-defined인지 검증한다.
걸음 ①. 첫 입력의 두 표현을 \(\frac ab\)와 \(\frac{a'}{b'}\)로 잡고 둘째 입력 \(\frac cd\)는 고정한다.
걸음 ②. \(\frac ab = \frac{a'}{b'}\)를 등식으로 옮기면 교차곱 \(\underline{\quad(1)\quad}\)이다.
걸음 ③. 비교할 두 값은 \(\frac{ac}{bd}\)와 \(\frac{a'c}{b'd}\)이고, 두 값이 같은지는 교차곱으로 판정한다. 좌변의 교차곱을 계산하면
이고, 가운데 등식에서 걸음 ②의 등식을 대입했다. 따라서 \(\frac{ac}{bd} = \frac{a'c}{b'd}\)이다. 둘째 입력에 대해서도 같은 계산이 문자만 바꿔 반복되므로 두 입력 모두에서 표현 무관이고, 그러므로 분수 곱셈은 well-defined \(\underline{\quad(3)\quad}\)이다.
결론. 예제 2.2의 \(\oplus\)와 달리 표현을 바꿔도 값이 변하지 않았다. 연산을 정하는 정의는 성질을 정하는 정의와 달리 well-def를 \(\underline{\quad(4)\quad}\) 검증해야 한다.
훈련 2 ●●○ — 수식과 근거를 함께#
이번에는 검사 항목의 이름과 근거 문장도 빈칸이다.
과제. “정수 \(n\)이 사각수(square number)”를 정의하고 네 조건을 점검한다.
정의. 음이 아닌 정수 \(n\)이 사각수라 함은, \(n = \underline{\quad(1)\quad}\)인 정수 \(k\)가 존재하는 것이다.
점검 ①. 조건에 애매어가 없고 이름도 조건과 어긋나지 않으며, 양화사는 \(\underline{\quad(2)\quad}\)이다. 따라서 이 정의의 후진면은 \(\underline{\quad(3)\quad}\)법이다.
점검 ②. 조건이 쓰는 용어는 정수\(\cdot\)곱\(\cdot\)등호\(\cdot\)존재뿐이고, 어느 것도 사각수를 쓰지 않는다 — 근거는 \(\underline{\quad(4)\quad}\)이다.
점검 ③. 이 정의는 값이 아니라 \(\underline{\quad(5)\quad}\)을 주므로 검사가 자동 통과한다.
점검 ④. 비공허의 증거는 \(9 = 3^2\)이고, 비자명의 증거는 \(\underline{\quad(6)\quad}\)이다.
되돌아보기. 만약 \(k\)의 자격 “정수”를 지우면 임의의 음이 아닌 실수 \(n\)이 \(k = \sqrt n\)으로 조건을 만족하므로 \(\underline{\quad(7)\quad}\) 조건이 무너진다.
훈련 3 ●●● — 뼈대만 남기고#
이번에는 공리계를 세우는 것부터 시작한다. 무정의 용어는 집합 \(S\)와 \(S\) 위의 관계 \(\sim\)이고, 공리는 둘뿐이다.
두 공리
A1 (반사): 모든 \(x \in S\)에 대해 \(x \sim x\)이다.
A2 (대칭): \(x \sim y\)이면 \(y \sim x\)이다.
과제. 아래 네 칸을 통째로 채운다.
① 무모순성 모형과 그 검증: \(\underline{\quad(1)\quad}\)
② A2의 독립성 모형과 그 검증: \(\underline{\quad(2)\quad}\)
③ “\(x \sim y\)이고 \(y \sim z\)이면 \(x \sim z\)”(추이)가 A1과 A2에서 유도되는가. 모형으로 답하시오: \(\underline{\quad(3)\quad}\)
④ ③에서 한 판정이 1권 36주차의 어느 물음과 같은 종류인가: \(\underline{\quad(4)\quad}\)
(이 훈련이 문제 10의 예행연습이다.)
연습문제 (20문항)#
해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 접근까지만 읽고 다시 시도한다.
이번 주의 채점 기준
답이 아니라 근거가 점수다. 이번 주의 제출 규격은 §2 끝의 제작 보고 서식 네 줄이다: ① 무정의 용어와 만들 것의 종류 ② 본문(정의 한 문장 또는 공리 목록) ③ 검사 — 정의 문제는 네 조건을 순서대로 적고 well-def는 검사 서식 세 줄을 실제로 적는다, 공리계 문제는 무모순성 모형과 공리별 독립성 모형을 각각 제시한다 ④ 통과\(\cdot\)불통과의 선언. “정의는 맞다”만 적은 답안은 ③이 없으므로 0점이고, ill-defined를 주장하면서 갈리는 표현 한 쌍을 제시하지 않은 답안도 0점이다. 힌트 상자는 5분 이상 막힌 뒤에만 연다.
기본 ●○○#
1. [백지] 이론의 4층위, 좋은 정의의 4조건, 공리계의 3덕목, well-def의 뜻을 쓰시오.
힌트
정의 19.1, 19.2, 19.4와 정의 19.3의 검사 서식이 그대로 답이다. 통째로 옮기기보다 각
항목이 무엇을 막아 주는지 한 줄씩 덧붙이며 적는 쪽이 재현률이 높다 — 층위는
무한 후퇴를, 네 조건은 정의로 성립하지 않는 문장을, 세 덕목은 모순된 출발
명제를 막는다.
2. 다음 “정의”의 결함을 지목하시오 (어느 조건 위반인지). (a) “\(n\)이 작은 수라 함은 \(n < 100\)인 것이다.” (b) “짝수: 홀수가 아닌 정수 / 홀수: 짝수가 아닌 정수.” (c) “\(x\)가 흥미로운 실수라 함은 흥미로운 성질을 갖는 것이다.” (d) “\(x\)가 초록수라 함은 \(x \neq x\)인 것이다.”
힌트
네 조건을 순서대로 걸어 보는 것이 방법이다. (a)는 조건 자체는 판정되므로
무엇이 어긋났는지 한 번 더 생각한다. (b)와 (c)는 조건을 아래층까지 풀어 보면
갈린다. (d)는 조건을 만족하는 대상을 하나라도 만들어 보면 드러난다.
3. 예제 2.2를 백지에서 재현하시오 — \(\frac12 = \frac24\) 반례로 ill-defined임을 보이는 부분까지.
힌트
재현의 뼈대는 검사 서식 세 줄이다: 두 표현 잡기 / 같음의 등식(교차곱) /
두 값 계산과 비교. 마지막 비교를 소수 어림으로 하면 근거 목록 밖이다 —
교차곱으로 적는다.
4. §3의 빈칸 사다리 훈련 1~3을 백지에서 완성하시오.
힌트
훈련 3이 막히면 예제 2.3의 A3 독립성 논증을 먼저 다시 본다. 관계를 하나도
두지 않는 모형과 관계를 전부 두는 모형, 이 둘이 독립성 검사에서 가장 먼저
시도할 후보다.
5. 예제 2.1을 백지에서 재현하시오 — 네 조건 점검까지.
힌트
정의 문장 한 줄만 적고 끝내면 재현의 절반이다. 네 조건 각각에 한 줄씩,
특히 ④에는 예 하나와 비예 하나를 실제 수로 적는다. 비예 쪽에는 “후보를 다
훑었다”는 줄이 필요하다.
6. “무정의 용어가 왜 필요한가”를 “모든 것을 정의하려는” 시도의 무한 후퇴와 순환으로 설명하시오 (두 문장).
힌트
§1.3의 층 삭제 실험 (가)가 그대로 답이다. 두 갈래로 갈라 적는다 — 낱말이
무한히 필요해지는 쪽과, 유한하면 앞의 낱말이 다시 나오는 쪽.
표준 ●●○#
7. “완전수”(진약수의 합이 자신과 같은 수 — S4주차 예제 2.3)를 정의로 다시 쓰고 네 조건을 점검하시오 — 특히 비공허(\(6\), \(28\))와 비자명(\(12\)).
8. 연산 \(\frac ab \boxplus \frac cd = \frac{ad + bc}{bd}\)(분수 덧셈)이 well-defined임을 검증하시오 — \(\frac ab = \frac{a'}{b'}\)를 대입해 훈련 1의 곱셈판과 같은 계산을 수행하시오.
표기 — 잉여류 \([a]\)
정수 \(a\)가 법 \(n\)에 대해 결정하는 잉여류를 \([a]\)로 적고 “대괄호 에이”로 읽는다. \([a] = [a']\)은 “\(a \equiv a' \pmod n\)”, 곧 “\(n \mid (a - a')\)”과 완전히 같은 말이다(1권 20주차 정의 20.1). 하나의 잉여류는 표현이 무한히 많다 — 법 \(2\)에서 \([0] = [2] = [4] = [-2]\)이다. 표현이 여럿이므로 잉여류 위에 연산을 정의할 때마다 well-defined 검사가 요구된다. 정식 정의와 \(\mathbb{Z}_n\)의 구조는 C11주차(Chartrand 9장)에서 다룬다. 아래 문제 9\(\cdot\)11\(\cdot\)17에서는 위 두 줄만 알면 된다.
9. 다음 연산이 ill-defined임을 반례로 보이시오: 정수를 \(\mathbb{Z}_2\)의 원소로 볼 때 \([a] \star [b] = [a^b]\) (거듭제곱). 이어서 지수 자리가 밑 자리와 다르게 처리되는 이유를 한 문장으로 적으시오.
힌트
밑을 고정하고 지수 쪽 표현만 바꾸는 것이 가장 짧다. 법 \(2\)에서 \([0] = [2]\)이므로,
어떤 밑 \([a]\)에 대해 \(a^0\)과 \(a^2\)을 비교하면 된다. 밑을 \(2\)로 잡으면 두 값이
\(1\)과 \(4\)이고, 이 둘이 법 \(2\)에서 같은 잉여류인지 확인한다.
10. 공리계 점검: “동치관계” 공리(반사\(\cdot\)대칭\(\cdot\)추이 — 1권 36주차)에 대해 (a) 무모순성 모형을 제시하시오 (예: “\(=\)” 또는 “\(\equiv \pmod 3\)”). (b) 대칭 공리의 독립성을 보이시오 (반사와 추이는 만족하나 대칭은 아닌 관계 — 예: “\(\le\)”).
11. “\(\mathbb{Z}_3\)에서 \([a] + [b] = [a+b]\)”가 well-defined임을 검증하시오 — \([a] = [a']\), \([b] = [b']\)이면 \([a+b] = [a'+b']\)임을 \(3 \mid (a - a')\)과 \(3 \mid (b - b')\)에서 유도하시오.
12. 다음 답안을 진단하시오.
“정의: 실수 \(x\)의 ‘반쪽’ \(h(x)\)를, \(x = \frac pq\)인 유리수이면 \(\frac p{2q}\)로, 무리수이면 \(\frac x2\)로 정의한다.”
유리수 쪽이 well-defined인지 검사 서식으로 확인하고, 두 경우가 무대를 빠짐없이 그리고 겹침 없이 덮는지도 판정하시오.
힌트
먼저 유리수 쪽에 서식을 건다. \(\frac pq = \frac{p'}{q'}\)에서 \(\frac p{2q}\)와
\(\frac{p'}{2q'}\)가 같은지 교차곱으로 확인한다. 그 다음 두 경우를 판정하고,
마지막으로 두 경우가 각각 주는 값을 \(x\)로 다시 적어 비교해 본다. 결함이
있다면 그것이 네 조건 중 어디인지, 아니면 조건 밖의 다른 문제인지까지 밝힌다.
13. 평행선 공리(“직선 밖 한 점을 지나 그 직선에 평행한 직선이 정확히 하나 존재한다”)의 독립성을, 그것을 깨는 모형(구면 기하는 평행선 0개, 쌍곡 기하는 여러 개)의 존재로 설명하시오 (S18주차 문제 9(b)와 연결). “독립인 공리를 바꾸면 새 이론이 태어난다”를 두 문장으로 적으시오.
이 문제가 빌려 쓰는 사실
구면 위의 큰 원을 “직선”으로 읽는 모형과 쌍곡 평면의 모형이 나머지 공리를 전부 만족한다는 것은 이 교재에서 증명하지 않았으므로 지금은 인정하고 쓴다(증명은 기하 교재로 미룬다). S18주차 문제 9(b)가 무대의 제약으로 다룬 것은 평면과 구면까지이고, 쌍곡 평면은 그 문제의 범위 밖이므로 이번 주에 별도로 인정하고 쓰는 사실이다. 이 문제가 요구하는 것은 두 기하를 세우는 일이 아니라, 정의 19.4의 독립성 검사법이 그 두 모형에 어떻게 걸리는지를 적는 일이다.
힌트
독립성 검사법의 문장을 그대로 옮겨 놓고 빈칸을 채우는 것이 방법이다 —
“그 공리만 거짓이고 나머지는 참인 모형이 존재하므로 그 공리는 나머지에서
유도되지 않는다.” 여기서 “그 공리”에 평행선 공리를, “모형”에 구면 또는
쌍곡을 넣으면 첫 문장이 완성된다.
14. 러셀 재구성: “무제한 내포 공리”(임의의 성질 \(P\)에 대해 \(\{x : P(x)\}\)가 집합이다)가 무모순성을 깨뜨림을 \(R = \{x : x \notin x\}\)로 보이시오 (1권 6주차 §1.7의 정식 재현). 이어서 이 공리를 분출 공리(이미 있는 집합 \(A\)에서 \(\{x \in A : P(x)\}\)만 만든다)로 약화하면 왜 역설이 사라지는지 설명하시오.
힌트
앞부분은 두 갈래를 각각 한 줄로 적는다 — \(R \in R\)이라 하면 \(R\)이 \(R\)의 조건
“\(x \notin x\)”를 만족해야 하므로 \(R \notin R\)이고, \(R \notin R\)이라 하면 \(R\)이
그 조건을 만족하므로 \(R \in R\)이다. 양쪽 모두 반대쪽이 나온다는 것까지 적으면
앞부분이 끝난다. 뒷부분은 \(R_A = \{x \in A : x \notin x\}\)에 같은 논법을 그대로
걸어 보는 것이 방법이다 — 나오는 것이 모순이 아니라 “\(R_A \notin A\)”라는 참인
결론임을 §1.6의 해결 단락에서 끌어온다.
도전 ●●●#
15. (정의 설계) 두 정수 \(a, b\)의 최대공약수 \(\gcd(a, b)\)를 well-defined하게 정의하시오. (a) “공약수 중 최대”로 정의할 때 최댓값의 존재(공약수 집합이 유한이고 비어 있지 않음)와 유일성(S13주차)을 확인하시오. (b) \(\gcd(0, 0)\)에서 모든 정수가 공약수가 되어 최대가 없는 문제를 어떻게 처리할지 적고, “정의가 모든 입력에서 값을 주는가”를 점검하시오.
힌트
(a)는 두 걸음이다 — 집합이 위로 유계임을 보이고, 유계인 정수 집합에 최댓값이
있음을 쓴다. \(d \mid a\)이고 \(a \neq 0\)이면 \(d\)의 크기가 \(|a|\)를 넘지 못한다는
사실이 유계의 근거다. (b)는 결함을 숨기지 말고 명시하는 것이 답이다.
16. (공리계 종합) 군(group)의 공리(결합\(\cdot\)항등원\(\cdot\)역원 — C18주차 예고)를 진술하시오. (a) 무모순성 모형을 제시하시오 (\(\mathbb{Z}\)와 \(+\)). (b) 항등원의 유일성이 공리가 아니라 정리임을 보이시오 (S13주차 문제 9) — 유도되는 것을 공리 목록에 넣으면 독립성이 깨진다.
이 문제가 빌려 쓰는 사실
군의 공리는 C18주차(Chartrand 15장)에서 정식으로 다룬다. 이번 주에는 공리 세 줄을 진술하고 정의 19.4의 세 덕목을 거는 것까지만 하면 되고, 군론의 정리는 하나도 쓰지 않는다.
힌트
(b)는 S13주차 문제 9의 계산을 그대로 옮기되 덧셈을 이항연산으로 바꾸면 된다 —
두 항등원 \(e_1\), \(e_2\)를 잡고 \(e_1\)의 조건에 \(e_2\)를, \(e_2\)의 조건에 \(e_1\)을
넣으면 같은 식이 두 번 나온다. 그 다음에 “그러므로 공리로 둘 필요가 없다”는
한 줄을 독립성의 언어로 적는 것이 이 문제의 몫이다.
17. (well-def 심화) 함수 \(f : \mathbb{Z}_n \to \mathbb{Z}_n\)을 \(f([a]) = [a^2]\)으로 정의할 때 well-defined임을 증명하시오 (\([a] = [b]\), 곧 \(n \mid (a - b)\)이면 \(n \mid (a^2 - b^2)\) — 인수분해 \(a^2 - b^2 = (a-b)(a+b)\)를 쓰시오). 이어서 \(g([a]) = [2^a]\)에서는 왜 같은 검사가 통하지 않는지를 문제 9와 연결해 적으시오.
힌트
앞부분은 검사 서식 세 걸음이 그대로 돈다 — 두 표현 \([a]\), \([b]\) / 같음의 등식
\(n \mid (a-b)\) / 값의 같음 \(n \mid (a^2 - b^2)\). 뒷부분은 \(2^{a+n}\)을 \(2^a\)로
묶어 보면 무엇이 더 필요한지가 드러난다.
18. (무모순성의 한계) “충분히 강하고 무모순인 공리계는 자신의 무모순성을 스스로 증명할 수 없다”(괴델 제2불완전성)를 서술적으로 소개하고, 이것이 “모형으로 무모순성을 보증”하는 방법(예제 2.3)과 어떻게 공존하는지 설명하시오. 엄밀한 증명은 요구하지 않는다.
이 문제가 빌려 쓰는 사실
괴델의 두 불완전성 정리는 이 교재의 범위 밖이므로 지금은 인정하고 쓴다. 이 문제가 요구하는 것은 정리의 증명이 아니라, 정의 19.4의 검사법 ①(모형 제시)이 그 정리와 충돌하지 않는 이유를 적는 일이다.
힌트
충돌하지 않는 이유는 한 낱말에 있다 — 모형은 어디에서 만들어지는가. 예제
2.3의 모형 \(\mathbb{R}\)는 순서 공리계 바깥에서 왔다. 그 사실을 “무모순성은
절대적이 아니라 무엇에 대해 상대적이다”라는 문장으로 옮기면 답이 완성된다.
19. (설계) 이번 학기에 이름 없이 쓴 개념 하나(“상계”, “수렴”, “단조수열” 등)를 골라 정식 정의로 짓고 네 조건을 점검한 뒤, 그 정의로 작은 정리 하나를 진술하고 증명하시오. (예: “유계 수열”을 정의하고 “수렴하는 수열은 유계이다”를 증명 — S7주차 문제 11이 부품이다.)
힌트
정의 짓기와 정리 증명을 한 답안에 담는 문제이므로 순서를 지킨다 — 정의 \(\to\)
네 조건 \(\to\) 정리 진술 \(\to\) 증명. 예시를 그대로 따라간다면, 증명은 꼬리와 머리를
나누어 각각 유계임을 보이고 둘을 합치는 세 걸음이다.
20. (서술) (a) 정의와 공리를 읽는 쪽에서 만드는 쪽으로 넘어갈 때 새로 생기는 세 책임(무순환\(\cdot\)well-def\(\cdot\)무모순)이 각각 이전의 어느 개념이 이름을 바꾼 것인지 밝히시오 (무순환은 층위와 S4주차의 정의 환원, well-def는 유일성(S13주차), 무모순은 귀류의 기반(S11주차)). (b) 러셀의 역설이 왜 만드는 쪽의 사례인지 — 읽기만 할 때는 드러나지 않던 것이 무엇인지 두 문장으로 적으시오.
힌트
(a)는 세 줄을 각각 “이전에는 …로 했고, 이번 주에는 … 검사로 이름이 붙었다”
꼴로 적는다. (b)는 확인 12의 답이 출발점이다 — 무제한 내포 공리를 쓰는
쪽에서 볼 때 그 공리는 무엇으로 보였고, 세우는 쪽에서 볼 때는 무엇이 되는가.
백지 재현 — 복습 프로토콜#
이번 주의 5일 루틴. 원서와 교안을 번갈아 쓰는 순서다.
요일 |
할 일 |
|---|---|
1일차 |
원서 Solow 17~18장 통독 (모르는 문장은 표시만 하고 통과) |
2일차 |
교안 §0~§2 — 개념과 예제. 확인 상자는 연필로 먼저 답한다 |
3일차 |
원서 재독 — 1일차에 표시한 문장이 전부 해결되었는지 확인하고, 원서 17~18장의 연습문제 몇 개를 직접 시도 |
4일차 |
교안 §3 빈칸 사다리 + §4 연습문제 20문항 |
5일차 |
백지 재현 1차(틀 카드)\(\cdot\)2차(완전 백지) + 체크리스트 |
3일차의 재독이 이번 주에는 특히 중요하다. 원서 17~18장은 좋은 정의의 예와 공리계 사례를 나란히 보이는 방식으로 지나가므로, 교안 정의 19.2의 네 조건과 §1.5의 덕목 표를 손에 쥐고 다시 읽으면 원서의 각 사례가 어느 항목을 예시한 것인지 짚을 수 있다. 원서가 정의를 제시하고 곧바로 다음으로 넘어간 자리에서 well-defined 검사가 필요한지 아닌지를 스스로 판정해 보는 것이 이 주의 재독 과제다.
1차 시도 — 틀 카드 허용. 다음 세 상자만 옮겨 적은 카드를 펴 놓는다: 정의 19.2의 네 조건, 정의 19.3의 검사 서식 세 줄, 정의 19.4의 세 덕목. 그 상태에서 예제 2.1을 정의 문장부터 네 조건 점검까지 적고, 이어서 예제 2.2를 검사 서식 세 줄로 적는다. 예제 본문과 확인 상자는 보지 않는다.
2차 시도 — 완전 백지. 아무것도 보지 않고 수행한다.
정의 19.1의 네 층위를 순서대로 쓰고, 각 층을 빼면 무엇이 무너지는지 한 줄씩 적었다.
정의 19.2의 네 조건을 쓰고, 조건마다 위반 사례를 하나씩 제시했다.
정의 19.3의 검사 서식 세 줄을 쓰고, “같은 대상”을 등식으로 옮기는 번역표(유리수\(\cdot\)잉여류)를 재현했다.
성질을 정하는 정의와 값을 정하는 정의의 갈림을 한 문장으로 적었다.
정의 19.4의 세 덕목과 각각의 검사법(모형 하나 / 공리마다 반례 모형)을 재현했다.
무모순성이 최우선인 이유를 \(\lor\) 첨가와 선언 삼단논법 두 줄로 적었다.
러셀의 역설을 재현하고, 무너진 것이 정의가 아니라 공리임을 밝혔다. 분출 공리로의 약화도 적었다.
§1.7의 만드는 쪽의 네 책임을 재현했다.
예제 2.1을 정의 문장부터 네 조건 점검까지 처음부터 끝까지 재현했다.
예제 2.2를 검사 서식 세 줄로 재현하고, \(\oplus\)가 무엇을 조작하는 규칙이었는지 적었다.
예제 2.3의 무모순성 모형과 A2\(\cdot\)A3 독립성 모형을 각각 검증까지 재현하고, A1이 A3에서 유도되어 이 공리계가 최소가 아님을 적었다.
§2 끝의 제작 보고 서식 네 줄을 재현했다.
막힌 지점별 처방. 막힌 지점이 무엇을 다시 볼지 알려 준다.
막힌 지점 |
처방 |
|---|---|
정의를 짓기는 했는데 무엇을 점검할지 모르겠다 |
정의 19.2 — 네 조건을 순서대로 걸고, 항목마다 한 줄씩 쓴다 |
well-def 검사를 어디에 걸어야 할지 모르겠다 |
확인 9 — 값을 주는 정의인가 성질을 주는 정의인가만 먼저 묻는다 |
“같은 대상”을 등식으로 옮기지 못한다 |
정의 19.3의 번역표 — 유리수는 교차곱, 잉여류는 나누어떨어짐 |
ill-defined라고 주장했는데 근거가 약하다 |
예제 2.2 — 갈리는 표현 한 쌍을 실제 수로 제시하고 교차곱으로 비교한다 |
무모순성 모형이 떠오르지 않는다 |
예제 2.3 — 가장 익숙한 수 체계부터 넣어 본다. 실수\(\cdot\)정수\(\cdot\)유한 집합 순서다 |
독립성 모형이 떠오르지 않는다 |
예제 2.3과 훈련 3 — 관계를 하나도 두지 않는 모형과 전부 두는 모형이 첫 두 후보다 |
러셀의 역설에서 무엇이 무너졌는지 헷갈린다 |
확인 12 — 정의는 네 조건을 통과했고 무너진 것은 공리다 |
층위와 무순환의 차이를 말하지 못한다 |
§1.3과 §1.4 — 층위는 이론 전체의 구조이고 무순환은 정의 한 문장의 조건이다 |
하나라도 실패하면 그 항목만 다시 적고 다음날 재시도한다.
해설#
각 해설은 접근(문제 앞에서 무엇을 생각하는가)과 풀이로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다.
빈칸 사다리 — 훈련 1#
(1) \(ab' = a'b\) (2) \(a'b\) (3) 이다 (참이다) (4) 반드시 별도로
※ 이 훈련의 요점은 걸음 ②의 등식이 어디에 대입되는지다. \((ac)(b'd)\)를 그대로 비교하려 하면 막히고, \((ab')(cd)\)로 묶어 걸음 ②의 등식이 들어갈 자리를 만들어야 계산이 돈다. 예제 2.2의 \(\oplus\)에서는 같은 묶기가 되지 않는다 — \((a + c)(b' + d)\)는 \(ab'\)를 인수로 갖지 않기 때문이다. 곧 곱셈이 통과하고 덧셈 꼴의 \(\oplus\)가 탈락하는 것은 우연이 아니라 이 묶기의 가능 여부에서 갈린다. 한 가지가 더 있다 — well-defined를 주장할 때는 두 입력 모두에서 표현 무관을 보여야 한다. 첫 입력만 바꿔 보고 닫으면 둘째 입력이 검사되지 않은 채로 남는다. 한쪽만 바꾸는 것으로 충분한 것은 ill-defined를 주장할 때뿐이다(값이 갈리는 쌍 하나면 불통과가 확정되기 때문이다 — 확인 20). 이 훈련에서는 \(\odot\)의 식이 두 입력에 대해 대칭이므로 “둘째 입력에 대해서도 문자만 바꿔 같은 계산이 반복된다”는 한 줄로 그 몫을 치른다.
빈칸 사다리 — 훈련 2#
(1) \(k^2\) (2) \(\exists\) (존재) (3) 구성 (4) 정의 19.2의 ② 무순환 (5) 성질 (참\(\cdot\)거짓) (6) \(2\)는 사각수가 아니다 (\(k = 0\)에서 \(0\), \(\lvert k \rvert = 1\)에서 \(1\), \(\lvert k \rvert \ge 2\)에서 \(4\) 이상이므로 후보가 없다 — \(k^2 = (-k)^2\)이라 음의 \(k\)는 절댓값으로 함께 처리된다) (7) ④ 비자명
※ (6)에서 “\(2\)는 사각수가 아니다”만 적고 끝내면 절반이다. 후보를 다 훑었다는 줄이 있어야 “아직 못 찾았다”와 구별된다. 이 정의의 \(k\)는 양의 정수가 아니라 정수이므로, 훑을 때 \(k = 0\)과 음의 \(k\)를 빠뜨리지 않아야 한다. (7)의 붕괴는 §1.4 조건 삭제 실험 표 마지막 줄과 같은 꼴이다 — 자격을 지우는 순간 무대의 전부가 이름을 받고, 이름이 아무것도 구별하지 못하게 된다.
빈칸 사다리 — 훈련 3#
(1) \(S = \mathbb{Z}\)로 두고 \(\sim\)을 “\(x \sim y \iff x = y\)”로 읽는다. A1은 \(x = x\)이므로 참이고, A2는 \(x = y\)이면 \(y = x\)이므로 참이다. 두 공리를 전부 만족하는 대상이 존재하므로 무모순이다.
(2) \(S = \{a, b\}\)로 두고 \(\sim\)을 \(a \sim a\), \(b \sim b\), \(a \sim b\)의 세 쌍에서만 성립하는 관계로 둔다. A1은 \(a \sim a\)와 \(b \sim b\)가 모두 성립하므로 참이고, A2는 \(a \sim b\)가 성립하지만 \(b \sim a\)가 성립하지 않으므로 거짓이다. A2만 거짓이고 A1은 참인 모형이 존재하므로 A2는 A1에서 유도되지 않는다 — A2는 독립이다.
(3) 유도되지 않는다. \(S = \{a, b, c\}\)로 두고 \(\sim\)을 세 자기 쌍 (\(a \sim a\), \(b \sim b\), \(c \sim c\))과 \(a \sim b\), \(b \sim a\), \(b \sim c\), \(c \sim b\)에서만 성립하는 관계로 둔다. A1은 세 자기 쌍이 있으므로 참이고, A2는 성립하는 쌍이 전부 왕복하므로 참이다. 그러나 \(a \sim b\)이고 \(b \sim c\)인데 \(a \sim c\)는 성립하지 않으므로 추이는 거짓이다. 추이만 거짓이고 A1\(\cdot\)A2는 참인 모형이 존재하므로 추이는 A1과 A2에서 유도되지 않는다.
(4) 1권 36주차가 해부한 “대칭적이고 추이적이면 반사는 공짜”라는 주장과 같은 종류의 물음이다. 그쪽은 반사가 대칭\(\cdot\)추이에서 유도되는지를 묻고 이쪽은 추이가 반사\(\cdot\)대칭에서 유도되는지를 묻는데, 둘 다 세 성질 중 하나를 나머지 둘에서 뽑을 수 있는지를 묻는 독립성 물음이고, 둘 다 답이 “유도되지 않는다”이며, 둘 다 반례 모형 하나로 결판난다.
※ 이 훈련의 요점은 독립성 검사가 세 성질 사이에서 세 번 반복된다는 것이다. 1권 36주차에서 세 성질을 따로 배운 이유가 여기서 드러난다 — 셋이 서로 유도되지 않으므로 각각이 별도의 요구다.
문제 1#
접근. 네 덩어리를 재생하는 문제다. 외운 문장을 옮기기보다 각 덩어리가 무엇을 막아 주는지 한 줄씩 덧붙이며 적는 쪽이 재현률이 높다. 층위는 무한 후퇴와 순환을 막고, 네 조건은 정의로 성립하지 않는 문장이 정의 행세를 하는 것을 막고, 세 덕목은 모순된 출발 명제와 군더더기 공리를 막고, well-def는 같은 대상에 두 값이 붙는 것을 막는다.
풀이. 4층위. ① 무정의 용어 — 정의하지 않고 출발하는 원초 개념(집합\(\cdot\)원소, 점\(\cdot\)선). ② 공리 — 증명 없이 참으로 놓는 출발 명제. ③ 정의 — 아래층의 용어만으로 새 용어를 iff로 도입한 것. ④ 정리 — ①②③과 논리만으로 증명되는 명제.
정의의 4조건. ① 명확성 — 용어와 조건이 iff로 이어지고, 조건에 애매어가 없으며, 이름이 조건과 어긋나지 않는다. ② 무순환 — 조건이 피정의어를 직접\(\cdot\)간접으로 포함하지 않는다. ③ well-defined — 같은 대상의 여러 표현에 대해 결과가 표현 선택에 무관하다. ④ 비공허\(\cdot\)비자명 — 조건을 만족하는 대상이 있고 무대의 전부는 아니다.
공리계의 3덕목. ① 무모순성 — 모순이 유도되지 않는다. 검사는 모형 하나. ② 독립성 — 각 공리가 나머지에서 유도되지 않는다. 검사는 공리마다 반례 모형 하나. ③ 완전성 — 모든 명제가 증명 또는 반증된다. 대개 요구하지 않는다.
well-def의 뜻. 대상 \(r\)의 두 표현 \(r_1 = r_2\)에 대해 정의가 주는 값이 같다는 것. 아니면 ill-defined이고, 그 문장은 정의로 성립하지 않는다.
복기. 네 덩어리는 검사 대상이 다르다 — 층위는 이론 전체, 네 조건은 정의 한 문장, 세 덕목은 공리 목록, well-def는 정의가 주는 값이다. 무엇을 검사하는지부터 적으면 나머지가 따라 나온다.
문제 2#
접근. 네 조건을 순서대로 거는 것이 방법이다. (a)는 조건 자체는 판정 가능하므로 “조건을 풀 수 있는가”가 아니라 “이름과 조건이 맞는가”를 물어야 하고, (b)와 (c)는 조건을 아래층까지 풀어 보려 하면 곧바로 막히며, (d)는 조건을 만족하는 대상을 하나라도 만들어 보면 드러난다.
풀이. (a) ① 명확성 위반(이름과 조건의 정합 조각을 어긴다). 조건 “\(n < 100\)”은 판정 가능하고 애매어도 없지만 이름 “작은 수”와 어긋난다. \(99\)와 \(-10^6\)이 같은 이름을 받고 \(100\)과 \(99\)가 다른 이름을 받는데, 그 경계 \(100\)에 근거가 없다. 이름이 조건과 일치하지 않으면 읽는 사람이 정리를 오독하므로, 이름을 “\(100\) 미만의 정수”로 바꾸거나 조건을 이름에 맞게 다시 세워야 한다.
(b) ② 무순환 위반. \(4\)가 짝수인지 물으면 홀수가 아닌지를 물어야 하고, 그것은 다시 짝수인지를 묻는다. 두 정의가 서로를 조건으로 삼아 어느 쪽도 아래층으로 내려가지 않으므로 판정이 시작되지 않는다. 수리하려면 한쪽을 원초적으로 세워야 한다 — 예를 들어 “짝수: \(n = 2k\)인 정수 \(k\)가 존재한다”로 놓고 홀수를 그 부정으로 두면, 이번에는 짝수가 아래층으로 내려가므로 순환이 끊긴다.
(c) ② 무순환 위반 (그리고 ① 명확성 위반). 조건 “흥미로운 성질을 갖는다”에 피정의어 “흥미로운”이 그대로 들어 있어 순환이고, 동시에 “흥미로운”은 판정 기준이 없는 애매어이므로 명확성도 어긴다. 두 조건을 함께 어기는 사례다.
(d) ④ 비공허 위반. \(x \neq x\)인 실수는 하나도 없으므로 “초록수”는 아무것도 가리키지 않는다. 이 이름을 쓴 전칭 명제는 전부 공허 참이 되어, “모든 초록수는 \(7\)보다 크다”와 “모든 초록수는 \(7\)보다 작다”가 동시에 참이 된다.
복기. 네 조건은 서로 배타적이지 않다 — (c)처럼 둘을 함께 어길 수 있다. 답안에는 어긴 조건을 전부 적고, 각각에 대해 무엇이 무너지는지 한 줄씩 붙인다.
문제 3#
접근. 재현의 뼈대는 검사 서식 세 줄이다. 두 표현을 잡고, 같음을 등식으로 옮기고, 두 값을 계산해 비교한다. 마지막 비교를 소수 어림으로 하면 근거 목록 밖이므로 교차곱으로 적는다.
풀이. 걸음 ①: 첫 입력의 두 표현을 \(\frac12\)과 \(\frac24\)로 잡고 둘째 입력은 \(\frac13\)으로 고정한다.
걸음 ②: \(1 \cdot 4 = 4\)이고 \(2 \cdot 2 = 4\)이므로 \(\frac12 = \frac24\)이다. 두 표현은 같은 유리수를 가리킨다.
걸음 ③: 정의가 주는 두 값을 계산하면
이고, 교차곱은 \(2 \cdot 7 = 14\)와 \(5 \cdot 3 = 15\)로 다르므로 \(\frac25 \neq \frac37\)이다. 같은 입력에 서로 다른 출력이 나왔으므로 \(\oplus\)는 ill-defined이고, 이 문장은 유리수 위의 연산의 정의로 성립하지 않는다. \(\blacksquare\)
복기. ill-defined를 주장할 때 필요한 것은 갈리는 표현 한 쌍뿐이다. well-defined를 주장할 때는 임의의 두 표현에 대한 유도가 필요하므로 비용이 훨씬 크다. 이 비대칭이 반례와 증명의 비대칭(S18주차 확인 6)과 같은 구조다.
검산. \(\frac25\)와 \(\frac37\)을 다시 확인하면 \(\frac25 = 0.4\)이고 \(\frac37 \approx 0.4286\)으로 실제로 다르다. 어림은 답안에 적지 않고 오류 탐지에만 쓴다.
문제 4#
접근. 세 훈련이 각각 다른 것을 묻는다. 훈련 1은 well-def 검사의 계산, 훈련 2는 정의 짓기의 네 조건, 훈련 3은 공리계의 두 덕목이다. 한 번에 재현되지 않으면 훈련별로 나누어 다른 날에 재시도한다.
풀이. §6 앞부분의 훈련 1~3 답과 대조한다. 특히 다음 세 자리에서 갈린다. 훈련 1의 (2)는 \((ac)(b'd)\)를 \((ab')(cd)\)로 묶는 자리이고, 이 묶기가 없으면 걸음 ②의 등식을 대입할 곳이 없다. 훈련 2의 (6)은 비자명의 증거인데 “후보를 다 훑었다”는 줄이 함께 있어야 완성이다. 훈련 3의 (3)은 모형의 원소가 셋 필요하다 — 추이가 어긋나려면 \(a \sim b\), \(b \sim c\), \(a \not\sim c\)의 세 자리가 있어야 하고 원소 둘로는 그 배치를 만들 수 없다.
복기. 세 훈련을 관통하는 것은 “검사에는 재료가 필요하다”는 것이다. well-def 검사의 재료는 두 표현이고, 네 조건 검사의 재료는 예와 비예이고, 덕목 검사의 재료는 모형이다. 재료를 만들지 않고 판정만 적은 답안이 이번 주의 가장 흔한 실점이다.
문제 5#
접근. 정의 문장 한 줄만 적고 끝내면 재현의 절반이다. 네 조건 각각에 한 줄씩 붙이고, ④에는 예와 비예를 실제 수로 적는다. 조건 ③은 “성질 정의이므로 자동 통과”라는 한 줄이 필요하다 — 점검하지 않은 것과 점검해서 통과한 것은 다르다.
풀이. 정의. 양의 정수 \(n\)이 삼각수라 함은, \(n = \frac{k(k+1)}2\)인 양의 정수 \(k\)가 존재하는 것이다.
① 명확성. 조건 안의 낱말은 양의 정수\(\cdot\)곱\(\cdot\)합\(\cdot\)나누기 2\(\cdot\)등호\(\cdot\)존재뿐이고 애매어가 없으며, 이름 “삼각수”도 조건이 가리키는 것(점을 삼각형 꼴로 쌓은 개수)과 어긋나지 않는다. 양화사는 \(\exists\)이므로 후진면은 구성법이다.
② 무순환. 위 여섯 용어 중 어느 것도 삼각수를 직접 또는 간접으로 쓰지 않는다. 전부 산술과 논리의 층에서 이미 확정된 용어다.
③ well-defined. 이 정의는 값이 아니라 “삼각수인가 아닌가”라는 참\(\cdot\)거짓을 주고, 대표원을 골라 값을 계산하는 자리가 없으므로 표현 선택이 개입할 자리도 없다. 성질 정의이므로 자동 통과한다.
④ 비공허\(\cdot\)비자명. 비공허: \(k = 3\)에서 \(\frac{3 \cdot 4}2 = 6\)이므로 \(6\)은 삼각수다. 비자명: \(5\)는 삼각수가 아니다 — \(k = 1, 2\)에서 값이 \(1, 3\)이고 \(k \ge 3\)이면 값이 \(6\) 이상이므로 남은 후보가 없다. \(\blacksquare\)
검산. \(k = 1, \dots, 6\)에서 \(1, 3, 6, 10, 15, 21\)이 나오고 이웃한 값의 차가 \(2, 3, 4, 5, 6\)으로 하나씩 커진다. 정의가 뽑은 꼴이 사례의 규칙과 일치한다.
문제 6#
접근. §1.3의 층 삭제 실험 (가)가 그대로 답이다. “모든 것을 정의한다”는 규칙을 실제로 지키려 할 때 무슨 일이 벌어지는지를 두 갈래로 갈라 적는다 — 낱말이 무한히 필요해지는 쪽과, 낱말이 유한하면 앞의 것이 다시 나오는 쪽.
풀이. 어떤 용어를 정의하면 그 정의에 쓰인 용어들을 다시 정의해야 하고, 그 용어들에 쓰인 용어들을 또 정의해야 하므로, 정의의 사슬은 끝나지 않거나(무한 후퇴) 유한한 낱말로는 언젠가 앞에서 쓴 용어로 되돌아온다(순환). 무한 후퇴는 어느 정의도 완성되지 않게 하고 순환은 판정이 시작되지 않게 하므로, 사슬을 유한 번에 끊기 위해 정의하지 않고 출발하는 용어를 바닥에 두어야 한다.
복기. 이 논법의 형태는 공리에 대해서도 그대로 반복된다 — 근거의 사슬도 유한 번에 끊어야 하고, 그것을 끊는 것이 공리다. 용어의 바닥과 근거의 바닥이 각각 필요하다는 것이 확인 5의 정리다.
문제 7#
접근. S4주차 예제 2.3에서 소화한 정의를 이번에는 만드는 쪽에서 다시 적는 문제다. 조건은 그때와 같지만 적을 것이 늘어난다 — 네 조건을 순서대로 통과시켜야 하고, 특히 ④에는 예 둘과 비예 하나를 실제 계산으로 적어야 한다.
풀이. 정의. 양의 정수 \(n\)이 완전수라 함은, \(n\)의 양의 약수 중 \(n\) 자신을 제외한 것들의 합이 \(n\)과 같은 것이다.
① 명확성. 조건이 쓰는 “약수”, “합”, “등호”는 전부 판정이 정해진 용어이고 애매어가 없으며, 이름 “완전수”도 조건과 어긋나지 않는다. 조건 안의 양화사는 합의 범위에 숨어 있는 전칭이다 — “\(n\)을 나누고 \(0 < d < n\)인 모든 \(d\)”가 그것이며, 따라서 이 정의의 후진면은 약수를 빠짐없이 나열해 합을 계산하는 것이다.
② 무순환. 약수는 나누어떨어짐(1권 2주차)으로 정의되고 나누어떨어짐은 곱으로 정의되므로, 조건이 쓰는 용어가 전부 완전수보다 아래층이다. 순환 없음.
③ well-defined. 이 정의는 값이 아니라 성질을 주고 대표원을 골라 계산하는 자리가 없으므로 자동 통과한다.
④ 비공허\(\cdot\)비자명. 비공허: \(6\)의 진약수는 \(1, 2, 3\)이고 합이 \(6\)이므로 \(6\)은 완전수이며, \(28\)의 진약수는 \(1, 2, 4, 7, 14\)이고 합이 \(28\)이므로 \(28\)도 완전수다. 비자명: \(12\)의 진약수는 \(1, 2, 3, 4, 6\)이고 합이 \(16 \neq 12\)이므로 \(12\)는 완전수가 아니다. \(\blacksquare\)
복기. “자신을 제외한”이라는 조각을 빠뜨리면 정의가 어떻게 달라지는지가 S4주차 §1.8의 걸음 삭제 실험에 있다 — \(6\)의 약수 전부의 합은 \(12\)이므로 \(6\)이 탈락하고, 실제로는 \(n = 1\)만 남는 전혀 다른 개념이 된다. 여기서 주의할 것은 네 조건이 그래도 전부 통과한다는 점이다. \(n = 1\)이 조건을 만족하므로 비공허이고 모든 양의 정수가 만족하는 것은 아니므로 비자명이며, 명확성과 무순환도 그대로다. 무너지는 것은 조건이 아니라 의도한 개념과의 일치이고, 대표 사례 \(6\)과 \(28\)이 탈락하는 것은 조건 검사만으로는 잡히지 않는다. 예와 비예를 실제로 만들어 대조해야 드러나는 결함이며, S4주차 §1.8의 걸음 ③이 예 둘과 비예 둘을 요구한 이유가 여기 있다.
문제 8#
접근. 훈련 1의 곱셈판과 계산 구조가 같다. 걸음 ②의 등식 \(ab' = a'b\)를 대입할 자리를 만들려면, 교차곱을 전개한 뒤 \(ab'\)가 인수로 나타나는 항을 찾아 묶어야 한다. \(\boxplus\)의 분자에는 \(ad\)와 \(bc\) 두 항이 있으므로 전개 후 항이 둘씩 나온다.
풀이. 걸음 ①: 첫 입력의 두 표현을 \(\frac ab\)와 \(\frac{a'}{b'}\)로 잡고 둘째 입력 \(\frac cd\)는 고정한다.
걸음 ②: \(\frac ab = \frac{a'}{b'}\)를 등식으로 옮기면 \(ab' = a'b\)이다.
걸음 ③: 비교할 두 값은 \(\frac{ad + bc}{bd}\)와 \(\frac{a'd + b'c}{b'd}\)이다. 교차곱을 각각 전개하면
이다. 둘째 항은 \(bb'cd\)로 서로 같고, 첫째 항은 \(ab'd^2\)와 \(a'bd^2\)인데 걸음 ②에 의해 \(ab' = a'b\)이므로 양변에 \(d^2\)을 곱하여 \(ab'd^2 = a'bd^2\)이다(근거 ③). 따라서 두 교차곱이 같으므로 \(\frac{ad+bc}{bd} = \frac{a'd+b'c}{b'd}\)이고, \(\boxplus\)는 well-defined이다. \(\blacksquare\)
복기. 둘째 입력의 표현을 바꾸는 경우는 \(\boxplus\)의 식이 두 입력에 대해 대칭이므로 같은 계산이 문자만 바꿔 반복된다. 답안에는 “둘째 입력에 대해서도 대칭이므로 같다”는 한 줄을 적으면 충분하다.
검산. \(\frac12 \boxplus \frac13 = \frac{1 \cdot 3 + 2 \cdot 1}{6} = \frac56\)이고 \(\frac24 \boxplus \frac13 = \frac{2 \cdot 3 + 4 \cdot 1}{12} = \frac{10}{12} = \frac56\)으로 일치한다.
문제 9#
접근. ill-defined를 보이는 데 필요한 것은 값이 갈리는 표현 한 쌍이다. \(\star\)는 입력이 둘이므로 한쪽만 바꾸면 되는데, 밑 쪽을 바꾸면 법 \(2\)에서 \(a\)의 홀짝만 결과를 정하므로 갈리지 않는다. 남는 것은 지수 쪽이고, 법 \(2\)에서 \([0] = [2]\)이므로 지수를 \(0\)과 \(2\)로 바꿔 보면 된다.
풀이. 법 \(2\)에서 \(0 - 2 = -2\)이고 \(2 \mid (-2)\)이므로 \([0] = [2]\)이다. 밑을 \([2]\)로 고정하고 지수의 두 표현을 각각 넣으면
이다. \(1 - 0 = 1\)이고 \(2 \nmid 1\)이므로 \([1] \neq [0]\)이다. 같은 입력 (\([2]\)와 \([0] = [2]\))에 서로 다른 출력이 나왔으므로 \(\star\)는 ill-defined이고, 이 문장은 \(\mathbb{Z}_2\) 위의 연산의 정의로 성립하지 않는다. \(\blacksquare\)
지수 자리가 다른 이유. 밑 쪽은 곱셈이 잉여류를 보존하므로(1권 20주차 §1.5의 (C5)) \(a \equiv a'\)이면 \(a^b \equiv a'^b\)가 따라 나오지만, 지수 쪽은 잉여류 위의 연산이 아니라 반복 횟수이므로 \(b \equiv b'\)가 \(a^b \equiv a^{b'}\)를 주지 않는다. \(a^{b+n} = a^b \cdot a^n\)이므로, \(a^n \equiv 1\)이면 지수를 \(n\)만큼 옮겨도 결과가 유지된다. 그러나 그 조건이 없으면 유지가 일반적으로 보장되지 않는다 — 위에서 쓴 \(a = 2\), \(n = 2\)가 그 경우다. \(2^2 = 4 \equiv 0 \pmod 2\)이므로 \(a^n \equiv 1\)이 아니고, 실제로 지수를 \(2\)만큼 옮기자 값이 갈렸다.
덧붙여 밑을 \([0]\)으로 잡으면 \([0] \star [0]\)이 \([0^0]\)이 되는데, \(0^0\)을 \(1\)로 약속하느냐 정의하지 않은 채 두느냐에 따라 이 자리의 값이 달라진다. 관례를 정의로 명시하지 않으면 검사 자체가 갈리므로, §1.8이 “관례는 근거가 아니다”라고 못 박은 이유가 여기서도 드러난다.
복기. 이 문제와 문제 17이 한 쌍이다. 밑에 붙은 연산은 검사가 통과하고 지수에 붙은 연산은 통과하지 않는다는 갈림을 한 줄로 적어 두면, C11주차에서 \(\mathbb{Z}_n\)의 연산을 만들 때 무엇을 정의할 수 있고 무엇을 정의할 수 없는지가 미리 갈린다.
문제 10#
접근. 정의 19.4의 검사법 두 줄을 그대로 실행하는 문제다. (a)는 세 공리를 전부 만족하는 관계 하나를 제시하고 공리마다 검증을 붙이면 되고, (b)는 대칭만 어기고 반사\(\cdot\)추이는 지키는 관계 하나를 제시하면 된다. 검증을 생략하고 이름만 적으면 모형을 제시한 것이 아니다.
풀이. 공리는 셋이다 — A1(반사): 모든 \(x\)에 대해 \(x R x\). A2(대칭): \(x R y\)이면 \(y R x\). A3(추이): \(x R y\)이고 \(y R z\)이면 \(x R z\) (1권 36주차).
(a) 무모순성. \(S = \mathbb{Z}\)로 두고 \(R\)을 “\(=\)”로 읽는다. A1은 \(x = x\)이므로 참, A2는 \(x = y\)이면 \(y = x\)이므로 참, A3은 \(x = y\)이고 \(y = z\)이면 \(x = z\)이므로 참이다. 세 공리를 전부 만족하는 대상이 존재하므로 이 공리계는 무모순이다. (\(R\)을 “\(\equiv \pmod 3\)”으로 읽어도 같다 — 1권 20주차 §1.5의 (C1)(C2)(C3)이 정확히 세 공리다.)
(b) 대칭의 독립성. \(S = \mathbb{R}\)로 두고 \(R\)을 “\(\le\)”로 읽는다. A1은 \(x \le x\)이므로 참이고, A3은 \(x \le y\)이고 \(y \le z\)이면 \(x \le z\)이므로 참이다 (1권 16주차 (W6). (W6)이 글자 그대로 적은 것은 부등호 하나가 \(\le\)로 바뀐 경우까지인데, 둘 다 \(\le\)인 경우도 같은 논증이 그대로 작동한다 — \(x = y\)이거나 \(y = z\)이면 남은 부등식이 그대로 결론이고, 둘 다 \(<\)이면 (W6)의 원래 진술이 쓰인다). 그러나 \(1 \le 2\)이면서 \(2 \le 1\)은 거짓이므로 A2는 위배된다. A2만 거짓이고 A1\(\cdot\)A3은 참인 모형이 존재하므로 A2는 A1과 A3에서 유도되지 않는다 — 대칭은 독립이다. \(\blacksquare\)
복기. 독립성 모형을 고를 때 가장 빠른 길은 “익숙한 관계 중 그 성질만 없는 것”을 떠올리는 것이다. 대칭이 없는 익숙한 관계는 순서이고, 반사가 없는 익숙한 관계는 엄격 부등호이며, 추이가 없는 익숙한 관계는 훈련 3에서 만든 유한 모형이다. 세 후보를 외워 두면 세 성질의 독립성이 모두 즉시 나온다.
문제 11#
접근. 검사 서식 세 걸음이 그대로 돈다. 걸음 ②에서 “\([a] = [a']\)”을 “\(3 \mid (a - a')\)”으로 옮기는 번역이 핵심이고, 그 다음은 1권 2주차에서 만든 부품(배수의 합은 배수)을 쓰면 끝난다. 이번에는 입력이 둘이므로 두 표현 쌍을 동시에 바꾼다.
풀이. 걸음 ①: 첫 입력의 두 표현을 \([a]\)와 \([a']\)로, 둘째 입력의 두 표현을 \([b]\)와 \([b']\)로 잡는다.
걸음 ②: \([a] = [a']\)은 \(3 \mid (a - a')\)이고, \([b] = [b']\)은 \(3 \mid (b - b')\)이다. 곧 \(a - a' = 3s\), \(b - b' = 3t\)인 정수 \(s, t\)가 존재한다.
걸음 ③: 정의가 주는 두 값은 \([a + b]\)와 \([a' + b']\)이다. 두 값이 같으려면 \(3 \mid \big((a+b) - (a'+b')\big)\)이면 되는데,
이고 \(s + t\)는 정수이므로(근거 ②) \(3 \mid \big((a+b) - (a'+b')\big)\)이다. 따라서 \([a+b] = [a'+b']\)이고, \(\mathbb{Z}_3\)의 덧셈은 well-defined이다. \(\blacksquare\)
복기. 이 계산은 1권 20주차 §1.5의 (C4) 합 보존과 글자 그대로 같다. 그때는 합동의 한 성질이었고 여기서는 정의의 성립 조건이다 — 같은 계산이 놓이는 자리가 바뀌면 하는 일이 바뀐다. C11주차에서 \(\mathbb{Z}_n\)의 덧셈과 곱셈을 정의할 때 가장 먼저 요구되는 것이 이 두 줄이다.
검산. \([4] = [1]\)이고 \([5] = [2]\)인데 \([4 + 5] = [9] = [0]\)이고 \([1 + 2] = [3] = [0]\)으로 일치한다.
문제 12#
접근. 진단 문제이므로 결함을 찾는 것부터가 아니라 검사를 실제로 도는 것부터 한다. 유리수 쪽에 검사 서식을 걸고, 두 경우가 무대를 덮는지 판정하고, 마지막으로 두 경우가 각각 주는 값을 \(x\)로 다시 적어 비교한다. 세 번째 걸음에서 이 답안의 진짜 성격이 드러난다.
풀이. ① 명확성. 조건 “\(x = \frac pq\)인 유리수이다”와 “무리수이다”에는 판정할 수 없는 낱말이 없고, 이름 “반쪽”도 두 경우가 주는 값 \(\frac x2\)와 어긋나지 않는다. 통과다.
② 무순환. 조건이 쓰는 용어는 유리수\(\cdot\)무리수\(\cdot\)정수\(\cdot\)나눗셈뿐이고 어느 것도 “반쪽”을 직접 또는 간접으로 쓰지 않는다. 통과다.
③ 유리수 쪽의 well-def 검사. 두 표현을 \(\frac pq\)와 \(\frac{p'}{q'}\)로 잡으면 같음의 등식은 \(pq' = p'q\)이다. 두 값 \(\frac p{2q}\)와 \(\frac{p'}{2q'}\)의 교차곱을 비교하면 \(p(2q') = 2(pq') = 2(p'q) = p'(2q)\)이므로 두 값은 같다. 유리수 쪽은 well-defined다.
두 경우의 판정. 모든 실수는 유리수이거나 무리수이고 둘을 동시에 만족할 수 없으므로, 두 경우는 무대를 빠짐없이 덮고 겹치지 않는다. 전수와 배타 모두 통과다.
두 값의 비교. \(x = \frac pq\)이면 유리수 쪽이 주는 값은 \(\frac p{2q} = \frac12 \cdot \frac pq = \frac x2\)이고, 무리수 쪽이 주는 값도 \(\frac x2\)이다. 곧 두 경우가 같은 값을 준다.
진단. ①②③이 모두 통과했다. ④는 걸리지 않는다 — \(h\)는 조건으로 대상을 가르는 정의가 아니라 무대의 모든 실수에 값을 주는 정의이므로, 정의 19.2 뒤의 단서대로 ④ 대신 “모든 입력에서 값을 주는가”를 묻는다. 두 경우가 무대를 빠짐없이 덮으므로 그것도 통과다. 따라서 이 정의는 정의로 성립한다. 다만 경우를 나눌 이유가 없다 — 두 경우가 같은 값을 주므로 “\(h(x) = \frac x2\)”라는 한 줄로 충분하고, 불필요한 경우 나누기는 읽는 사람에게 두 경우가 다른 값을 준다는 잘못된 신호를 보낸다. 네 조건의 위반은 아니지만 1권 20주차 §1.7의 글쓰기 규칙 5조(기호보다 말이 명확하면 말로 쓴다)와 같은 계열의 결함이다. \(\blacksquare\)
복기. 진단 문제에서 “결함이 있다”가 늘 정답인 것은 아니다. 검사를 다 돌린 뒤에 통과했다면 통과했다고 적고, 그럼에도 남는 문제가 있으면 그것이 어느 목록의 항목인지까지 밝히는 것이 이번 주의 규격이다.
문제 13#
접근. 정의 19.4의 독립성 검사법을 그대로 옮겨 놓고 빈칸을 채우는 문제다 — “그 공리만 거짓이고 나머지는 참인 모형이 존재하므로 그 공리는 나머지에서 유도되지 않는다.” 여기서 “그 공리”에 평행선 공리를, “모형”에 구면 기하와 쌍곡 기하를 넣으면 앞부분이 완성되고, 뒷부분은 그 사실이 이론의 개수에 대해 무엇을 말하는지를 적는 일이다.
풀이. 평행선 공리를 뺀 나머지 공리를 전부 만족하면서 평행선 공리만 다르게 성립하는 모형이 둘 있다. 구면 기하에서는 큰 원을 “직선”으로 읽는데 임의의 두 큰 원이 만나므로 주어진 직선 밖의 점을 지나는 평행선이 하나도 없고, 쌍곡 기하에서는 같은 점을 지나는 평행선이 무한히 많다. 두 모형 모두 나머지 공리는 만족하고 평행선 공리만 위배하므로, 정의 19.4의 독립성 검사법에 의해 평행선 공리는 나머지에서 유도되지 않는다 — 곧 독립이다.
독립인 공리는 참\(\cdot\)거짓이 나머지 공리로 결정되지 않으므로, 그 자리에 다른 명제를 놓아도 나머지와 충돌하지 않는다. 그래서 평행선 공리를 유클리드의 것으로 놓으면 유클리드 기하가, 평행선 0개로 놓으면 구면 기하가, 무한개로 놓으면 쌍곡 기하가 각각 완결된 이론으로 나온다 — 독립인 공리 하나를 바꾸는 것이 새 이론 하나를 만드는 일이다. \(\blacksquare\)
복기. 이 논법이 예제 2.3의 A3 독립성 논증과 글자 하나만 다르다. 모형 하나로 독립성을 보이고, 독립임이 확인된 자리에 다른 명제를 놓아 새 이론을 얻는 것 — 공리계를 세우는 쪽에서 가장 큰 수확이 나오는 자리가 여기다.
문제 14#
접근. 앞부분은 1권 6주차 §1.7의 논법을 정식으로 다시 적는 일이고, 뒷부분은 약화된 공리에서 같은 논법을 돌렸을 때 결론이 어떻게 바뀌는지를 보는 일이다. 뒷부분이 핵심이다 — 논법이 사라지는 것이 아니라 결론이 모순에서 참인 명제로 바뀐다는 것을 보여야 한다.
풀이. 무모순성의 실패. 무제한 내포 공리를 성질 “\(x \notin x\)”에 적용해 \(R = \{x : x \notin x\}\)가 집합이라고 하자. \(R\)이 집합이므로 “\(R \in R\)인가”를 물을 수 있고, 답은 참이거나 거짓이다.
\(R \in R\)이라 하자. 그러면 \(R\)은 \(R\)의 원소이므로 \(R\)을 정의한 조건 “\(x \notin x\)”를 만족해야 하고, 곧 \(R \notin R\)이다 — 가정과 모순이다.
\(R \notin R\)이라 하자. 그러면 \(R\)은 조건 “\(x \notin x\)”를 만족하므로 \(R\)의 원소이고, 곧 \(R \in R\)이다 — 가정과 모순이다.
두 갈래가 무대를 덮는데 어느 쪽도 모순이므로, 이 공리를 가진 공리계에서는 \(P\)와 \(\neg P\)가 함께 유도된다. 무모순성이 깨졌다. \(\blacksquare\)
약화 후. 분출 공리에서는 이미 있는 집합 \(A\)를 먼저 잡아야 하고, 만들 수 있는 것은 \(R_A = \{x \in A : x \notin x\}\)뿐이다. 같은 논법을 걸어 보자. \(R_A \in R_A\)라 하면 \(R_A\)가 조건을 만족하므로 \(R_A \notin R_A\)이고 모순이다. 따라서 \(R_A \notin R_A\)이다. 이제 \(R_A \in A\)라고 하면, \(R_A \in A\)이고 \(R_A \notin R_A\)이므로 \(R_A\)는 \(R_A\)의 조건을 모두 만족하여 \(R_A \in R_A\)가 되어 모순이다. 그러므로 \(R_A \notin A\)이다.
곧 논법이 주는 결론이 모순이 아니라 “\(R_A\)는 \(A\)에 속하지 않는다”라는 참인 명제로 바뀐다. 어떤 집합 \(A\)를 잡아도 그 바깥의 대상이 하나 만들어진다는 뜻이고, 이것은 모순이 아니라 “모든 집합을 담는 집합은 없다”는 정리다. 공리를 약화한 대가로 만들 수 있는 집합이 줄고, 그 대가로 무모순성이 회복된다.
복기. 같은 논법이 강한 공리 위에서는 모순을 내고 약한 공리 위에서는 정리를 낸다. 논법을 고친 것이 아니라 논법이 딛고 선 공리를 고친 것이며, 이것이 §1.6에서 말한 “검사가 두 층에서 각각 필요하다”의 실물이다.
문제 15#
접근. (a)는 정의를 적는 것으로 끝나지 않는다. “최대”라는 말이 값을 주므로, 그 값이 존재하고 유일함을 보여야 정의가 성립한다. 존재는 두 걸음이다 — 공약수 집합이 비어 있지 않고 위로 유계임을 보인 뒤 최댓값의 존재를 쓴다. (b)는 결함을 숨기지 말고 명시하는 것이 답이다.
풀이. 정의. 정수 \(a, b\)가 모두 \(0\)은 아니라 하자. \(a\)와 \(b\)의 공약수 전체의 집합을 \(D = \{d \in \mathbb{Z} : d \mid a \text{ 이고 } d \mid b\}\)라 할 때, \(\gcd(a, b)\)는 \(D\)의 최댓값이다.
(a) 존재. \(D\)는 비어 있지 않다 — \(1 \mid a\)이고 \(1 \mid b\)이므로 \(1 \in D\)이다. \(D\)는 위로 유계다 — \(a \neq 0\)이라 하면(둘 중 하나는 \(0\)이 아니므로 일반성을 잃지 않는다), \(d \mid a\)이고 \(a \neq 0\)일 때 \(d\)의 크기는 \(|a|\)를 넘지 못하므로 \(D\)의 모든 원소가 \(|a|\) 이하다. 비어 있지 않고 위로 유계인 정수 집합에는 최댓값이 존재하므로 \(D\)의 최댓값이 존재한다.
유일. 최댓값은 유일하다. \(M_1\), \(M_2\)가 둘 다 \(D\)의 최댓값이라 하면 \(M_1 \in D\)이고 \(M_2\)가 최대이므로 \(M_1 \le M_2\)이고, 대칭적으로 \(M_2 \le M_1\)이므로 \(M_1 = M_2\)이다 (S13주차의 유일성 얼굴 1). 존재와 유일이 모두 확인되었으므로 \(\gcd(a, b)\)는 well-defined하게 하나의 값을 갖는다.
(b) \(\gcd(0, 0)\). 모든 정수 \(d\)에 대해 \(d \mid 0\)이므로 \(D = \mathbb{Z}\)이고, \(\mathbb{Z}\)는 위로 유계가 아니므로 최댓값이 없다. 곧 위 정의는 입력 \((0, 0)\)에서 값을 주지 못한다. 처리 방법은 둘이다 — ㄱ. 정의역에서 \((0,0)\)을 제외하고 “둘 다 \(0\)은 아니라 하자”를 정의 문장에 명시한다(위에서 택한 방법). ㄴ. \(\gcd(0, 0) = 0\)을 별도로 규정한다. 어느 쪽이든 명시해야 하며, 명시하지 않은 채 두면 정의가 전역적이라는 잘못된 인상을 준다. \(\blacksquare\)
복기. “정의가 모든 입력에서 값을 주는가”는 네 조건에 없는 다섯째 점검이고, 값을 주는 정의에만 붙는다. C15주차에서 \(\gcd\)를 “\(a\)와 \(b\)의 공약수이면서 \(a\)와 \(b\)의 모든 공약수가 나누어떨어뜨리는 음이 아닌 수”로 다시 정의하면 \((0,0)\)에서도 자연히 \(0\)이 나와 예외가 사라진다 — 모든 정수가 \(0\)을 나누므로 \(0\)이 그 조건을 만족하기 때문이다. 나눗셈의 방향을 뒤집어 “모든 공약수를 나누는 수”로 적으면 전혀 다른 것이 되므로(그 조건을 만족하는 음이 아닌 수는 \(1\)이다) 방향을 반드시 지킨다. 정의를 다시 세우는 것이 예외를 없애는 표준 수단이다.
문제 16#
접근. (a)는 세 공리를 진술하고 익숙한 대상 하나에 각각을 검증하는 일이다. (b)는 S13주차 문제 9의 계산을 이항연산으로 옮긴 뒤, 그 결과가 독립성에 대해 무엇을 뜻하는지 한 줄로 적는 것이 몫이다. 계산만 적고 독립성을 언급하지 않으면 이 문제의 절반이다.
풀이. 공리. 집합 \(G\)와 그 위의 이항연산 \(\ast\)에 대해: (G1) 결합 — 모든 \(a, b, c \in G\)에 대해 \((a \ast b) \ast c = a \ast (b \ast c)\). (G2) 항등원 — 모든 \(a \in G\)에 대해 \(e \ast a = a \ast e = a\)인 \(e \in G\)가 존재한다. (G3) 역원 — 각 \(a \in G\)에 대해 \(a \ast a' = a' \ast a = e\)인 \(a' \in G\)가 존재한다.
(a) 무모순성. \(G = \mathbb{Z}\), \(\ast\)를 \(+\)로 둔다. (G1)은 정수 덧셈의 결합법칙이므로 참이고, (G2)는 \(e = 0\)이 \(0 + a = a + 0 = a\)를 만족하므로 참이며, (G3)은 각 \(a\)에 대해 \(a' = -a\)가 \(a + (-a) = (-a) + a = 0\)을 만족하므로 참이다. 세 공리를 전부 만족하는 대상이 존재하므로 군의 공리계는 무모순이다.
(b) 항등원의 유일성은 정리다. \(e_1\), \(e_2\)가 둘 다 (G2)의 항등원이라 하자. \(e_1\)이 항등원이므로 \(a = e_2\)를 넣으면 \(e_1 \ast e_2 = e_2\)이고, \(e_2\)가 항등원이므로 \(a = e_1\)을 넣으면 \(e_1 \ast e_2 = e_1\)이다. 같은 식 \(e_1 \ast e_2\)가 두 값과 같으므로 \(e_1 = e_1 \ast e_2 = e_2\)이다. \(\blacksquare\)
이 유도는 (G2)만 썼으므로 “항등원은 유일하다”는 공리 목록에서 유도되는 명제, 곧 정리다. 이것을 (G4)로 공리 목록에 넣으면 (G4)가 나머지에서 유도되므로 정의 19.4의 ② 독립성이 깨진다. 공리계 설계의 판단은 여기서 나온다 — 유도되는 것은 정리로 두고, 유도되지 않는 최소한만 공리로 둔다. 예제 2.3의 순서 공리계가 A1을 목록에 남겨 두고 최소가 아니게 된 것이 같은 일이다.
복기. S13주차 문제 9의 계산이 글자 하나 바뀌지 않고 그대로 왔다. 그때는 “유일성 증명의 얼굴 1”이라는 기법의 예였고 여기서는 “이 명제는 공리가 아니라 정리다”라는 설계 판단의 근거다. 같은 증명이 놓이는 자리에 따라 다른 일을 한다.
문제 17#
접근. 앞부분은 검사 서식 세 걸음이 그대로 돈다 — 두 표현, 같음의 등식, 값의 같음. 걸음 ③에서 \(a^2 - b^2\)을 \((a-b)(a+b)\)로 인수분해하면 \(n \mid (a-b)\)가 곧바로 쓰인다. 뒷부분은 \(2^{a+n}\)을 \(2^a\)로 묶어 보면 무엇이 더 필요한지가 드러난다.
풀이. \(f\)의 well-definedness. 걸음 ①: 같은 잉여류의 두 표현을 \([a]\)와 \([b]\)로 잡는다. 걸음 ②: \([a] = [b]\)는 \(n \mid (a - b)\), 곧 \(a - b = nk\)인 정수 \(k\)가 존재한다는 것이다. 걸음 ③: 두 값 \([a^2]\)과 \([b^2]\)이 같으려면 \(n \mid (a^2 - b^2)\)이면 되는데,
이고 \(k(a+b)\)는 정수이므로(근거 ②) \(n \mid (a^2 - b^2)\)이다. 따라서 \([a^2] = [b^2]\), 곧 \(f([a]) = f([b])\)이고 \(f\)는 well-defined이다. \(\blacksquare\)
\(g([a]) = [2^a]\)에서 통하지 않는 이유. 같은 서식을 걸면 걸음 ③에서 \(n \mid (2^a - 2^b)\)를 보여야 한다. \(a - b = nk\)이므로 \(a = b + nk\)이고
이다. 이 식이 언제나 \(n\)의 배수인 것은 아니다. \(n = 2\), \(b = 0\), \(k = 1\)로 잡으면 \(a = 2\)이고
인데 \(2 \nmid 3\)이므로 \([2^2] \neq [2^0]\)이다. 곧 \([0] = [2]\)인데 \(g\)가 주는 값은 \([1]\)과 \([0]\)으로 갈린다 — 이것이 문제 9에서 든 반례와 같은 쌍이다. (\(2^b\)가 \(n\)과 서로소인 경우에 한해 갈림의 판정이 \(n \mid \big(2^{nk} - 1\big)\)인지로 좁혀지고, 일반적으로는 \(2^b\) 쪽이 함께 관여하므로 한 줄짜리 필요조건으로 요약할 수 없다. 검사가 요구하는 것은 필요조건의 요약이 아니라 값이 갈리는 쌍 하나이므로, 위 반례로 불통과가 확정된다.)
곧 밑에 붙은 연산(제곱)은 곱셈이 잉여류를 보존하므로 검사가 통과하고, 지수에 붙은 연산은 지수가 잉여류가 아니라 반복 횟수이므로 통과하지 않는다.
복기. 문제 9와 이 문제를 나란히 두면 규칙이 하나 나온다 — 잉여류 위에 정의할 수 있는 연산은 덧셈과 곱셈으로 조립되는 것뿐이다. 제곱은 곱셈의 반복이라 통과하고, 거듭제곱의 지수는 그렇지 않다. C11주차에서 \(\mathbb{Z}_n\)의 연산 목록이 덧셈과 곱셈 둘로 정해지는 이유가 이것이다.
문제 18#
접근. 정리의 증명이 아니라 두 방법이 충돌하지 않는 이유를 적는 문제다. 충돌하지 않는 이유는 한 낱말에 있다 — 모형은 어디에서 만들어지는가. 예제 2.3의 모형 \(\mathbb{R}\)는 순서 공리계 바깥에서 왔고, 그 사실을 “무모순성은 절대적이 아니라 상대적이다”라는 문장으로 옮기면 답이 완성된다.
풀이. 정리의 내용. 페아노 산술을 담을 만큼 강하고 무모순인 공리계 \(T\)에 대해, “\(T\)는 무모순이다”라는 명제를 \(T\)의 언어로 적을 수 있지만 그 명제를 \(T\) 안에서 증명할 수는 없다. 곧 어떤 이론도 자기 지반의 안전을 자기 힘으로 보증하지 못한다.
모형 방법과의 공존. 예제 2.3에서 순서 공리계의 무모순성을 보증한 것은 \(S = \mathbb{R}\), \(\prec\) = \(<\)라는 모형이었는데, 이 모형은 순서 공리계 안에서 만들어진 것이 아니다. 실수 전체가 존재한다는 것과 그 위의 부등호가 세 공리를 만족한다는 것은 순서 공리계보다 강한 이론(집합론 ZFC)에서 나온다. 곧 그 논증이 실제로 보인 것은 “순서 공리계는 무모순이다”가 아니라 **”ZFC가 무모순이면 순서 공리계도 무모순이다”**이다.
두 방법이 충돌하지 않는 이유가 여기 있다. 모형 방법이 주는 것은 언제나 상대적 무모순성이고, 괴델이 금지한 것은 절대적 무모순성을 이론 내부에서 증명하는 일이다. 서로 다른 것을 말하므로 공존한다. 대신 상대적 무모순성의 사슬은 위로 계속 올라가고 어딘가에서 끝나야 하는데, 가장 아래의 이론에 대해서는 증명이 아니라 정합성과 오랜 사용 경험으로 받아들이는 수밖에 없다.
복기. 이 구조가 §1.3의 층 삭제 실험과 같다. 근거의 사슬은 유한 번에 끊어야 하고, 끊는 자리가 공리다. 무모순성의 사슬도 유한 번에 끊어야 하고, 끊는 자리에는 증명이 아니라 수용이 놓인다. 만드는 쪽의 책임은 그 수용의 자리가 어디인지를 밝히는 데까지이며, 그 너머는 증명의 문제가 아니다.
문제 19#
접근. 정의 짓기와 정리 증명을 한 답안에 담는 문제이므로 순서를 지킨다 — 정의 \(\to\) 네 조건 \(\to\) 정리 진술 \(\to\) 증명. 예시를 따라간다면 증명은 세 걸음이다. 수렴의 정의에 \(\varepsilon = 1\)을 넣어 꼬리가 유계임을 얻고, 머리는 유한 개이므로 최댓값을 잡고, 둘을 합친다.
풀이 (예시). 정의. 수열 \((a_n)\)이 유계라 함은, 모든 \(n\)에 대해 \(\lvert a_n \rvert \le M\)인 실수 \(M\)이 존재하는 것이다.
① 명확성. 조건은 “\(\exists M \forall n\)” 꼴이고 애매어가 없으며, 이름 “유계”도 조건(경계 \(M\)이 있다)과 어긋나지 않는다. 양화사가 \(\exists\)이 바깥에 있으므로 후진면은 구성법이다 — \(M\)을 하나 만들어 제시해야 한다. ② 무순환. 조건이 쓰는 용어는 실수\(\cdot\)절댓값\(\cdot\)부등호\(\cdot\)수열의 항뿐이고 유계를 쓰지 않는다. ③ well-defined. 값이 아니라 성질을 주므로 자동 통과한다. ④ 비공허\(\cdot\)비자명. 비공허: \(a_n = \frac1n\)은 \(M = 1\)로 유계다. 비자명: \(a_n = n\)은 유계가 아니다 — 어떤 \(M\)을 잡아도 \(n > M\)인 \(n\)에서 조건이 깨진다.
정리. 수렴하는 수열은 유계이다.
증명. \(a_n \to L\)이라 하자. 수렴의 정의에 \(\varepsilon = 1\)을 특수화하면 (\(1 > 0\)이므로 자격이 성립한다), \(n > N\)인 모든 \(n\)에 대해 \(\lvert a_n - L \rvert < 1\)인 자연수 \(N\)이 존재한다(S7주차 문제 11). 절댓값의 뜻에 의해 이것은 \(-1 < a_n - L < 1\)이고, 양변에 \(L\)을 더하면 \(L - 1 < a_n < L + 1\)이다(근거 ③, 1권 16주차 (W2)). 한편 \(L \le \lvert L \rvert\)이고 \(-\lvert L \rvert \le L\)이므로 \(a_n < \lvert L \rvert + 1\)이고 \(a_n > -\lvert L \rvert - 1\)이며, 따라서 \(n > N\)인 모든 \(n\)에 대해 \(\lvert a_n \rvert < \lvert L \rvert + 1\)이다. 여기까지 쓴 것은 (W2)와 절댓값의 뜻뿐이다. 한편 \(\lvert a_1 \rvert, \dots, \lvert a_N \rvert\)은 유한 개이고 비어 있지 않으므로 \(K = \max\{\lvert a_1 \rvert, \dots, \lvert a_N \rvert\}\)가 존재한다(근거 ④의 “유한하고 비어 있지 않은 실수 집합에 최댓값이 존재함”). 이제 \(M = \max\{K,\ \lvert L \rvert + 1\}\)로 두면, \(n \le N\)인 \(n\)에서는 \(\lvert a_n \rvert \le K \le M\)이고 \(n > N\)인 \(n\)에서는 \(\lvert a_n \rvert < \lvert L \rvert + 1 \le M\)이므로, 모든 \(n\)에 대해 \(\lvert a_n \rvert \le M\)이다. 따라서 \((a_n)\)은 유계이다. \(\blacksquare\)
복기. 정의를 짓는 일과 정리를 증명하는 일이 한 답안에서 만나면 정의의 후진면이 증명의 마지막 줄을 정한다 — 유계의 후진면이 구성법이었으므로 증명은 \(M\)을 실제로 만들어 제시하는 것으로 끝난다. 정의를 지을 때 후진면을 적어 두면 그 정의로 쓸 증명의 마지막 줄이 미리 정해진다.
문제 20#
접근. (a)는 세 줄을 “이전에는 …로 했고 이번 주에는 … 검사로 이름이 붙었다” 꼴로 적는다. (b)는 확인 12의 답이 출발점이다 — 무제한 내포 공리가 쓰는 쪽에서 어떻게 보였고 세우는 쪽에서 무엇이 되는지를 가른다.
풀이 (예시 답안).
(a) 무순환은 S4주차의 “정의는 더 원초적인 것으로 환원된다”가 이름을 바꾼 것이다. 그때는 정의를 읽어 조건을 아래층으로 푸는 일이었고, 이번 주에는 내가 쓴 조건이 아래층으로 끝까지 내려가는지를 검사하는 일이 되었다 — 정의 19.1의 층위가 그 검사의 기준이다.
well-def는 S13주차의 유일성이 이름을 바꾼 것이다. “표현이 달라도 값이 하나”는 “그 값이 유일하다”와 같은 주장이고, 실제로 문제 15에서 최댓값의 유일성을 보인 계산이 \(\gcd\)가 하나의 값을 갖는 근거였다. 유일성이 정리의 결론이던 자리에서 정의의 성립 조건으로 옮겨 앉았다.
무모순은 S11주차 귀류의 기반이 이름을 바꾼 것이다. 귀류는 모순 하나로 명제를 확정하는 기법이고, 그것이 작동하려면 이론 자체에 모순이 없어야 한다 — 모순된 이론에서는 모든 명제가 증명되므로 귀류가 아무것도 배제하지 못한다. 기법의 암묵적 전제이던 것이 공리계 전체의 검사 항목이 되었다.
(b) 무제한 내포 공리는 쓰는 쪽에서 볼 때 편리한 표기 규칙일 뿐이다 — 조건을 적으면 집합이 생기므로 집합을 만들 때마다 근거를 대지 않아도 된다. 세우는 쪽에서 보면 같은 공리가 이론 전체의 무모순성을 건 선언이 되고, 러셀 집합 하나가 그 선언을 깨뜨려 이론 전체를 무너뜨린다. 편리함은 쓰는 쪽에 돌아가고 그 편리함이 가능한지에 대한 책임은 세우는 쪽에 남는데, 읽기만 할 때는 그 책임이 이미 치러졌다는 사실 자체가 보이지 않는다.
복기. 이번 주의 세 검사는 새 개념이 아니라 이미 손에 있던 것들의 재배치다. 그래서 백지 재현에서 세 검사를 각각의 출처(S4주차\(\cdot\)S13주차\(\cdot\)S11주차)와 함께 적으면 목록이 훨씬 잘 복구된다.
다음 주 예고 (S20주차). 1학기의 마지막 주다. Solow 부록 A~D의 네 분야 — 집합론, 실해석, 정수론, 그래프이론 — 에서 실제 증명을 하나씩 골라 S17주차의 결정 나무로 해부한다. 어느 줄이 어떤 기법의 산물인지 줄마다 지목하는 훈련이고, 그 위에 1학기 전체를 묶는 수료 시험이 얹힌다. 이번 주에 만든 정의와 공리는 그 부록의 증명들이 딛고 선 지반이므로, 해부할 때 “이 증명이 인용하는 정의는 어느 층에서 왔는가”를 함께 묻게 된다. 원서 부록 A~D를 훑고 온다.