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)\) |
확인 10. 도착점 칸의 빈칸을 채워 보자. “\(x \in A^c \cap B^c\)”를 정의로
두 번 번역하면 어떤 논리식이 되는가.
답
\(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의 서식대로 왼쪽 집합의 임의의 원소를 무대에 올린다.
확인 11. 첫 문장을 완성해 보자: “(\(\subseteq\)) \(\underline{\qquad}\)라 하자.”
답
“(\(\subseteq\)) \(x \in (A \cup B)^c\)라 하자.” 파트 표시 (\(\subseteq\))를 함께
적어 두면 채점자와 자신 모두 지금 어느 의무를 수행 중인지 알 수 있다.
2단계 — 정의를 풀어 논리식으로 번역한다. “\(x \in (A \cup B)^c\)”는 아직 집합 표기다. §1.5의 사전대로 여집합의 정의, 합집합의 정의를 차례로 쓴다.
확인 12. 둘째 문장을 완성해 보자:
“여집합의 정의에 의해 \(\underline{\quad}\)이고, 합집합의 정의에 의해
이는 \(\neg(\underline{\qquad})\)이다.”
답
“\(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\) 꼴이다.
확인 13. 셋째 문장을 완성해 보자:
“\(\underline{\qquad}\)에 의해 \(x \notin A \land x \notin B\)이다.”
답
“드모르간 2(\(\neg(P \lor Q) \equiv \neg P \land \neg Q\), 9주차)”에 의해.
근거 ④의 인용이다. 이 한 줄이 빠지면 남는 것은 표기 변환뿐이므로 증명이
아무것도 하지 않은 것이 된다.
4단계 — 역번역해 집합 표현으로 되돌린다. 논리식 상태로는 결론을 선언할 수 없다. 목표가 집합의 원소 소속이므로 정의를 거꾸로 써서 되돌린다.
확인 14. 넷째 문장을 완성해 보자:
“즉 \(x \in \underline{\quad}\)이고 \(x \in \underline{\quad}\)이므로
\(x \in \underline{\qquad}\)이다.”
답
“즉 \(x \in A^c\)이고 \(x \in B^c\)이므로 \(x \in A^c \cap B^c\)이다.”
여집합의 정의를 두 번, 교집합의 정의를 한 번 거꾸로 쓴 것이다. 이것으로
(\(\subseteq\)) 파트가 닫힌다.
5단계 — 반대 파트를 쓰고 종합을 선언한다. 둘째 의무가 남아 있다. 1~4단계의 근거가 전부 정의와 동치 법칙이므로 각 줄을 거꾸로 읽어도 그대로 성립한다.
확인 15. (\(\supseteq\)) 파트의 네 줄을 순서대로 적어 보자.
\(x \in A^c \cap B^c\)에서 출발해 \(x \in (A \cup B)^c\)로 도착한다.
답
“(\(\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\}\)이다.
확인 16. 위 대입에서 \(x = 5\)를 잡으면 완성본의 각 줄이 어떤 문장이 되는가.
첫 줄부터 넷째 줄까지 따라 읽어 보자.
답
“\(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의 자격 조건을 만족하므로 다음 한 줄로 압축해도 된다.
다만 압축 전에 각 단계가 진짜 \(\iff\)인지 확인한다. 한 단계라도 \(\Rightarrow\)뿐이면 (\(\supseteq\)) 방향의 근거가 사라지므로 두 파트로 분리해 써야 한다.
예제 2.2 — 분배법칙#
명제. \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\).
이번에는 설계만 함께 하고, 본문은 완성본으로 본다.
확인 17. 번역표를 채워 보자.
좌변: \(x \in A \cap (B \cup C)\) \(\to\) \(\underline{\qquad}\)
우변: \(x \in (A \cap B) \cup (A \cap C)\) \(\to\) \(\underline{\qquad}\)
둘을 잇는 9주차 법칙의 이름은 무엇인가.
답
좌변: \(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\)에 대해
첫째와 셋째 동치는 교집합\(\cdot\)합집합의 정의(근거 ①)이고 둘째 동치는 분배 1의 인용(근거 ④)이다. 모든 단계가 \(\iff\)이므로 두 집합은 같다. \(\blacksquare\)
사슬로 적을 수 있었던 것은 세 단계가 전부 왕복 가능했기 때문이다. 그 확인을 건너뛰면 압축이 성립하지 않는다.
예제 2.3 — 조건제시법 집합의 상등 (3주차 문제 9에서 미룬 증명)#
명제. \(\{3k + 1 : k \in \mathbb{Z}\} = \{3k - 2 : k \in \mathbb{Z}\}\).
이번에는 설계부터 스스로 해 보자. 앞의 두 예제와 달리 원소가 논리 연산이 아니라 생성식으로 주어져 있다.
확인 18. (\(\subseteq\)) 파트의 첫 문장은 “\(x \in \{3k+1 : k \in \mathbb{Z}\}\)라
하자”이다. 이 조건을 정의로 풀면 무엇을 손에 넣는가. 그리고 도착점
“\(x \in \{3k - 2 : k \in \mathbb{Z}\}\)”를 보이려면 무엇을 제시해야 하는가.
답
손에 넣는 것: “\(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\)가 존재한다. 그러면
이고 \(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\)가 존재한다. 그러면
이고 \(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}\}\)라 하자 … |
확인 19. 빈칸 (1)(2)(3)을 채워 보자. 예제 2.2는 이 표의 ①~⑤ 중
어디까지를 사슬 한 줄로 압축한 것인가.
답
(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\)분배 유형, 증인 제작이면 생성형 집합 유형이다.
방금 확인한 뼈대에 이름을 붙인다.
백지 암기 대상
집합 상등 증명의 틀
① 상등이면 파트 둘로 나눈다(모든 단계가 \(\iff\)임을 확인했으면 사슬 한 줄로 압축해도 된다) \(\to\) ② “\(x \in (\text{왼쪽 집합})\)라 하자” \(\to\) ③ 정의로 논리식(또는 생성식)으로 번역한다 \(\to\) ④ 논리 법칙을 인용하거나 증인을 제작한다 \(\to\) ⑤ 정의로 역번역해 도착점을 선언한다 \(\to\) ⑥ 반대 파트를 같은 방식으로 쓰고 종합을 선언한다
이 틀은 28주차의 순서쌍 추적, 37주차의 동치류, 44주차의 상과 원상에서 그대로 재사용된다 — 바뀌는 것은 ③의 번역표뿐이다.
빈칸 사다리 — 지지대를 하나씩 빼며#
필사에서 자립으로 넘어가는 다리다. 훈련이 진행될수록 빈칸이 커진다. 베끼지 말고 빈칸만 스스로 채운다. 답은 해설(§6)에 있다 — 다 채운 뒤에 대조한다.
훈련 1 ●○○ — 수식 빈칸#
명제. \(A - B = A \cap B^c\) (5주차 문제 12의 승격).
증명. 임의의 \(x\)에 대해
첫 동치는 차집합의 정의, 둘째는 \(\underline{\quad(4)\quad}\)의 정의, 셋째는 \(\underline{\quad(5)\quad}\)의 정의이다. 모든 단계가 동치이므로 두 집합은 같다. \(\blacksquare\)
훈련 2 ●●○ — 수식과 근거를 함께#
이번에는 근거의 이름도 빈칸이다.
명제. \((A^c)^c = A\) (5주차 문제 5의 승격).
증명. 임의의 \(x\)에 대해
첫 동치의 근거는 \(\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파트(또는 완전 동치 사슬)를 지킨다.
이번 주의 채점 기준
답이 아니라 근거가 점수다. “\((A \cup B)^c = A^c \cap B^c\)는 참(맞음)”은 0점이고,
각 줄에 정의 이름 또는 9주차 법칙 이름이 붙은 양방향 추적이 만점이다.
특히 상등 문제에서 한 파트만 쓰고 끝낸 답안은 절반이 아니라 미완성이다 —
§1.3의 삭제 실험이 그 이유다. 힌트 상자는 5분 이상 막힌 뒤에만 연다.
기본 ●○○#
1. [백지] 세 가지 목표(\(a \in A\) / \(A \subseteq B\) / \(A = B\))의 증명 서식을 쓰시오.
힌트
§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\))
힌트
(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\}\)를 원소 추적으로 증명하시오.
힌트
오프닝은 “\(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\))을 백지에서 완성하시오.
힌트
빈칸을 외워 채우는 것이 아니라 사슬 전체를 다시 만든다. 좌변을 차집합의
정의로 풀면 “그리고”가 나오고, 오른쪽 조각을 여집합의 정의로 되돌리면
우변이 된다.
5. 드모르간 제2법칙 \((A \cap B)^c = A^c \cup B^c\)를 예제 2.1의 방법(동치 사슬 가능)으로 증명하시오.
힌트
예제 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\)임을 증명하시오.
힌트
가정이 둘이다 — 명제의 가정 \(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주차 목록)
힌트
예제 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\)의 동치 확인이 핵심)
힌트
(\(\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\) (드모르간))
힌트
문제의 힌트대로 번역하면 \(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 — 또는 직접 양방향)
힌트
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 유형).
힌트
두 생성식의 차이는 상수항 \(3\)과 \(-2\)이고 그 차는 5다. 5를 하나 옮겨
\(5k + 3 = 5(k + 1) - 2\)를 만들면 증인이 나온다.
13. 증명 또는 반증: \((A - B) \cup (B - A) = (A \cup B) - (A \cap B)\). (실험 \(\to\) 판단 \(\to\) 실행. 참이라면 번역 후 논리 조작이 다소 길다 — 각 방향을 케이스로 처리해도 좋다)
힌트
먼저 §1.7의 1단계를 실행한다: \(A = \{1,2\}\), \(B = \{2,3\}\)으로 양변을 계산해
본다. 일치하면 증명으로 가고, 각 방향에서 “또는”이 나올 때마다 경우를 나눈다.
14. 증명 또는 반증: \(A - (B - C) = (A - B) \cup C\).
힌트
우변에서 \(C\)가 \(A\)와 아무 관계 없이 통째로 더해진다는 점이 수상하다.
\(C\)의 원소를 \(A\) 바깥에 두면 좌변에는 없고 우변에는 있는 원소가 생긴다.
도전 ●●●#
반례로 반증하기 — 이번 주의 꼴
“임의의 집합 \(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\) — 대칭으로 반대 방향도)
세 집합의 합집합\(\cdot\)교집합 — 표기 약속
정의 5.1의 \(\cup, \cap\)은 집합 두 개를 받는 연산이므로, \(A \cup B \cup 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\))
힌트
원소 추적으로 처음부터 다시 쓸 필요가 없다. 예제 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)\)의 쌍둥이)
힌트
번역하면 좌변이 \(P \land \neg(Q \land R)\)이다. 드모르간 1로 괄호를 풀고,
이어서 분배 1을 쓰면 우변의 꼴이 나온다. 인용할 법칙이 두 개다.
19. (진단) 다음 답안의 결함을 지적하시오. ‘지우기’는 정당한 연산인가. 이어서 반례를 제시해 이 명제 자체가 거짓임을 보이시오.
“명제: \(A \cap B = A \cap C\)이면 \(B = C\)이다. 증명: 양변에서 \(A \cap\)를 지우면 \(B = C\)이다. \(\blacksquare\)”
힌트
결론이 거짓인데 논증이 그럴듯하면 오류는 계산이 아니라 **허용되지 않은
연산**에 있다(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\)가 존재한다. 그러면
이고 \(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\)에 대해
첫 동치는 차집합의 정의(정의 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\)에 대해
첫째와 둘째 동치는 여집합\(\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\)에 대해
첫째와 셋째 동치는 합집합\(\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\)에 대해, 차집합의 정의를 두 번 적용하면
이고, 드모르간 1에 의해 오른쪽 조각은 \(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\)에 대해, 조건제시법의 정의에 의해
이고, 25주차 문제 12에 의해 \(6 \mid x \iff (2 \mid x) \land (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\)가 존재한다. 그러면
이고 \(k + 1\)은 정수이므로, \(x \in \{5k - 2 : k \in \mathbb{Z}\}\)이다. (\(\supseteq\)) \(x \in \{5k - 2 : k \in \mathbb{Z}\}\)라 하자. 정의에 의해 \(x = 5k - 2\)인 정수 \(k\)가 존재한다. 그러면
이고 \(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 = \{1\} - \{2\} = \{1\}\)이므로
이다. \(\{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\)에 적용하면
이고, 다시 예제 2.1을 두 집합 \(A\)와 \(B\)에 적용하면 \((A \cup B)^c = A^c \cap B^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\)교집합의 정의로 번역하면
이고, 드모르간 1에 의해
이며, 분배 1에 의해
이다. 마지막 식을 차집합과 합집합의 정의로 역번역하면 \(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\) 역번역)이 그대로 쓰이고, 바뀌는 것은 번역표 한 줄뿐이다.