집합의 대수와 분할

검색 조건을 바꾸어도 결과가 같다는 것을 보이려면 특정 데이터 몇 개만 검사하기보다 포함 조건을 비교하는 편이 좋습니다. 집합 연산과 논리적 동치를 사용해 집합 항등식을 증명합니다.

집합이 같다는 것은 양쪽 포함

A=B를 보이려면 A의 임의의 원소가 B에 속하고, B의 임의의 원소도 A에 속함을 보이면 됩니다. 합집합·교집합의 교환·결합·분배법칙은 논리합·논리곱의 법칙과 연결됩니다. 예를 들어 $A\cap(B\cup C)=(A\cap B)\cup(A\cap C)$입니다.

임의의 x에 대해 왼쪽에 속한다는 말은 'x∈A이고, x∈B 또는 x∈C'입니다. 논리 분배법칙으로 '(x∈A이고 x∈B) 또는 (x∈A이고 x∈C)'와 동치입니다. 이는 오른쪽에 속한다는 뜻입니다. 임의의 x에서 포함 여부가 같으므로 두 집합이 같습니다.

여집합과 드모르간 법칙

같은 전체집합 U에서 $(A\cup B)^c=A^c\cap B^c$입니다. 왼쪽에 속한 x는 A에도 B에도 속하지 않아야 하므로 오른쪽에 속합니다. $(A\cap B)^c=A^c\cup B^c$도 같은 방식으로 보입니다. 전체집합을 중간에 바꾸면 여집합의 의미도 달라져 이 비교를 그대로 적용할 수 없습니다.

집합의 크기를 셀 때는 중복을 고려합니다. 유한집합에서 $|A\cup B|=|A|+|B|-|A\cap B|$입니다. 교집합 원소는 두 번 세었으므로 한 번 뺍니다. A⊆B라면 A∪B=B이고 A∩B=A입니다. A⊆B에서 B⊆A까지 자동으로 따라오지는 않습니다.

분할: 겹치지 않고 빠지지 않게

집합 A의 분할은 비어 있지 않은 블록들의 모음으로, 서로 다른 블록은 서로소이고 모든 블록의 합집합은 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가 빠져 분할이 아닙니다.

분할은 '같은 기준에 따라 동일 그룹으로 묶기'의 결과입니다. 동치관계는 그 기준을 관계의 성질로 설명합니다.

스스로 풀어보기

문제 1. $(A-B)\cap B=\varnothing$를 원소의 조건으로 증명하세요.

힌트: 원소가 있다고 가정하면 B 포함 여부가 충돌합니다.

풀이: 왼쪽의 원소 x가 있다면 x∈A−B이므로 x∉B입니다. 동시에 교집합의 원소이므로 x∈B입니다. 두 조건이 모순이어서 원소가 없고 공집합입니다. 집합을 임의로 선택하지 않았으므로 모든 A,B에서 성립합니다.

문제 2. A={1,2,3,4}의 모음 {{1,2},{3},{4}}는 분할인가요? {{1,2},∅,{3,4}}는 어떤 조건을 위반하나요?

풀이: 첫 모음은 블록이 모두 비어 있지 않고 서로 겹치지 않으며 합집합이 A이므로 분할입니다. 둘째는 공집합 블록을 포함해 비어 있지 않은 블록이라는 정의를 위반합니다. 공집합을 빼면 분할이 됩니다.

집합식이 길면 x의 포함 조건으로 번역하세요. 이 방법은 관계의 성질 증명에도 그대로 사용합니다.