1강부터 집합을 써 왔습니다. N, Z, Q, R가 모두 집합이고, 22강에서 한정 기호를 쓸 때마다 "x∈A"라고 범위를 밝혔습니다. 그러나 집합이 무엇인지, 두 집합이 같다는 것이 무슨 뜻인지는 한 번도 정하지 않았습니다.
이 강의가 그 자리를 메웁니다. 그리고 여기서 얻는 것은 새로운 계산 규칙이 아니라 21강의 논리를 그대로 옮긴 것입니다. 집합의 교집합은 논리곱이고 합집합은 논리합이며, 집합의 드모르간 법칙은 명제의 드모르간 법칙과 같은 식입니다. 두 세계가 같은 구조라는 사실을 확인하는 것이 이 강의의 실제 내용입니다.
- 집합을 원소나열법과 조건제시법으로 적을 수 있습니다.
- 두 집합이 같음을 양쪽 포함을 보여 증명할 수 있습니다.
- 합집합, 교집합, 차집합, 여집합을 계산하고 벤 다이어그램으로 확인할 수 있습니다.
- 집합의 드모르간 법칙과 분배법칙을 논리 법칙에서 유도할 수 있습니다.
- 멱집합과 곱집합의 원소 개수를 셀 수 있습니다.
문제. 다음 세 집합을 각각 원소를 모두 나열하는 방식과 조건을 적는 방식으로 쓰세요.
(가) 10보다 작은 짝수인 자연수
(나) x2−5x+6=0의 실근
(다) x2+1=0의 실근
생각의 실마리. 나열하는 방식은 원소가 적을 때 편하고, 조건을 적는 방식은 원소가 많거나 무한할 때 필요합니다. (다)에서는 조건을 만족하는 것이 하나도 없을 수 있다는 점에 주의합니다.
풀이. (가)를 나열하면 {2,4,6,8}입니다. 조건으로 적으면 {n∈N∣n<10,n은 짝수}입니다.
(나)는 5강에서 배운 대로 x2−5x+6=(x−2)(x−3)이므로 근이 2와 3입니다. 나열하면 {2,3}이고, 조건으로 적으면 {x∈R∣x2−5x+6=0}입니다.
(다)는 모든 실수에서 x2+1≥1>0이므로 조건을 만족하는 실수가 하나도 없습니다. 나열하면 {}이고 이것을 ∅으로 씁니다. 조건으로 적으면 {x∈R∣x2+1=0}이며, 이 집합이 공집합입니다.
이 문제에서 배우는 것: 집합과 두 가지 표기법.
집합은 어떤 대상들의 모임이고, 그 대상 하나하나를 원소라고 합니다. a가 집합 A의 원소임을 a∈A로 쓰고, 원소가 아님을 a∈/A로 씁니다.
집합을 적는 방법은 두 가지입니다.
| 방법 |
모양 |
쓸 때 |
| 원소나열법 |
\ |
원소가 적고 전부 적을 수 있을 때 |
| 조건제시법 |
\ |
원소가 많거나 무한할 때 |
조건제시법의 세로줄 ∣은 "그런 것들"이라고 읽습니다. {x∈R∣x>0}은 "실수 x 중에서 x>0인 것들의 집합"입니다.
집합에서 지켜야 할 두 가지 약속이 있습니다.
첫째, 원소의 순서는 의미가 없습니다. {1,2}와 {2,1}은 같은 집합입니다.
둘째, 같은 원소를 여러 번 적어도 한 번 적은 것과 같습니다. {1,1,2}는 {1,2}입니다.
원소가 하나도 없는 집합을 공집합이라 하고 ∅으로 씁니다. 공집합은 하나뿐입니다. 원소가 없다는 조건이 집합을 완전히 결정하기 때문입니다.
바로 확인.
확인 1-1. {x∈Z∣x2<10}을 원소나열법으로 쓰세요.
답. {−3,−2,−1,0,1,2,3}입니다. (±3)2=9<10이고 (±4)2=16>10입니다.
확인 1-2. {1,3,5,7,…}을 조건제시법으로 쓰세요.
답. {n∈N∣n은 홀수} 또는 {2k−1∣k∈N}입니다.
확인 1-3. ∅과 {∅}은 같은 집합입니까?
답. 다릅니다. ∅은 원소가 하나도 없고, {∅}은 공집합을 원소로 하나 가지는 집합입니다. 원소 개수가 각각 0개와 1개입니다.
문제. A={x∈R∣x2−3x+2=0}이고 B={1,2}일 때 A=B임을 증명하세요. 증명은 무엇을 보이는 것으로 이루어져야 합니까?
생각의 실마리. 두 집합이 같다는 것을 눈으로 확인하는 것이 아니라 증명해야 합니다. 그러려면 "같다"의 정의가 필요합니다. 집합은 원소로만 결정되므로, 두 집합이 같다는 것은 원소가 정확히 일치한다는 뜻입니다. 그것을 22강의 한정 기호로 어떻게 적을지 생각합니다.
풀이. 두 집합이 같다는 것은 ∀x,(x∈A↔x∈B)입니다. 21강에서 p↔q가 (p→q)∧(q→p)였으므로 이 증명은 두 방향으로 나뉩니다.
A⊆B 방향. x∈A라고 하면 x2−3x+2=0입니다. 인수분해하면 (x−1)(x−2)=0이고, 실수에서 곱이 0이면 두 인수 중 하나가 0이므로 x=1 또는 x=2입니다. 어느 쪽이든 x∈B입니다.
B⊆A 방향. x∈B라고 하면 x=1 또는 x=2입니다. x=1이면 1−3+2=0이고, x=2이면 4−6+2=0입니다. 두 경우 모두 x2−3x+2=0이므로 x∈A입니다.
양쪽이 모두 성립하므로 A=B입니다.
이 문제에서 배우는 것: 부분집합과 집합의 상등.
A의 모든 원소가 B의 원소일 때 A를 B의 부분집합이라 하고 A⊆B로 씁니다. 기호로 적으면
A⊆B는∀x,(x∈A→x∈B)
입니다. 정의가 조건문이므로 부분집합임을 증명하는 방법이 정해집니다. 임의의 x∈A를 잡고 x∈B를 보입니다. 23강 문제 2에서 배운 임의의 원소 잡기가 그대로 쓰입니다.
두 집합이 같다는 것은 원소가 정확히 일치한다는 뜻이며
A=B⟺A⊆B 그리고 B⊆A
입니다. 그래서 집합의 상등을 증명할 때는 언제나 두 방향을 각각 증명합니다. 이것을 양쪽 포함 증명이라고 하며, 이 단원에서 계속 쓰는 표준 절차입니다.
부분집합에 대해 기억할 사실이 세 가지 있습니다.
- 모든 집합 A에 대하여 ∅⊆A입니다. 정의가 조건문이고 x∈∅이 항상 거짓이므로 21강의 공허하게 참에 해당합니다.
- 모든 집합 A에 대하여 A⊆A입니다.
- A⊆B이고 B⊆C이면 A⊆C입니다.
A⊆B이면서 A=B일 때 A를 B의 진부분집합이라 하고 A⊊B로 씁니다. 1강에서 N⊂Z⊂Q⊂R라고 쓴 것이 모두 진부분집합입니다.
바로 확인.
확인 2-1. {1,2}⊆{1,2,3}입니까? {1,2}∈{1,2,3}입니까?
답. 앞은 참이고 뒤는 거짓입니다. {1,2,3}의 원소는 1,2,3이지 {1,2}가 아닙니다. ∈과 ⊆를 혼동하지 않아야 합니다.
확인 2-2. A={x∈Z∣x는 4의 배수}이고 B={x∈Z∣x는 짝수}일 때 A⊆B임을 증명하고, B⊆A가 거짓임을 보이세요.
답. x∈A이면 x=4k=2(2k)이므로 짝수이고 x∈B입니다. 반대로 2∈B이지만 2∈/A이므로 B⊆A는 거짓입니다.
확인 2-3. ∅⊆∅입니까?
답. 참입니다. 정의가 공허하게 참이므로 성립하며, 따라서 ∅=∅입니다.
문제. 전체집합을 U={1,2,3,4,5,6}, A={1,2,3}, B={3,4,5}라고 합니다.
(1) A∪B, A∩B, A∖B, Ac를 각각 구하세요.
(2) (A∪B)c와 Ac∩Bc를 각각 계산해 비교하세요.
생각의 실마리. (2)의 결과가 21강 문제 3의 드모르간 법칙과 같은 모양임을 확인하고, 왜 같아지는지 그 이유까지 봅니다. 집합 연산의 정의를 논리 연결사로 적어 보면 답이 보입니다.
풀이. (1) 합집합은 둘 중 하나에라도 속하는 원소를 모읍니다.
A∪B={1,2,3,4,5}
교집합은 둘 다에 속하는 원소를 모읍니다.
A∩B={3}
차집합 A∖B는 A에는 속하지만 B에는 속하지 않는 원소입니다.
A∖B={1,2}
여집합 Ac는 전체집합에서 A를 뺀 것입니다.
Ac=U∖A={4,5,6}
(2) A∪B={1,2,3,4,5}이므로
(A∪B)c={6}
한편 Ac={4,5,6}이고 Bc={1,2,6}이므로
Ac∩Bc={6}
두 결과가 같습니다.
이 문제에서 배우는 것: 집합 연산과 논리 연결사의 대응.
집합 연산의 정의를 조건제시법으로 적으면 논리 연결사가 그대로 나타납니다.
| 집합 연산 |
정의 |
대응하는 논리 |
| A∪B |
\ |
논리합 ∨ |
| A∩B |
\ |
논리곱 ∧ |
| A^ |
\ |
부정 ¬ |
| A∖B |
\ |
p∧¬q |
| A⊆B |
∀x,(x∈A→x∈B) |
조건문 → |
이 대응 덕분에 21강에서 증명한 논리 법칙이 집합 법칙으로 그대로 번역됩니다. 드모르간 법칙이 그 예입니다.
(A∪B)c=Ac∩Bc,(A∩B)c=Ac∪Bc
첫 식을 증명해 봅니다. x∈(A∪B)c는 ¬(x∈A∨x∈B)이고, 21강의 드모르간 법칙으로 이는 x∈/A∧x∈/B이며, 이것이 곧 x∈Ac∩Bc입니다. 모든 단계가 동치이므로 양쪽 포함이 한꺼번에 증명됩니다.
같은 방식으로 분배법칙도 얻습니다.
A∩(B∪C)=(A∩B)∪(A∩C)
A∪(B∩C)=(A∪B)∩(A∪C)
21강 문제 11에서 명제로 확인한 것과 같은 식입니다. 여기서 주의할 점이 있습니다. 수의 연산에서는 곱셈만 덧셈에 분배되지만, 집합에서는 양방향 모두 분배됩니다. ∩이 ∪에 분배되고 ∪도 ∩에 분배됩니다.
바로 확인.
확인 3-1. U={1,…,10}, A={2,4,6,8}, B={1,2,3,4}일 때 A∖B와 B∖A를 구하세요.
답. A∖B={6,8}이고 B∖A={1,3}입니다. 차집합은 순서를 바꾸면 달라집니다.
확인 3-2. (A∩B)c=Ac∪Bc를 논리의 드모르간 법칙으로 증명하세요.
답. x∈(A∩B)c는 ¬(x∈A∧x∈B)이고, 드모르간 법칙으로 x∈/A∨x∈/B이며 이는 x∈Ac∪Bc입니다.
확인 3-3. A∖B=A∩Bc임을 정의로 확인하세요.
답. A∖B의 정의가 x∈A∧x∈/B이고, x∈/B는 x∈Bc이므로 A∩Bc와 같습니다.
문제. 임의의 집합 A, B, C에 대하여 A∩(B∪C)=(A∩B)∪(A∩C)임을 양쪽 포함으로 증명하세요.
생각의 실마리. 문제 3에서는 논리 법칙을 인용해 한 줄로 끝냈지만, 여기서는 정의만 써서 양쪽 포함을 각각 증명합니다. 각 방향에서 임의의 원소를 잡고 정의를 풀어 쓰는 것부터 시작합니다. 21강의 논리곱과 논리합의 정의가 계산 규칙이 됩니다.
풀이. ⊆ 방향. 임의의 x∈A∩(B∪C)를 잡습니다.
교집합의 정의에 따라 x∈A이고 x∈B∪C입니다. 합집합의 정의에 따라 x∈B이거나 x∈C입니다. 경우를 나눕니다.
x∈B인 경우, x∈A이므로 x∈A∩B입니다. 따라서 x∈(A∩B)∪(A∩C)입니다.
x∈C인 경우, x∈A이므로 x∈A∩C입니다. 따라서 역시 x∈(A∩B)∪(A∩C)입니다.
두 경우가 전부이고 각각에서 결론이 나왔으므로 이 방향이 증명되었습니다.
⊇ 방향. 임의의 x∈(A∩B)∪(A∩C)를 잡습니다. 합집합의 정의에 따라 x∈A∩B이거나 x∈A∩C입니다.
x∈A∩B인 경우, x∈A이고 x∈B입니다. x∈B이므로 x∈B∪C이고, 따라서 x∈A∩(B∪C)입니다.
x∈A∩C인 경우도 같은 방식으로 x∈A이고 x∈C⊆B∪C이므로 x∈A∩(B∪C)입니다.
양쪽 포함이 모두 성립하므로 두 집합은 같습니다.
이 문제에서 배우는 것: 집합 등식 증명의 표준 절차.
집합의 등식 X=Y를 증명하는 절차는 언제나 같습니다.
- X⊆Y를 증명합니다. 임의의 x∈X를 잡고, 정의를 풀어 논리식으로 바꾼 뒤, x∈Y를 유도합니다.
- Y⊆X를 증명합니다. 방향만 바꿔 같은 일을 합니다.
각 방향에서 하는 일은 결국 21강의 논리 계산입니다. 집합 기호를 논리식으로 바꾸고, 논리 법칙으로 변형하고, 다시 집합 기호로 돌아옵니다.
모든 단계가 동치라면 두 방향을 따로 쓰지 않고 한 줄로 이을 수 있습니다. 문제 3에서 드모르간 법칙을 증명할 때 그렇게 했습니다. 그러나 한쪽 방향만 성립하는 단계가 섞이면 반드시 나눠 써야 하므로, 처음에는 두 방향을 항상 따로 쓰는 습관을 들이는 편이 안전합니다.
증명 안에서 경우 나누기를 쓴 자리에 주목합니다. 합집합이 가정 쪽에 있으면 경우를 나눕니다. x∈B∪C라는 가정은 "x∈B 또는 x∈C"이므로 23강 문제 4의 경우 나누기가 그대로 필요합니다. 반대로 합집합이 결론 쪽에 있으면 둘 중 하나만 보이면 됩니다.
바로 확인.
확인 4-1. A∪(B∩C)=(A∪B)∩(A∪C)의 ⊆ 방향을 증명하세요.
답. x∈A∪(B∩C)를 잡습니다. x∈A이면 x∈A∪B이고 x∈A∪C이므로 교집합에 속합니다. x∈B∩C이면 x∈B에서 x∈A∪B이고 x∈C에서 x∈A∪C이므로 역시 교집합에 속합니다.
확인 4-2. A⊆B이면 A∩B=A임을 증명하세요.
답. A∩B⊆A는 교집합의 정의로 자명합니다. 반대로 x∈A이면 A⊆B에 의해 x∈B이므로 x∈A∩B입니다.
확인 4-3. 증명에서 합집합이 가정 쪽에 나오면 무엇을 합니까?
답. 경우를 나눕니다. 결론 쪽에 나오면 둘 중 하나만 보이면 됩니다.
문제. A={1,2,3}일 때
(1) A의 부분집합을 모두 적고 개수를 세세요.
(2) B={a,b}일 때 A×B의 원소를 모두 적고 개수를 세세요.
(3) 원소가 n개인 집합의 부분집합 개수와, 원소가 m개와 n개인 두 집합의 곱집합 원소 개수를 각각 구하세요.
생각의 실마리. (1)에서 부분집합을 만드는 과정을 선택의 연속으로 보면 19강의 곱의 법칙이 그대로 적용됩니다. 원소 하나하나에 대해 무엇을 결정해야 합니까? (2)에서는 순서쌍을 만드는 것이므로 앞자리와 뒷자리를 각각 정합니다.
풀이. (1) 부분집합을 원소 개수별로 적습니다.
- 원소 0개: ∅
- 원소 1개: \{1\},\{2\},\
- 원소 2개: \{1,2\},\{1,3\},\
- 원소 3개: \
모두 1+3+3+1=8개입니다. 각 줄의 개수가 (03),(13),(23),(33)으로 19강의 조합과 일치합니다.
(2) 순서쌍을 앞자리 기준으로 적습니다.
A×B={(1,a),(1,b),(2,a),(2,b),(3,a),(3,b)}
6개입니다.
(3) 부분집합을 만드는 일은 각 원소마다 "넣는다"와 "넣지 않는다" 중 하나를 고르는 것입니다. 원소가 n개이고 각각 2가지이므로 19강의 곱의 법칙에 따라 2n개입니다. 25강 문제 16에서 귀납법으로도 증명했습니다.
곱집합의 원소는 앞자리를 m가지, 뒷자리를 n가지로 고르므로 mn개입니다.
이 문제에서 배우는 것: 멱집합과 곱집합.
A의 모든 부분집합을 원소로 하는 집합을 A의 멱집합이라 하고 P(A)로 씁니다.
P(A)={X∣X⊆A},∣P(A)∣=2∣A∣
여기서 ∣A∣는 A의 원소 개수입니다. 멱집합의 원소는 집합이라는 점에 주의합니다. 1∈A이지만 1∈/P(A)이고 {1}∈P(A)입니다.
A와 B의 곱집합은 앞자리를 A에서, 뒷자리를 B에서 고른 순서쌍의 집합입니다.
A×B={(a,b)∣a∈A,b∈B},∣A×B∣=∣A∣⋅∣B∣
순서쌍에서는 순서가 의미를 가집니다. (1,a)와 (a,1)은 다르고, A×B와 B×A도 일반적으로 다릅니다. 집합 {1,2}={2,1}과 대비되는 점입니다.
곱집합이 중요한 이유는 27강에서 함수를 정의할 때 쓰이기 때문입니다. 함수는 A×B의 특별한 부분집합으로 정의됩니다. 9강에서 그래프로 그렸던 것이 실제로는 곱집합의 부분집합이었습니다.
유한집합의 크기를 셀 때 자주 쓰는 식도 정리해 둡니다. 19강의 포함배제와 같은 원리입니다.
∣A∪B∣=∣A∣+∣B∣−∣A∩B∣
바로 확인.
확인 5-1. P(∅)을 구하고 원소 개수를 세세요.
답. P(∅)={∅}이고 원소가 1개입니다. 20=1과 일치합니다.
확인 5-2. ∣A∣=4, ∣B∣=3, ∣A∩B∣=2일 때 ∣A∪B∣를 구하세요.
답. 4+3−2=5입니다.
확인 5-3. P({1,2})의 원소를 모두 적으세요.
답. ∅,{1},{2},{1,2} 네 개입니다.
| 기호 |
읽는 법 |
정의 |
| a∈A |
원소입니다 |
a가 A에 속합니다 |
| A⊆B |
부분집합입니다 |
∀x,(x∈A→x∈B) |
| A=B |
같습니다 |
A⊆B이고 B⊆A |
| A∪B |
합집합 |
x∈A 또는 x∈B |
| A∩B |
교집합 |
x∈A 그리고 x∈B |
| A∖B |
차집합 |
x∈A 그리고 x∈/B |
| A^ |
여집합 |
U에서 A를 뺀 것 |
| P(A) |
멱집합 |
A의 모든 부분집합의 집합 |
| A×B |
곱집합 |
순서쌍 (a,b)의 집합 |
| 법칙 |
식 |
| 드모르간 |
(A∪B)c=Ac∩Bc, (A\cap B)^{c}=A^{c}\cup B^ |
| 분배 |
A∩(B∪C)=(A∩B)∪(A∩C) |
| 분배 |
A∪(B∩C)=(A∪B)∩(A∪C) |
| 차집합 |
A\setminus B=A\cap B^ |
| 크기 |
∣A∪B∣=∣A∣+∣B∣−∣A∩B∣ |
| 크기 |
∣P(A)∣=2∣A∣, ∣A×B∣=∣A∣∣B∣ |
| 상황 |
쓸 도구 |
| 집합 등식을 증명합니다 |
양쪽 포함을 각각 증명합니다 |
| 가정에 합집합이 있습니다 |
경우를 나눕니다 |
| 결론에 합집합이 있습니다 |
둘 중 하나를 보입니다 |
| 여집합이 섞여 있습니다 |
드모르간 법칙으로 안으로 밀어 넣습니다 |
| 두 집합이 다름을 보입니다 |
한쪽에만 있는 원소를 하나 제시합니다 |
문제 6. A={1,2,3,4}, B={3,4,5}일 때 A∪B, A∩B, A∖B를 구하세요.
답. A∪B={1,2,3,4,5}, A∩B={3,4}, A∖B={1,2}입니다.
문제 7. A∩∅과 A∪∅을 구하세요.
답. A∩∅=∅이고 A∪∅=A입니다.
문제 8. A⊆B와 A∪B=B가 동치임을 증명하세요.
답. A⊆B라면 x∈A∪B일 때 x∈A면 x∈B이고 x∈B면 그대로이므로 A∪B⊆B이고, 반대 포함은 자명하므로 A∪B=B입니다. 역으로 A∪B=B라면 x∈A일 때 x∈A∪B=B이므로 A⊆B입니다.
문제 9. (A∖B)∩B=∅임을 증명하세요.
답. x가 양쪽에 속한다면 x∈/B이면서 x∈B가 되어 모순입니다. 그런 x가 없으므로 교집합이 공집합입니다.
문제 10. ∣A∣=6, ∣B∣=8, ∣A∪B∣=11일 때 ∣A∩B∣를 구하세요.
답. 6+8−∣A∩B∣=11이므로 ∣A∩B∣=3입니다.
문제 11. P({1,2,3,4})의 원소 개수를 구하세요.
답. 24=16개입니다.
문제 12. A×B=B×A가 항상 성립합니까? 반례를 드세요.
답. 성립하지 않습니다. A={1}, B={2}이면 A×B={(1,2)}이고 B×A={(2,1)}이며 순서쌍이 다릅니다. 다만 A=B이거나 한쪽이 공집합이면 같습니다.
문제 13. A∖(B∪C)=(A∖B)∩(A∖C)임을 드모르간 법칙으로 증명하세요.
답. A∖(B∪C)=A∩(B∪C)c=A∩Bc∩Cc입니다. 오른쪽은 (A∩Bc)∩(A∩Cc)=A∩Bc∩Cc이므로 같습니다.
문제 14. A∩B=A∪B이면 A=B임을 증명하세요.
답. x∈A이면 x∈A∪B=A∩B이므로 x∈B입니다. 대칭적으로 x∈B이면 x∈A입니다. 따라서 A=B입니다.
문제 15. {x∈R∣x2<4}를 구간으로 쓰세요.
답. x2<4는 ∣x∣<2이므로 (−2,2)입니다. 8강의 절댓값 부등식과 같습니다.
문제 16. A⊆B이고 B⊆A이면 A=B인 이유를 설명하세요.
답. 집합의 상등이 그렇게 정의되어 있기 때문입니다. 원소가 서로 완전히 포함되면 원소 전체가 일치합니다.
문제 17. ∣A∣=3일 때 A의 부분집합 중 원소가 정확히 2개인 것은 몇 개입니까?
답. (23)=3개입니다.
문제 18. ∅∈P(A)입니까? A∈P(A)입니까?
답. 둘 다 참입니다. 공집합과 자기 자신은 언제나 부분집합이므로 멱집합의 원소입니다.
심화 1. 집합의 드모르간 법칙이 왜 논리의 드모르간 법칙과 같은 식인지 설명하세요.
답. 집합 연산이 논리 연결사의 번역이기 때문입니다.
풀이. x∈A∪B는 정의상 x∈A∨x∈B이고, x∈Ac는 ¬(x∈A)입니다. 그러므로 x∈(A∪B)c를 논리식으로 옮기면 정확히 ¬(p∨q)이고, 여기에 논리의 드모르간 법칙을 적용해 ¬p∧¬q를 얻으면 다시 집합 기호로 x∈Ac∩Bc가 됩니다.
남는 것. 집합론의 법칙을 따로 외울 필요가 없습니다. 21강의 논리 법칙을 알고 있으면 ∪↔∨, ∩↔∧, c↔¬로 바꾸기만 하면 됩니다. 두 이론이 같은 구조를 가진다는 사실은 뒤에서 다시 나타납니다. 확률에서 사건의 연산도 정확히 같은 규칙을 따르므로 121강 이후의 계산이 여기서 이미 준비됩니다.
심화 2. P(A∩B)=P(A)∩P(B)임을 증명하고, P(A∪B)=P(A)∪P(B)가 거짓임을 반례로 보이세요.
답. 앞은 참이고 뒤는 거짓입니다.
풀이. 앞을 증명합니다. X∈P(A∩B)는 X⊆A∩B이고, 이는 X⊆A이면서 X⊆B와 같습니다. 따라서 X∈P(A)∩P(B)이며 모든 단계가 동치이므로 양쪽 포함이 동시에 성립합니다.
뒤에 대해서는 A={1}, B={2}를 봅니다. A∪B={1,2}이므로 {1,2}∈P(A∪B)입니다. 그러나 {1,2}는 A의 부분집합도 아니고 B의 부분집합도 아니므로 오른쪽에 속하지 않습니다. 반례입니다.
남는 것. 두 결과의 차이는 ⊆가 ∩과는 잘 맞지만 ∪과는 맞지 않는다는 데서 옵니다. "X가 둘 다의 부분집합"과 "X가 교집합의 부분집합"은 같지만, "X가 둘 중 하나의 부분집합"은 "X가 합집합의 부분집합"보다 강합니다. 한 방향만 성립하는 관계를 등식으로 잘못 적는 것이 집합론에서 가장 흔한 실수입니다.
심화 3. 세 집합에 대한 포함배제 공식 ∣A∪B∪C∣를 유도하세요.
답. ∣A∣+∣B∣+∣C∣−∣A∩B∣−∣B∩C∣−∣C∩A∣+∣A∩B∩C∣입니다.
풀이. 두 집합의 공식을 두 번 씁니다. A∪B를 하나의 집합으로 보면
∣A∪B∪C∣=∣A∪B∣+∣C∣−∣(A∪B)∩C∣
입니다. 첫 항에 두 집합 공식을 적용하고, 마지막 항에 분배법칙을 써서 (A∪B)∩C=(A∩C)∪(B∩C)로 바꾼 뒤 다시 두 집합 공식을 적용합니다.
∣(A∩C)∪(B∩C)∣=∣A∩C∣+∣B∩C∣−∣A∩B∩C∣
세 식을 합치면 결과가 나옵니다.
남는 것. 19강에서 여사건과 포함배제를 셈으로 다뤘는데, 여기서는 집합 연산으로 유도했습니다. 같은 결과에 이르는 두 길이며, 집합 쪽 유도가 원소 개수가 늘어나도 그대로 확장된다는 장점이 있습니다.
심화 4. A△B=(A∖B)∪(B∖A)를 대칭차라고 합니다. A△B=(A∪B)∖(A∩B)임을 증명하세요.
답. 두 표현이 같습니다.
풀이. x∈A△B는 "x∈A이고 x∈/B" 또는 "x∈B이고 x∈/A"입니다. 두 경우 모두에서 x는 A와 B 중 적어도 하나에 속하므로 x∈A∪B이고, 동시에 둘 다에 속하지는 않으므로 x∈/A∩B입니다. 따라서 왼쪽이 오른쪽에 포함됩니다.
반대로 x∈(A∪B)∖(A∩B)이면 적어도 하나에 속하고 둘 다에는 속하지 않으므로 정확히 하나에 속합니다. A에만 속하면 x∈A∖B이고 B에만 속하면 x∈B∖A이므로 왼쪽에 속합니다.
남는 것. 대칭차는 21강의 배타적 논리합에 대응합니다. "둘 중 정확히 하나"라는 일상어의 "또는"이 여기 있습니다. 논리 연결사와 집합 연산의 대응이 ∨와 ∪을 넘어 계속 이어진다는 것을 보여 주는 예입니다.
심화 5. A⊆B일 때 P(A)⊆P(B)임을 증명하고, 역이 성립하는지 판정하세요.
답. 참이고 역도 참입니다.
풀이. X∈P(A)이면 X⊆A이고 A⊆B이므로 포함의 추이성에 의해 X⊆B이며 X∈P(B)입니다.
역을 봅니다. P(A)⊆P(B)라고 하면 A⊆A이므로 A∈P(A)⊆P(B)이고, 따라서 A⊆B입니다.
남는 것. 역의 증명에서 A 자신을 멱집합의 원소로 쓰는 것이 요령입니다. 멱집합에 대한 명제를 원래 집합에 대한 명제로 되돌릴 때 가장 큰 원소인 A를 대입하는 이 수법은 자주 쓰입니다.
심화 6. "모든 집합의 집합"을 만들 수 있습니까?
답. 만들 수 없습니다.
풀이. 모든 집합의 집합 V가 있다고 가정합니다. 그러면 P(V)의 모든 원소도 집합이므로 P(V)⊆V입니다. 그런데 29강에서 증명할 정리에 따르면 어떤 집합도 자기 멱집합과 크기가 같을 수 없고 멱집합이 항상 더 큽니다. P(V)가 V의 부분집합이면서 V보다 크다는 것은 모순입니다.
더 직접적인 모순도 있습니다. R={X∣X∈/X}를 생각합니다. R∈R이라면 정의에 따라 R∈/R이고, R∈/R이라면 정의에 따라 R∈R입니다. 어느 쪽도 불가능합니다.
남는 것. 21강 심화 6의 "이 문장은 거짓입니다"와 같은 구조입니다. 자기 자신을 가리키는 대상은 다루는 범위를 제한하지 않으면 모순을 낳습니다. 그래서 현대의 집합론은 아무 모임이나 집합으로 인정하지 않고, 이미 있는 집합에서 만들어지는 것만 집합으로 받아들입니다. 22강에서 한정 기호의 범위를 반드시 밝히라고 한 이유가 여기까지 이어집니다.
집합 연산은 파이썬의 집합 자료형으로 그대로 확인할 수 있습니다. 표준 자료형이므로 외부 라이브러리가 아니며, 원소 개수 계산에는 numpy를 씁니다.
import numpy as np
U = set(range(1, 7))
A = {1, 2, 3}
B = {3, 4, 5}
# 문제 3: 기본 연산
print(sorted(A | B), sorted(A & B), sorted(A - B), sorted(U - A))
# [1, 2, 3, 4, 5] [3] [1, 2] [4, 5, 6]
# 문제 3: 드모르간 법칙
print((U - (A | B)) == ((U - A) & (U - B))) # True
print((U - (A & B)) == ((U - A) | (U - B))) # True
# 문제 4: 분배법칙
C = {2, 5, 6}
print((A & (B | C)) == ((A & B) | (A & C))) # True
print((A | (B & C)) == ((A | B) & (A | C))) # True
# 문제 5: 멱집합의 크기와 포함배제
n = np.arange(0, 11)
print(2**n) # [ 1 2 4 8 16 32 64 128 256 512 1024]
print(len(A | B) == len(A) + len(B) - len(A & B)) # True
# 심화 2: 멱집합은 교집합과는 맞고 합집합과는 어긋납니다.
def powerset(s):
s = sorted(s)
out = []
for mask in range(2 ** len(s)):
out.append(frozenset(x for i, x in enumerate(s) if mask >> i & 1))
return set(out)
P, Q = {1}, {2}
print(powerset(P & Q) == (powerset(P) & powerset(Q))) # True
print(powerset(P | Q) == (powerset(P) | powerset(Q))) # False
print(sorted(powerset(P | Q) - (powerset(P) | powerset(Q)), key=sorted))
# [frozenset({1, 2})]
# 심화 4: 대칭차의 두 표현
print((A ^ B) == ((A | B) - (A & B))) # True
출력이 주석과 모두 일치합니다. 마지막에서 두 번째 줄이 심화 2의 반례를 그대로 찍어 줍니다. P(A∪B)에는 있는데 P(A)∪P(B)에는 없는 원소가 정확히 {1,2} 하나이며, 손으로 든 반례와 일치합니다.
- A⊆B의 정의를 논리식으로 쓰세요.
- A=B를 증명하려면 무엇을 보입니까?
- ∅⊆A가 참인 이유는 무엇입니까?
- (A∩B)c를 드모르간 법칙으로 바꾸세요.
- A∖B를 ∩과 여집합으로 쓰세요.
- ∣A∣=5일 때 ∣P(A)∣를 구하세요.
- A×B와 B×A는 항상 같습니까?
- 증명에서 가정에 합집합이 나오면 무엇을 합니까?
정답.
- ∀x,(x∈A→x∈B)입니다.
- A⊆B와 B⊆A를 각각 보입니다.
- x∈∅이 항상 거짓이라 조건문이 공허하게 참이기 때문입니다.
- Ac∪Bc입니다.
- A∩Bc입니다.
- 25=32입니다.
- 같지 않습니다. A=B이고 둘 다 공집합이 아니면 다릅니다.
- 경우를 나눕니다.
| 기호 |
읽는 법 |
뜻 |
| ∈, ∈/ |
원소입니다, 원소가 아닙니다 |
소속 관계입니다 |
| ⊆, ⊊ |
부분집합, 진부분집합 |
포함 관계입니다 |
| ∪, ∩ |
합집합, 교집합 |
논리합과 논리곱에 대응합니다 |
| ∖ |
차집합 |
A에서 B를 뺍니다 |
| A^ |
여집합 |
전체집합에서 A를 뺍니다 |
| △ |
대칭차 |
정확히 하나에만 속하는 원소입니다 |
| P(A) |
멱집합 |
부분집합 전체의 집합입니다 |
| A×B |
곱집합 |
순서쌍의 집합입니다 |
| ∣A∣ |
크기 |
원소의 개수입니다 |
| \ |
조건제시법 |
조건을 만족하는 원소들입니다 |
다음 27강에서는 곱집합의 부분집합으로 함수를 정확히 정의하고, 9강에서 그림으로만 이해한 함수의 성질을 단사와 전사로 나눕니다.