집합의 대수와 분할

검색 조건을 다른 모양으로 바꾸어 쓴 뒤 결과가 같은지 확인하고 싶다고 해 봅시다. 데이터 몇 개로 실행해 결과를 비교할 수도 있지만, 그 데이터에서 같았다고 모든 데이터에서 같다고 말할 수는 없습니다. 두 조건이 언제나 같은 결과를 낸다는 것은 원소가 어느 쪽에 들어가는지를 비교해 증명할 수 있습니다. 이 글에서는 집합의 연산과 논리적 동치를 이용해 집합의 법칙을 증명하고, 원소의 개수를 세는 방법과 집합을 나누는 방법을 익힙니다.

두 집합이 같다는 것

두 집합 A와 B가 같다는 것은 원소가 정확히 같다는 뜻입니다. 이것을 보이려면 A의 임의의 원소가 B에 속한다는 것, 곧 $A\subseteq B$와, B의 임의의 원소가 A에 속한다는 것, 곧 $B\subseteq A$를 모두 보이면 됩니다. 한쪽 포함만으로는 부족합니다. $\{1\}\subseteq\{1,2\}$이지만 두 집합은 다르기 때문입니다.

분배법칙 $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$를 이 방법으로 증명해 보겠습니다. 임의의 원소 x에 대해, x가 왼쪽에 속한다는 것은 "$x\in A$이고, $x\in B$ 또는 $x\in C$"라는 뜻입니다. 여기에는 논리곱이 논리합에 대해 분배되는 논리의 분배법칙 $P\land(Q\lor R)\equiv(P\land Q)\lor(P\land R)$를 씁니다. 2장에서 따로 다루지는 않았지만, 세 명제의 여덟 가지 조합을 진리표로 계산하면 모든 줄에서 두 식의 값이 같으므로 동치입니다. 이 법칙에 따라 앞의 조건은 "($x\in A$이고 $x\in B$) 또는 ($x\in A$이고 $x\in C$)"와 동치이고, 이것은 x가 오른쪽에 속한다는 뜻입니다. 임의의 x가 왼쪽에 속하는 것과 오른쪽에 속하는 것이 동치이므로 양쪽 포함이 한꺼번에 성립하고, 두 집합은 같습니다. 집합의 등식을 원소가 속하는 조건으로 바꾸면, 논리 법칙으로 증명할 수 있는 것입니다.

여집합과 드모르간 법칙

전체집합 U가 정해져 있을 때, 여집합에도 드모르간 법칙이 성립합니다.

x가 $(A\cup B)^c$에 속한다는 것은 "$x\in A$ 또는 $x\in B$"가 거짓이라는 뜻이고, 논리의 드모르간 법칙에 따라 "$x\notin A$이고 $x\notin B$"와 동치입니다. 이것이 x가 $A^c\cap B^c$에 속한다는 뜻이므로 첫 등식이 성립합니다. 둘째 등식도 같은 방법으로 보입니다. 두 여집합이 같은 전체집합에서 계산된다는 점이 중요한데, 중간에 전체집합이 바뀌면 여집합의 뜻이 달라져 이 비교가 성립하지 않습니다.

전체집합이 작다면 모든 부분집합의 조합으로 법칙을 확인해 볼 수 있습니다. $U=\{1,2,3\}$의 부분집합은 8개이므로, 두 집합의 쌍은 64개, 세 집합의 조합은 512개입니다.

from itertools import combinations

U = {1, 2, 3}
subsets = [set(c) for r in range(4) for c in combinations(sorted(U), r)]
pairs = [(a, b) for a in subsets for b in subsets]
triples = [(a, b, c) for a in subsets for b in subsets for c in subsets]
print(len(subsets), len(pairs), len(triples))
print(all(U - (a | b) == (U - a) & (U - b) for a, b in pairs))
print(all(a & (b | c) == (a & b) | (a & c) for a, b, c in triples))
print(all(U - (a & b) == (U - a) & (U - b) for a, b in pairs))

8 64 512
True
True
False

드모르간 법칙과 분배법칙은 모든 조합에서 성립했습니다. 마지막 줄은 $(A\cap B)^c$를 $A^c\cap B^c$로 잘못 바꾼 식인데, 어떤 조합에서 거짓이 되어 False가 나왔습니다. 이렇게 작은 전체집합에서 모든 경우를 확인하면 틀린 법칙을 빠르게 걸러 낼 수 있습니다. 하지만 원소가 셋인 U에서 맞았다고 모든 집합에서 맞는다는 증명이 되는 것은 아니므로, 법칙이 참이라는 것은 앞의 원소 논증으로 보입니다.

합집합의 원소 세기

유한집합의 합집합에 원소가 몇 개인지 셀 때는 겹치는 부분에 주의해야 합니다. $|A|+|B|$를 계산하면 $A\cap B$의 원소를 A에서 한 번, B에서 한 번, 모두 두 번 세게 되므로 한 번을 빼야 합니다.

집합이 셋이면 두 집합씩 겹치는 부분을 빼고, 세 집합이 모두 겹치는 부분은 더했다 뺐다를 거치며 한 번도 세지 않게 되므로 다시 더합니다. 이렇게 더하고 빼며 세는 방법을 포함·배제의 원리(inclusion–exclusion principle)라고 합니다.

부분집합 관계가 있으면 식이 간단해집니다. $A\subseteq B$이면 $A\cup B=B$이고 $A\cap B=A$입니다. 다만 $A\subseteq B$라고 해서 $B\subseteq A$까지 따라오는 것은 아닙니다.

분할: 겹치지 않고 빠짐없이 나누기

집합 A를 몇 개의 부분집합으로 나누는데, 각 부분집합이 비어 있지 않고, 서로 다른 두 부분집합은 공통 원소가 없으며, 모두 합치면 A가 되도록 나눈 것을 A의 분할(partition)이라고 합니다. 나눈 부분집합 하나하나를 블록이라고 부릅니다. A의 모든 원소가 정확히 하나의 블록에 들어가는 것이 분할의 핵심입니다.

$A=\{0,1,2,3,4,5\}$를 짝수 $\{0,2,4\}$와 홀수 $\{1,3,5\}$로 나누면 분할입니다. $\{0,1,2\}$와 $\{2,3,4,5\}$는 2가 두 블록에 겹치므로 분할이 아니고, $\{0,1\}$과 $\{2,3\}$은 4와 5가 빠졌으므로 분할이 아닙니다. 세 조건을 그대로 코드로 옮기면 다음과 같습니다.

def is_partition(blocks, whole):
    if any(len(block) == 0 for block in blocks):
        return False
    for i in range(len(blocks)):
        for j in range(i + 1, len(blocks)):
            if blocks[i] & blocks[j]:
                return False
    return set().union(*blocks) == whole


W = {0, 1, 2, 3, 4, 5}
print(is_partition([{0, 2, 4}, {1, 3, 5}], W))
print(is_partition([{0, 1, 2}, {2, 3, 4, 5}], W), is_partition([{0, 1}, {2, 3}], W))

True
False False

첫 반복은 빈 블록이 있는지, 둘째 반복은 서로 다른 두 블록이 겹치는지 확인합니다. blocks[i] & blocks[j]가 비어 있지 않으면 참으로 여겨지므로 겹치는 원소가 있다는 뜻입니다. 마지막 줄의 set().union(*blocks)는 모든 블록의 합집합이고, 이것이 원래 집합과 같아야 빠진 원소가 없습니다.

분할은 "같은 기준을 만족하는 것끼리 한 무리로 묶은" 결과입니다. 짝수와 홀수로 나눈 것은 "2로 나눈 나머지가 같다"는 기준으로 묶은 것입니다. 어떤 기준이 분할을 만들어 내는지는 다음 장의 동치관계에서 다룹니다.

더 깊이: 분할은 모두 몇 가지인가

원소가 n개인 집합을 분할하는 방법의 수를 벨 수(Bell number)라 하고 $B_n$으로 씁니다. $\{a,b,c\}$라면 한 블록으로 둔 $\{a,b,c\}$, 하나를 떼어 낸 $\{a\},\{b,c\}$와 $\{b\},\{a,c\}$와 $\{c\},\{a,b\}$, 모두 떼어 낸 $\{a\},\{b\},\{c\}$로 다섯 가지라서 $B_3=5$입니다. 공집합은 블록이 하나도 없는 분할 하나뿐이라 $B_0=1$로 정하며, OEIS의 A000110에 따르면 $B_0$부터 차례로 1, 1, 2, 5, 15, 52, 203입니다.

벨 수는 새 원소 하나가 어느 블록에 들어가는지로 나누어 세면 앞의 값들로 계산할 수 있습니다. 원소가 $n+1$개일 때 새 원소 x가 든 블록은 x와 나머지 n개 가운데 몇 개로 이루어지고, 그 블록에 들지 않은 원소들은 자기들끼리 아무렇게나 분할됩니다. x와 같은 블록에 넣을 원소를 j개 고르는 방법이 $\binom nj$가지이고 남은 $n-j$개를 나누는 방법이 $B_{n-j}$가지이므로, $\binom nj=\binom n{n-j}$를 써서 정리하면 $B_{n+1}=\sum_{k=0}^{n}\binom nk B_k$입니다. 예를 들어 $B_4=1\cdot1+3\cdot1+3\cdot2+1\cdot5=15$입니다.

분할과 동치관계는 서로 하나씩 대응하므로, $B_n$은 원소가 n개인 집합 위의 동치관계의 수이기도 합니다. 블록의 수까지 정해 두고 세는 수는 제2종 스털링 수(Stirling number of the second kind)라고 하며, 블록의 수를 1부터 n까지 바꾸어 가며 더하면 $B_n$이 됩니다.

정리

• 두 집합이 같음은 양쪽 포함 $A\subseteq B$와 $B\subseteq A$를 모두 보여 증명하며, 원소가 속하는 조건으로 바꾸면 논리 법칙으로 증명할 수 있습니다.
• 분배법칙과 드모르간 법칙은 논리의 같은 법칙에서 나오며, 드모르간 법칙은 같은 전체집합에서 여집합을 계산할 때 성립합니다.
• 작은 전체집합의 모든 부분집합으로 법칙을 확인하면 틀린 식을 빠르게 걸러 낼 수 있지만, 참이라는 것은 원소 논증으로 보입니다.
• 포함·배제의 원리는 겹치는 부분을 빼고 더하며 합집합의 크기를 셉니다. $|A\cup B|=|A|+|B|-|A\cap B|$입니다.
• 분할은 비어 있지 않고 서로 겹치지 않으며 합치면 전체가 되는 블록들로 집합을 나눈 것입니다.

연습 문제

1. 공집합이 되는 식

$(A-B)\cap B=\varnothing$임을 원소의 조건으로 증명하세요.

2. 분할인지 판정하기

$A=\{1,2,3,4\}$에 대해 $\{\{1,2\},\{3\},\{4\}\}$는 분할인가요? $\{\{1,2\},\varnothing,\{3,4\}\}$는 분할의 어떤 조건을 어기나요?

3. 포함·배제로 세기

학생 중 Python을 배우는 사람이 4명, Java를 배우는 사람이 3명, C를 배우는 사람이 4명입니다. Python과 Java를 함께 배우는 사람은 2명, Java와 C는 2명, Python과 C는 2명이고, 세 언어를 모두 배우는 사람은 1명입니다. 적어도 한 언어를 배우는 사람은 몇 명인가요?

집합식이 길어지면 원소 x가 속하는 조건으로 바꾸어 보세요. 같은 방법은 다음 장의 관계의 성질을 증명할 때도 그대로 씁니다.