# 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}$ | :::{container} quotebox **확인 13.** 우변 칸의 빈칸을 채워 보자. 어떤 정의를 어떤 순서로 쓰는가. ::: :::{admonition} 답 :class: quotebox dropdown $(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$ 하나가 아니다. :::{container} quotebox **확인 14.** 첫 문장을 완성해 보자: "임의의 $\underline{\qquad}$에 대해 …" ::: :::{admonition} 답 :class: quotebox dropdown "임의의 순서쌍 $(x, y)$에 대해." 파트를 나눠 "($\subseteq$) $(x,y) \in A \times (B \cap C)$라 하자"로 열어도 같다. 어느 쪽이든 잡는 것은 성분 둘을 가진 $(x, y)$이며, §1.1의 붕괴를 막는 조각이 이 한 문장에 들어 있다. 아래에서는 모든 단계가 $\iff$이므로 27주차 §1.6의 동치 사슬 서식을 쓴다. ::: **2단계 — 좌변을 번역한다.** 근거가 둘이므로 줄도 둘로 나눈다. :::{container} quotebox **확인 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})$이다." ::: :::{admonition} 답 :class: quotebox dropdown $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)$이다. :::{container} quotebox **확인 16.** $P$가 왼쪽에 한 번, 오른쪽에 두 번 나온다. 이 개수 차이를 메우는 동치는 무엇이고, 그 뒤에 필요한 조작은 무엇인가. ::: :::{admonition} 답 :class: quotebox dropdown §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단계 — 역번역해 집합 표현으로 되돌린다.** :::{container} quotebox **확인 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}$" ::: :::{admonition} 답 :class: quotebox dropdown "$\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)\}$이다. :::{container} quotebox **확인 18.** 위 대입에서 $(x, y) = (1, 3)$을 잡으면 완성본의 각 줄이 어떤 문장이 되는가. 둘째 줄부터 따라 읽어 보자. ::: :::{admonition} 답 :class: quotebox dropdown "$(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이므로 의무가 둘이고, 방향마다 손에 드는 것과 만들 것이 다르다. :::{container} quotebox **확인 19.** 번역표를 채워 보자. ($\Rightarrow$) 첫 문장은 "$\underline{\quad}$라 하자"이고, 정의 28.2로 번역하면 $\underline{\quad}$를 손에 넣는다. ($\Leftarrow$) 가정 $\mathcal{P}(A) \subseteq \mathcal{P}(B)$를 쓰려면 $\mathcal{P}(A)$의 원소를 하나 제시해야 한다. 어떤 집합을 제시하는가. ::: :::{admonition} 답 :class: quotebox dropdown ($\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}$. 이번에는 설계부터 스스로 해 보자. 앞의 두 예제와 달리 무한할 수 있는 첨자를 다루므로, 개수를 세지 않는 도구만 써야 한다. :::{container} quotebox **확인 20.** ($\subseteq$)의 출발점 $x \in \big(\bigcup_{i \in I} A_i\big)^c$와 도착점 $x \in \bigcap_{i \in I} A_i^{\,c}$를 각각 논리식으로 번역하면 무엇인가. 둘을 잇는 11주차 규칙의 이름은 무엇인가. ::: :::{admonition} 답 :class: quotebox dropdown 출발점: 정의 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$에 대해 $$ x \in \Big(\bigcup_{i \in I} A_i\Big)^{\!c} \iff \neg\Big(\exists i \in I,\ x \in A_i\Big) \iff \forall i \in I,\ x \notin A_i $$ $$ \iff \forall i \in I,\ x \in A_i^{\,c} \iff x \in \bigcap_{i \in I} A_i^{\,c} $$ 첫 동치는 여집합의 정의와 정의 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}$ | :::{container} quotebox **확인 21.** 빈칸 (1)(2)(3)을 채워 보자. 예제 2.2는 이 표의 어느 칸이 비어 있는 유형인가. ::: :::{admonition} 답 :class: quotebox dropdown (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$역방향으로 쓰는 같은 동작이다. ::: 방금 확인한 뼈대에 이름을 붙인다. :::{admonition} 백지 암기 대상 :class: keybox **자료형별 원소 추적의 틀** ① 왼쪽 집합의 원소가 무엇인지 정한다(순서쌍 / 집합 / 보통 원소) $\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). :::{admonition} 이번 주의 채점 기준 :class: quotebox 답이 아니라 **근거**가 점수다. "$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$)의 세 가지 번역 규칙을 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown §1.6의 표를 덮고 각 줄의 **왼쪽 집합의 꼴**부터 떠올린다. 꼴이 정해지면 원소의 자료형이 정해지고, 자료형이 번역 규칙을 하나로 정한다. ::: **2.** $A \times \emptyset = \emptyset$임을 증명하시오. (힌트: 원소 $(x,y)$가 있다고 하면 $y$는 어디에?) :::{admonition} 힌트 :class: quotebox dropdown "이 집합은 공집합이다"를 보이는 서식은 6주차 문제 19와 같다 — 원소가 하나 있다고 가정하고 모순을 끌어낸다. 잡을 원소가 순서쌍이라는 점만 다르다. ::: **3.** 빈칸 훈련($A \subseteq C, B \subseteq D \Rightarrow A \times B \subseteq C \times D$)을 백지에서 완성하시오. :::{admonition} 힌트 :class: quotebox dropdown 빈칸을 외워 채우려 하지 말고 §1.6의 순서로 재구성한다: 자료형 $\to$ 오프닝 $\to$ 정의 28.1로 성분 분해 $\to$ 가정을 성분마다 한 번씩 적용 $\to$ 정의 28.1로 재조립. ::: **4.** 예제 2.1을 백지에 재현하시오. :::{admonition} 힌트 :class: quotebox dropdown 다섯 줄 중 실제로 내용이 있는 줄은 셋째 하나다. 그 줄에서 무엇을 복제하고 무엇을 재배열하는지부터 떠올리면 나머지는 번역과 역번역으로 채워진다. ::: **5.** $\{9^n : n \in \mathbb{N}\} \subseteq \{3^n : n \in \mathbb{N}\}$임을 증명하고, 두 집합이 같지 **않음**을 원소 하나로 보이시오. :::{admonition} 힌트 :class: quotebox dropdown 앞부분은 생성형 집합의 포함이므로 증인 제작이다(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의 수치 재방문 — 다음 문제의 실험). :::{admonition} 힌트 :class: quotebox dropdown 멱집합을 나열할 때는 크기 0부터 순서대로 적는다 — $\emptyset$, 원소 하나짜리, 원소 둘짜리. $|A| = 2$이므로 $|\mathcal{P}(A)| = 2^2 = 4$개가 나와야 한다(개수 공식은 지금은 인정하고 쓴다 — 31주차에서 증명). ::: ### 표준 ●●○ **7.** $(A \cup B) \times C = (A \times C) \cup (B \times C)$를 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 예제 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부터 — 양방향 각각 원소 추적) :::{admonition} 힌트 :class: quotebox dropdown 보조 iff를 먼저 증명해 두면 본 증명은 정의 28.2를 양쪽에 씌우는 사슬 한 줄로 끝난다. 보조 iff의 ($\Rightarrow$)는 $x \in X$를 잡아 한 번 추적하면 두 결론이 동시에 나온다. ::: **9.** $\mathcal{P}(A) \cup \mathcal{P}(B) \subseteq \mathcal{P}(A \cup B)$를 증명하고, 역포함이 일반적으로 거짓임을 반례로 보이시오 (4주차 문제 19). :::{admonition} 힌트 :class: quotebox dropdown 오프닝은 "$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$가 이미 확보된 문맥이다.) :::{admonition} 힌트 :class: quotebox dropdown 사슬로 밀기보다 양방향 포함으로 나눠 쓰는 편이 안전하다. ($\supseteq$) 방향에서 드모르간 1로 갈래가 둘 생기는데, 그중 하나는 이미 손에 든 사실과 어긋나므로 남는 갈래가 하나뿐이다. ::: :::{admonition} 첨자족이 낀 상등을 증명하는 법 — 문제 12$\cdot$13$\cdot$16에서 쓴다 :class: quotebox 첨자족의 상등도 서식은 정의 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$임을 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown (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의 방법으로 증명하시오. :::{admonition} 조건제시 집합의 상등 — 문제 14에서 쓴다 :class: quotebox $\{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}\}$임을 증명하시오. (각 방향 모두 증인 제작) ### 도전 ●●● :::{admonition} 새 도구 — 비어 있지 않은 집합에서 원소 하나 꺼내 쓰기 :class: quotebox "$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)$를 추적하시오.) :::{admonition} 힌트 :class: quotebox dropdown ($\Rightarrow$)에서 만든 순서쌍 $(x, y)$는 $A \times B$에 있고, 가정에 의해 $B \times A$에도 있다. 같은 순서쌍을 $B \times A$의 기준으로 다시 읽으면 **첫 성분**에 대해 무엇을 알게 되는가. ::: :::{admonition} 지금은 증명 없이 인정하고 쓰는 사실 — 아르키메데스 성질 (45주차에서 공식 채택) :class: quotebox 임의의 실수 $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$인 원소의 배제) :::{admonition} 힌트 :class: quotebox dropdown ($\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$를 무엇으로 잡으면 좌변이 공짜로 성립하는가?) :::{admonition} 힌트 :class: quotebox dropdown (b)에서 반례가 완결되려면 두 가지를 적어야 한다 — 가정 부분이 실제로 참임을 계산으로 확인하고, 결론 부분이 실제로 거짓임을 확인한다(27주차 §1.7). 문제 2의 결과가 가정 확인에 그대로 쓰인다. ::: **18.** (진단) 다음 답안의 결함을 지적하시오. :::{container} quotebox "명제: $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$" (오프닝부터 무엇이 무너졌는가? 올바른 증명의 스케치도 제시하시오.) ::: :::{admonition} 힌트 :class: quotebox dropdown 결함을 "틀렸다"로 적으면 지적이 되지 않는다. 어느 줄에서 어떤 규칙이 다른 규칙으로 바뀌어 적용되었는지를 지목한다 — §1.3의 삭제 실험 ①이 그 규칙 교체를 미리 해부해 두었다. ::: **19.** $(A \cap B) \times (C \cap D) = (A \times C) \cap (B \times D)$를 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 양변을 끝까지 번역하면 둘 다 소속 조건 네 개가 $\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)$에 대해 $$ (x,y) \in A \times (B \cap C) \iff x \in A \land (y \in B \land y \in C) $$ $$ \iff (x \in A \land y \in B) \land (x \in A \land y \in C) $$ $$ \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(근거 ①), 둘째 동치는 멱등 $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)$에 대해 $$ (x,y) \in (A \cup B) \times C \iff (x \in A \lor x \in B) \land y \in C $$ $$ \iff (x \in A \land y \in C) \lor (x \in B \land y \in C) \quad (\land\text{의 교환} + \text{분배 1, 9주차}) $$ $$ \iff (x,y) \in A \times C \lor (x,y) \in B \times C \iff (x,y) \in (A \times C) \cup (B \times C) $$ 첫 동치는 정의 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$에 대해 $$ X \in \mathcal{P}(A \cap B) \iff X \subseteq A \cap B \iff (X \subseteq A \land X \subseteq B) $$ $$ \iff (X \in \mathcal{P}(A) \land X \in \mathcal{P}(B)) \iff X \in \mathcal{P}(A) \cap \mathcal{P}(B) $$ 이다. 첫째와 셋째 동치는 정의 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$에 대해 $$ x \in \Big(\bigcap_{i \in I} A_i\Big)^{\!c} \iff \neg\Big(\forall i \in I,\ x \in A_i\Big) \iff \exists i \in I,\ x \notin A_i $$ $$ \iff \exists i \in I,\ x \in A_i^{\,c} \iff x \in \bigcup_{i \in I} A_i^{\,c} $$ 첫 동치는 여집합의 정의(정의 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$가 존재한다. 그러면 $$ x = 12a + 4b = 4(3a + 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)$에 대해 $$ (x,y) \in (A \cap B) \times (C \cap D) \iff (x \in A \land x \in B) \land (y \in C \land y \in D) $$ $$ \iff (x \in A \land y \in C) \land (x \in B \land y \in D) \quad (\land\text{의 교환·결합}) $$ $$ \iff (x,y) \in A \times C \land (x,y) \in B \times D \iff (x,y) \in (A \times C) \cap (B \times D) $$ 첫 동치는 정의 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$결론 확인)이 그 서식의 뼈대가 된다.