28주차 · 강의 — 예제 · 연습 · 해설#
예제 — 세 자료형의 증명을 함께 만들기#
완성된 증명을 먼저 보이지 않는다. 백지에서 시작해 한 줄씩 만든다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다.
예제 2.1 — 곱의 분배법칙#
명제. \(A \times (B \cap C) = (A \times B) \cap (A \times C)\).
설계 — 쓰기 전에 정하는 두 가지. 원소의 자료형을 먼저 정하고, 양변을 논리식으로 번역해 출발점과 도착점을 나란히 놓는다.
말 |
논리식 번역 |
|
|---|---|---|
원소의 자료형 |
양변의 원소 |
순서쌍 \((x, y)\) |
출발점 (좌변) |
\((x,y) \in A \times (B \cap C)\) |
\(x \in A \land (y \in B \land y \in C)\) |
도착점 (우변) |
\((x,y) \in (A \times B) \cap (A \times C)\) |
\(\underline{\quad(?)\quad}\) |
확인 13. 우변 칸의 빈칸을 채워 보자. 어떤 정의를 어떤 순서로 쓰는가.
답
\((x \in A \land y \in B) \land (x \in A \land y \in C)\). 먼저 교집합의 정의(정의 5.1)로
“\((x,y) \in A \times B\)이고 \((x,y) \in A \times C\)”로 나눈 뒤, 각 조각에 정의 28.1을
적용한다. 출발점과 도착점을 나란히 놓으면 할 일이 드러난다 — 좌변에는 \(x \in A\)가
한 번, 우변에는 두 번 나온다. 그 개수 차이를 메우는 것이 이 증명의 전부다.
1단계 — 원소를 잡는다. 잡을 것은 \(x\) 하나가 아니다.
확인 14. 첫 문장을 완성해 보자: “임의의 \(\underline{\qquad}\)에 대해 …”
답
“임의의 순서쌍 \((x, y)\)에 대해.” 파트를 나눠 “(\(\subseteq\)) \((x,y) \in A \times (B \cap C)\)라
하자”로 열어도 같다. 어느 쪽이든 잡는 것은 성분 둘을 가진 \((x, y)\)이며, §1.1의 붕괴를
막는 조각이 이 한 문장에 들어 있다. 아래에서는 모든 단계가 \(\iff\)이므로 27주차 §1.6의
동치 사슬 서식을 쓴다.
2단계 — 좌변을 번역한다. 근거가 둘이므로 줄도 둘로 나눈다.
확인 15. 둘째 문장을 완성해 보자:
“\((x,y) \in A \times (B \cap C) \iff x \in A \land \underline{\quad}\)이고, 안쪽을 한 번 더
번역하면 \(\iff x \in A \land (\underline{\quad} \land \underline{\quad})\)이다.”
답
\(y \in B \cap C\) / \(y \in B\) / \(y \in C\). 첫 동치의 근거는 정의 28.1(곱), 둘째 동치의
근거는 정의 5.1(교집합)이다. 한 줄에 몰아 적어도 되지만, 각 줄에 근거 하나가 원칙이다.
3단계 — 논리 법칙으로 조작한다. 여기가 이 증명에서 유일하게 내용이 있는 줄이다. \(P\)를 “\(x \in A\)”, \(Q\)를 “\(y \in B\)”, \(R\)을 “\(y \in C\)”로 두면 손에 든 것은 \(P \land (Q \land R)\), 만들 것은 \((P \land Q) \land (P \land R)\)이다.
확인 16. \(P\)가 왼쪽에 한 번, 오른쪽에 두 번 나온다. 이 개수 차이를 메우는 동치는
무엇이고, 그 뒤에 필요한 조작은 무엇인가.
답
§1.7에서 등록한 멱등 \(P \equiv P \land P\)가 \(P\)를 복제한다. 그러면
\(P \land (Q \land R) \equiv (P \land P) \land (Q \land R)\)이고, \(\land\)의 교환\(\cdot\)결합으로
순서를 바꾸면 \((P \land Q) \land (P \land R)\)이 된다. \(\land\)로 이어진 조건들은 몇 번
적히든 순서가 어떻든 같은 요구이므로, 복제와 재배열은 진리값을 바꾸지 않는다 —
그래서 이 단계도 \(\iff\)다.
4단계 — 역번역해 집합 표현으로 되돌린다.
확인 17. 마지막 두 동치를 완성해 보자:
“\((x \in A \land y \in B) \land (x \in A \land y \in C) \iff \underline{\qquad} \iff (x,y) \in \underline{\qquad}\)”
답
“\(\iff (x,y) \in A \times B \land (x,y) \in A \times C \iff (x,y) \in (A \times B) \cap (A \times C)\).”
정의 28.1을 두 번, 정의 5.1을 한 번 거꾸로 쓴 것이다. 사슬의 모든 단계가 \(\iff\)이므로
왼쪽에서 오른쪽으로 읽으면 (\(\subseteq\)), 오른쪽에서 왼쪽으로 읽으면 (\(\supseteq\))이
되고, 정의 27.1에 의해 상등이 선언된다.
완성본. 방금 만든 문장들을 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 “왜?”에 스스로 답해 본다.
증명의 한 줄 |
왜 이 줄을 쓰는가? |
|---|---|
임의의 순서쌍 \((x, y)\)에 대해 동치 사슬로 보인다. |
원소가 순서쌍임을 선언한다 — 오프닝의 교체가 이 증명의 출발점이다. |
\((x,y) \in A \times (B \cap C) \iff x \in A \land (y \in B \land y \in C)\) |
곱의 정의(정의 28.1)와 교집합의 정의(정의 5.1)를 차례로 쓴 번역(근거 ①). |
\(\iff (x \in A \land y \in B) \land (x \in A \land y \in C)\) |
멱등으로 \(x \in A\)를 복제하고 \(\land\)의 교환\(\cdot\)결합으로 재배열한다(근거 ④). |
\(\iff (x,y) \in A \times B \land (x,y) \in A \times C\) |
정의 28.1을 두 조각에 거꾸로 적용한 역번역(근거 ①). |
\(\iff (x,y) \in (A \times B) \cap (A \times C)\) |
교집합의 정의로 되돌린다. 모든 단계가 \(\iff\)이므로 상등이다(정의 27.1). \(\blacksquare\) |
이 다섯 줄이 “임의의” 집합을 처리하는 이유. \(A = \{1\}\), \(B = \{2, 3\}\), \(C = \{3, 4\}\)를 넣어 읽어 보자. \(B \cap C = \{3\}\)이므로 좌변은 \(\{(1,3)\}\)이고, \(A \times B = \{(1,2),(1,3)\}\), \(A \times C = \{(1,3),(1,4)\}\)이므로 우변도 \(\{(1,3)\}\)이다.
확인 18. 위 대입에서 \((x, y) = (1, 3)\)을 잡으면 완성본의 각 줄이 어떤 문장이 되는가.
둘째 줄부터 따라 읽어 보자.
답
“\((1,3) \in \{1\} \times \{3\} \iff 1 \in \{1\} \land (3 \in \{2,3\} \land 3 \in \{3,4\})\)”
\(\to\) “\(\iff (1 \in \{1\} \land 3 \in \{2,3\}) \land (1 \in \{1\} \land 3 \in \{3,4\})\)”
\(\to\) “\(\iff (1,3) \in A \times B \land (1,3) \in A \times C\)”. 모든 줄이 그대로 성립한다.
증명의 어느 줄도 \(x\)가 1이라는 사실이나 \(B\)가 \(\{2,3\}\)이라는 사실을 쓰지 않았으므로,
같은 다섯 줄이 어떤 집합 조합에도 그대로 작동한다.
예제 2.2 — 멱집합 iff (4주차 문제 16의 완성)#
명제. \(A \subseteq B \iff \mathcal{P}(A) \subseteq \mathcal{P}(B)\).
이번에는 설계만 함께 하고, 본문은 완성본으로 본다. 목표가 iff이므로 의무가 둘이고, 방향마다 손에 드는 것과 만들 것이 다르다.
확인 19. 번역표를 채워 보자.
(\(\Rightarrow\)) 첫 문장은 “\(\underline{\quad}\)라 하자”이고, 정의 28.2로 번역하면
\(\underline{\quad}\)를 손에 넣는다.
(\(\Leftarrow\)) 가정 \(\mathcal{P}(A) \subseteq \mathcal{P}(B)\)를 쓰려면 \(\mathcal{P}(A)\)의
원소를 하나 제시해야 한다. 어떤 집합을 제시하는가.
답
(\(\Rightarrow\)) 첫 문장은 “\(X \in \mathcal{P}(A)\)라 하자”이고, 정의 28.2로 \(X \subseteq A\)를
손에 넣는다. 가정 \(A \subseteq B\)와 부분집합의 추이성(4주차 훈련 1)을 이으면
\(X \subseteq B\)가 되고, 정의 28.2를 거꾸로 써서 \(X \in \mathcal{P}(B)\)로 닫는다.
(\(\Leftarrow\)) 제시하는 집합은 \(A\) 자신이다. \(A \subseteq A\)이므로(4주차 §1.3)
\(A \in \mathcal{P}(A)\)이고, 가정을 적용하면 \(A \in \mathcal{P}(B)\), 곧 \(A \subseteq B\)가
곧바로 나온다. 원소 추적이 필요 없는 방향이다.
증명.
(\(\Rightarrow\)) \(A \subseteq B\)라 가정하자. \(X \in \mathcal{P}(A)\)라 하자. 정의 28.2에 의해 \(X \subseteq A\)이고, 가정에 의해 \(A \subseteq B\)이므로, 부분집합의 추이성에 의해 \(X \subseteq B\)이다. 다시 정의 28.2에 의해 \(X \in \mathcal{P}(B)\)이다. 따라서 \(\mathcal{P}(A) \subseteq \mathcal{P}(B)\)이다.
(\(\Leftarrow\)) \(\mathcal{P}(A) \subseteq \mathcal{P}(B)\)라 가정하자. \(A \subseteq A\)이므로 정의 28.2에 의해 \(A \in \mathcal{P}(A)\)이고, 가정에 의해 \(A \in \mathcal{P}(B)\)이다. 다시 정의 28.2에 의해 \(A \subseteq B\)이다.
양방향이 모두 성립하므로 \(A \subseteq B \iff \mathcal{P}(A) \subseteq \mathcal{P}(B)\)이다. \(\blacksquare\)
관찰. (\(\Leftarrow\))에서 제시한 원소는 \(A\) 자신이다. “자기 자신도 부분집합”(4주차 §1.3)이라는 한 줄짜리 관찰이 여기서 가정을 발동시키는 유일한 열쇠가 되었다. 멱집합이 낀 명제에서 손에 든 가정이 포함 관계뿐일 때는, 어떤 집합을 \(\mathcal{P}(A)\)의 원소로 제시할지가 증명의 전부다.
예제 2.3 — 첨자 드모르간#
명제. \(\left(\bigcup_{i \in I} A_i\right)^{\!c} = \bigcap_{i \in I} A_i^{\,c}\).
이번에는 설계부터 스스로 해 보자. 앞의 두 예제와 달리 무한할 수 있는 첨자를 다루므로, 개수를 세지 않는 도구만 써야 한다.
확인 20. (\(\subseteq\))의 출발점 \(x \in \big(\bigcup_{i \in I} A_i\big)^c\)와 도착점
\(x \in \bigcap_{i \in I} A_i^{\,c}\)를 각각 논리식으로 번역하면 무엇인가. 둘을 잇는
11주차 규칙의 이름은 무엇인가.
답
출발점: 정의 5.2로 \(\neg\big(x \in \bigcup_{i \in I} A_i\big)\), 정의 28.3으로
\(\neg\big(\exists i \in I,\ x \in A_i\big)\). 도착점: 정의 28.3과 정의 5.2로
\(\forall i \in I,\ x \notin A_i\). 잇는 규칙은 \(\neg\exists \leadsto \forall\neg\)
(11주차 부정 총목록 5행)이다. 번역해 놓고 보면 증명할 것이 이 규칙 하나뿐임이
드러난다 — 27주차 예제 2.1이 드모르간 2 하나로 닫힌 것과 같은 모양이고, 유한이
무한으로 바뀌면서 법칙의 이름만 교체되었다.
증명. 임의의 \(x\)에 대해
첫 동치는 여집합의 정의와 정의 28.3(근거 ①), 둘째 동치는 양화사 부정 \(\neg\exists \leadsto \forall\neg\)(근거 ④, 11주차), 셋째는 여집합의 정의를 거꾸로 쓴 것, 넷째는 정의 28.3을 거꾸로 쓴 것이다. 모든 단계가 \(\iff\)이므로 두 집합은 같다. \(\blacksquare\)
이번 증명은 표 없이 산문과 사슬로 적었다. 표는 연습 단계의 장치이고, 실전의 증명은 처음부터 끝까지 이런 산문이다.
검산. \(I = \{1, 2\}\)로 두면 위 등식은 \((A_1 \cup A_2)^c = A_1^{\,c} \cap A_2^{\,c}\) — 27주차 예제 2.1에서 이미 증명한 2집합 드모르간이다. 무한 버전이 유한 버전을 특수 경우로 포함한다.
관찰 — 세 예제의 같은 뼈대#
예제 2.1, 2.2, 2.3은 소재만 다를 뿐 뼈대가 같다. 대응표의 빈칸을 채워 보자.
단계 |
예제 2.1 (곱) |
예제 2.3 (첨자) |
|---|---|---|
① 원소의 자료형 확인 |
순서쌍 \((x, y)\) |
\(\underline{\quad(1)\quad}\) |
② 원소 잡기 |
임의의 \((x,y)\)에 대해 |
임의의 \(x\)에 대해 |
③ 정의로 번역 |
정의 28.1 + 정의 5.1 |
정의 5.2 + 정의 28.3 |
④ 내용 있는 한 수 |
멱등 + \(\land\)의 재배열 |
\(\underline{\quad(2)\quad}\) |
⑤ 역번역\(\cdot\)종합 |
\((x,y) \in (A \times B) \cap (A \times C)\) |
\(\underline{\quad(3)\quad}\) |
확인 21. 빈칸 (1)(2)(3)을 채워 보자. 예제 2.2는 이 표의 어느 칸이 비어 있는 유형인가.
답
(1) 보통 원소 \(x\) (2) 양화사 부정 \(\neg\exists \leadsto \forall\neg\)의 인용
(3) \(x \in \bigcap_{i \in I} A_i^{\,c}\). 예제 2.2는 ②가 비어 있는 유형이다 —
(\(\Leftarrow\)) 방향에서는 원소를 잡는 대신 원소 \(A\)를 제시했다. 세 예제의 차이는
①\(\cdot\)④와, 예제 2.2의 (\(\Leftarrow\))에서 ②가 ‘잡기’가 아니라 ‘제시’로 바뀐 것뿐이고,
③과 ⑤는 어느 예제에서나 정의를 정방향\(\cdot\)역방향으로 쓰는 같은 동작이다.
방금 확인한 뼈대에 이름을 붙인다.
백지 암기 대상
자료형별 원소 추적의 틀
① 왼쪽 집합의 원소가 무엇인지 정한다(순서쌍 / 집합 / 보통 원소) \(\to\) ② 그 자료형에 맞는 이름으로 원소를 잡는다(\((x,y)\) / \(X\) / \(x\)) \(\to\) ③ 정의 28.1~28.3으로 번역한다 \(\to\) ④ 논리 법칙(멱등\(\cdot\)분배\(\cdot\)드모르간\(\cdot\)양화사 부정)을 인용하거나 증인을 제시한다 \(\to\) ⑤ 정의를 거꾸로 써서 역번역하고 종합을 선언한다
27주차의 틀에서 바뀐 칸은 ①과 ②뿐이다. 이 틀은 37주차의 동치류, 44주차의 상과 원상에서 자료형만 갈아 끼운 채 다시 쓰인다.
빈칸 사다리 — 지지대를 하나씩 빼며#
필사에서 자립으로 넘어가는 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 해설(§6)에 있다 — 다 채운 뒤에 대조한다.
훈련 1 ●○○ — 수식 빈칸#
명제. \(A \subseteq C\)이고 \(B \subseteq D\)이면 \(A \times B \subseteq C \times D\)이다.
증명. \(A \subseteq C\), \(B \subseteq D\)라 가정하자. \(\underline{\quad(1)\quad} \in A \times B\)라 하자. 곱의 정의(정의 28.1)에 의해 \(x \in A\)이고 \(y \in \underline{\quad(2)\quad}\)이다. 가정에 의해 \(x \in C\)이고 \(y \in D\)이다. 다시 정의 28.1에 의해 \((x, y) \in \underline{\quad(3)\quad}\)이다. 따라서 \(A \times B \subseteq C \times D\)이다. \(\blacksquare\)
훈련 2 ●●○ — 수식과 근거를 함께#
이번에는 근거의 이름도 빈칸이다.
명제. \(\mathcal{P}(A \cap B) \subseteq \mathcal{P}(A)\).
증명. \(\underline{\quad(1)\quad} \in \mathcal{P}(A \cap B)\)라 하자. \(\underline{\quad(2)\quad}\)에 의해 \(X \subseteq A \cap B\)이다. 한편 \(x \in A \cap B\)이면 \(\underline{\quad(3)\quad}\)의 정의에 의해 \(x \in A\)이므로 \(A \cap B \subseteq A\)이다. 따라서 \(\underline{\quad(4)\quad}\)에 의해 \(X \subseteq A\)이고, 다시 \(\underline{\quad(5)\quad}\)에 의해 \(X \in \mathcal{P}(A)\)이다. \(\blacksquare\)
훈련 3 ●●● — 뼈대만 남기고#
명제. \(j \in I\)가 고정된 첨자일 때 \(\bigcap_{i \in I} A_i \subseteq A_j\)이다.
증명의 뼈대. 각 칸을 통째로 채운다. 목표가 포함이므로 파트는 하나이고, 번역하면 \(\forall\)이 나오므로 “고른 하나에 적용하기”가 필요하다.
① 원소 잡기: \(\underline{\quad(1)\quad}\)
② 정의로 번역: \(\underline{\quad(2)\quad}\)
③ 고른 첨자에 적용하고 마무리: \(\underline{\quad(3)\quad}\)
(이 훈련이 문제 12(b)와 문제 16의 예행연습이다 — 두 문제 모두 \(\forall\)을 잘 고른 첨자 하나에 적용하지만, 거기서 얻는 것은 결론이 아니라 모순이다.)
연습문제 (20문항)#
해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 ‘접근’까지만 읽고 다시 시도한다 \(\to\) 그래도 안 되면 풀이를 읽는다. 증명 문제는 첫 문장을 쓰기 전에 “왼쪽 집합의 원소는 무엇인가”부터 정한다(§1.6).
이번 주의 채점 기준
답이 아니라 근거가 점수다. “\(A \times (B \cap C) = (A \times B) \cap (A \times C)\)는
참(맞음)”은 0점이고, 원소의 자료형을 밝힌 오프닝과 각 줄에 붙은 정의\(\cdot\)법칙 이름이
만점이다. 특히 순서쌍이 낀 문제에서 “\(x \in A \times B\)라 하자”로 시작한 답안은 이후
줄의 내용과 무관하게 첫 줄에서 이미 무효다 — §1.3의 삭제 실험 ①이 그 이유다.
힌트 상자는 5분 이상 막힌 뒤에만 연다.
기본 ●○○#
1. [백지] 순서쌍 추적\(\cdot\)멱집합 추적\(\cdot\)첨자 번역(\(\exists\)/\(\forall\))의 세 가지 번역 규칙을 쓰시오.
힌트
§1.6의 표를 덮고 각 줄의 왼쪽 집합의 꼴부터 떠올린다. 꼴이 정해지면 원소의
자료형이 정해지고, 자료형이 번역 규칙을 하나로 정한다.
2. \(A \times \emptyset = \emptyset\)임을 증명하시오. (힌트: 원소 \((x,y)\)가 있다고 하면 \(y\)는 어디에?)
힌트
“이 집합은 공집합이다”를 보이는 서식은 6주차 문제 19와 같다 — 원소가 하나 있다고
가정하고 모순을 끌어낸다. 잡을 원소가 순서쌍이라는 점만 다르다.
3. 빈칸 훈련(\(A \subseteq C, B \subseteq D \Rightarrow A \times B \subseteq C \times D\))을 백지에서 완성하시오.
힌트
빈칸을 외워 채우려 하지 말고 §1.6의 순서로 재구성한다: 자료형 \(\to\) 오프닝 \(\to\) 정의
28.1로 성분 분해 \(\to\) 가정을 성분마다 한 번씩 적용 \(\to\) 정의 28.1로 재조립.
4. 예제 2.1을 백지에 재현하시오.
힌트
다섯 줄 중 실제로 내용이 있는 줄은 셋째 하나다. 그 줄에서 무엇을 복제하고 무엇을
재배열하는지부터 떠올리면 나머지는 번역과 역번역으로 채워진다.
5. \(\{9^n : n \in \mathbb{N}\} \subseteq \{3^n : n \in \mathbb{N}\}\)임을 증명하고, 두 집합이 같지 않음을 원소 하나로 보이시오.
힌트
앞부분은 생성형 집합의 포함이므로 증인 제작이다(27주차 예제 2.3) — \(9\)를 \(3\)의
거듭제곱으로 고쳐 쓰면 증인이 보인다. 뒷부분은 오른쪽에만 있는 원소를 하나 지목하고,
그것이 왼쪽에 없음을 크기 비교로 확인한다.
6. \(A = \{1, 2\}\), \(B = \{2, 3\}\)에 대해 \(\mathcal{P}(A) \cap \mathcal{P}(B)\)와 \(\mathcal{P}(A \cap B)\)를 각각 나열해 일치를 확인하시오 (4주차 문제 19의 수치 재방문 — 다음 문제의 실험).
힌트
멱집합을 나열할 때는 크기 0부터 순서대로 적는다 — \(\emptyset\), 원소 하나짜리, 원소
둘짜리. \(|A| = 2\)이므로 \(|\mathcal{P}(A)| = 2^2 = 4\)개가 나와야 한다(개수 공식은 지금은
인정하고 쓴다 — 31주차에서 증명).
표준 ●●○#
7. \((A \cup B) \times C = (A \times C) \cup (B \times C)\)를 증명하시오.
힌트
예제 2.1과 같은 사슬이다. 좌변을 번역하면 \((\cdot \lor \cdot) \land \cdot\) 꼴, 우변을
번역하면 \((\cdot \land \cdot) \lor (\cdot \land \cdot)\) 꼴이 된다. 두 꼴을 잇는 9주차
목록의 법칙 이름을 찾는 것이 전부다.
8. \(\mathcal{P}(A \cap B) = \mathcal{P}(A) \cap \mathcal{P}(B)\)를 증명하시오. (힌트: \(X \subseteq A \cap B \iff X \subseteq A \land X \subseteq B\)라는 보조 iff부터 — 양방향 각각 원소 추적)
힌트
보조 iff를 먼저 증명해 두면 본 증명은 정의 28.2를 양쪽에 씌우는 사슬 한 줄로 끝난다.
보조 iff의 (\(\Rightarrow\))는 \(x \in X\)를 잡아 한 번 추적하면 두 결론이 동시에 나온다.
9. \(\mathcal{P}(A) \cup \mathcal{P}(B) \subseteq \mathcal{P}(A \cup B)\)를 증명하고, 역포함이 일반적으로 거짓임을 반례로 보이시오 (4주차 문제 19).
힌트
오프닝은 “\(X \in \mathcal{P}(A) \cup \mathcal{P}(B)\)라 하자”이고, 합집합의 정의에서
“또는”이 나오므로 경우를 나눈다. 반례는 문제 6의 두 집합에서 한쪽에도 통째로
들어가지 않는 부분집합을 하나 고르면 된다.
10. 예제 2.2(\(A \subseteq B \iff \mathcal{P}(A) \subseteq \mathcal{P}(B)\))를 백지에 재현하시오.
11. \(A \times (B - C) = (A \times B) - (A \times C)\)를 증명하시오. (우변의 번역에 드모르간이 한 번 필요하다: \(\neg(x \in A \land y \in C)\) — 그런데 \(x \in A\)가 이미 확보된 문맥이다.)
힌트
사슬로 밀기보다 양방향 포함으로 나눠 쓰는 편이 안전하다. (\(\supseteq\)) 방향에서
드모르간 1로 갈래가 둘 생기는데, 그중 하나는 이미 손에 든 사실과 어긋나므로 남는
갈래가 하나뿐이다.
첨자족이 낀 상등을 증명하는 법 — 문제 12\(\cdot\)13\(\cdot\)16에서 쓴다
첨자족의 상등도 서식은 정의 27.1 그대로 양방향 포함이다. 달라지는 것은 각 방향의
몸통이다. \(\bigcup\) 쪽으로 들어가려면 \(\exists\)를 만들어야 하므로 **첨자 하나를
제시**하고, \(\bigcap\) 쪽에서 나오려면 \(\forall\)을 쓰는 것이므로 **첨자 하나를 골라
적용**한다(훈련 3). 반대로 \(\bigcap\)이 공집합임을 보이려면 \(\forall\)을 무너뜨려야
하므로, 잘 고른 첨자 하나에서 탈락함을 보이면 충분하다.
12. \(n \in \mathbb{N}\)에 대해 \(A_n = \{n, n+1\}\)이라 하자. (a) \(\bigcup_{n \in \mathbb{N}} A_n = \mathbb{N}\)임을 증명하시오. (b) \(\bigcap_{n \in \mathbb{N}} A_n = \emptyset\)임을 증명하시오.
힌트
(a)의 (\(\supseteq\))에서 \(m \in \mathbb{N}\)을 잡았을 때 제시할 첨자는 \(m\) 자신이다 —
\(m \in A_m\)인지 확인해 본다. (b)는 위 상자의 마지막 문장이다. 후보 \(x\)를 \(A_1\)에서
먼저 가둔 뒤, 그 후보가 탈락하는 첨자를 하나 지목한다.
13. 첨자 드모르간의 짝 \(\left(\bigcap_{i \in I} A_i\right)^{c} = \bigcup_{i \in I} A_i^{\,c}\)를 예제 2.3의 방법으로 증명하시오.
조건제시 집합의 상등 — 문제 14에서 쓴다
\(\{f(a, b) : a, b \in \mathbb{Z}\}\) 꼴의 집합은 원소가 “그 식으로 표현 가능한 수” 전부다.
따라서 소속 판정은 존재 명제이고, 각 방향의 몸통은 증인 제작이다(27주차 예제 2.3).
매개변수가 둘이면 증인도 둘 — 한 방향에서는 받은 \(a, b\)로 새 증인 하나를 만들고,
반대 방향에서는 받은 \(k\)로 증인 두 개를 만든다.
14. \(\{12a + 4b : a, b \in \mathbb{Z}\} = \{4k : k \in \mathbb{Z}\}\)임을 증명하시오. (각 방향 모두 증인 제작)
도전 ●●●#
새 도구 — 비어 있지 않은 집합에서 원소 하나 꺼내 쓰기
“\(B \neq \emptyset\)”이라는 가정은 그 자체로는 아무 등식도 주지 않는다. 쓰는 방법은
하나뿐이다 — 원소가 없지 않다는 뜻이므로 \(y \in B\)인 \(y\)가 존재한다고 선언하고
그 \(y\)를 이름으로 받아 쓴다. 이렇게 받은 \(y\)에 대해서는 “\(y \in B\)”라는 사실 하나만
쓸 수 있고, 그 밖의 성질은 아무것도 가정하지 않는다. 문제 15\(\cdot\)17\(\cdot\)18이 전부 이 한
동작에 걸려 있다.
15. \(A, B\)가 공집합이 아닐 때, \(A \times B = B \times A \iff A = B\)임을 증명하시오. ((\(\Leftarrow\))는 대입. (\(\Rightarrow\)): \(x \in A\)라 하자 — \(B\)의 원소 \(y\)를 하나 꺼내(\(B \neq \emptyset\)을 여기서 쓴다) \((x, y)\)를 추적하시오.)
힌트
(\(\Rightarrow\))에서 만든 순서쌍 \((x, y)\)는 \(A \times B\)에 있고, 가정에 의해 \(B \times A\)에도
있다. 같은 순서쌍을 \(B \times A\)의 기준으로 다시 읽으면 첫 성분에 대해 무엇을
알게 되는가.
지금은 증명 없이 인정하고 쓰는 사실 — 아르키메데스 성질 (45주차에서 공식 채택)
임의의 실수 \(x > 0\)에 대해 \(\frac{1}{n} < x\)인 자연수 \(n\)이 존재한다. 실수 세계의
성질이므로 지금까지의 근거 ①~④만으로는 유도되지 않는다. 문제 16에서 이 사실을
인정하고 쓰며, 45주차에서 공식 채택한다.
16. \(\bigcap_{n \in \mathbb{N}} \left[0, \tfrac{1}{n}\right] = \{0\}\)임을 증명하시오. (6주차 예제 2.3의 승격. 사용 가능 사실: 임의의 실수 \(x > 0\)에 대해 \(\tfrac{1}{n} < x\)인 자연수 \(n\)이 존재한다 — 아르키메데스 성질. 양방향 포함으로: \(\supseteq\)는 \(0\)의 검증, \(\subseteq\)는 \(x > 0\)인 원소의 배제)
힌트
(\(\subseteq\))에서 잡은 \(x\)에 대해 먼저 \(x \ge 0\)을 확보한다 — 첫 구간 \([0, 1]\)에서
곧바로 나온다. 그다음 \(x > 0\)을 가정해 모순을 끌어낸다. 아르키메데스가 주는 \(n\)이
\(\forall n\)을 무너뜨리는 그 하나다.
17. (a) \(A \subseteq B\)이면 \(A \times C \subseteq B \times C\)임을 증명하시오. (b) 역(”\(A \times C \subseteq B \times C\)이면 \(A \subseteq B\)”)이 일반적으로 거짓임을 반례로 보이시오. (힌트: \(C\)를 무엇으로 잡으면 좌변이 공짜로 성립하는가?)
힌트
(b)에서 반례가 완결되려면 두 가지를 적어야 한다 — 가정 부분이 실제로 참임을
계산으로 확인하고, 결론 부분이 실제로 거짓임을 확인한다(27주차 §1.7). 문제 2의
결과가 가정 확인에 그대로 쓰인다.
18. (진단) 다음 답안의 결함을 지적하시오.
“명제: \(A \times B \subseteq A' \times B'\)이면 \(A \subseteq A'\)이다 (\(A, B\) 비공). 증명: \(x \in A \times B\)라 하자. 그러면 \(x \in A\)이고 \(x \in B\)이다. 가정에 의해 \(x \in A' \times B'\)이므로 \(x \in A'\)이다. 따라서 \(A \subseteq A'\). \(\blacksquare\)”
(오프닝부터 무엇이 무너졌는가? 올바른 증명의 스케치도 제시하시오.)
힌트
결함을 “틀렸다”로 적으면 지적이 되지 않는다. 어느 줄에서 어떤 규칙이 다른 규칙으로
바뀌어 적용되었는지를 지목한다 — §1.3의 삭제 실험 ①이 그 규칙 교체를 미리 해부해 두었다.
19. \((A \cap B) \times (C \cap D) = (A \times C) \cap (B \times D)\)를 증명하시오.
힌트
양변을 끝까지 번역하면 둘 다 소속 조건 네 개가 \(\land\)로 이어진 식이 된다. 다른 것은
괄호의 묶는 방식뿐이므로 내용이 있는 줄은 재배열 한 줄이다. 멱등이 필요한지
아닌지를 조건 개수로 판단해 본다.
20. (서술) (a) 순서쌍 추적과 보통 원소 추적의 차이를 한 문장으로. (b) 첨자 드모르간과 11주차 양화사 부정 규칙의 관계를 두 문장 이내로 — “2부(논리)가 7부(집합)의 엔진”이라는 관점에서.
백지 재현 — 복습 프로토콜#
권장 일정 — 1~3일차: §0~§4 학습과 연습문제 / 4일차: 1차 재현 / 5일차: 완전 백지 재현. 재현은 두 번으로 나눈다. 한 번에 완전 백지로 가지 않는다.
1차 시도 (4일차) — 틀 카드 허용. §1.6의 세 오프닝 표와 정의 28.1~28.3만 펴 놓고, 예제 2.1과 예제 2.3을 처음부터 끝까지 적는다. 본문과 해설은 보지 않는다.
2차 시도 (5일차) — 완전 백지. 아무것도 보지 않고 수행한다:
세 번역 규칙(정의 28.1\(\cdot\)28.2\(\cdot\)28.3)을 조각 그대로 정확히 썼다.
§1.6의 세 오프닝을 왼쪽 집합의 꼴에서 재구성했다.
예제 2.1을 다섯 줄 사슬로 재현하고, 셋째 줄의 근거를 멱등과 재배열로 짚었다.
예제 2.3을 재현하고, 둘째 동치의 근거가 11주차 총목록 5행임을 말했다.
예제 2.2에서 (\(\Leftarrow\)) 방향에 제시하는 원소가 \(A\) 자신임을 설명했다.
“\(x \in A \times B\)라 하자, 그러면 \(x \in A\)이고 \(x \in B\)이다”가 어느 규칙을 어느 규칙으로 바꿔 읽은 것인지 설명했다 (문제 18).
\(\mathcal{P}\)가 \(\cap\)과는 완전히, \(\cup\)과는 한쪽만 호환된다는 비대칭을 반례까지 함께 말했다.
재현한 증명의 각 줄에 근거 ①~④ 중 무엇이 붙는지 말할 수 있다.
막힌 지점별 처방. 막힌 지점이 무엇을 다시 볼지 알려 준다.
막힌 지점 |
처방 |
|---|---|
첫 문장이 나오지 않는다 |
§1.6 — “왼쪽 집합의 원소는 무엇인가”부터 답한다 |
순서쌍을 잡았는데 다음 줄이 없다 |
정의 28.1 — 성분 두 개의 소속으로 분해한다 |
\(\mathcal{P}\)가 낀 줄에서 막힌다 |
정의 28.2 — \(\in\)과 \(\subseteq\)를 잇는 통로는 이 한 줄뿐이다 |
\(\bigcup, \bigcap\)에서 막힌다 |
정의 28.3 — \(\exists\)면 첨자를 제시하고, \(\forall\)이면 첨자를 골라 적용한다 |
번역했는데 잇는 법칙이 안 보인다 |
§1.7 — 9주차 목록 여덟 개와 멱등\(\cdot\)재배열\(\cdot\)양화사 부정을 하나씩 대 본다 |
비공 조건을 어디에 쓰는지 모르겠다 |
§4 도전 앞 상자 — 원소 하나를 꺼내 이름으로 받는다 |
참인지 거짓인지 판단이 안 선다 |
27주차 §1.7 — 작은 집합 대입으로 실험부터 한다 |
하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다.
해설#
각 해설은 접근(문제 앞에서 무엇을 생각하는가)과 풀이로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다.
빈칸 사다리 — 훈련 1#
(1) \((x, y)\) (2) \(B\) (3) \(C \times D\)
※ 오프닝에서 \((x,y)\)를 잡는 것이 이 훈련의 전부다. 정의 28.1이 성분 두 개의 독립적인 소속으로 분해해 주므로, 가정 \(A \subseteq C\)와 \(B \subseteq D\)를 성분마다 한 번씩 적용하면 된다. 마지막 줄에서 정의 28.1을 거꾸로 써서 순서쌍으로 재조립하지 않으면 결론이 선언되지 않는다.
빈칸 사다리 — 훈련 2#
(1) \(X\) (2) 정의 28.2 (멱집합의 소속 판정) (3) 교집합 (4) 부분집합의 추이성 (4주차 훈련 1) (5) 정의 28.2
※ 원소가 집합인 자리이므로 오프닝의 문자는 대문자 \(X\)다. 뼈대는 “정의 28.2로 내려가서 \(\to\) 포함 관계로 일한 뒤 \(\to\) 정의 28.2로 다시 올라온다”이며, 문제 8과 문제 9가 같은 뼈대에 각각 보조 iff와 경우 나누기를 얹은 것이다. 가운데 문장(\(A \cap B \subseteq A\))은 한 줄짜리 원소 추적으로 그 자리에서 확보했다.
빈칸 사다리 — 훈련 3#
(1) \(x \in \bigcap_{i \in I} A_i\)라 하자. (2) 정의 28.3에 의해 \(\forall i \in I,\ x \in A_i\)이다. (3) \(j \in I\)이므로 이 전칭 문장을 첨자 \(j\)에 적용하면 \(x \in A_j\)이다. 따라서 \(\bigcap_{i \in I} A_i \subseteq A_j\)이다. \(\blacksquare\)
※ \(\forall\)을 손에 들었을 때 할 수 있는 일은 하나다 — 무대 안의 첨자를 하나 골라 적용한다. 고를 자격은 “\(j \in I\)”라는 조건이 준다. 문제 12(b)와 문제 16은 이 동작을 결론이 아니라 모순을 만드는 데 쓴다: 잘 고른 첨자 하나에서 탈락시키면 \(\forall\)이 무너진다.
문제 1#
접근. 세 규칙을 문장으로 외우려 하면 막힌다. §1.6의 순서로 재구성한다 — 왼쪽 집합의 꼴이 원소의 자료형을 정하고, 자료형이 번역 규칙을 정한다.
풀이. ① 곱: \((x, y) \in S \times T \iff x \in S \land y \in T\) (정의 28.1). 원소가 순서쌍이므로 오프닝은 “\((x,y) \in \cdots\)라 하자”이다. ② 멱집합: \(X \in \mathcal{P}(A) \iff X \subseteq A\) (정의 28.2). 원소가 집합이므로 오프닝은 “\(X \in \cdots\)라 하자”이다. ③ 첨자족: \(x \in \bigcup_{i \in I} A_i \iff \exists i \in I,\ x \in A_i\)이고 \(x \in \bigcap_{i \in I} A_i \iff \forall i \in I,\ x \in A_i\) (정의 28.3).
복기. 세 규칙 모두 4주차\(\cdot\)6주차의 정의를 소속 판정의 꼴로 옮겨 적은 것이다. 이번 주에 늘어난 것은 증명법이 아니라 번역표 세 줄이며, 27주차의 세 걸음(번역 \(\to\) 조작 \(\to\) 역번역)은 그대로다.
문제 2#
접근. “이 집합은 공집합이다”를 보이는 서식은 6주차 문제 19와 같다 — 원소가 하나 있다고 가정하고 모순을 끌어낸다. 다른 점은 잡을 원소가 순서쌍이라는 것뿐이고, 정의 28.1이 성분 둘로 분해해 주면 둘째 성분에서 곧바로 모순이 나온다.
풀이. 모순을 위해 \(A \times \emptyset\)에 원소가 있다고 가정하자. 그 원소는 \(A \times \emptyset\)의 원소이므로 순서쌍이며, \((x, y) \in A \times \emptyset\)이라 하자. 정의 28.1에 의해 \(x \in A\)이고 \(y \in \emptyset\)이다. 그런데 공집합의 정의(정의 3.2)에 의해 \(\emptyset\)에는 원소가 하나도 없으므로 \(y \in \emptyset\)은 거짓이다. 모순이다. 따라서 \(A \times \emptyset\)에는 원소가 없고, \(A \times \emptyset = \emptyset\)이다. \(\blacksquare\)
복기. 두 성분 중 하나만 무너져도 순서쌍 전체가 탈락한다 — 정의 28.1의 “\(\land\)” 조각이 하는 일이다. 이 결과가 문제 17(b)의 반례에서 가정 확인에 그대로 쓰인다.
문제 3#
접근. 빈칸의 답을 외워 채우려 하지 말고 §1.6의 순서로 재구성한다: 왼쪽 집합이 \(A \times B\)이므로 자료형은 순서쌍 \(\to\) 오프닝 \(\to\) 정의 28.1로 성분 분해 \(\to\) 가정을 성분마다 한 번씩 적용 \(\to\) 정의 28.1로 재조립.
풀이. \(A \subseteq C\)이고 \(B \subseteq D\)라 가정하자. \((x, y) \in A \times B\)라 하자. 정의 28.1에 의해 \(x \in A\)이고 \(y \in B\)이다. 가정 \(A \subseteq C\)에 의해 \(x \in C\)이고, 가정 \(B \subseteq D\)에 의해 \(y \in D\)이다. 다시 정의 28.1에 의해 \((x, y) \in C \times D\)이다. \(A \times B\)의 임의의 원소가 \(C \times D\)의 원소이므로 \(A \times B \subseteq C \times D\)이다. \(\blacksquare\)
복기. 두 가정이 서로 다른 성분에 각각 작용한다 — 성분이 독립적으로 검사된다는 정의 28.1의 성질이 그대로 증명의 구조가 되었다. 문제 17(a)는 이 명제에서 \(B\)와 \(D\)를 모두 같은 집합으로 둔 특수한 경우다(그 집합이 문제 17의 \(C\), 훈련 1의 \(C\)가 문제 17의 \(B\)에 해당한다).
문제 4#
접근. 다섯 줄 중 실제로 내용이 있는 줄은 셋째 하나다. 그 줄에서 무엇을 복제하고 무엇을 재배열하는지부터 떠올리면, 나머지 네 줄은 정의 28.1과 정의 5.1의 번역\(\cdot\)역번역으로 자동으로 채워진다.
풀이. 임의의 순서쌍 \((x, y)\)에 대해
첫 동치는 정의 28.1과 정의 5.1(근거 ①), 둘째 동치는 멱등 \(P \equiv P \land P\)로 \(x \in A\)를 복제한 뒤 \(\land\)의 교환\(\cdot\)결합으로 재배열한 것(근거 ④), 셋째와 넷째는 정의 28.1과 정의 5.1을 거꾸로 쓴 역번역이다. 모든 단계가 \(\iff\)이므로 정의 27.1에 의해 두 집합은 같다. \(\blacksquare\)
복기. 자가 채점의 기준은 셋이다 — 오프닝이 순서쌍인가, 셋째 줄에 멱등의 이름이 붙어 있는가, 마지막에 “모든 단계가 \(\iff\)”라는 확인이 있는가. 셋째 줄의 근거를 적지 않으면 조건 개수가 늘어난 이유가 설명되지 않은 채 남는다.
문제 5#
접근. 앞부분은 생성형 집합의 포함이므로 증인 제작이다(27주차 예제 2.3) — \(9\)를 \(3\)의 거듭제곱으로 고쳐 쓰면 증인이 드러난다. 뒷부분은 오른쪽에만 있는 원소를 하나 지목하고, 그것이 왼쪽에 없음을 크기 비교로 확인한다. 원소 하나의 배제가 진부분집합의 완결 조건이다.
풀이. (\(\subseteq\)) \(x \in \{9^n : n \in \mathbb{N}\}\)이라 하자. 정의에 의해 \(x = 9^n\)인 자연수 \(n\)이 존재한다. 그러면 \(x = 9^n = (3^2)^n = 3^{2n}\)이고(지수법칙 — 근거 ③), \(n \ge 1\)이므로 \(2n\)도 자연수다. 따라서 \(x\)는 \(3^{(\text{자연수})}\) 꼴이므로 \(x \in \{3^n : n \in \mathbb{N}\}\)이고, 증인은 \(2n\)이다. 같지 않음: \(3 = 3^1\)이고 \(1 \in \mathbb{N}\)이므로 \(3 \in \{3^n : n \in \mathbb{N}\}\)이다. 한편 \(3 \in \{9^n : n \in \mathbb{N}\}\)이려면 \(9^n = 3\)인 자연수 \(n\)이 필요한데, \(n \ge 1\)이면 \(9^n \ge 9 > 3\)이므로(거듭제곱의 단조성 — 근거 ③) 그런 \(n\)은 없다. 따라서 \(3 \notin \{9^n : n \in \mathbb{N}\}\)이고 두 집합은 같지 않다. 곧 진부분집합이다. \(\blacksquare\)
복기. 포함은 증인 제작으로, 상등의 부정은 원소 하나의 배제로 처리한다 — 두 작업의 서식이 서로 다르다는 점이 이 문제의 요지다. 배제 쪽에서 “없다”를 주장했으므로 후보 전부가 걸러졌음을 크기 비교로 보였다. (검산: \(n = 2\)이면 \(81 = 3^4\), 증인 \(2n = 4\) ✓)
문제 6#
접근. 4주차 문제 19의 수치를 그대로 쓴다. 멱집합을 나열할 때는 크기 0부터 순서대로 적는다 — \(\emptyset\), 원소 하나짜리, 원소 둘짜리. \(|A| = 2\)이므로 \(|\mathcal{P}(A)| = 2^2 = 4\)개가 나와야 한다(4주차에서 인정하고 쓰는 사실 — 증명은 31주차 귀납법).
풀이. \(A \cap B = \{1,2\} \cap \{2,3\} = \{2\}\)이므로 \(\mathcal{P}(A \cap B) = \mathcal{P}(\{2\}) = \{\emptyset, \{2\}\}\)이다. 한편 \(\mathcal{P}(A) = \{\emptyset, \{1\}, \{2\}, \{1,2\}\}\)이고 \(\mathcal{P}(B) = \{\emptyset, \{2\}, \{3\}, \{2,3\}\}\)이므로, 두 목록에 공통으로 나타나는 원소를 고르면 \(\mathcal{P}(A) \cap \mathcal{P}(B) = \{\emptyset, \{2\}\}\)이다. 두 결과가 일치한다.
복기. 이 일치는 우연이 아니라 문제 8의 정리가 \(A = \{1,2\}\), \(B = \{2,3\}\)에서 실현된 것이다. 수치 확인은 근거가 아니라 방향을 정하는 실험이며(27주차 §1.7), “임의의 \(A, B\)”에 대한 주장은 문제 8에서 증명한다. 교집합을 계산할 때 원소가 집합이라는 점에 주의한다 — \(\{2\}\)와 \(2\)는 다른 대상이다.
문제 7#
접근. 예제 2.1과 같은 사슬이다. 좌변을 번역하면 \((P \lor Q) \land R\) 꼴, 우변을 번역하면 \((P \land R) \lor (Q \land R)\) 꼴이 된다. 두 꼴을 잇는 것은 9주차 목록의 분배 1이며, \(\land\)의 교환으로 \(\lor\) 묶음을 오른쪽으로 보낸 뒤 적용한다.
풀이. 임의의 순서쌍 \((x, y)\)에 대해
첫 동치는 정의 28.1과 정의 5.1(근거 ①), 둘째는 \(\land\)의 교환으로 \((P \lor Q) \land R\)를 \(R \land (P \lor Q)\)로 맞춘 뒤 분배 1을 적용해 \((R \land P) \lor (R \land Q)\)를 얻고, 다시 각 항에 \(\land\)의 교환을 써서 \((P \land R) \lor (Q \land R)\)로 정리한 것(근거 ④), 셋째와 넷째는 역번역이다. 모든 단계가 \(\iff\)이므로 두 집합은 같다. \(\blacksquare\)
복기. 예제 2.1은 \(\cap\)이라 멱등이 필요했고, 이 문제는 \(\cup\)이라 분배 1이 필요했다. 첫 성분 쪽에 붙은 연산의 논리 대응(\(\cup \to \lor\), \(\cap \to \land\))이 그대로 사슬의 엔진이 된다.
문제 8#
접근. 보조 iff \(X \subseteq A \cap B \iff (X \subseteq A \land X \subseteq B)\)를 먼저 증명해 두면, 본 증명은 정의 28.2를 양쪽에 씌우는 사슬 한 줄로 끝난다. 보조 iff의 (\(\Rightarrow\))는 \(x \in X\)를 한 번 잡아 추적하면 두 결론이 동시에 나온다.
풀이. 먼저 보조 iff를 보인다. (\(\Rightarrow\)) \(X \subseteq A \cap B\)라 하자. \(x \in X\)라 하자. 가정에 의해 \(x \in A \cap B\)이고, 교집합의 정의에 의해 \(x \in A\)이고 \(x \in B\)이다. \(x\)가 임의였으므로 \(X \subseteq A\)이고 \(X \subseteq B\)이다. (\(\Leftarrow\)) \(X \subseteq A\)이고 \(X \subseteq B\)라 하자. \(x \in X\)라 하자. 두 가정에 의해 \(x \in A\)이고 \(x \in B\)이므로, 교집합의 정의에 의해 \(x \in A \cap B\)이다. 따라서 \(X \subseteq A \cap B\)이다. 이제 임의의 대상 \(X\)에 대해
이다. 첫째와 셋째 동치는 정의 28.2, 둘째는 방금 증명한 보조 iff, 넷째는 교집합의 정의다. 모든 단계가 \(\iff\)이므로 정의 27.1에 의해 두 집합은 같다. \(\blacksquare\)
복기. 층이 둘인 문제는 아래층(부분집합의 세계)에서 일을 끝낸 뒤 정의 28.2로 한 번에 올라오는 것이 정석이다. 보조 iff는 아래층의 정리이고 사슬은 그것을 위층으로 옮기는 통로다. 문제 9의 실패는 정확히 이 보조 iff가 \(\cup\)에서는 성립하지 않기 때문에 생긴다.
문제 9#
접근. 오프닝은 “\(X \in \mathcal{P}(A) \cup \mathcal{P}(B)\)라 하자”이고, 합집합의 정의에서 “또는”이 나오므로 경우를 나눈다. 두 경우 모두 도착점이 같아서 증명이 닫힌다. 반례는 문제 6의 두 집합에서 \(A\)에도 \(B\)에도 통째로 들어가지 않는 부분집합을 하나 고르면 된다.
풀이. (\(\subseteq\)) \(X \in \mathcal{P}(A) \cup \mathcal{P}(B)\)라 하자. 합집합의 정의에 의해 \(X \in \mathcal{P}(A)\) 또는 \(X \in \mathcal{P}(B)\)이다. 두 경우로 나눈다. 경우 1(\(X \in \mathcal{P}(A)\)): 정의 28.2에 의해 \(X \subseteq A\)이다. 한편 \(x \in A\)이면 합집합의 정의에 의해 \(x \in A \cup B\)이므로 \(A \subseteq A \cup B\)이고, 부분집합의 추이성에 의해 \(X \subseteq A \cup B\)이다. 경우 2(\(X \in \mathcal{P}(B)\)): 정의 28.2에 의해 \(X \subseteq B\)이고, \(x \in B\)이면 \(x \in A \cup B\)이므로 \(B \subseteq A \cup B\)이며, 추이성에 의해 \(X \subseteq A \cup B\)이다. 어느 경우든 \(X \subseteq A \cup B\)이므로 정의 28.2에 의해 \(X \in \mathcal{P}(A \cup B)\)이다. 따라서 \(\mathcal{P}(A) \cup \mathcal{P}(B) \subseteq \mathcal{P}(A \cup B)\)이다. \(\blacksquare\) 역포함의 반례: \(A = \{1,2\}\), \(B = \{2,3\}\)이라 하자. \(A \cup B = \{1,2,3\}\)이고 \(\{1,3\} \subseteq \{1,2,3\}\)이므로 \(\{1,3\} \in \mathcal{P}(A \cup B)\)이다. 그런데 \(3 \notin A\)이므로 \(\{1,3\} \nsubseteq A\)이고, \(1 \notin B\)이므로 \(\{1,3\} \nsubseteq B\)이다. 따라서 \(\{1,3\} \notin \mathcal{P}(A) \cup \mathcal{P}(B)\)이고 두 집합은 같지 않다.
복기. \(\mathcal{P}\)는 \(\cap\)과는 완전히 호환되고(문제 8) \(\cup\)과는 한쪽만 호환된다. 이유는 문제 8의 보조 iff에 있다 — “\(X \subseteq A \cup B\)이면 \(X \subseteq A\) 또는 \(X \subseteq B\)”는 거짓이며, \(X\)가 두 집합에 걸쳐 있을 수 있기 때문이다. 반례의 \(\{1,3\}\)이 정확히 그 걸침을 실현한 원소다.
문제 10#
접근. 두 방향의 몸통이 완전히 다르다는 점을 먼저 떠올린다. (\(\Rightarrow\))는 원소 \(X\)를 잡아 추적하는 보통의 포함 증명이고, (\(\Leftarrow\))는 원소를 잡는 것이 아니라 \(A\) 자신을 제시해 가정을 발동시키는 증명이다.
풀이. (\(\Rightarrow\)) \(A \subseteq B\)라 가정하자. \(X \in \mathcal{P}(A)\)라 하자. 정의 28.2에 의해 \(X \subseteq A\)이고, 가정에 의해 \(A \subseteq B\)이므로, 부분집합의 추이성(4주차 훈련 1)에 의해 \(X \subseteq B\)이다. 다시 정의 28.2에 의해 \(X \in \mathcal{P}(B)\)이다. 따라서 \(\mathcal{P}(A) \subseteq \mathcal{P}(B)\)이다. (\(\Leftarrow\)) \(\mathcal{P}(A) \subseteq \mathcal{P}(B)\)라 가정하자. 4주차 §1.3에 의해 \(A \subseteq A\)이므로 정의 28.2에 의해 \(A \in \mathcal{P}(A)\)이다. 가정에 의해 \(A \in \mathcal{P}(B)\)이고, 다시 정의 28.2에 의해 \(A \subseteq B\)이다. 양방향이 모두 성립하므로 \(A \subseteq B \iff \mathcal{P}(A) \subseteq \mathcal{P}(B)\)이다. \(\blacksquare\)
복기. 자가 채점의 기준은 (\(\Leftarrow\))에서 제시한 원소가 \(A\) 자신이라는 점을 명시했는가이다. 포함 관계만 손에 든 상태에서 멱집합의 소속을 만들어 내는 방법은 “자기 자신도 부분집합”이라는 사실 하나뿐이며, 이 발상이 4주차의 사소해 보이던 관찰을 회수한다.
문제 11#
접근. 사슬로 한 번에 밀기보다 양방향 포함으로 나눠 쓰는 편이 안전하다. 우변의 번역에 부정이 들어가므로 드모르간 1이 필요하고, 그 결과 갈래가 둘 생기는데 그중 하나(\(x \notin A\))는 이미 손에 든 사실과 어긋나므로 남는 갈래가 하나뿐이다. 27주차 문제 9에서 차집합의 부정을 다룬 것과 같은 수다.
풀이. (\(\subseteq\)) \((x, y) \in A \times (B - C)\)라 하자. 정의 28.1에 의해 \(x \in A\)이고 \(y \in B - C\)이다. 차집합의 정의에 의해 \(y \in B\)이고 \(y \notin C\)이다. \(x \in A\)이고 \(y \in B\)이므로 정의 28.1에 의해 \((x, y) \in A \times B\)이다. 한편 \((x, y) \in A \times C\)라면 정의 28.1에 의해 \(y \in C\)가 되어 \(y \notin C\)와 모순이므로 \((x, y) \notin A \times C\)이다. 따라서 차집합의 정의에 의해 \((x, y) \in (A \times B) - (A \times C)\)이다. (\(\supseteq\)) \((x, y) \in (A \times B) - (A \times C)\)라 하자. 차집합의 정의에 의해 \((x,y) \in A \times B\)이고 \((x,y) \notin A \times C\)이다. 앞의 것에서 정의 28.1에 의해 \(x \in A\)이고 \(y \in B\)이다. 뒤의 것은 정의 28.1에 의해 \(\neg(x \in A \land y \in C)\)이고, 드모르간 1에 의해 \(x \notin A\) 또는 \(y \notin C\)이다. 그런데 \(x \in A\)가 이미 확보되어 있으므로 첫째 갈래는 거짓이고, 따라서 \(y \notin C\)이다. 그러면 \(y \in B\)이고 \(y \notin C\)이므로 \(y \in B - C\)이고, 정의 28.1에 의해 \((x, y) \in A \times (B - C)\)이다. 양방향 포함이 성립하므로 두 집합은 같다. \(\blacksquare\)
복기. “또는”이 나왔는데 갈래 하나가 이미 확보된 사실과 어긋나면, 경우 나누기 없이 남은 갈래로 곧바로 넘어갈 수 있다. 이 축약이 성립하는 조건은 하나 — 버리는 갈래가 거짓임을 문장으로 지적했는가이다.
문제 12#
접근. (a)의 (\(\supseteq\))에서 \(m \in \mathbb{N}\)을 잡았을 때 제시할 첨자는 \(m\) 자신이다 — \(m \in A_m = \{m, m+1\}\)이 곧바로 확인된다. (b)는 \(\forall\)을 무너뜨리는 문제이므로 잘 고른 첨자 하나면 충분하다. 다만 후보 \(x\)가 자연수라는 것부터 \(A_1\)에서 확보해야 \(x + 1\)을 첨자로 쓸 수 있다.
풀이. (a) (\(\subseteq\)) \(x \in \bigcup_{n \in \mathbb{N}} A_n\)이라 하자. 정의 28.3에 의해 \(x \in A_n\)인 자연수 \(n\)이 존재한다. \(A_n = \{n, n+1\}\)이므로 \(x = n\) 또는 \(x = n + 1\)이고, \(n\)과 \(n+1\)은 모두 자연수이므로 \(x \in \mathbb{N}\)이다. (\(\supseteq\)) \(m \in \mathbb{N}\)이라 하자. \(A_m = \{m, m+1\}\)이므로 \(m \in A_m\)이다. 곧 \(m \in A_n\)인 자연수 \(n\)이 존재하며(\(n = m\)이 증인), 정의 28.3에 의해 \(m \in \bigcup_{n \in \mathbb{N}} A_n\)이다. 양방향 포함이 성립하므로 \(\bigcup_{n \in \mathbb{N}} A_n = \mathbb{N}\)이다. \(\blacksquare\) (b) 모순을 위해 \(x \in \bigcap_{n \in \mathbb{N}} A_n\)인 \(x\)가 있다고 가정하자. 정의 28.3에 의해 모든 자연수 \(n\)에 대해 \(x \in A_n\)이다. 첨자 \(n = 1\)에 적용하면 \(x \in A_1 = \{1, 2\}\)이므로 \(x\)는 자연수이고, 따라서 \(x + 1\)도 자연수여서 첨자로 쓸 수 있다. 첨자 \(n = x + 1\)에 적용하면 \(x \in A_{x+1} = \{x+1, x+2\}\)이다. 그런데 \(x \neq x + 1\)이고 \(x \neq x + 2\)이므로 \(x \notin \{x+1, x+2\}\)이다. 모순이다. 따라서 그런 \(x\)는 없고, \(\bigcap_{n \in \mathbb{N}} A_n = \emptyset\)이다. \(\blacksquare\)
복기. \(\exists\)를 만들 때는 증인 하나를 제시하고, \(\forall\)을 무너뜨릴 때는 반례가 되는 첨자 하나를 고른다 — 두 작업 모두 “하나”로 끝난다는 것이 양화사 감각의 핵심이다. (b)에서 \(n = 1\)을 먼저 적용해 \(x\)의 정체를 좁힌 것은, 다음 단계에서 \(x + 1\)을 첨자로 쓸 자격을 확보하기 위한 준비다. (검산: \(x = 5\)이면 \(A_6 = \{6,7\}\)에 5가 없다 ✓)
문제 13#
접근. 예제 2.3의 사슬에서 양화사와 규칙만 바꾼다. 이번에 손에 드는 것은 \(\neg\forall\)이므로 11주차 부정 총목록 4행 \(\neg\forall \leadsto \exists\neg\)를 쓴다. 첨자가 무한해도 규칙 한 번이면 끝난다는 사정은 예제 2.3과 같다.
풀이. 임의의 \(x\)에 대해
첫 동치는 여집합의 정의(정의 5.2)와 정의 28.3(근거 ①), 둘째 동치는 양화사 부정 \(\neg\forall \leadsto \exists\neg\)(근거 ④, 11주차 총목록 4행), 셋째는 여집합의 정의를 거꾸로 쓴 것, 넷째는 정의 28.3을 거꾸로 쓴 것이다. 모든 단계가 \(\iff\)이므로 두 집합은 같다. \(\blacksquare\)
복기. 예제 2.3과 이 문제를 나란히 놓으면 대응이 드러난다 — \(\bigcup\)의 여집합에는 \(\neg\exists = \forall\neg\)가, \(\bigcap\)의 여집합에는 \(\neg\forall = \exists\neg\)가 붙는다. 27주차의 2집합 드모르간 두 개가 그대로 무한판으로 올라온 것이다. (검산: \(I = \{1,2\}\)이면 \((A_1 \cap A_2)^c = A_1^{\,c} \cup A_2^{\,c}\) ✓)
문제 14#
접근. 양변 모두 생성형 집합이므로 각 방향의 몸통은 증인 제작이다. (\(\subseteq\))는 받은 \(a, b\)로 증인 \(k\)를 하나 만들고, (\(\supseteq\))는 받은 \(k\)로 증인 \(a, b\) 두 개를 만든다. 만든 증인이 정수임을 확인하는 줄(근거 ②)을 빠뜨리면 미완성이다.
풀이. (\(\subseteq\)) \(x \in \{12a + 4b : a, b \in \mathbb{Z}\}\)라 하자. 정의에 의해 \(x = 12a + 4b\)인 정수 \(a, b\)가 존재한다. 그러면
이고, 정수의 곱과 합은 정수이므로 \(3a + b \in \mathbb{Z}\)이다(근거 ②). 따라서 \(x\)는 \(4 \times (\text{정수})\) 꼴이므로 \(x \in \{4k : k \in \mathbb{Z}\}\)이고, 증인은 \(k = 3a + b\)이다. (\(\supseteq\)) \(x \in \{4k : k \in \mathbb{Z}\}\)라 하자. 정의에 의해 \(x = 4k\)인 정수 \(k\)가 존재한다. 그러면 \(x = 4k = 12 \cdot 0 + 4k\)이고 \(0, k \in \mathbb{Z}\)이므로 \(x \in \{12a + 4b : a, b \in \mathbb{Z}\}\)이다. 증인은 \(a = 0\), \(b = k\)이다. 양방향 포함이 성립하므로 두 집합은 같다. \(\blacksquare\)
복기. 매개변수의 개수가 방향마다 다르면 증인의 개수도 방향마다 다르다 — 한쪽은 둘을 받아 하나를 만들고, 반대쪽은 하나를 받아 둘을 만든다. \(\{12a + 4b\}\)의 정체는 \(12\)와 \(4\)의 최대공약수 \(4\)의 배수 전체이며, “정수 결합이 만드는 집합은 최대공약수의 배수 전체”라는 정수론의 정리(베주 항등식)의 가장 작은 사례다. 이 빚은 50주차에서 정산한다. (검산: \(a=1, b=2\)이면 \(20 = 4 \times 5\), 증인 \(3a+b = 5\) ✓)
문제 15#
접근. (\(\Leftarrow\))는 \(A = B\)를 대입하면 곧바로 닫힌다. (\(\Rightarrow\))가 본론이며, \(x \in A\)를 잡아도 순서쌍이 없으면 가정을 발동시킬 수 없다는 점이 관건이다. \(B \neq \emptyset\)에서 원소 \(y\)를 하나 꺼내 \((x, y)\)를 만들면 가정이 작동하고, 같은 순서쌍을 \(B \times A\)의 기준으로 다시 읽으면 첫 성분의 소속이 바뀐다.
풀이. (\(\Leftarrow\)) \(A = B\)라 가정하자. 그러면 \(A \times B = A \times A = B \times A\)이다. (\(\Rightarrow\)) \(A \times B = B \times A\)라 가정하자. 먼저 \(A \subseteq B\)를 보인다. \(x \in A\)라 하자. \(B \neq \emptyset\)이므로 \(y \in B\)인 \(y\)가 존재한다. 정의 28.1에 의해 \((x, y) \in A \times B\)이고, 가정에 의해 \((x, y) \in B \times A\)이다. 정의 28.1을 \(B \times A\)에 대해 적용하면 첫 성분에 대해 \(x \in B\)이다. 따라서 \(A \subseteq B\)이다. 다음으로 \(B \subseteq A\)를 보인다. \(y \in B\)라 하자. \(A \neq \emptyset\)이므로 \(x \in A\)인 \(x\)가 존재한다. 정의 28.1에 의해 \((y, x) \in B \times A\)이고, 가정에 의해 \((y, x) \in A \times B\)이므로 첫 성분에 대해 \(y \in A\)이다. 따라서 \(B \subseteq A\)이다. 양방향 포함이 성립하므로 정의 27.1에 의해 \(A = B\)이다. 양방향이 모두 성립하므로 \(A \times B = B \times A \iff A = B\)이다. \(\blacksquare\)
복기. 비공 조건이 소비되는 자리는 각 방향에서 “꺼내 올 원소”의 존재 하나뿐이다. \(A\)나 \(B\)가 공집합이면 양변이 모두 공집합이 되어(문제 2) 가정은 참인데 결론이 거짓일 수 있으므로, 이 조건이 정리를 떠받친다. 같은 대여 동작이 문제 18의 올바른 증명에서 그대로 재사용된다.
문제 16#
접근. (\(\supseteq\))는 \(0\)이 모든 구간에 속함을 검증하면 끝난다. (\(\subseteq\))에서는 잡은 \(x\)에 대해 먼저 \(x \ge 0\)을 확보한 뒤(\(n = 1\)의 구간에서 나온다), \(x > 0\)을 가정해 모순을 끌어낸다. 아르키메데스가 주는 \(n\)이 \(\forall n\)을 무너뜨리는 그 하나다.
풀이. (\(\supseteq\)) 임의의 자연수 \(n\)에 대해 \(0 \le 0 \le \tfrac1n\)이므로 \(0 \in [0, \tfrac1n]\)이다. 모든 \(n\)에 대해 성립하므로 정의 28.3에 의해 \(0 \in \bigcap_{n \in \mathbb{N}} [0, \tfrac1n]\)이고, \(\{0\}\)의 원소는 \(0\)뿐이므로 \(\{0\} \subseteq \bigcap_{n \in \mathbb{N}} [0, \tfrac1n]\)이다. (\(\subseteq\)) \(x \in \bigcap_{n \in \mathbb{N}} [0, \tfrac1n]\)이라 하자. 정의 28.3에 의해 모든 자연수 \(n\)에 대해 \(x \in [0, \tfrac1n]\)이다. 첨자 \(n = 1\)에 적용하면 \(x \in [0, 1]\)이므로 \(x \ge 0\)이다. 모순을 위해 \(x > 0\)이라 가정하자. 아르키메데스 성질(문제 16 앞 상자에서 인정하고 쓰는 사실)에 의해 \(\tfrac1N < x\)인 자연수 \(N\)이 존재한다. 그 \(N\)에 대해 \(x > \tfrac1N\)이므로 \(x \notin [0, \tfrac1N]\)인데, 이는 모든 \(n\)에 대해 \(x \in [0, \tfrac1n]\)이라는 것과 모순이다. 따라서 \(x > 0\)은 불가능하고, \(x \ge 0\)과 합치면 \(x = 0\), 곧 \(x \in \{0\}\)이다. 양방향 포함이 성립하므로 \(\bigcap_{n \in \mathbb{N}} [0, \tfrac1n] = \{0\}\)이다. \(\blacksquare\)
복기. “무한히 많은 조건을 동시에 만족하는 원소”를 다루는 첫 엄밀 증명이다. 구조는 문제 12(b)와 같다 — \(\forall n\)을 무너뜨리는 첨자 하나를 지목한다. 다른 점은 그 첨자를 손으로 만들 수 없어서 존재를 아르키메데스 성질에서 빌려 왔다는 것이다. 6주차 예제 2.3에서 계산으로만 얻었던 결과가 여기서 증명으로 승격되었다.
문제 17#
접근. (a)는 훈련 1에서 \(B\)와 \(D\)를 모두 \(C\)로 둔 특수한 경우이므로 같은 뼈대로 쓴다. (b)는 반례이며, 좌변이 조건 없이 성립하도록 \(C\)를 고르는 것이 요령이다. \(C = \emptyset\)이면 문제 2에 의해 양변이 모두 공집합이 되어 포함이 자동으로 참이 되고, \(A\)와 \(B\)는 자유롭게 고를 수 있다.
풀이. (a) \(A \subseteq B\)라 가정하자. \((x, y) \in A \times C\)라 하자. 정의 28.1에 의해 \(x \in A\)이고 \(y \in C\)이다. 가정에 의해 \(x \in B\)이고 \(y \in C\)는 그대로이므로, 정의 28.1에 의해 \((x, y) \in B \times C\)이다. 따라서 \(A \times C \subseteq B \times C\)이다. \(\blacksquare\) (b) 반례로 \(A = \{1\}\), \(B = \{2\}\), \(C = \emptyset\)을 잡는다. 가정 부분의 확인: 문제 2에 의해 \(A \times C = \emptyset\)이고 \(B \times C = \emptyset\)이며, \(\emptyset \subseteq \emptyset\)이므로 \(A \times C \subseteq B \times C\)가 참이다. 결론 부분의 확인: \(1 \in A\)이지만 \(1 \notin B = \{2\}\)이므로 \(A \nsubseteq B\)이다. 가정이 참이고 결론이 거짓인 사례가 있으므로 역은 일반적으로 거짓이다.
복기. 역이 성립하려면 \(C \neq \emptyset\)이라는 조건이 필요하며, 그 조건 아래서는 문제 15의 (\(\Rightarrow\))와 같은 대여 논증으로 증명된다 — \(C\)에서 \(y\)를 하나 꺼내 \((x, y)\)를 만들면 가정이 발동한다. “공집합이면 포함이 공허하게 참”이라는 반례 구조는 이후 주차에서도 반복해 쓰인다.
문제 18#
접근. 결함을 “틀렸다”로 적으면 지적이 되지 않는다. 어느 줄에서 어떤 규칙이 다른 규칙으로 바뀌어 적용되었는지를 지목한다. 이 답안은 오프닝에서 원소의 자료형을 잘못 잡았고, 그 결과 곱의 판정 기준을 교집합의 판정 기준으로 바꿔 읽었다 — §1.3의 삭제 실험 ①이 해부해 둔 붕괴다.
풀이. 결함은 둘째 줄에 있고, 원인은 첫째 줄에 있다. 첫째 줄 “\(x \in A \times B\)라 하자”는 \(A \times B\)의 원소를 성분 없는 대상 \(x\)로 잡았다. 그러나 정의 28.1에 의해 \(A \times B\)의 원소는 순서쌍이므로, 잡아야 할 것은 \((x, y)\)다. 둘째 줄 “그러면 \(x \in A\)이고 \(x \in B\)이다”는 그 결과로 나온 문장인데, 이는 \(A \cap B\)의 판정 기준(정의 5.1)이지 \(A \times B\)의 판정 기준이 아니다. 규칙이 교체되었으므로 이후 전개는 전부 무효다. 실제로 \(A = \{1\}\), \(B = \{2\}\)이면 \(A \times B = \{(1,2)\}\)로 원소가 있지만 \(A \cap B = \emptyset\)이다. 올바른 증명의 스케치: \(A \times B \subseteq A' \times B'\)이라 가정하자. \(x \in A\)라 하자. \(B \neq \emptyset\)이므로 \(y \in B\)인 \(y\)가 존재한다. 정의 28.1에 의해 \((x, y) \in A \times B\)이고, 가정에 의해 \((x, y) \in A' \times B'\)이므로, 다시 정의 28.1에 의해 \(x \in A'\)이다. 따라서 \(A \subseteq A'\)이다. \(\blacksquare\)
복기. 첫 줄에서 자료형을 잘못 잡으면 이후 줄들이 각각으로는 옳아 보여도 증명 전체가 무효가 된다. 오프닝 점검이 이번 주 채점 기준의 첫 항목인 이유가 여기에 있다. 올바른 증명이 문제 15의 대여 동작을 그대로 재사용한다는 점도 함께 확인해 둔다.
문제 19#
접근. 양변을 끝까지 번역하면 둘 다 소속 조건 네 개(\(x \in A\), \(x \in B\), \(y \in C\), \(y \in D\))가 \(\land\)로 이어진 식이 된다. 다른 것은 괄호의 묶는 방식뿐이므로 내용이 있는 줄은 재배열 한 줄이다. 예제 2.1과 달리 양변의 조건 개수가 같으므로 복제가 필요 없고, 멱등은 쓰지 않는다.
풀이. 임의의 순서쌍 \((x, y)\)에 대해
첫 동치는 정의 28.1과 정의 5.1을 차례로 쓴 번역(근거 ①), 둘째 동치는 \(\land\)로 이어진 네 조건의 순서와 묶음을 바꾼 재배열(근거 ④), 셋째와 넷째는 역번역이다. 모든 단계가 \(\iff\)이므로 두 집합은 같다. \(\blacksquare\)
복기. 예제 2.1은 조건 개수가 양변에서 달라 멱등이 필요했고, 이 문제는 개수가 같아 재배열만으로 닫힌다. 번역을 끝까지 마친 뒤 양변의 조건 목록을 세어 보면 어떤 법칙이 필요한지가 그 자리에서 정해진다. (검산: \(A = \{1\}\), \(B = \{1,2\}\), \(C = \{3\}\), \(D = \{3,4\}\)이면 양변 모두 \(\{(1,3)\}\) ✓)
문제 20#
접근. (a)는 두 추적의 공통점과 차이점을 자료형이라는 한 낱말로 정리하는 문항이다. (b)는 정의 28.3이 \(\bigcup, \bigcap\)을 \(\exists, \forall\)로 옮겨 놓았다는 사실과, 그 결과 여집합 법칙이 부정 규칙의 직역이 된다는 사실을 잇는다.
풀이. (예시 답안) (a) 오프닝에서 잡는 원소의 자료형이 다를 뿐이다 — 순서쌍 \((x, y)\)를 잡아 정의 28.1로 성분별 소속으로 분해한다는 점 외에, “번역 \(\to\) 논리 조작 \(\to\) 역번역”이라는 엔진은 27주차의 원소 추적과 완전히 같다. (b) 첨자 합\(\cdot\)교는 정의 28.3에 의해 \(\exists\)\(\cdot\)\(\forall\)의 집합 표기이므로, 그 여집합 법칙은 양화사 부정 규칙(\(\neg\exists \leadsto \forall\neg\), \(\neg\forall \leadsto \exists\neg\))을 그대로 번역해 옮긴 것이다. 2부에서 만든 논리 도구(진리표 동치, 드모르간, 양화사 부정)가 유한\(\cdot\)무한을 가리지 않고 집합 항등식 전체의 엔진이라는 사정이 이번 주로 드러났다.
복기. 서술 문항의 채점 기준도 근거다 — “같다”나 “비슷하다”로 끝내지 않고, 어느 정의\(\cdot\)어느 규칙이 어느 자리에서 쓰이는지를 이름으로 지목했는지를 본다. (a)에서 “정의 28.1”, (b)에서 “11주차 총목록 4\(\cdot\)5행”이라는 이름이 들어가면 완결이다.
다음 주 예고: 반증(disproof) — 거짓인 명제를 거짓이라고 증명하는 기술을 정식 과목으로 다룬다. 반례를 찾는 전략, “존재 명제의 반증은 전칭 명제의 증명”이라는 역전, 그리고 39개까지 맞다가 40번째에서 무너진 추측의 사례가 나온다. 1주차 문제 18 이래 매주 해 온 반례 찾기가 서식을 갖춘 증명으로 승격되며, 이번 주의 문제 9\(\cdot\)17에서 쓴 반례 제시의 두 조건(가정 확인\(\cdot\)결론 확인)이 그 서식의 뼈대가 된다.