27주차 — 집합 포함과 상등의 증명

내용

27주차 — 집합 포함과 상등의 증명#

이 주의 길잡이

핵심 문장: 집합 증명의 첫 문장은 언제나 “\(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\)) — 병행자 참고용. 원서 없이 읽을 수 있다.

이번 주 목표#

\(A \subseteq B\) 증명(원소 추적)과 \(A = B\) 증명(양방향 포함)의 서식을 백지에 쓰고 실행할 수 있다.
드모르간 법칙\(\cdot\)분배법칙을 9주차 동치 목록을 근거로 삼아 엄밀하게 증명할 수 있다.
조건제시법\(\cdot\)생성형 집합의 상등을 증인 제작으로 증명할 수 있다 — 3주차 문제 9에서 미뤄 둔 항목을 갚는다.
“증명 또는 반증” 절차로 집합 항등식의 참\(\cdot\)거짓을 판별하고, 거짓이면 구체적 반례를 제시할 수 있다.

본문 곳곳의 확인 상자는 연필로 먼저 답하는 자리다. 바로 아래의 답 상자는 (웹에서는 접혀 있다) 스스로 답한 뒤에 열어 대조한다.

준비 운동 (26주차 복습)#

\(A \subseteq B\)의 정의를 쓰시오 (4주차 정의 4.1).
\(x \in A \cup B\), \(x \in A \cap B\), \(x \in A - B\), \(x \in A^c\)를 각각 논리식으로 번역하시오 (5\(\cdot\)7주차).
논리의 드모르간 법칙 2개와 분배법칙 1개를 쓰시오 (9주차).
임의의 집합 \(A, B\)에 대해 \((A \cup B)^c = A^c \cap B^c\)가 성립함을, 지금 아는 방법으로 설명해 보시오.
존재 명제 “\(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번을 이미 아는 도구 두 가지로 끝까지 밀어붙여 보자.

시도 1 — 그림으로 밀어붙이기

명제: 임의의 집합 \(A, B\)에 대해 \((A \cup B)^c = A^c \cap B^c\).

“원 두 개를 서로 겹치게 그린다. \(A \cup B\)는 두 원이 덮는 영역이므로

\((A \cup B)^c\)는 두 원 바깥의 영역이다. \(A^c\)는 왼쪽 원 바깥, \(B^c\)는 오른쪽

원 바깥이므로 그 교집합도 두 원 바깥의 영역이다. 따라서 … “

여기서 멈춘다. 다음 줄에 쓸 말이 “따라서 그림이 같다”뿐인데, 명제가 주장하는 것은 그려 본 그 배치가 아니라 임의의 \(A, B\)이다.

시도 2 — 예로 밀어붙이기

“\(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\}\)이다. 일치한다.

다른 예로 바꿔도 일치한다. 따라서 … “

여기서도 멈춘다. 확인한 예는 유한 개이고, 확인하지 않은 집합의 조합은 무한히 많다.

확인 1. 두 시도에 공통으로 빠진 것은 무엇인가. 1주차에서 “모든 짝수”를

다루기 위해 한 일을 떠올려, 한 구절로 적어 보자.

답

임의의 대상을 대표하는 문자다. 1주차에서는 특정 숫자 6 대신 문자 \(m\)을

무대에 올려 “모든 짝수”를 한 번에 처리했다. 집합에서 그 문자에 해당하는

것은 집합 자체가 아니라 원소 \(x\)이다 — 상등도 포함도 결국 “각 원소가

어느 쪽에 속하는가”의 문제이기 때문이다(3주차 상등 기준).

그림은 배치 하나를, 예는 집합 하나를 보여 준다. 문자 \(x\) 하나는 원소 전부를

대표한다.

이 주 전체의 기준

집합에 대한 주장을 증명하려면 원소 하나를 문자로 잡아 추적한다.

그림과 예는 참\(\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}\)

확인 2. 빈칸 (1)~(5)를 채우고, 마지막 열이 “참”인 행의 공통점을

앞의 두 열로 한 문장으로 적어 보자.

답

(1) 참 (2) 참 (3) 거짓 (4) 참 (5) 참.

마지막 열이 참인 행은 정확히 앞의 두 열이 동시에 참인 행이다.

첫째 행처럼 한쪽만 참이면 상등이 아니다 — \(B\)에 여분의 원소 3이 남아 있다.

셋째 행처럼 양쪽 다 거짓이어도 아니다. 상등의 판정이 포함 판정 두 번으로

환원된다는 것이 이 표의 관찰이다.

이 관찰에 정식 이름과 형식을 붙인다. 식 자체에 새로운 것은 없다 — 3주차의 상등 기준을 방금 표에서 한 두 번의 대조로 바꿔 적었을 뿐이다.

정의 27.1 — 상등의 판정 기준: 양방향 포함 (double inclusion) [백지 암기 대상]#

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\)에 있으므로 두 포함이 모두 성립한다. 두 방향이 모두 확인되었으므로 상등과 양방향 포함은 서로 필요충분이다.

확인 3. \(A \subseteq B\) 한 방향만 증명하고 “따라서 \(A = B\)”로 끝낸 답안이

있다. 무엇이 보장되지 않는가. 반례가 되는 두 집합을 하나 들어 보자.

답

\(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파트 서식을 이름 없이 세 번 예습했다.

확인 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}\}\)

답

(가) “\(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)

확인 5. 빈칸 (1)(2)(3)을 채워 보자. 새로 배우는 내용이 있는가.

답

(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주차에서 진리표로 증명해 근거 ④에 등록한 동치 법칙 여덟 개는 논리식에만 적용되고, 번역한 뒤에는 그대로 쓸 수 있다.

백지 암기 대상

원소 추적의 세 걸음

① 번역: 집합 표현을 정의로 풀어 논리식으로 바꾼다(근거 ①) \(\to\) ② 조작: 9주차 동치 법칙으로 논리식을 목표 쪽 모양으로 바꾼다(근거 ④) \(\to\) ③ 역번역: 정의를 거꾸로 써서 집합 표현으로 되돌린다(근거 ①)

세 걸음 모두 진리값을 보존한다. 다만 ①\(\cdot\)③은 같은 명제를 다른 표기로 옮길 뿐이고, 식의 모양을 실제로 바꾸는 것은 ②뿐이다. ②가 비어 있는 항등식도 있다 — 훈련 1의 \(A - B = A \cap B^c\)가 그런 경우로, 번역과 역번역만으로 닫힌다. 세 걸음이 전부 진리값을 보존한다는 사실이 §1.6에서 사슬 압축을 정당화하는 근거다. ①\(\cdot\)③이 표기만 옮기고 ②가 모양을 바꾼다는 이 사정을 짧게 “논리 법칙이 엔진”이라 부른다 — 문제 20이 이 표현의 뜻을 묻는다.

확인 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주차 법칙은

어느 것인가.

답

드모르간 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\) 방향만 성립하면 두 파트로 분리해 각각 써야 한다.

확인 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\)

답

(가)는 \(\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). 다만 반례 제시는 다르다 — 구체적 집합 하나면 “임의의 \(A, B, C\)에 대해”라는 주장이 무너지므로, 이때는 계산 자체가 증명이 된다.

확인 8. 반례를 제시한 답안이 완결되려면 무엇을 함께 적어야 하는가.

“\(A = \{1\}\), \(B = \{2\}\), \(C = \{3\}\)이면 성립하지 않는다”로 끝내면

무엇이 빠진 것인가.

답

양변을 실제로 계산해 서로 다름을 보이는 두 줄이 빠졌다. 반례는 집합을

지목하는 것으로 끝나지 않는다 — 좌변이 무엇이고 우변이 무엇인지 각각

계산한 뒤 “\(\{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\)거짓을 짐작하는 실험 도구이며, 답안의 어느 줄도 그림으로 정당화되지 않는다.

확인 9. 어떤 답안에 다음 세 문장이 나왔다. 각각 허용되는가.

허용된다면 몇 번 근거인가.

(가) “벤 다이어그램에서 두 영역이 같으므로 두 집합은 같다”

(나) “드모르간 2에 의해 \(\neg(x \in A \lor x \in B)\)는 \(x \notin A \land x \notin B\)와 동치이다”

(다) “여집합의 정의에 의해 \(x \in A^c\)는 \(x \notin A\)이다”

답

(가) 불허 — 그림은 목록 밖이다. 같은 관찰을 원소 추적으로 다시 쓰기 전에는

근거가 되지 않는다.

(나) 허용 — 근거 ④. 9주차에서 진리표로 증명해 등록한 법칙이다.

(다) 허용 — 근거 ①. 정의에 의한 번역이므로 양방향으로 쓸 수 있다.

정의 27.1과 §1.4의 서식 표는 외운다 — 통째로만 외우지 말고 §1.3의 조각별 역할과 함께 외운다. 조각을 잊어도 “여분의 원소를 어느 쪽에서 막는가”에서 재구성할 수 있다.