# 27주차 — 집합 포함과 상등의 증명 :::{admonition} 이 주의 길잡이 :class: keybox **핵심 문장**: 집합 증명의 첫 문장은 언제나 "$x \in A$라 하자"이고, 그다음은 정의 번역과 논리 조작뿐이다. **이 주의 위치**: 50주 과정의 27주차. 4주차의 원소 추적과 9주차의 동치 목록을 합쳐, 5주차에서 그림으로 관찰만 했던 드모르간 법칙을 정식으로 증명한다. **원서 대응**: BoP(Book of Proof) 8.1–8.3 (How to Prove $a \in A$ / $A \subseteq B$ / $A = B$) — 병행자 참고용. 원서 없이 읽을 수 있다. ::: ## 이번 주 목표 1. $A \subseteq B$ 증명(원소 추적)과 $A = B$ 증명(양방향 포함)의 서식을 백지에 쓰고 실행할 수 있다. 1. 드모르간 법칙$\cdot$분배법칙을 9주차 동치 목록을 근거로 삼아 엄밀하게 증명할 수 있다. 1. 조건제시법$\cdot$생성형 집합의 상등을 증인 제작으로 증명할 수 있다 — 3주차 문제 9에서 미뤄 둔 항목을 갚는다. 1. "증명 또는 반증" 절차로 집합 항등식의 참$\cdot$거짓을 판별하고, 거짓이면 구체적 반례를 제시할 수 있다. 본문 곳곳의 **확인** 상자는 연필로 먼저 답하는 자리다. 바로 아래의 **답** 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다. ## 준비 운동 (26주차 복습) 1. $A \subseteq B$의 정의를 쓰시오 (4주차 정의 4.1). 1. $x \in A \cup B$, $x \in A \cap B$, $x \in A - B$, $x \in A^c$를 각각 논리식으로 번역하시오 (5$\cdot$7주차). 1. 논리의 드모르간 법칙 2개와 분배법칙 1개를 쓰시오 (9주차). 1. 임의의 집합 $A, B$에 대해 $(A \cup B)^c = A^c \cap B^c$가 성립함을, 지금 아는 방법으로 설명해 보시오. 1. 존재 명제 "$x = 3k + 1$인 정수 $k$가 존재한다"를 증명하는 서식(증인 제작과 조건 검증)을 $x = 7$에 대해 쓰시오 (26주차). ### 자주 나오는 세 가지 답 — 4번 문항 방금 쓴 답은 대개 다음 세 유형 중 하나다. 셋 다 옳은 부분이 있고, 셋 다 이번 주에 메울 정확한 간격이 있다. - **유형 1 — 벤 다이어그램.** 원 두 개를 겹쳐 그리고 양쪽 영역을 칠해 같은 자리가 남는 것을 보인다. 5주차에서 실제로 한 작업이고, 관찰로서는 정확하다. 빠진 것은 그림이 덮는 범위다 — 그린 것은 두 원이 겹치는 배치 **한 장**이다. 서로소인 경우, 한쪽이 다른 쪽에 포함되는 경우, 집합이 셋 이상인 경우까지 그 한 장이 대표하는지를 그림 자체는 말해 주지 않는다. - **유형 2 — 구체적 집합 대입.** $U = \{1, \dots, 6\}$, $A = \{1,2,3\}$, $B = \{3,4\}$ 같은 예를 몇 개 넣어 양변이 같음을 확인한다. 계산은 옳고, 거짓인 항등식을 걸러내는 데는 이 방법이 가장 빠르다(§1.7에서 정식 절차로 쓴다). 문제는 주장이 "임의의 집합 $A, B$"에 대한 것이라는 점이다 — 확인한 사례 밖에서 무너지는 주장의 표본은 1주차 문제 18에 있다. - **유형 3 — 말로 설명.** "합집합의 바깥이면 둘 다의 바깥이니까 당연하다." 이 직관은 옳고, 실제로 증명의 내용도 이 문장이다. 빠진 것은 번역이다 — "둘 다의 바깥"이 $x \notin A$이고 $x \notin B$라는 논리식이 되고, "당연하다"가 9주차에 등록된 동치 법칙의 인용이 되어야 검사 가능한 증명이 된다. ## 개념 — 집합의 주장을 증명 가능한 꼴로 ### 1 그림과 예로 밀어붙이면 어디서 막히는가 증명을 시작하기 전에 실패 사례를 본다. 준비 운동 4번을 이미 아는 도구 두 가지로 끝까지 밀어붙여 보자. :::{admonition} 시도 1 — 그림으로 밀어붙이기 :class: quotebox 명제: 임의의 집합 $A, B$에 대해 $(A \cup B)^c = A^c \cap B^c$. "원 두 개를 서로 겹치게 그린다. $A \cup B$는 두 원이 덮는 영역이므로 $(A \cup B)^c$는 두 원 바깥의 영역이다. $A^c$는 왼쪽 원 바깥, $B^c$는 오른쪽 원 바깥이므로 그 교집합도 두 원 바깥의 영역이다. 따라서 … " ::: 여기서 멈춘다. 다음 줄에 쓸 말이 "따라서 그림이 같다"뿐인데, 명제가 주장하는 것은 그려 본 그 배치가 아니라 **임의의** $A, B$이다. :::{admonition} 시도 2 — 예로 밀어붙이기 :class: quotebox "$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 **확인 1.** 두 시도에 공통으로 빠진 것은 무엇인가. 1주차에서 "모든 짝수"를 다루기 위해 한 일을 떠올려, 한 구절로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown **임의의 대상을 대표하는 문자**다. 1주차에서는 특정 숫자 6 대신 문자 $m$을 무대에 올려 "모든 짝수"를 한 번에 처리했다. 집합에서 그 문자에 해당하는 것은 집합 자체가 아니라 **원소** $x$이다 — 상등도 포함도 결국 "각 원소가 어느 쪽에 속하는가"의 문제이기 때문이다(3주차 상등 기준). 그림은 배치 하나를, 예는 집합 하나를 보여 준다. 문자 $x$ 하나는 원소 전부를 대표한다. ::: :::{admonition} 이 주 전체의 기준 :class: quotebox 집합에 대한 주장을 증명하려면 원소 하나를 문자로 잡아 추적한다. 그림과 예는 참$\cdot$거짓을 짐작하는 실험 도구이고, 근거 목록에는 없다. ::: ### 2 상등을 검사 가능한 절차로 — 표 채우기 3주차에서 세운 상등 기준은 "원소가 완전히 같다"였다. 이 기준은 옳지만 절차가 아니다 — 원소가 무한히 많으면 대조를 끝낼 수 없다. 유한한 사례부터 채워 절차를 찾아보자. | **사례** | **$A \subseteq B$** | **$B \subseteq A$** | **$A = B$** | |---|---|---|---| | $A = \{1,2\}$, $B = \{1,2,3\}$ | 참 | 거짓 | 거짓 | | $A = \{1,2\}$, $B = \{2,1\}$ | 참 | $\underline{\quad(1)\quad}$ | $\underline{\quad(2)\quad}$ | | $A = \{1,2\}$, $B = \{2,3\}$ | 거짓 | $\underline{\quad(3)\quad}$ | 거짓 | | $A = \emptyset$, $B = \emptyset$ | 참 | $\underline{\quad(4)\quad}$ | $\underline{\quad(5)\quad}$ | :::{container} quotebox **확인 2.** 빈칸 (1)~(5)를 채우고, 마지막 열이 "참"인 행의 공통점을 앞의 두 열로 한 문장으로 적어 보자. ::: :::{admonition} 답 :class: quotebox dropdown (1) 참 (2) 참 (3) 거짓 (4) 참 (5) 참. 마지막 열이 참인 행은 정확히 **앞의 두 열이 동시에 참인 행**이다. 첫째 행처럼 한쪽만 참이면 상등이 아니다 — $B$에 여분의 원소 3이 남아 있다. 셋째 행처럼 양쪽 다 거짓이어도 아니다. 상등의 판정이 포함 판정 두 번으로 환원된다는 것이 이 표의 관찰이다. ::: 이 관찰에 정식 이름과 형식을 붙인다. 식 자체에 새로운 것은 없다 — 3주차의 상등 기준을 방금 표에서 한 두 번의 대조로 바꿔 적었을 뿐이다. ### 정의 27.1 — 상등의 판정 기준: 양방향 포함 (double inclusion) [백지 암기 대상] :::{container} quotebox 3주차의 상등 기준("원소가 완전히 같다")으로부터: 집합 $A, B$에 대해 $A = B$인 것과 ($A \subseteq B$이고 $B \subseteq A$)인 것은 서로 필요충분이다. 기호로는 $A = B \iff (A \subseteq B) \land (B \subseteq A)$. ::: 상등의 정의는 3주차의 것 하나이고, 27.1은 그 정의를 검사 가능한 절차로 바꾼 **판정 기준**이다. 새 기호는 없다. 증명에서 이 한 문장은 **의무 두 개**로 읽힌다. **왜 3주차 정의와 같은 말인가** — 이 한 단락이 판정 기준의 증명이다. $A \subseteq B$는 "$A$의 원소는 전부 $B$에도 있다"이고 $B \subseteq A$는 그 반대이므로, 둘이 동시에 성립하면 "어느 한쪽에만 있는 원소가 하나도 없다", 곧 3주차의 기준대로 원소가 완전히 같다. 거꾸로 원소가 완전히 같으면 $A$의 원소는 전부 $B$에 있고 $B$의 원소는 전부 $A$에 있으므로 두 포함이 모두 성립한다. 두 방향이 모두 확인되었으므로 상등과 양방향 포함은 서로 필요충분이다. :::{container} quotebox **확인 3.** $A \subseteq B$ 한 방향만 증명하고 "따라서 $A = B$"로 끝낸 답안이 있다. 무엇이 보장되지 않는가. 반례가 되는 두 집합을 하나 들어 보자. ::: :::{admonition} 답 :class: quotebox dropdown $B$에 $A$ 바깥의 원소가 남아 있을 가능성이 보장되지 않는다. $A = \{1,2\}$, $B = \{1,2,3\}$이 반례다 — $A \subseteq B$는 참이지만 $3 \in B$, $3 \notin A$이므로 $A \neq B$이다. 두 방향은 각각 다른 여분을 금지한다: $A \subseteq B$는 $A$쪽의 여분을, $B \subseteq A$는 $B$쪽의 여분을 막는다. ::: ### 3 정의 해부 — 조각마다 하는 일 정의 27.1은 세 조각으로 되어 있고, 조각마다 판정에서 맡는 역할이 다르다. | **조각** | **하는 일** | **판정에서의 역할** | |---|---|---| | "$A \subseteq B$" | 왼쪽에서 오른쪽으로 건너감을 요구 | 첫째 파트 — "$x \in A$라 하자"로 시작해 $x \in B$로 끝낸다 | | "이고" | 두 요구의 **결합** | 한쪽만 쓰면 미완성이다 — 두 파트를 각각 끝까지 쓴다 | | "$B \subseteq A$" | 반대 방향의 건너감을 요구 | 둘째 파트 — "$x \in B$라 하자"로 시작해 $x \in A$로 끝낸다 | **조각 삭제 실험.** 가운데 조각과 셋째 조각, 즉 "이고 $B \subseteq A$"를 지워 보자. 그러면 $\{1,2\} \subseteq \{1,2,3\}$이므로 $\{1,2\} = \{1,2,3\}$이 참이 된다. 같은 방식으로 $\emptyset$은 모든 집합과 같아지고($\emptyset \subseteq B$는 항상 참), "같다"는 말은 아무것도 구별하지 못한다 — 1주차 §1.3에서 "짝수"의 정의가 무너진 것과 같은 붕괴다. ### 4 세 가지 증명 목표와 서식 [백지 암기 대상] 이번 주에 마주칠 목표는 세 가지뿐이고, 목표의 꼴이 첫 문장과 마지막 문장을 정한다. 무엇을 쓸지 고민하는 자리가 아니라 표를 읽는 자리다. | **목표** | **첫 문장** | **마지막 문장** | |---|---|---| | $a \in A$ | $A$의 조건($A = \{x : P(x)\}$)을 꺼낸다 | $P(a)$가 참이므로 $a \in A$이다 | | $A \subseteq B$ | $x \in A$라 하자 | 따라서 $x \in B$이므로 $A \subseteq B$이다 | | $A = B$ | ($\subseteq$) $x \in A$라 하자 … ($\supseteq$) $x \in B$라 하자 | 양방향 포함이 성립하므로 $A = B$이다 | 첫 문장에서 잡는 $x$는 특정 원소가 아니라 **임의의 원소**다 — 증명의 어느 줄도 "$x$는 3이다" 같은 정보를 쓰지 않으므로 논증이 $A$의 어느 원소에나 적용된다 (1주차 확인 13의 일반성). $A = B$의 서식이 두 파트인 것은 정의 27.1의 "이고" 조각을 실행한 결과이며, 3주차 문제 16과 5주차 문제 16$\cdot$19에서 이 2파트 서식을 이름 없이 세 번 예습했다. :::{container} quotebox **확인 4.** 다음 각 목표에 대해 첫 문장을 적어 보자. (가) $\{x \in \mathbb{Z} : 6 \mid x\} \subseteq \{x \in \mathbb{Z} : 3 \mid x\}$ (나) $(A \cap B)^c = A^c \cup B^c$ (다) $-12 \in \{4k : k \in \mathbb{Z}\}$ ::: :::{admonition} 답 :class: quotebox dropdown (가) "$x \in \{x \in \mathbb{Z} : 6 \mid x\}$라 하자." 곧 "$6 \mid x$인 정수 $x$를 임의로 잡자"와 같은 말이다. (나) "($\subseteq$) $x \in (A \cap B)^c$라 하자." 그리고 그 파트가 끝난 뒤 "($\supseteq$) $x \in A^c \cup B^c$라 하자."로 둘째 파트를 연다. (다) 원소 판정이므로 잡을 원소가 없다 — 조건 $x = 4k$를 만족시키는 정수 $k$를 제시하는 것이 전부다: $-12 = 4 \times (-3)$. ::: ### 5 번역 사전 — 집합 기호를 논리식으로 첫 문장을 쓰고 나면 손에 "$x \in (\text{어떤 집합 표현})$"이 남는다. 그다음 할 일은 1주차 이래 매주 같다 — **정의를 풀어 쓴다**. 집합 연산의 정의(5주차)가 곧 논리식으로의 번역표다. | **집합 표현** | **논리식** | **번역의 근거** | |---|---|---| | $x \in A \cup B$ | $x \in A \lor x \in B$ | 합집합의 정의 (정의 5.1) | | $x \in A \cap B$ | $\underline{\quad(1)\quad}$ | 교집합의 정의 (정의 5.1) | | $x \in A - B$ | $\underline{\quad(2)\quad}$ | 차집합의 정의 (정의 5.1) | | $x \in A^c$ | $\underline{\quad(3)\quad}$ | 여집합의 정의 (정의 5.2) | :::{container} quotebox **확인 5.** 빈칸 (1)(2)(3)을 채워 보자. 새로 배우는 내용이 있는가. ::: :::{admonition} 답 :class: quotebox dropdown (1) $x \in A \land x \in B$ (2) $x \in A \land x \notin B$ (3) $x \notin A$. 새로 배우는 내용은 없다 — 5주차 정의 5.1$\cdot$5.2를 "그리고/또는/아니다"에서 $\land, \lor, \neg$로 기호만 바꿔 적은 것이다. 7주차에서 만든 논리–집합 사전이 그대로 이번 주의 번역표가 된다. ::: 번역을 하는 이유는 하나다. 9주차에서 진리표로 증명해 근거 ④에 등록한 동치 법칙 여덟 개는 **논리식에만** 적용되고, 번역한 뒤에는 그대로 쓸 수 있다. :::{admonition} 백지 암기 대상 :class: keybox **원소 추적의 세 걸음** ① 번역: 집합 표현을 정의로 풀어 논리식으로 바꾼다(근거 ①) $\to$ ② 조작: 9주차 동치 법칙으로 논리식을 목표 쪽 모양으로 바꾼다(근거 ④) $\to$ ③ 역번역: 정의를 거꾸로 써서 집합 표현으로 되돌린다(근거 ①) ::: 세 걸음 모두 진리값을 보존한다. 다만 ①$\cdot$③은 같은 명제를 다른 표기로 옮길 뿐이고, 식의 **모양**을 실제로 바꾸는 것은 ②뿐이다. ②가 비어 있는 항등식도 있다 — 훈련 1의 $A - B = A \cap B^c$가 그런 경우로, 번역과 역번역만으로 닫힌다. 세 걸음이 전부 진리값을 보존한다는 사실이 §1.6에서 사슬 압축을 정당화하는 근거다. ①$\cdot$③이 표기만 옮기고 ②가 모양을 바꾼다는 이 사정을 짧게 "논리 법칙이 엔진"이라 부른다 — 문제 20이 이 표현의 뜻을 묻는다. :::{container} quotebox **확인 6.** 예제 2.1에서 증명할 $(A \cup B)^c = A^c \cap B^c$의 좌변을 번역하면 $\neg(x \in A \lor x \in B)$이고, 우변을 번역하면 $x \notin A \land x \notin B$이다. 이 둘을 잇는 데 필요한 9주차 법칙은 어느 것인가. ::: :::{admonition} 답 :class: quotebox dropdown **드모르간 2**: $\neg(P \lor Q) \equiv \neg P \land \neg Q$. $P$를 "$x \in A$", $Q$를 "$x \in B$"로 두면 좌변의 번역이 그대로 $\neg(P \lor Q)$, 우변의 번역이 $\neg P \land \neg Q$이다. 집합의 드모르간 법칙은 논리의 드모르간 법칙을 번역해 옮긴 것이라는 사실이 여기서 드러난다. ::: ### 6 동치 사슬 — 두 파트를 한 줄로 압축하는 조건 번역$\cdot$조작$\cdot$역번역의 각 단계가 전부 $\iff$이면, 사슬을 왼쪽에서 오른쪽으로 읽는 것이 ($\subseteq$) 파트이고 오른쪽에서 왼쪽으로 읽는 것이 ($\supseteq$) 파트다. 사슬 하나로 두 파트를 처리할 수 있다(25주차 동치 사슬). 자격 조건은 하나다 — **모든 단계가 진짜 $\iff$인지 확인한다.** 한 단계라도 $\Rightarrow$ 방향만 성립하면 두 파트로 분리해 각각 써야 한다. :::{container} quotebox **확인 7.** 다음 두 단계 중 $\iff$인 것과 $\Rightarrow$뿐인 것을 가려 보자. (가) $x \in A \cap B \ \leftrightarrow\ x \in A \land x \in B$ (나) $x \in A \ \rightarrow\ x \in A \cup B$ ::: :::{admonition} 답 :class: quotebox dropdown (가)는 $\iff$이다 — 교집합의 정의 자체가 양방향의 약속이므로, 정의에 의한 번역은 언제나 왕복 가능하다. (나)는 $\Rightarrow$뿐이다. $A = \{1\}$, $B = \{2\}$, $x = 2$이면 $x \in A \cup B$이지만 $x \notin A$이므로 역방향이 무너진다. 정의 번역은 예외 없이 왕복 가능하고, 일방통행은 정의 번역이 아닌 단계 — 정보를 버리는 단계(한쪽으로 흡수하거나 조건을 느슨하게 하는 단계) — 에서만 생긴다. ::: ### 7 "증명 또는 반증" 모드 집합 등식이 주어졌는데 참인지 거짓인지 알려 주지 않는 문제가 이번 주부터 나온다(문제 13$\cdot$14$\cdot$16$\cdot$18). 절차를 고정해 둔다. 1. **실험.** 작은 집합을 대입하거나 벤 다이어그램을 그려 양변을 계산한다. 1. **판단.** 실험이 전부 일치하면 참으로 짐작하고, 한 번이라도 어긋나면 그 순간 거짓이 확정된다. 1. **실행.** 참이면 양방향 원소 추적(또는 동치 사슬)으로 증명하고, 거짓이면 어긋난 사례를 **반례**로 정식 제시한다. 실험은 근거가 아니라 방향을 정하는 절차다(§1.1). 다만 반례 제시는 다르다 — 구체적 집합 하나면 "임의의 $A, B, C$에 대해"라는 주장이 무너지므로, 이때는 계산 자체가 증명이 된다. :::{container} quotebox **확인 8.** 반례를 제시한 답안이 완결되려면 무엇을 함께 적어야 하는가. "$A = \{1\}$, $B = \{2\}$, $C = \{3\}$이면 성립하지 않는다"로 끝내면 무엇이 빠진 것인가. ::: :::{admonition} 답 :class: quotebox dropdown **양변을 실제로 계산해 서로 다름을 보이는 두 줄**이 빠졌다. 반례는 집합을 지목하는 것으로 끝나지 않는다 — 좌변이 무엇이고 우변이 무엇인지 각각 계산한 뒤 "$\{1\} \neq \{1,3\}$"처럼 다름을 명시해야 검사가 가능하다. 1주차 문제 18에서 $f(40) = 1681 = 41^2$까지 계산해 보인 것과 같은 요구다. ::: ### 8 근거 목록 갱신 — 칸은 그대로 네 개 이번 주에도 새 칸은 생기지 않는다. ① 칸에 정의 27.1이 추가되고, ④ 칸이 9주차 동치 목록을 본격적으로 쓰기 시작할 뿐이다. | **근거** | **내용** | **이번 주에는 이렇게 쓴다** | |---|---|---| | ① 정의 | 집합 상등(3주차)$\cdot$조건제시법(3주차), 부분집합(정의 4.1), 집합 연산(정의 5.1$\cdot$5.2), **상등 판정(정의 27.1)**, 세 집합 표기 약속(§4 문제 17 앞 상자) | "$x \in A \cup B$" $\leftrightarrow$ "$x \in A \lor x \in B$" 사이를 번역한다 | | ② 닫힘성 | 정수의 합$\cdot$차$\cdot$곱은 정수 | 증인 $k + 1$이 정수임을 별도 설명 없이 쓴다(예제 2.3) | | ③ 등식의 성질 | 대입 / 전개 / 묶기 | $3k + 1 = 3(k+1) - 2$로 고쳐 쓴다 | | ④ 이미 증명한 명제 | 9주차 동치 목록 8개, 1~26주차의 예제$\cdot$문제 | "드모르간 2에 의해"로 한 줄을 정당화한다 | 벤 다이어그램은 목록에 없다. 그림은 참$\cdot$거짓을 짐작하는 실험 도구이며, 답안의 어느 줄도 그림으로 정당화되지 않는다. :::{container} quotebox **확인 9.** 어떤 답안에 다음 세 문장이 나왔다. 각각 허용되는가. 허용된다면 몇 번 근거인가. (가) "벤 다이어그램에서 두 영역이 같으므로 두 집합은 같다" (나) "드모르간 2에 의해 $\neg(x \in A \lor x \in B)$는 $x \notin A \land x \notin B$와 동치이다" (다) "여집합의 정의에 의해 $x \in A^c$는 $x \notin A$이다" ::: :::{admonition} 답 :class: quotebox dropdown (가) 불허 — 그림은 목록 밖이다. 같은 관찰을 원소 추적으로 다시 쓰기 전에는 근거가 되지 않는다. (나) 허용 — 근거 ④. 9주차에서 진리표로 증명해 등록한 법칙이다. (다) 허용 — 근거 ①. 정의에 의한 번역이므로 양방향으로 쓸 수 있다. ::: 정의 27.1과 §1.4의 서식 표는 외운다 — 통째로만 외우지 말고 §1.3의 조각별 역할과 함께 외운다. 조각을 잊어도 "여분의 원소를 어느 쪽에서 막는가"에서 재구성할 수 있다.