# 27주차 · 강의 — 예제 · 연습 · 해설 ## 예제 — 집합 증명을 함께 만들기 완성된 증명을 먼저 보이지 않는다. 백지에서 시작해 한 줄씩 만든다. 각 단계에서 확인 상자의 빈칸을 연필로 먼저 채운 뒤 답을 연다. ### 예제 2.1 — 드모르간 법칙 (5주차에서 미룬 증명) **명제.** 임의의 집합 $A, B$에 대해 $(A \cup B)^c = A^c \cap B^c$. **설계 — 쓰기 전에 정하는 두 가지.** 목표가 상등이므로 정의 27.1에 의해 의무가 둘이다. 각 파트의 출발점과 도착점을 번역해서 먼저 정한다. | | **말** | **논리식 번역** | |---|---|---| | ($\subseteq$) 출발점 | $x \in (A \cup B)^c$ | $\neg(x \in A \lor x \in B)$ | | ($\subseteq$) 도착점 | $x \in A^c \cap B^c$ | $\underline{\quad(?)\quad}$ | | ($\supseteq$) 출발점 | $x \in A^c \cap B^c$ | $x \notin A \land x \notin B$ | | ($\supseteq$) 도착점 | $x \in (A \cup B)^c$ | $\neg(x \in A \lor x \in B)$ | :::{container} quotebox **확인 10.** 도착점 칸의 빈칸을 채워 보자. "$x \in A^c \cap B^c$"를 정의로 두 번 번역하면 어떤 논리식이 되는가. ::: :::{admonition} 답 :class: quotebox dropdown $x \notin A \land x \notin B$. 교집합의 정의로 $x \in A^c \land x \in B^c$가 되고, 여집합의 정의를 두 조각에 각각 적용하면 $x \notin A \land x \notin B$가 된다. 출발점 $\neg(x \in A \lor x \in B)$와 도착점 $x \notin A \land x \notin B$가 정해졌다. 그 사이는 논리 조작이다. ::: **1단계 — 파트를 열고 원소를 잡는다.** 상등의 첫 파트를 선언하고, §1.4의 서식대로 왼쪽 집합의 임의의 원소를 무대에 올린다. :::{container} quotebox **확인 11.** 첫 문장을 완성해 보자: "($\subseteq$) $\underline{\qquad}$라 하자." ::: :::{admonition} 답 :class: quotebox dropdown "($\subseteq$) $x \in (A \cup B)^c$라 하자." 파트 표시 ($\subseteq$)를 함께 적어 두면 채점자와 자신 모두 지금 어느 의무를 수행 중인지 알 수 있다. ::: **2단계 — 정의를 풀어 논리식으로 번역한다.** "$x \in (A \cup B)^c$"는 아직 집합 표기다. §1.5의 사전대로 여집합의 정의, 합집합의 정의를 차례로 쓴다. :::{container} quotebox **확인 12.** 둘째 문장을 완성해 보자: "여집합의 정의에 의해 $\underline{\quad}$이고, 합집합의 정의에 의해 이는 $\neg(\underline{\qquad})$이다." ::: :::{admonition} 답 :class: quotebox dropdown "$x \notin A \cup B$"이고, 이는 $\neg(x \in A \lor x \in B)$이다. 번역을 두 단계로 나눠 적는 이유는 근거가 두 개(정의 5.2와 정의 5.1)이기 때문이다. 한 줄에 몰아 적어도 되지만, 각 줄에 근거 하나가 원칙이다. ::: **3단계 — 논리 법칙으로 조작한다.** 여기가 이 증명에서 유일하게 내용이 있는 줄이다. 손에 든 것은 $\neg(P \lor Q)$ 꼴, 만들 것은 $\neg P \land \neg Q$ 꼴이다. :::{container} quotebox **확인 13.** 셋째 문장을 완성해 보자: "$\underline{\qquad}$에 의해 $x \notin A \land x \notin B$이다." ::: :::{admonition} 답 :class: quotebox dropdown "드모르간 2($\neg(P \lor Q) \equiv \neg P \land \neg Q$, 9주차)"에 의해. 근거 ④의 인용이다. 이 한 줄이 빠지면 남는 것은 표기 변환뿐이므로 증명이 아무것도 하지 않은 것이 된다. ::: **4단계 — 역번역해 집합 표현으로 되돌린다.** 논리식 상태로는 결론을 선언할 수 없다. 목표가 집합의 원소 소속이므로 정의를 거꾸로 써서 되돌린다. :::{container} quotebox **확인 14.** 넷째 문장을 완성해 보자: "즉 $x \in \underline{\quad}$이고 $x \in \underline{\quad}$이므로 $x \in \underline{\qquad}$이다." ::: :::{admonition} 답 :class: quotebox dropdown "즉 $x \in A^c$이고 $x \in B^c$이므로 $x \in A^c \cap B^c$이다." 여집합의 정의를 두 번, 교집합의 정의를 한 번 거꾸로 쓴 것이다. 이것으로 ($\subseteq$) 파트가 닫힌다. ::: **5단계 — 반대 파트를 쓰고 종합을 선언한다.** 둘째 의무가 남아 있다. 1~4단계의 근거가 전부 정의와 동치 법칙이므로 각 줄을 거꾸로 읽어도 그대로 성립한다. :::{container} quotebox **확인 15.** ($\supseteq$) 파트의 네 줄을 순서대로 적어 보자. $x \in A^c \cap B^c$에서 출발해 $x \in (A \cup B)^c$로 도착한다. ::: :::{admonition} 답 :class: quotebox dropdown "($\supseteq$) $x \in A^c \cap B^c$라 하자. 교집합과 여집합의 정의에 의해 $x \notin A \land x \notin B$이다. 드모르간 2에 의해 $\neg(x \in A \lor x \in B)$, 즉 $x \notin A \cup B$이다. 따라서 $x \in (A \cup B)^c$이다." 마지막으로 "양방향 포함이 성립하므로 $(A \cup B)^c = A^c \cap B^c$이다. $\blacksquare$"를 적으면 증명이 끝난다. ::: **완성본.** 방금 만든 문장들을 이어 붙이면 아래 왼쪽 열이 된다. 손으로 베껴 쓰면서 각 줄 옆의 "왜?"에 스스로 답해 본다. | 증명의 한 줄 | 왜 이 줄을 쓰는가? | |---|---| | ($\subseteq$) $x \in (A \cup B)^c$라 하자. | 상등은 의무가 둘(정의 27.1). 첫 파트를 열고 왼쪽 집합의 임의의 원소를 잡는다. | | 여집합의 정의에 의해 $x \notin A \cup B$, 즉 $\neg(x \in A \lor x \in B)$이다. | 집합 표기를 논리식으로 번역한다(근거 ①). 정의 5.2와 정의 5.1을 차례로 쓴다. | | 드모르간 2에 의해 $x \notin A$이고 $x \notin B$이다. | 9주차에 등록된 동치 법칙의 인용(근거 ④). 이 증명에서 실제로 내용이 있는 유일한 줄이다. | | 즉 $x \in A^c$이고 $x \in B^c$이므로 $x \in A^c \cap B^c$이다. | 정의를 거꾸로 써서 집합 표현으로 되돌린다(근거 ①). 첫 파트가 닫힌다. | | ($\supseteq$) $x \in A^c \cap B^c$라 하자. 정의에 의해 $x \notin A$이고 $x \notin B$이며, 드모르간 2에 의해 $\neg(x \in A \lor x \in B)$, 즉 $x \in (A \cup B)^c$이다. | 둘째 의무. 모든 단계가 정의와 동치 법칙이므로 같은 근거를 역순으로 쓴다. | | 양방향 포함이 성립하므로 $(A \cup B)^c = A^c \cap B^c$이다. $\blacksquare$ | 정의 27.1을 인용하며 종합을 선언한다. | **이 여섯 줄이 "임의의" 집합을 처리하는 이유.** $U = \{1, \dots, 6\}$, $A = \{1,2,3\}$, $B = \{3,4\}$를 넣어 읽어 보자. $(A \cup B)^c = \{1,2,3,4\}^c = \{5,6\}$이고 $A^c \cap B^c = \{4,5,6\} \cap \{1,2,5,6\} = \{5,6\}$이다. :::{container} quotebox **확인 16.** 위 대입에서 $x = 5$를 잡으면 완성본의 각 줄이 어떤 문장이 되는가. 첫 줄부터 넷째 줄까지 따라 읽어 보자. ::: :::{admonition} 답 :class: quotebox dropdown "$5 \in \{1,2,3,4\}^c$라 하자" $\to$ "$5 \notin \{1,2,3,4\}$, 즉 $\neg(5 \in A \lor 5 \in B)$" $\to$ "$5 \notin A$이고 $5 \notin B$" $\to$ "$5 \in A^c$이고 $5 \in B^c$이므로 $5 \in A^c \cap B^c$". 모든 줄이 그대로 성립한다. 증명의 어느 줄도 $x$가 5라는 사실이나 $A$가 $\{1,2,3\}$이라는 사실을 쓰지 않았으므로, 같은 여섯 줄이 어떤 집합 조합에도 그대로 작동한다. ::: **관찰 — 동치 사슬로 압축하기.** 완성본의 모든 단계는 정의 또는 동치 법칙이라 전부 $\iff$이다. §1.6의 자격 조건을 만족하므로 다음 한 줄로 압축해도 된다. $$ x \in (A \cup B)^c \iff \neg(x \in A \lor x \in B) \iff x \notin A \land x \notin B \iff x \in A^c \cap B^c $$ 다만 압축 전에 각 단계가 진짜 $\iff$인지 확인한다. 한 단계라도 $\Rightarrow$뿐이면 ($\supseteq$) 방향의 근거가 사라지므로 두 파트로 분리해 써야 한다. ### 예제 2.2 — 분배법칙 **명제.** $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$. 이번에는 설계만 함께 하고, 본문은 완성본으로 본다. :::{container} quotebox **확인 17.** 번역표를 채워 보자. 좌변: $x \in A \cap (B \cup C)$ $\to$ $\underline{\qquad}$ 우변: $x \in (A \cap B) \cup (A \cap C)$ $\to$ $\underline{\qquad}$ 둘을 잇는 9주차 법칙의 이름은 무엇인가. ::: :::{admonition} 답 :class: quotebox dropdown 좌변: $x \in A \land (x \in B \lor x \in C)$. 우변: $(x \in A \land x \in B) \lor (x \in A \land x \in C)$. 잇는 법칙은 **분배 1**: $P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)$. 9주차 §1.6의 목록에 있고, 7주차 문제 15에서 진리표로 이미 확인했다. 번역해 놓고 보면 증명할 것이 논리 분배법칙 하나뿐임이 드러난다. ::: **증명.** 임의의 $x$에 대해 $$ x \in A \cap (B \cup C) \iff x \in A \land (x \in B \lor x \in C) $$ $$ \iff (x \in A \land x \in B) \lor (x \in A \land x \in C) \quad \text{(분배 1, 9주차)} $$ $$ \iff x \in (A \cap B) \cup (A \cap C) $$ 첫째와 셋째 동치는 교집합$\cdot$합집합의 정의(근거 ①)이고 둘째 동치는 분배 1의 인용(근거 ④)이다. 모든 단계가 $\iff$이므로 두 집합은 같다. $\blacksquare$ 사슬로 적을 수 있었던 것은 세 단계가 전부 왕복 가능했기 때문이다. 그 확인을 건너뛰면 압축이 성립하지 않는다. ### 예제 2.3 — 조건제시법 집합의 상등 (3주차 문제 9에서 미룬 증명) **명제.** $\{3k + 1 : k \in \mathbb{Z}\} = \{3k - 2 : k \in \mathbb{Z}\}$. 이번에는 설계부터 스스로 해 보자. 앞의 두 예제와 달리 원소가 논리 연산이 아니라 **생성식**으로 주어져 있다. :::{container} quotebox **확인 18.** ($\subseteq$) 파트의 첫 문장은 "$x \in \{3k+1 : k \in \mathbb{Z}\}$라 하자"이다. 이 조건을 정의로 풀면 무엇을 손에 넣는가. 그리고 도착점 "$x \in \{3k - 2 : k \in \mathbb{Z}\}$"를 보이려면 무엇을 제시해야 하는가. ::: :::{admonition} 답 :class: quotebox dropdown 손에 넣는 것: "$x = 3k + 1$인 정수 $k$가 존재한다" — 존재가 보장된 정수 $k$를 받아 쓴다. 제시해야 하는 것: "$x = 3m - 2$"가 되는 **정수 $m$을 실제로 만들어 보이는 것**. 생성형 집합의 원소 판정은 "그 꼴로 표현할 수 있는가"를 묻는 존재 명제이므로, 26주차의 증인 제작이 각 파트의 몸통이 된다. $3k + 1 = 3(k+1) - 2$이므로 증인은 $m = k + 1$이다. ::: **증명.** ($\subseteq$) $x \in \{3k+1 : k \in \mathbb{Z}\}$라 하자. 정의에 의해 $x = 3k + 1$인 정수 $k$가 존재한다. 그러면 $$ x = 3k + 1 = 3k + 3 - 2 = 3(k + 1) - 2 $$ 이고 $k + 1$은 정수이므로(근거 ②), $x$는 $3(\text{정수}) - 2$ 꼴이다. 따라서 $x \in \{3k - 2 : k \in \mathbb{Z}\}$이다. ($\supseteq$) $x \in \{3k - 2 : k \in \mathbb{Z}\}$라 하자. 정의에 의해 $x = 3k - 2$인 정수 $k$가 존재한다. 그러면 $$ x = 3k - 2 = 3k - 3 + 1 = 3(k - 1) + 1 $$ 이고 $k - 1$은 정수이므로, $x \in \{3k + 1 : k \in \mathbb{Z}\}$이다. 양방향 포함이 성립하므로 두 집합은 같다. $\blacksquare$ 이번 증명은 표 없이 산문으로 적었다. 표는 연습 단계의 장치이고, 실전의 증명은 처음부터 끝까지 이런 산문이다. **검산.** $k = 0$이면 좌변의 원소는 $x = 1$이고, 증인 $m = k + 1 = 1$을 넣으면 $3 \times 1 - 2 = 1$이다. 검산은 증명이 아니지만 증인 제작의 실수를 잡아 준다. ### 관찰 — 세 예제의 같은 뼈대 예제 2.1, 2.2, 2.3은 소재만 다를 뿐 뼈대가 같다. 대응표의 빈칸을 채워 보자. | **단계** | **예제 2.1** | **예제 2.3** | |---|---|---| | ① 파트 열고 원소 잡기 | $x \in (A \cup B)^c$라 하자 | $\underline{\quad(1)\quad}$ | | ② 정의로 번역 | $\neg(x \in A \lor x \in B)$ | $x = 3k + 1$인 정수 $k$가 존재 | | ③ 내용 있는 한 수 | 드모르간 2의 인용 | $\underline{\quad(2)\quad}$ | | ④ 역번역$\cdot$결론 | $x \in A^c \cap B^c$ | $\underline{\quad(3)\quad}$ | | ⑤ 반대 파트 | $x \in A^c \cap B^c$라 하자 … | $x \in \{3k-2 : k \in \mathbb{Z}\}$라 하자 … | :::{container} quotebox **확인 19.** 빈칸 (1)(2)(3)을 채워 보자. 예제 2.2는 이 표의 ①~⑤ 중 어디까지를 사슬 한 줄로 압축한 것인가. ::: :::{admonition} 답 :class: quotebox dropdown (1) $x \in \{3k+1 : k \in \mathbb{Z}\}$라 하자 (2) $3k + 1 = 3(k+1) - 2$로 고쳐 쓰고 증인 $k + 1$을 제작 (3) $x \in \{3k - 2 : k \in \mathbb{Z}\}$ 예제 2.2는 ①~⑤ 전부를 사슬 한 줄로 압축한 것이다 — 모든 단계가 $\iff$였기 때문에 가능했다. 세 예제의 차이는 ③에 들어가는 내용뿐이고, ③이 논리 법칙이면 드모르간$\cdot$분배 유형, 증인 제작이면 생성형 집합 유형이다. ::: 방금 확인한 뼈대에 이름을 붙인다. :::{admonition} 백지 암기 대상 :class: keybox **집합 상등 증명의 틀** ① 상등이면 파트 둘로 나눈다(모든 단계가 $\iff$임을 확인했으면 사슬 한 줄로 압축해도 된다) $\to$ ② "$x \in (\text{왼쪽 집합})$라 하자" $\to$ ③ 정의로 논리식(또는 생성식)으로 번역한다 $\to$ ④ 논리 법칙을 인용하거나 증인을 제작한다 $\to$ ⑤ 정의로 역번역해 도착점을 선언한다 $\to$ ⑥ 반대 파트를 같은 방식으로 쓰고 종합을 선언한다 ::: 이 틀은 28주차의 순서쌍 추적, 37주차의 동치류, 44주차의 상과 원상에서 그대로 재사용된다 — 바뀌는 것은 ③의 번역표뿐이다. ## 빈칸 사다리 — 지지대를 하나씩 빼며 필사에서 자립으로 넘어가는 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 해설(§6)에 있다 — 다 채운 뒤에 대조한다. ### 훈련 1 ●○○ — 수식 빈칸 **명제.** $A - B = A \cap B^c$ (5주차 문제 12의 승격). **증명.** 임의의 $x$에 대해 $$ x \in A - B \iff x \in A \land \underline{\quad(1)\quad} \iff x \in A \land x \in \underline{\quad(2)\quad} \iff x \in \underline{\quad(3)\quad} $$ 첫 동치는 차집합의 정의, 둘째는 $\underline{\quad(4)\quad}$의 정의, 셋째는 $\underline{\quad(5)\quad}$의 정의이다. 모든 단계가 동치이므로 두 집합은 같다. $\blacksquare$ ### 훈련 2 ●●○ — 수식과 근거를 함께 이번에는 근거의 이름도 빈칸이다. **명제.** $(A^c)^c = A$ (5주차 문제 5의 승격). **증명.** 임의의 $x$에 대해 $$ x \in (A^c)^c \iff \underline{\quad(1)\quad} \iff \neg(\underline{\quad(2)\quad}) \iff x \in A $$ 첫 동치의 근거는 $\underline{\quad(3)\quad}$의 정의이고, 둘째 동치의 근거도 같은 정의이며, 셋째 동치의 근거는 9주차 목록의 $\underline{\quad(4)\quad}$ 법칙이다. 모든 단계가 동치이므로 두 집합은 같다. $\blacksquare$ ### 훈련 3 ●●● — 뼈대만 남기고 **명제.** $A \subseteq B$이면 $A \cup C \subseteq B \cup C$이다. **증명의 뼈대.** 각 칸을 통째로 채운다. 목표가 상등이 아니라 포함이므로 파트는 하나이고, 번역하면 "또는"이 나오므로 경우 나누기(17주차)가 필요하다. - ① 가정 선언과 원소 잡기: $\underline{\quad(1)\quad}$ - ② 정의로 번역하고 경우를 나눔: $\underline{\quad(2)\quad}$ - ③ 각 경우의 처리와 마무리: $\underline{\quad(3)\quad}$ (이 훈련이 문제 6의 예행연습이다 — 문제 6은 $\cap$ 버전이라 경우 나누기가 필요 없다는 차이가 있다.) ## 연습문제 (20문항) 해설을 보기 전에 문제당 최소 10분 스스로 시도한다. 막히면 곧바로 풀이를 읽지 말고, 해설의 '접근'까지만 읽고 다시 시도한다 $\to$ 그래도 안 되면 풀이를 읽는다. $\subseteq$ 증명의 오프닝("$x \in \cdot$라 하자")과 상등의 2파트(또는 완전 동치 사슬)를 지킨다. :::{admonition} 이번 주의 채점 기준 :class: quotebox 답이 아니라 **근거**가 점수다. "$(A \cup B)^c = A^c \cap B^c$는 참(맞음)"은 0점이고, 각 줄에 정의 이름 또는 9주차 법칙 이름이 붙은 양방향 추적이 만점이다. 특히 상등 문제에서 한 파트만 쓰고 끝낸 답안은 절반이 아니라 미완성이다 — §1.3의 삭제 실험이 그 이유다. 힌트 상자는 5분 이상 막힌 뒤에만 연다. ::: ### 기본 ●○○ **1.** [백지] 세 가지 목표($a \in A$ / $A \subseteq B$ / $A = B$)의 증명 서식을 쓰시오. :::{admonition} 힌트 :class: quotebox dropdown §1.4의 표를 덮고, 각 목표의 **첫 문장**부터 적는다. 첫 문장이 나오면 마지막 문장은 그 짝으로 정해진다. ::: **2.** 다음 원소 판정을 증명하시오 (조건 확인 서식). (a) $14 \in \{3k + 2 : k \in \mathbb{Z}\}$ (b) $10 \notin \{4k + 1 : k \in \mathbb{Z}\}$ (힌트: $10 = 4k+1$이면 $4k = 9$) :::{admonition} 힌트 :class: quotebox dropdown (a)는 증인 하나를 제시하면 끝난다 — $14 = 3 \times \underline{\quad} + 2$. (b)는 반대로 증인이 **없음**을 보여야 한다. 조건식을 $k$에 대해 풀어 그 값이 정수가 아님을 지적하면 후보가 전부 배제된다. ::: **3.** $\{x \in \mathbb{Z} : 8 \mid x\} \subseteq \{x \in \mathbb{Z} : 4 \mid x\}$를 원소 추적으로 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 오프닝은 "$x \in \{x \in \mathbb{Z} : 8 \mid x\}$라 하자". 조건을 나누어떨어짐의 정의(2주차)로 풀면 $x = 8k$를 얻고, 도착점은 $x = 4 \times (\text{정수})$ 꼴이다. 4주차 문제 12와 같은 계산이다. ::: **4.** 빈칸 훈련($A - B = A \cap B^c$)을 백지에서 완성하시오. :::{admonition} 힌트 :class: quotebox dropdown 빈칸을 외워 채우는 것이 아니라 사슬 전체를 다시 만든다. 좌변을 차집합의 정의로 풀면 "그리고"가 나오고, 오른쪽 조각을 여집합의 정의로 되돌리면 우변이 된다. ::: **5.** 드모르간 제2법칙 $(A \cap B)^c = A^c \cup B^c$를 예제 2.1의 방법(동치 사슬 가능)으로 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 예제 2.1에서 $\cup$과 $\cap$의 자리를 맞바꾼 명제다. 인용할 법칙도 드모르간 2가 아니라 **드모르간 1**($\neg(P \land Q) \equiv \neg P \lor \neg Q$)로 바뀐다. ::: **6.** $A \subseteq B$이면 $A \cap C \subseteq B \cap C$임을 증명하시오. :::{admonition} 힌트 :class: quotebox dropdown 가정이 둘이다 — 명제의 가정 $A \subseteq B$와 오프닝의 $x \in A \cap C$. 후자를 "그리고"로 분해한 뒤, $A$쪽 조각에만 가정을 적용한다. $C$쪽 조각은 손대지 않고 그대로 가져간다. ::: ### 표준 ●●○ **7.** 분배법칙의 짝 $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$를 증명하시오. (엔진: 논리 분배 2 — 9주차 목록) :::{admonition} 힌트 :class: quotebox dropdown 예제 2.2에서 $\land$와 $\lor$를 전부 맞바꾼 형태다. 번역만 정확히 하면 인용할 것이 분배 2($P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)$) 하나임이 보인다. ::: **8.** $(A \cup B) - B = A - B$임을 증명하시오. (양방향 — 번역하면 $(P \lor Q) \land \neg Q$와 $P \land \neg Q$의 동치 확인이 핵심) :::{admonition} 힌트 :class: quotebox dropdown ($\subseteq$)에서 손에 든 것은 "($x \in A$ 또는 $x \in B$) 그리고 $x \notin B$"이다. "또는"의 두 갈래 중 하나가 이미 부정되어 있으면 남는 갈래는 하나뿐이다. ::: **9.** $A - (A - B) = A \cap B$임을 증명하시오. (힌트: $x \in A - (A-B)$의 번역에 조건문의 부정 아닌 — 차집합 부정: $\neg(x \in A \land x \notin B) \equiv x \notin A \lor x \in B$ (드모르간)) :::{admonition} 힌트 :class: quotebox dropdown 문제의 힌트대로 번역하면 $x \in A \land (x \notin A \lor x \in B)$가 남는다. 바깥의 $x \in A$가 참인 상황에서 괄호 안 왼쪽 갈래는 어떻게 되는가. ::: **10.** $A \subseteq B \iff B^c \subseteq A^c$임을 증명하시오. (힌트: 원소 추적 + "$x \in B^c$라 하자 $\to$ $x \notin B$ $\to$ ($A \subseteq B$의 대우로) $x \notin A$" — 19주차 대우가 집합 세계에서 재등장한다) **11.** $\{x \in \mathbb{Z} : 6 \mid x\} = \{x \in \mathbb{Z} : 2 \mid x\} \cap \{x \in \mathbb{Z} : 3 \mid x\}$임을 증명하시오. (부품: 25주차 문제 12의 iff — 또는 직접 양방향) :::{admonition} 힌트 :class: quotebox dropdown 25주차 문제 12에서 "$6 \mid x \iff 2 \mid x$ 그리고 $3 \mid x$"를 이미 증명했다. 원소 조건의 동치가 손에 있으면 상등은 번역 두 번으로 끝난다. ::: **12.** $\{5k + 3 : k \in \mathbb{Z}\} = \{5k - 2 : k \in \mathbb{Z}\}$임을 증명하시오 (예제 2.3 유형). :::{admonition} 힌트 :class: quotebox dropdown 두 생성식의 차이는 상수항 $3$과 $-2$이고 그 차는 5다. 5를 하나 옮겨 $5k + 3 = 5(k + 1) - 2$를 만들면 증인이 나온다. ::: **13.** 증명 또는 반증: $(A - B) \cup (B - A) = (A \cup B) - (A \cap B)$. (실험 $\to$ 판단 $\to$ 실행. 참이라면 번역 후 논리 조작이 다소 길다 — 각 방향을 케이스로 처리해도 좋다) :::{admonition} 힌트 :class: quotebox dropdown 먼저 §1.7의 1단계를 실행한다: $A = \{1,2\}$, $B = \{2,3\}$으로 양변을 계산해 본다. 일치하면 증명으로 가고, 각 방향에서 "또는"이 나올 때마다 경우를 나눈다. ::: **14.** 증명 또는 반증: $A - (B - C) = (A - B) \cup C$. :::{admonition} 힌트 :class: quotebox dropdown 우변에서 $C$가 $A$와 아무 관계 없이 통째로 더해진다는 점이 수상하다. $C$의 원소를 $A$ 바깥에 두면 좌변에는 없고 우변에는 있는 원소가 생긴다. ::: ### 도전 ●●● :::{admonition} 반례로 반증하기 — 이번 주의 꼴 :class: quotebox "임의의 집합 $A, B, C$에 대해 ~이다"가 거짓임을 보이려면, 주장이 무너지는 구체적인 집합 한 벌이면 된다 — 1주차 문제 18에서 쓴 반례가 수 하나였고, 2주차 문제 15에서는 수의 조합이었으며, 이번에는 집합의 조합이다. 반례 제시의 완결 조건은 두 가지다: ① 좌변과 우변을 각각 실제로 계산한다 ② 계산 결과가 서로 다름을 명시한다(§1.7의 확인 8). ::: **15.** $A \subseteq B \iff A - B = \emptyset$임을 증명하시오. (($\Rightarrow$)는 6주차 문제 19의 승격 — 귀류 또는 원소 논증; ($\Leftarrow$)는 대우 또는 직접: $x \in A$인데 $x \notin B$이면 $x \in A - B \neq \emptyset$) **16.** $A = B \iff A \cup B \subseteq A \cap B$임을 증명 또는 반증하시오. (힌트: ($\Rightarrow$)는 대입. ($\Leftarrow$)는 $x \in A$라 하자 $\to$ $x \in A \cup B \subseteq A \cap B$ $\to$ $x \in B$ — 대칭으로 반대 방향도) :::{admonition} 세 집합의 합집합$\cdot$교집합 — 표기 약속 :class: quotebox 정의 5.1의 $\cup, \cap$은 집합 **두 개**를 받는 연산이므로, $A \cup B \cup C$는 그대로는 뜻이 정해지지 않은 표기다. 다음을 약속으로 둔다. $$ A \cup B \cup C := (A \cup B) \cup C, \qquad A \cap B \cap C := (A \cap B) \cap C $$ 이것은 증명해야 할 사실이 아니라 **표기의 정의**이며, 인용할 때는 근거 ①이다. (괄호를 반대로 묶어도 같은 집합이 된다는 사실 — 집합의 결합법칙 — 은 이 과정에서 아직 증명하지 않았고, 아래 문제에도 필요하지 않다. 약속대로 왼쪽부터 묶는다.) ::: **17.** 세 집합 버전 드모르간 $\big(A \cup B \cup C\big)^c = A^c \cap B^c \cap C^c$를 증명하시오. (두 집합 버전(예제 2.1)을 두 번 적용하는 조립 증명 권장: $A \cup B \cup C = (A \cup B) \cup C$) :::{admonition} 힌트 :class: quotebox dropdown 원소 추적으로 처음부터 다시 쓸 필요가 없다. 예제 2.1은 "임의의 집합 $A, B$"에 대한 정리이므로 $A$ 자리에 $A \cup B$를 통째로 넣어도 된다. 이미 증명한 명제를 부품으로 쓰는 것이 근거 ④다. ::: **18.** 증명 또는 반증: 임의의 집합 $A, B, C$에 대해 $A - (B \cap C) = (A - B) \cup (A - C)$. (드모르간의 차집합 버전 — 5주차 문제 17에서 수치 확인한 $A - (B \cup C) = (A-B) \cap (A-C)$의 쌍둥이) :::{admonition} 힌트 :class: quotebox dropdown 번역하면 좌변이 $P \land \neg(Q \land R)$이다. 드모르간 1로 괄호를 풀고, 이어서 분배 1을 쓰면 우변의 꼴이 나온다. 인용할 법칙이 두 개다. ::: **19.** (진단) 다음 답안의 결함을 지적하시오. '지우기'는 정당한 연산인가. 이어서 반례를 제시해 이 명제 자체가 거짓임을 보이시오. :::{container} quotebox "명제: $A \cap B = A \cap C$이면 $B = C$이다. 증명: 양변에서 $A \cap$를 지우면 $B = C$이다. $\blacksquare$" ::: :::{admonition} 힌트 :class: quotebox dropdown 결론이 거짓인데 논증이 그럴듯하면 오류는 계산이 아니라 **허용되지 않은 연산**에 있다(1주차 문제 6과 같은 진단 구조). 반례는 $B$와 $C$가 $A$ 바깥에서만 다르도록 만들면 된다. ::: **20.** (서술) (a) 집합 항등식 증명에서 "논리 법칙이 엔진"이라는 말의 뜻을 예제 2.1을 예로 두 문장 이내로. (b) 어떤 단계가 $\iff$가 아니라 $\Rightarrow$뿐이라면 동치 사슬 서식을 왜 포기해야 하는지 한 문장으로. ## 백지 재현 — 복습 프로토콜 권장 일정 — 1~3일차: §0~§4 학습과 연습문제 / 4일차: 1차 재현 / 5일차: 완전 백지 재현. 재현은 두 번으로 나눈다. 한 번에 완전 백지로 가지 않는다. **1차 시도 (4일차) — 틀 카드 허용.** §1.4의 서식 표와 §1.5의 번역 사전, 9주차 동치 목록만 펴 놓고 예제 2.1을 처음부터 끝까지 적는다. 본문과 정의는 보지 않는다. **2차 시도 (5일차) — 완전 백지.** 아무것도 보지 않고 수행한다: - [ ] 정의 27.1(상등의 양방향 포함 판정)을 조각 그대로 정확히 썼다. - [ ] 세 서식($a \in A$ / $A \subseteq B$ / $A = B$)의 첫 문장과 마지막 문장을 백지에 썼다. - [ ] 번역 사전 네 줄($\cup, \cap, -, {}^c$)을 백지에 썼다. - [ ] 드모르간 법칙(예제 2.1)을 번역–조작–역번역 구조로 재현했다. - [ ] 생성형 집합 상등(예제 2.3)의 증인 제작 구조를 재현했다. - [ ] 재현한 증명의 각 줄에 근거 ①~④ 중 무엇이 붙는지 말할 수 있다. - [ ] "증명 또는 반증" 절차(실험 $\to$ 판단 $\to$ 실행)와 반례의 완결 조건 두 가지를 말할 수 있다. **막힌 지점별 처방.** 막힌 지점이 무엇을 다시 볼지 알려 준다. | **막힌 지점** | **처방** | |---|---| | 첫 문장이 나오지 않는다 | §1.4 서식 표 — 목표의 꼴이 첫 문장을 정한다 | | 번역까지 했는데 다음 줄이 없다 | §1.5 — 손에 든 논리식에 9주차 목록 여덟 개를 하나씩 대 본다 | | 한 파트만 쓰고 끝냈다 | §1.3 조각 삭제 실험 — 한 방향은 여분의 원소를 막지 못한다 | | 동치 사슬이 맞는지 불안하다 | §1.6 확인 7 — 각 단계를 오른쪽에서 왼쪽으로 읽어 본다 | | 참인지 거짓인지 판단이 안 선다 | §1.7 — 작은 집합 대입으로 실험부터 한다 | | 생성형 집합에서 막힌다 | 예제 2.3 — 받은 정수로 증인을 제작해 제시한다 | 하나라도 실패하면 그 항목만 다시 필사하고 다음날 재시도한다. ## 해설 각 해설은 **접근**(문제 앞에서 무엇을 생각하는가)과 **풀이**로 나뉜다. 막혔을 때는 접근까지만 읽고 연필을 다시 잡는다. ### 빈칸 사다리 — 훈련 1 (1) $x \notin B$ (2) $B^c$ (3) $A \cap B^c$ (4) 여집합 (5) 교집합 ※ 좌변을 정의로 풀면 "그리고"가 드러나고, 오른쪽 조각 $x \notin B$를 여집합의 정의로 되돌리면 $x \in B^c$가 되어 교집합의 꼴이 완성된다. 이 훈련에서는 논리 법칙을 하나도 쓰지 않았다 — 번역과 역번역만으로 닫히는 항등식도 있다. ### 빈칸 사다리 — 훈련 2 (1) $x \notin A^c$ (2) $x \notin A$ (3) 여집합 (4) 이중부정 ※ 사슬을 풀어 쓰면 $x \in (A^c)^c \iff x \notin A^c \iff \neg(x \notin A) \iff x \in A$이다. 셋째 동치의 근거인 이중부정 $\neg(\neg P) \equiv P$는 9주차 목록의 첫 항목이고, 7주차 문제 7에서 진리표로 확인한 사실이다. 5주차 문제 5에서 수치로만 관찰했던 $(A^c)^c = A$가 이로써 임의의 집합에 대해 증명되었다. ### 빈칸 사다리 — 훈련 3 (1) $A \subseteq B$라 가정하고, $x \in A \cup C$라 하자. (2) 합집합의 정의에 의해 $x \in A$ 또는 $x \in C$이다. 두 경우로 나눈다. (3) 경우 1($x \in A$): 가정 $A \subseteq B$에 의해 $x \in B$이므로 $x \in B \cup C$이다. 경우 2($x \in C$): 합집합의 정의에 의해 곧바로 $x \in B \cup C$이다. 어느 경우든 $x \in B \cup C$이므로 $A \cup C \subseteq B \cup C$이다. $\blacksquare$ ※ "또는"이 나오면 경우를 나눈다(17주차). 경우 나누기의 채점 기준은 그대로다 — 경우들이 전체를 빠짐없이 덮는가, 각 경우가 각각 완결되는가. ### 문제 1 **접근.** 세 서식을 외운 문장으로 떠올리려 하면 막힌다. 목표의 꼴을 보고 **첫 문장**을 정하는 순서로 재구성한다 — 목표가 소속이면 조건 확인, 포함이면 원소 잡기, 상등이면 파트 둘이다. 마지막 문장은 첫 문장의 짝으로 자동으로 정해진다. **풀이.** ($a \in A$) "$A = \{x : P(x)\}$이다. $a$가 조건 $P$를 만족함을 확인한다: $P(a)$가 참이다. 따라서 $a \in A$이다." 조건이 여러 개면 전부 확인한다(26주차). ($A \subseteq B$) "$x \in A$라 하자. (정의로 번역하고 필요한 조작을 한다.) 따라서 $x \in B$이다. 그러므로 $A \subseteq B$이다." 여기서 $x$는 특정 원소가 아니라 임의의 원소다. ($A = B$) "($\subseteq$) $x \in A$라 하자. … 따라서 $x \in B$이다. ($\supseteq$) $x \in B$라 하자. … 따라서 $x \in A$이다. 양방향 포함이 성립하므로 $A = B$이다." 모든 단계가 $\iff$임을 확인했다면 사슬 한 줄로 두 파트를 압축해도 된다. **복기.** 세 서식은 목표의 꼴이 서식을 결정한다는 하나의 원리로 묶인다. 증명을 시작할 때 "무엇을 쓸까"가 아니라 "목표가 어느 줄인가"를 먼저 묻는다. ### 문제 2 **접근.** (a)는 존재 명제이므로 증인 하나를 제시하고 조건을 검증하면 끝난다 (26주차 구성적 존재 증명). (b)는 존재의 부정이므로 증인이 없음을 논증해야 한다 — 조건식을 $k$에 대해 풀어 유일한 후보가 정수가 아님을 보이면 모든 후보가 배제된다. **풀이.** (a) 집합의 조건은 "$14 = 3k + 2$인 정수 $k$가 존재한다"이다. $k = 4$를 증인으로 제시한다. 검증: $3 \times 4 + 2 = 12 + 2 = 14$이고 $4 \in \mathbb{Z}$이다. 따라서 $14 \in \{3k + 2 : k \in \mathbb{Z}\}$이다. $\blacksquare$ (b) $10 \in \{4k + 1 : k \in \mathbb{Z}\}$라면 $10 = 4k + 1$인 정수 $k$가 존재한다. 그 등식에서 $4k = 9$, 즉 $k = \frac{9}{4}$이다. 그런데 $\frac94$는 정수가 아니고, 등식을 만족하는 $k$는 이 하나뿐이므로 조건을 만족하는 정수 $k$는 존재하지 않는다. 따라서 $10 \notin \{4k + 1 : k \in \mathbb{Z}\}$이다. $\blacksquare$ **복기.** 소속의 증명과 비소속의 증명은 비대칭이다 — 소속은 증인 하나로, 비소속은 후보 전부의 배제로 끝난다(10주차 $\exists$와 $\forall$의 비대칭 표). (b)에서 후보 전부를 배제할 수 있었던 것은 일차식이라 해가 하나뿐이기 때문이다. ### 문제 3 **접근.** 포함이므로 파트는 하나다. 오프닝으로 왼쪽 집합의 임의의 원소를 잡고, 그 조건 "$8 \mid x$"를 나누어떨어짐의 정의(정의 2.1)로 풀어 등식을 받는다. 도착점은 "$4 \mid x$", 곧 $x = 4 \times (\text{정수})$ 꼴이다. **풀이.** $x \in \{x \in \mathbb{Z} : 8 \mid x\}$라 하자. 그러면 $x$는 정수이고 $8 \mid x$이므로, 정의에 의해 $x = 8k$인 정수 $k$가 존재한다. 그러면 $$ x = 8k = 4 \times (2k) $$ 이고 $2k$는 정수이므로(근거 ②), 정의에 의해 $4 \mid x$이다. 따라서 $x \in \{x \in \mathbb{Z} : 4 \mid x\}$이다. 임의의 원소에 대해 성립하므로 $\{x \in \mathbb{Z} : 8 \mid x\} \subseteq \{x \in \mathbb{Z} : 4 \mid x\}$이다. $\blacksquare$ **복기.** 조건제시법 집합의 원소 추적은 "조건을 정의로 풀고, 도착점 조건의 꼴을 만든다"로 요약된다 — 1주차 이래의 3단계 틀이 집합 표기를 입은 것뿐이다. 검산: $x = 24$이면 $24 = 8 \times 3 = 4 \times 6$으로 두 조건을 모두 만족한다. ### 문제 4 **접근.** 빈칸의 답을 외워 채우는 것이 아니라 사슬 전체를 다시 만든다. 좌변을 차집합의 정의로 풀면 "그리고"가 나오고, 오른쪽 조각을 여집합의 정의로 되돌리면 교집합의 꼴이 완성된다. 각 동치에 정의 이름이 붙었는지가 채점 대상이다. **풀이.** 임의의 $x$에 대해 $$ x \in A - B \iff x \in A \land x \notin B \iff x \in A \land x \in B^c \iff x \in A \cap B^c $$ 첫 동치는 차집합의 정의(정의 5.1), 둘째는 여집합의 정의(정의 5.2), 셋째는 교집합의 정의(정의 5.1)이다. 모든 단계가 정의에 의한 번역이므로 전부 $\iff$이고, 따라서 두 집합은 같다. $\blacksquare$ **복기.** 이 항등식은 논리 법칙을 하나도 쓰지 않는다. 그래서 차집합은 "교집합과 여집합으로 정의할 수 있는 파생 연산"이며, 이후 증명에서 $-$를 만나면 곧바로 차집합의 정의로 $x \in A \land x \notin B$까지 풀어 놓는 것이 표준 수순이 된다(문제 9$\cdot$13$\cdot$18). ### 문제 5 **접근.** 예제 2.1에서 $\cup$과 $\cap$의 자리가 맞바뀐 명제다. 번역해 보면 손에 드는 것이 $\neg(P \land Q)$ 꼴이므로, 인용할 법칙도 드모르간 2가 아니라 **드모르간 1**로 바뀐다. 모든 단계가 정의와 동치 법칙이므로 사슬로 쓸 수 있다. **풀이.** 임의의 $x$에 대해 $$ x \in (A \cap B)^c \iff \neg(x \in A \cap B) \iff \neg(x \in A \land x \in B) $$ $$ \iff x \notin A \lor x \notin B \iff x \in A^c \lor x \in B^c \iff x \in A^c \cup B^c $$ 첫째와 둘째 동치는 여집합$\cdot$교집합의 정의(근거 ①), 셋째 동치는 드모르간 1 $\neg(P \land Q) \equiv \neg P \lor \neg Q$의 인용(근거 ④), 넷째와 다섯째는 여집합$\cdot$합집합의 정의를 거꾸로 쓴 것이다. 모든 단계가 동치이므로 $(A \cap B)^c = A^c \cup B^c$이다. $\blacksquare$ **복기.** 집합의 드모르간 두 법칙은 논리의 드모르간 두 법칙과 하나씩 짝을 이룬다 — 부정이 괄호를 뚫고 들어가면 $\cup$과 $\cap$이 서로 뒤바뀐다. 검산: $U = \{1,\dots,5\}$, $A = \{1,2\}$, $B = \{2,3\}$이면 $(A \cap B)^c = \{2\}^c = \{1,3,4,5\}$이고 $A^c \cup B^c = \{3,4,5\} \cup \{1,4,5\} = \{1,3,4,5\}$이다. ### 문제 6 **접근.** 가정이 둘이라는 점이 이 문제의 요령이다 — 명제의 가정 $A \subseteq B$와, 포함 증명의 오프닝이 주는 $x \in A \cap C$이다. 후자를 "그리고"로 분해한 뒤 $A$쪽 조각에만 명제의 가정을 적용하고, $C$쪽 조각은 손대지 않고 그대로 가져간다. **풀이.** $A \subseteq B$라 가정하자. $x \in A \cap C$라 하자. 교집합의 정의에 의해 $x \in A$이고 $x \in C$이다. 가정 $A \subseteq B$와 $x \in A$로부터 $x \in B$이다(정의 4.1의 적용). 따라서 $x \in B$이고 $x \in C$이므로, 교집합의 정의에 의해 $x \in B \cap C$이다. 임의의 원소에 대해 성립하므로 $A \cap C \subseteq B \cap C$이다. $\blacksquare$ **복기.** "가정을 어디에 적용하는가"가 이 유형의 전부다. 분해한 조각 중 가정이 말하는 집합에 관한 조각만 승격시키고 나머지는 보존한다. $\cup$ 버전(훈련 3)에서는 분해가 "또는"이라 경우 나누기가 추가된다는 차이가 있다. ### 문제 7 **접근.** 예제 2.2에서 $\land$와 $\lor$를 전부 맞바꾼 형태다. 번역만 정확히 하면 인용할 것이 분배 2 하나임이 드러난다. 9주차 §1.6에서 분배 두 개는 각자 8행 진리표로 검증해야 근거 ④에 등록된다고 했으므로, 검증을 마쳤는지 먼저 확인한다. **풀이.** 임의의 $x$에 대해 $$ x \in A \cup (B \cap C) \iff x \in A \lor (x \in B \land x \in C) $$ $$ \iff (x \in A \lor x \in B) \land (x \in A \lor x \in C) \quad \text{(분배 2, 9주차)} $$ $$ \iff x \in (A \cup B) \cap (A \cup C) $$ 첫째와 셋째 동치는 합집합$\cdot$교집합의 정의(근거 ①), 둘째 동치는 분배 2 $P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)$의 인용(근거 ④)이다. 모든 단계가 동치이므로 두 집합은 같다. $\blacksquare$ **복기.** 예제 2.2와 이 문제를 나란히 놓으면 집합의 분배법칙 두 개가 논리의 분배법칙 두 개의 번역임이 드러난다. 수의 세계에서는 곱이 합에 분배될 뿐 합이 곱에 분배되지 않는데, 집합에서는 양쪽이 모두 성립한다는 점이 다르다. ### 문제 8 **접근.** 좌변을 번역하면 $(P \lor Q) \land \neg Q$이고 우변은 $P \land \neg Q$이다 ($P$: $x \in A$, $Q$: $x \in B$). "또는"의 두 갈래 중 한쪽이 이미 부정되어 있으면 남는 갈래는 하나뿐이다. 이 추론을 그대로 문장으로 옮기면 된다. **풀이.** ($\subseteq$) $x \in (A \cup B) - B$라 하자. 차집합의 정의에 의해 $x \in A \cup B$이고 $x \notin B$이다. 앞의 조건을 합집합의 정의로 풀면 $x \in A$ 또는 $x \in B$인데, $x \notin B$이므로 뒤 갈래는 성립할 수 없다. 따라서 $x \in A$이다. 결국 $x \in A$이고 $x \notin B$이므로 $x \in A - B$이다. ($\supseteq$) $x \in A - B$라 하자. 차집합의 정의에 의해 $x \in A$이고 $x \notin B$이다. $x \in A$이므로 합집합의 정의에 의해 $x \in A \cup B$이고, $x \notin B$가 그대로 남아 있으므로 $x \in (A \cup B) - B$이다. 양방향 포함이 성립하므로 $(A \cup B) - B = A - B$이다. $\blacksquare$ **복기.** "또는의 한 갈래가 막히면 다른 갈래가 강제된다"는 추론에는 선언 삼단논법이라는 이름이 있다. ($\supseteq$) 방향에서 $x \in A$로부터 $x \in A \cup B$를 얻는 줄은 그 자체로는 $\Rightarrow$뿐이다(확인 7). 좌우변이 실제로는 동치이지만($(P \lor Q) \land \neg Q \equiv P \land \neg Q$), 그 동치를 한 줄로 잇는 법칙(모순 $P \land \neg P \equiv F$, 항등)이 9주차 목록 8개에 없어 근거 ④로 인용할 수 없다 — 그래서 이 명제는 두 파트로 쓴다. ### 문제 9 **접근.** 문제의 힌트대로 좌변을 번역한다. 바깥의 차집합에서 $x \in A$가 나오고, 안쪽 차집합의 부정에 드모르간 1이 적용되어 "또는"이 생긴다. 그 "또는"의 왼쪽 갈래 $x \notin A$는 바깥의 $x \in A$와 동시에 성립할 수 없으므로 소멸한다. **풀이.** 임의의 $x$에 대해, 차집합의 정의를 두 번 적용하면 $$ x \in A - (A - B) \iff x \in A \land \neg(x \in A \land x \notin B) $$ 이고, 드모르간 1에 의해 오른쪽 조각은 $x \notin A \lor x \in B$가 되므로 $$ x \in A - (A-B) \iff x \in A \land (x \notin A \lor x \in B) $$ 이다. 여기서 $x \in A$가 참이므로 괄호 안의 $x \notin A$는 거짓이고, 따라서 괄호 전체는 $x \in B$와 동치다. ($x \in A$가 확정된 문맥에서 "또는"의 한 갈래가 소멸하는 이 조작은 문제 8의 선언 삼단논법과 같은 수다. 쓰인 동치는 $P \land (\neg P \lor Q) \equiv P \land Q$로 9주차 목록 8개에는 없지만, $P$가 참인 경우와 거짓인 경우 두 갈래로 나누면 즉시 확인된다 — $P$가 참이면 양변이 $Q$이고, $P$가 거짓이면 양변이 모두 거짓이다.) 그러므로 위 식은 $x \in A \land x \in B$, 곧 $x \in A \cap B$와 동치다. 모든 단계가 동치이므로 $A - (A - B) = A \cap B$이다. $\blacksquare$ **복기.** 한쪽이 이미 확정된 문맥에서 "또는"의 한 갈래가 소멸하는 조작은 문제 8과 같은 수이며, 28주차 문제에서 순서쌍 추적으로 다시 쓰인다. 검산: $A = \{1,2\}$, $B = \{2,3\}$이면 $A - B = \{1\}$, $A - \{1\} = \{2\}$이고 $A \cap B = \{2\}$이다. ### 문제 10 **접근.** iff이므로 파트가 둘이고, 각 파트 안에 다시 포함 증명이 들어 있다. ($\Rightarrow$)는 "$x \in B^c$라 하자"로 열고 $x \in A^c$로 닫는다. 중간에서 쓰는 추론이 19주차의 대우다 — "$x \in A$이면 $x \in B$"의 대우는 "$x \notin B$이면 $x \notin A$"이다. ($\Leftarrow$)는 방금 증명한 방향을 $B^c \subseteq A^c$에 그대로 적용해 얻는다. **풀이.** ($\Rightarrow$) $A \subseteq B$라 가정하자. $x \in B^c$라 하자. 여집합의 정의에 의해 $x \notin B$이다. 만약 $x \in A$라면 가정 $A \subseteq B$에 의해 $x \in B$가 되어 $x \notin B$와 모순이다. 따라서 $x \notin A$, 곧 $x \in A^c$이다. 임의의 원소에 대해 성립하므로 $B^c \subseteq A^c$이다. ($\Leftarrow$) $B^c \subseteq A^c$라 가정하자. 방금 증명한 ($\Rightarrow$)는 임의의 두 집합에 대한 명제이므로 $B^c$와 $A^c$에 적용할 수 있다. 그러면 $(A^c)^c \subseteq (B^c)^c$를 얻는다. 훈련 2에서 증명한 $(A^c)^c = A$, $(B^c)^c = B$를 대입하면 $A \subseteq B$이다. 양방향이 성립하므로 $A \subseteq B \iff B^c \subseteq A^c$이다. $\blacksquare$ **복기.** $P \Rightarrow Q$와 $\neg Q \Rightarrow \neg P$의 관계가 집합 세계에서 $A \subseteq B$와 $B^c \subseteq A^c$의 관계로 나타난다. 8주차에서 조건문을 진리집합으로 읽은 관점이 여기서 회수된다 — 논리와 집합이 같은 뼈대의 두 표기라는 사실의 가장 분명한 사례다. ### 문제 11 **접근.** 25주차 문제 12에서 "$6 \mid x \iff (2 \mid x) \land (3 \mid x)$"를 이미 증명했다. 원소 조건의 동치가 손에 있으면 상등 증명은 번역 두 번으로 끝난다 — 조건제시법 집합의 소속은 곧 조건의 참$\cdot$거짓이기 때문이다. 동치를 인용하지 않고 직접 양방향으로 써도 된다. **풀이.** 임의의 정수 $x$에 대해, 조건제시법의 정의에 의해 $$ x \in \{x \in \mathbb{Z} : 6 \mid x\} \iff 6 \mid x $$ 이고, 25주차 문제 12에 의해 $6 \mid x \iff (2 \mid x) \land (3 \mid x)$이며, 다시 조건제시법과 교집합의 정의에 의해 $$ (2 \mid x) \land (3 \mid x) \iff x \in \{x \in \mathbb{Z} : 2 \mid x\} \cap \{x \in \mathbb{Z} : 3 \mid x\} $$ 이다. 세 동치를 이으면 모든 단계가 $\iff$이므로 두 집합은 같다. $\blacksquare$ **복기.** 원소 조건의 동치는 곧 집합의 상등이다. 거꾸로 말하면, 두 집합이 같음을 보이는 가장 짧은 길은 소속 조건 두 개가 동치인 명제를 이미 증명해 두는 것이다. 검산: $x = 12$는 세 조건을 모두 만족하므로 양변 모두에 속한다. $x = 4$는 $2 \mid 4$이지만 $3 \nmid 4$이므로 교집합에 들지 않고, $6 \nmid 4$이므로 좌변에도 들지 않는다 — 두 집합에서 동시에 빠진다. ### 문제 12 **접근.** 예제 2.3과 같은 유형이다. 두 생성식의 상수항 차이가 $3 - (-2) = 5$로 계수와 같으므로, 5를 하나 옮겨 증인을 만들 수 있다. ($\subseteq$)의 증인은 $k + 1$, ($\supseteq$)의 증인은 $k - 1$이다. **풀이.** ($\subseteq$) $x \in \{5k + 3 : k \in \mathbb{Z}\}$라 하자. 정의에 의해 $x = 5k + 3$인 정수 $k$가 존재한다. 그러면 $$ x = 5k + 3 = 5k + 5 - 2 = 5(k + 1) - 2 $$ 이고 $k + 1$은 정수이므로, $x \in \{5k - 2 : k \in \mathbb{Z}\}$이다. ($\supseteq$) $x \in \{5k - 2 : k \in \mathbb{Z}\}$라 하자. 정의에 의해 $x = 5k - 2$인 정수 $k$가 존재한다. 그러면 $$ x = 5k - 2 = 5k - 5 + 3 = 5(k - 1) + 3 $$ 이고 $k - 1$은 정수이므로, $x \in \{5k + 3 : k \in \mathbb{Z}\}$이다. 양방향 포함이 성립하므로 두 집합은 같다. $\blacksquare$ **복기.** 생성형 집합 $\{5k + r : k \in \mathbb{Z}\}$는 상수항 $r$을 5만큼 바꿔도 같은 집합이다 — 5로 나눈 나머지가 같은 수 전체를 가리키기 때문이다. 이 관찰은 20주차의 합동 개념과 같은 내용이고, 40주차에서 함수의 치역을 조건제시법으로 다시 쓸 때 그대로 쓰인다. ### 문제 13 **접근.** §1.7의 절차를 따른다. 실험: $A = \{1,2\}$, $B = \{2,3\}$이면 좌변은 $\{1\} \cup \{3\} = \{1,3\}$이고 우변은 $\{1,2,3\} - \{2\} = \{1,3\}$으로 일치한다. 참으로 짐작하고 증명으로 간다. 각 방향에서 "또는"이 나올 때마다 경우를 나눈다. **풀이.** ($\subseteq$) $x \in (A-B) \cup (B-A)$라 하자. 합집합의 정의에 의해 두 경우다. 경우 1($x \in A - B$): $x \in A$이고 $x \notin B$이다. $x \in A$이므로 $x \in A \cup B$이다. 또 $x \in A \cap B$라면 $x \in B$가 되어 $x \notin B$와 모순이므로 $x \notin A \cap B$이다. 따라서 $x \in (A \cup B) - (A \cap B)$이다. 경우 2($x \in B - A$): $A$와 $B$의 역할만 바꾸면 된다. $x \in B$이고 $x \notin A$이므로 $x \in A \cup B$이고, $x \in A \cap B$라면 $x \in A$가 되어 모순이므로 $x \notin A \cap B$이다. 따라서 $x \in (A \cup B) - (A \cap B)$이다. ($\supseteq$) $x \in (A \cup B) - (A \cap B)$라 하자. 차집합의 정의에 의해 $x \in A \cup B$이고 $x \notin A \cap B$이다. 앞의 조건에서 두 경우다. 경우 1($x \in A$): 만약 $x \in B$라면 $x \in A \cap B$가 되어 모순이므로 $x \notin B$이다. 따라서 $x \in A - B$이고 $x \in (A-B) \cup (B-A)$이다. 경우 2($x \in B$): 대칭으로 $x \notin A$이므로 $x \in B - A$이고 $x \in (A-B) \cup (B-A)$이다. 양방향 포함이 성립하므로 두 집합은 같다. $\blacksquare$ **복기.** 이 집합은 "정확히 한쪽에만 속하는 원소들"이며 **대칭차**라 부르고 $A \triangle B$로 쓴다 — 기호는 "에이 대칭차 비"로 읽는다. 7주차 문제 8에서 만든 배타적 또는의 진리표 (F, T, T, F)가 그대로 이 집합의 소속 조건이다. 검산: $A = \{1,2\}$, $B = \{2,3\}$에서 $A \triangle B = \{1,3\}$이고 2는 양쪽에 속하므로 빠진다. ### 문제 14 **접근.** 우변에서 $C$가 $A$와 아무런 관계 없이 통째로 더해진다는 점이 수상하다. 좌변은 $A$의 부분집합인데 우변은 $C$를 통째로 포함하므로, $C$에 $A$ 바깥의 원소를 두면 두 변이 어긋난다. §1.7의 실험 단계에서 이 관찰을 그대로 반례로 만든다. **풀이.** 반증한다. 반례: $A = \{1\}$, $B = \{2\}$, $C = \{3\}$. 좌변을 계산하면 $B - C = \{2\} - \{3\} = \{2\}$이므로 $$ A - (B - C) = \{1\} - \{2\} = \{1\} $$ 이고, 우변을 계산하면 $A - B = \{1\} - \{2\} = \{1\}$이므로 $$ (A - B) \cup C = \{1\} \cup \{3\} = \{1, 3\} $$ 이다. $\{1\} \neq \{1,3\}$이므로 주어진 등식은 임의의 집합에 대해 성립하지 않는다. $\blacksquare$ **복기.** 반례를 만들 때는 "우변에만 들어갈 수 있는 원소"를 노린다 — 여기서는 $C$의 원소 3이다. 참인 변형은 $A - (B - C) = (A - B) \cup (A \cap C)$이며, $C$ 자리에 $A \cap C$가 들어가 $A$ 바깥의 원소가 차단된다. $A = \{1\}$, $B = \{2\}$, $C = \{3\}$을 넣으면 $A \cap C = \emptyset$이므로 양변이 모두 $\{1\}$로 일치한다. ### 문제 15 **접근.** iff이므로 파트가 둘이다. ($\Rightarrow$)는 6주차 문제 19에서 설명 수준으로 다룬 사실을 정식 증명으로 승격시키는 것이고, "$A - B$에 원소가 있다면"으로 시작해 모순을 끌어낸다. ($\Leftarrow$)는 포함 증명이므로 "$x \in A$라 하자"로 열고, $x \notin B$를 가정하면 공집합에 원소가 있게 되는 모순을 쓴다. **풀이.** ($\Rightarrow$) $A \subseteq B$라 가정하자. 모순을 위해 $A - B$에 원소 $x$가 있다고 하자. 차집합의 정의에 의해 $x \in A$이고 $x \notin B$이다. 그런데 $A \subseteq B$와 $x \in A$로부터 $x \in B$이므로 $x \notin B$와 모순이다. 따라서 $A - B$에는 원소가 하나도 없다: $A - B = \emptyset$이다. ($\Leftarrow$) $A - B = \emptyset$이라 가정하자. $x \in A$라 하자. 만약 $x \notin B$라면 차집합의 정의에 의해 $x \in A - B = \emptyset$이 되어, 공집합에 원소가 있다는 모순이 생긴다. 따라서 $x \in B$이다. 임의의 원소에 대해 성립하므로 $A \subseteq B$이다. 양방향이 성립하므로 $A \subseteq B \iff A - B = \emptyset$이다. $\blacksquare$ **복기.** "$X = \emptyset$을 보인다"는 목표는 "$X$에 원소가 있다고 가정해 모순을 끌어낸다"로 실행한다 — 공집합은 원소를 하나도 갖지 않는다는 정의 (정의 3.2)가 모순의 재료가 된다. 이 수는 29주차 반증 주간과 33주차 이후에서 반복해서 쓰인다. ### 문제 16 **접근.** 먼저 실험한다. $A = B = \{1\}$이면 $A \cup B = A \cap B = \{1\}$로 우변 조건이 성립하고, $A = \{1\}$, $B = \{2\}$이면 $A \cup B = \{1,2\}$, $A \cap B = \emptyset$이라 성립하지 않는다. 참으로 짐작하고 증명한다. ($\Leftarrow$)에서 $A \cup B \subseteq A \cap B$라는 조건이 원소를 양쪽으로 동시에 밀어 넣는다는 점이 핵심이다. **풀이.** 증명한다. ($\Rightarrow$) $A = B$라 가정하자. 보일 것은 포함 $A \cup B \subseteq A \cap B$ 하나이므로 원소 추적으로 곧장 간다. $x \in A \cup B$라 하자. 합집합의 정의에 의해 $x \in A$ 또는 $x \in B$이다. 경우 1($x \in A$): 가정 $A = B$를 대입하면 $x \in B$이기도 하다. 경우 2($x \in B$): 같은 대입으로 $x \in A$이기도 하다. 어느 경우든 $x \in A$이고 $x \in B$이므로, 교집합의 정의에 의해 $x \in A \cap B$이다. 임의의 원소에 대해 성립하므로 $A \cup B \subseteq A \cap B$이다. ($\Leftarrow$) $A \cup B \subseteq A \cap B$라 가정하자. 먼저 $A \subseteq B$를 보인다. $x \in A$라 하자. 합집합의 정의에 의해 $x \in A \cup B$이고, 가정에 의해 $x \in A \cap B$이므로 교집합의 정의에 의해 $x \in B$이다. 따라서 $A \subseteq B$이다. 다음으로 $B \subseteq A$를 보인다. $x \in B$라 하자. 같은 방식으로 $x \in A \cup B$이고 가정에 의해 $x \in A \cap B$이므로 $x \in A$이다. 따라서 $B \subseteq A$이다. 양방향 포함이 성립하므로 정의 27.1에 의해 $A = B$이다. 양방향이 성립하므로 $A = B \iff A \cup B \subseteq A \cap B$이다. $\blacksquare$ **복기.** $A \cap B \subseteq A \cup B$는 언제나 참이므로(5주차 문제 15), 이 문제의 조건은 사실상 $A \cup B = A \cap B$와 같다. 합집합과 교집합이 같아지는 상황이 곧 두 집합이 같은 상황이라는 것이 이 명제의 내용이다. ### 문제 17 **접근.** 원소 추적으로 처음부터 다시 쓸 필요가 없다. 예제 2.1은 "임의의 집합 $A, B$"에 대한 정리이므로 $A$ 자리에 $A \cup B$를 통째로 넣어도 된다. §4 문제 17 앞 상자의 표기 약속으로 세 집합을 둘로 묶은 뒤 예제 2.1을 두 번 적용하는 조립 증명이 가장 짧다. **풀이.** $A \cup B \cup C$는 $(A \cup B) \cup C$를 뜻한다(세 집합 합집합의 표기 약속 — §4 문제 17 앞 상자, 근거 ①). 예제 2.1을 두 집합 $A \cup B$와 $C$에 적용하면 $$ \big((A \cup B) \cup C\big)^c = (A \cup B)^c \cap C^c $$ 이고, 다시 예제 2.1을 두 집합 $A$와 $B$에 적용하면 $(A \cup B)^c = A^c \cap B^c$이므로 $$ (A \cup B \cup C)^c = (A^c \cap B^c) \cap C^c = A^c \cap B^c \cap C^c $$ 이다. 마지막 등호는 $(A^c \cap B^c) \cap C^c$를 $A^c \cap B^c \cap C^c$로 적는 표기 약속이다(같은 상자, 근거 ①) — 결합법칙은 쓰이지 않았다. $\blacksquare$ **복기.** 이미 증명한 정리(예제 2.1)를 부품으로 재사용하면 원소 추적 없이 조립만으로 끝난다(근거 ④). 나머지 두 등호는 표기를 풀고 되감는 일이라 내용이 없다. 같은 조립을 $n$번 반복하는 일반 버전은 귀납법이 필요하고, 31주차 문제 14가 정확히 그 문제이며 기초 단계가 이 주의 예제 2.1이다. ### 문제 18 **접근.** 5주차 문제 17에서 쌍둥이 항등식 $A - (B \cup C) = (A-B) \cap (A-C)$를 수치로 확인했으므로 이쪽도 참일 가능성이 높다. 실험으로 확인한 뒤 번역한다. $P$: $x \in A$, $Q$: $x \in B$, $R$: $x \in C$로 두면 좌변은 $P \land \neg(Q \land R)$이고 우변은 $(P \land \neg Q) \lor (P \land \neg R)$이다. 드모르간 1로 괄호를 풀고 분배 1을 쓰면 이어진다. **풀이.** 증명한다. 임의의 $x$에 대해 차집합$\cdot$교집합의 정의로 번역하면 $$ x \in A - (B \cap C) \iff x \in A \land \neg(x \in B \land x \in C) $$ 이고, 드모르간 1에 의해 $$ \iff x \in A \land (x \notin B \lor x \notin C) $$ 이며, 분배 1에 의해 $$ \iff (x \in A \land x \notin B) \lor (x \in A \land x \notin C) $$ 이다. 마지막 식을 차집합과 합집합의 정의로 역번역하면 $x \in (A - B) \cup (A - C)$이다. 모든 단계가 동치이므로 $A - (B \cap C) = (A - B) \cup (A - C)$이다. $\blacksquare$ **복기.** 인용한 법칙이 두 개(드모르간 1, 분배 1)라는 점이 앞의 문제들과 다르다. 번역해 놓고 나면 어떤 법칙을 어느 순서로 쓸지가 논리식의 모양만으로 정해진다. 검산: $A = \{1,2,3\}$, $B = \{2\}$, $C = \{3\}$이면 $B \cap C = \emptyset$이라 좌변은 $\{1,2,3\}$이고, 우변은 $\{1,3\} \cup \{1,2\} = \{1,2,3\}$이다. ### 문제 19 **접근.** 결론이 거짓인데 논증이 그럴듯하면 오류는 계산이 아니라 사용한 연산에 있다(1주차 문제 6과 같은 진단 구조). 여기서 쓰인 '지우기'는 등식 양변에서 $A \cap$를 벗기는 조작인데, 이것이 허용되려면 $\cap$에 역연산이 있어야 한다. 반례는 $B$와 $C$가 $A$ 바깥에서만 다르도록 만들면 된다. **풀이.** '지우기'는 정당한 연산이 아니다. 근거 목록 ①~④ 어디에도 "집합 등식의 양변에서 같은 연산을 벗겨도 된다"는 항목이 없고, 실제로 $A \cap$는 $A$ 바깥의 정보를 전부 버리는 연산이라 벗겨 낼 방법이 없다. 등식 양변에 같은 연산을 **더하는** 것과 이미 적용된 연산을 **되돌리는** 것은 다른 일이다. 명제 자체도 거짓이다. 반례: $A = \{1\}$, $B = \{1, 2\}$, $C = \{1, 3\}$. 이때 $A \cap B = \{1\}$이고 $A \cap C = \{1\}$이므로 가정 $A \cap B = A \cap C$는 성립하지만, $2 \in B$이고 $2 \notin C$이므로 $B \neq C$이다. $\blacksquare$ **복기.** 수의 등식에서 양변을 0으로 나눌 수 없듯이, 집합 등식에서도 되돌릴 수 없는 연산은 벗겨 낼 수 없다. 등식 변형에 쓸 수 있는 것은 가역인 조작뿐이며, 이는 25주차 동치 사슬의 규율과 같은 원리다. 38주차의 나머지류 계산에서 $\mathbb{Z}_6$에서 "$[2][1] = [2] = [8] = [2][4]$인데 $[1] \neq [4]$"라는 같은 계열의 현상을 다시 만난다. ### 문제 20 **접근.** (a)는 예제 2.1의 여섯 줄 중 어느 줄이 실제로 참$\cdot$거짓을 바꾸었는지 지목하는 문제다. (b)는 §1.6의 압축 자격 조건을 뒤집어 말하는 문제다 — 사슬이 무엇을 전제로 두 파트를 대신했는지 밝히면 답이 나온다. **풀이.** (예시 답안) (a) 예제 2.1에서 집합 정의에 의한 번역과 역번역은 같은 사실을 다른 표기로 옮겨 적은 것뿐이고, $\neg(P \lor Q)$를 $\neg P \land \neg Q$로 바꾼 드모르간 적용만이 내용을 가진 한 걸음이었다. 곧 집합 항등식의 참은 대응하는 논리 동치에 들어 있고, 집합 증명은 그것을 번역해 옮기는 작업이다. (b) 동치 사슬은 모든 단계가 왕복 가능하다는 전제 아래 양방향 포함을 한 줄로 압축한 것이므로, 한 단계라도 일방통행이면 ($\supseteq$) 방향의 근거가 사라져 두 파트를 따로 써야 한다. **복기.** (a)의 관점은 이후 계속 쓰인다 — 집합에 관한 새 항등식을 만나면 먼저 논리식으로 번역해 9주차 목록에 이미 있는 법칙인지 확인한다. 목록에 있으면 증명은 번역$\cdot$인용$\cdot$역번역 세 줄로 끝난다. --- **다음 주 예고:** 데카르트 곱$\cdot$멱집합$\cdot$첨자 집합이 얽힌 심화 집합 증명을 다룬다. $A \times (B \cap C) = (A \times B) \cap (A \times C)$처럼 원소가 **순서쌍**인 추적, 멱집합 $\mathcal{P}$가 낀 iff, 그리고 첨자 집합 $\bigcup_i$의 드모르간이 차례로 나온다. 이번 주의 세 걸음(번역 $\to$ 조작 $\to$ 역번역)이 그대로 쓰이고, 바뀌는 것은 번역표 한 줄뿐이다.