집합의 표현과 연산

블로그에서 태그 A가 붙은 글과 태그 B가 붙은 글을 찾을 때, 둘 중 하나라도 붙은 글을 모두 보여 줄지, 둘 다 붙은 글만 보여 줄지에 따라 결과가 달라집니다. 이런 선택은 "어떤 대상이 모임에 들어 있는가"로 정확하게 나타낼 수 있고, 그 모임을 집합이라고 합니다. 이 글에서는 집합을 적는 방법과 집합끼리의 연산을 익힙니다. 집합의 연산은 논리 연산과 짝을 이루므로, 2장의 진리표를 떠올리며 읽으면 이해하기 쉽습니다.

집합을 적는 두 방법

집합(set)은 서로 구별되는 대상들의 모임이고, 집합에 들어 있는 대상을 원소(element)라고 합니다. 집합을 적는 방법은 두 가지입니다. $A=\{1,2,3\}$처럼 원소를 중괄호 안에 모두 늘어놓는 원소나열법과, $A=\{x\in\mathbb N\mid1\le x\le3\}$처럼 원소가 만족할 조건을 적는 조건제시법입니다. 뒤의 것은 "1 이상 3 이하인 자연수 x 전체의 집합"이라고 읽습니다. 원소가 많거나 끝없이 많을 때는 조건제시법이 편합니다.

집합은 원소가 들어 있는지만 따지므로, 원소를 적는 순서나 같은 원소를 여러 번 적는 것은 집합을 바꾸지 않습니다. $\{3,1,2,2\}$는 $\{1,2,3\}$과 같은 집합입니다. 원소가 몇 개인지를 집합의 크기라 하고 $|A|$로 씁니다.

x가 집합 A의 원소라는 것은 $x\in A$로 씁니다. A의 모든 원소가 B에도 들어 있으면 A를 B의 부분집합(subset)이라 하고 $A\subseteq B$로 씁니다. 두 기호를 헷갈리지 않아야 합니다. $1\in\{1,2,3\}$은 1이 원소라는 뜻이고, $\{1\}\subseteq\{1,2,3\}$은 1 하나만 든 집합이 부분집합이라는 뜻입니다. 그런데 $\{1\}$이라는 집합 자체가 $\{1,2,3\}$의 원소인 것은 아닙니다. Python의 set으로 확인해 보겠습니다.

A = {1, 2, 3}
print({3, 1, 2, 2} == A, len(A))
print(1 in A, {1} <= A, {1} in A)
print(len(set()), len({frozenset()}))

True 3
True True False
0 1

in이 원소인지를, <=가 부분집합인지를 묻습니다. 원소가 하나도 없는 집합을 공집합(empty set)이라 하고 $\varnothing$으로 씁니다. 공집합은 원소가 0개이지만, 공집합 하나를 원소로 가진 $\{\varnothing\}$은 원소가 1개입니다. Python에서 빈 집합은 set()으로 만들고, 집합을 다른 집합의 원소로 넣으려면 바꿀 수 없는 집합인 frozenset을 써야 합니다. 딕셔너리의 키에 리스트를 쓸 수 없었던 것과 같은 이유입니다.

멱집합: 모든 부분집합의 집합

집합 A의 부분집합을 모두 모은 집합을 A의 멱집합(power set)이라 하고 $\mathcal P(A)$로 씁니다. $A=\{a,b\}$이면 부분집합은 아무것도 고르지 않은 $\varnothing$, 하나씩 고른 $\{a\}$와 $\{b\}$, 둘 다 고른 $\{a,b\}$이므로 $\mathcal P(A)=\{\varnothing,\{a\},\{b\},\{a,b\}\}$입니다. 공집합과 A 자신도 A의 부분집합이라는 점에 주의해야 합니다.

원소가 n개인 집합의 멱집합에는 원소가 $2^n$개입니다. 부분집합을 하나 만들 때 원소마다 넣을지 뺄지 두 가지를 정하므로, 선택의 조합이 $2\cdot2\cdots2=2^n$가지이기 때문입니다.

from itertools import combinations


def power_set(s):
    items = sorted(s)
    return [set(c) for r in range(len(items) + 1) for c in combinations(items, r)]


print([sorted(subset) for subset in power_set({"a", "b"})])
print([len(power_set(set(range(n)))) for n in range(5)])

[[], ['a'], ['b'], ['a', 'b']]
[1, 2, 4, 8, 16]

combinations(items, r)는 items에서 r개를 고르는 모든 조합을 내놓으므로, r을 0부터 원소 수까지 바꾸면 모든 부분집합이 나옵니다. 문자열 원소의 집합은 출력할 때마다 순서가 달라질 수 있어서 sorted로 정렬해 출력했습니다. 원소가 0, 1, 2, 3, 4개일 때 멱집합의 크기가 1, 2, 4, 8, 16으로 두 배씩 늘어납니다.

더 깊이: 무한집합에서도 멱집합이 더 크다

유한집합에서는 $n<2^n$이므로 멱집합이 늘 원래 집합보다 큽니다. 칸토어(Cantor)는 이것이 무한집합에서도 성립함을 보였습니다. 두 집합의 크기가 같다는 것을 원소끼리 빠짐없이 하나씩 짝지을 수 있다는 뜻으로 정하면, 어떤 집합 A에 대해서도 A의 원소마다 부분집합을 하나씩 대응시켜 모든 부분집합을 빠짐없이 덮는 함수는 없다는 것이 칸토어의 정리(Cantor's theorem)입니다. 함수와 그 성질은 6장에서 자세히 다룹니다.

증명은 모순증명입니다. A의 원소 x마다 부분집합 $f(x)$를 대응시켜 모든 부분집합을 덮는 f가 있다고 가정하고, 자기에게 대응한 부분집합에 자기가 들어 있지 않은 원소만 모은 집합 $D=\{x\in A\mid x\notin f(x)\}$를 만듭니다. D도 A의 부분집합이므로 $f(d)=D$인 d가 있어야 합니다. 그런데 $d\in D$라면 D의 정의에 따라 $d\notin f(d)=D$이고, $d\notin D$라면 $d\notin f(d)$이므로 D의 정의에 따라 $d\in D$입니다. 어느 쪽이든 모순이므로 그런 f는 없습니다.

원소 x마다 각 원소가 $f(x)$에 들었는지를 표의 한 행으로 적으면, D는 그 표의 대각선 칸을 모두 뒤집어 만든 행과 같습니다. 그래서 이 논증을 대각선 논법(diagonal argument)이라고 부릅니다. 자연수의 집합 $\mathbb N$과 그 멱집합 사이에도 짝을 지을 수 없으므로, 무한집합 사이에도 크기의 차이가 있고, 멱집합을 거듭 취하면 더 큰 무한이 끝없이 이어집니다.

집합의 연산

두 집합 A와 B에서 새 집합을 만드는 연산은 원소가 어떤 조건을 만족하면 들어가는지로 정의합니다. 합집합 $A\cup B$에는 A나 B 가운데 적어도 하나에 속한 원소가, 교집합 $A\cap B$에는 둘 다에 속한 원소가 들어갑니다. 차집합 $A-B$에는 A에는 있지만 B에는 없는 원소가 들어가고, 대칭차 $A\triangle B$에는 둘 가운데 정확히 한쪽에만 속한 원소가 들어갑니다.

이 정의는 논리 연산과 그대로 짝을 이룹니다. $x\in A\cup B$는 "$x\in A$ 또는 $x\in B$"이고, $x\in A\cap B$는 "$x\in A$ 그리고 $x\in B$"이며, 대칭차는 배타적 논리합에 해당합니다. 그래서 논리 연산의 법칙들이 집합의 법칙으로 옮겨 오는데, 이것은 다음 글에서 다룹니다.

여집합 $A^c$는 A에 속하지 않는 원소들의 집합입니다. 그런데 "A에 속하지 않는 것"이라고만 하면 범위가 정해지지 않으므로, 여집합을 쓰기 전에 다루는 대상 전체인 전체집합(universal set) U를 먼저 정해야 합니다. 여집합은 $U-A$입니다. $U=\{1,2,3,4,5\}$, $A=\{1,2,3\}$, $B=\{3,4\}$로 계산해 보겠습니다.

U = {1, 2, 3, 4, 5}
A, B = {1, 2, 3}, {3, 4}
print(A | B, A & B, A - B, B - A)
print(U - A, A ^ B)

{1, 2, 3, 4} {3} {1, 2} {4}
{4, 5} {1, 2, 4}

Python의 |, &, -, ^가 각각 합집합, 교집합, 차집합, 대칭차입니다. 그림에서 왼쪽 타원만의 영역이 $A-B=\{1,2\}$, 겹치는 가운데가 $A\cap B=\{3\}$, 오른쪽만의 영역이 $B-A=\{4\}$입니다. 차집합은 순서를 바꾸면 결과가 달라진다는 것도 확인할 수 있습니다. 두 타원 바깥의 5는 A에도 B에도 속하지 않으므로 합집합에는 없지만 $A^c$에는 들어 있습니다.

곱집합

곱집합(Cartesian product) $A\times B$는 A의 원소 a와 B의 원소 b로 만든 순서쌍 $(a,b)$를 모두 모은 집합입니다. 순서쌍은 첫째 자리와 둘째 자리를 구분하므로 $(1,x)$와 $(x,1)$은 다릅니다. $A=\{1,2\}$, $B=\{x,y\}$이면 $A\times B$는 $(1,x)$, $(1,y)$, $(2,x)$, $(2,y)$의 네 원소입니다. A의 원소마다 B의 원소를 하나씩 짝지으므로 $|A\times B|=|A|\cdot|B|$입니다.

from itertools import product

print(sorted(product([1, 2], ["x", "y"])))
print(len(list(product([1, 2], ["x", "y", "z"]))))
print(set(product([1, 2], ["x"])) == set(product(["x"], [1, 2])))

[(1, 'x'), (1, 'y'), (2, 'x'), (2, 'y')]
6
False

마지막 줄처럼 $A\times B$와 $B\times A$는 일반적으로 같지 않습니다. 곱집합은 다음 장에서 관계를 정의하는 바탕이 됩니다. 두 집합 사이의 관계는 곱집합의 부분집합, 곧 어떤 순서쌍들을 골라 모은 것이기 때문입니다.

정리

• 집합은 원소의 모임이며 원소나열법이나 조건제시법으로 적고, 원소의 순서와 반복은 집합을 바꾸지 않습니다.
• $x\in A$는 원소인지를, $A\subseteq B$는 부분집합인지를 뜻하며, 1과 $\{1\}$, $\varnothing$과 $\{\varnothing\}$을 구분해야 합니다.
• 멱집합은 모든 부분집합의 집합이고, 원소가 n개이면 크기가 $2^n$입니다.
• 합집합, 교집합, 차집합, 대칭차는 원소의 포함 조건으로 정의되며 논리합, 논리곱, 배타적 논리합과 짝을 이룹니다. 여집합은 전체집합을 먼저 정해야 합니다.
• 곱집합은 순서쌍의 집합이고 $|A\times B|=|A|\cdot|B|$이며, $A\times B$와 $B\times A$는 일반적으로 다릅니다.

연습 문제

1. 연산 계산하기

$A=\{1,3,5\}$, $B=\{3,4,5\}$에서 $A\cap B$, $B-A$, $A\triangle B$를 구하세요.

2. 집합을 원소로 가진 집합

$C=\{\varnothing,\{a\}\}$의 원소는 몇 개이고, 멱집합 $\mathcal P(C)$의 원소는 몇 개인가요? 멱집합을 나열하세요.

3. 곱집합의 멱집합

$|A|=2$, $|B|=3$일 때 $A\times B$의 원소 수와 $\mathcal P(A\times B)$의 원소 수를 구하세요.

원소와 부분집합의 기호가 헷갈리면 1과 $\{1\}$을 각각 그림으로 그려 보세요. 집합의 연산 법칙과 집합을 겹치지 않게 나누는 방법은 다음 글 집합의 대수와 분할에서 이어집니다.