요약

집합은 순서와 중복을 따지지 않는 “원소의 모음”이다. 합집합·교집합·차집합으로 모음을 조합하고, 부분집합을 모두 모은 멱집합, 순서쌍을 모은 곱집합으로 새 집합을 만든다. 데이터베이스의 표, 타입, 권한 그룹이 모두 집합이다. 다만 “자기 자신을 원소로 갖지 않는 모든 집합의 집합”처럼 아무 조건으로나 모으면 모순이 생긴다.

예시로 보기

동아리 A에 1, 2, 3, 4번 학생이, 동아리 B에 3, 4, 5번 학생이 있다.

연산 뜻 결과 파이썬
\(A \cup B\) 둘 중 하나라도 속한 학생 \(\{1,2,3,4,5\}\) A \| B
\(A \cap B\) 둘 다 속한 학생 \(\{3,4\}\) A & B
\(A - B\) A에만 속한 학생 \(\{1,2\}\) A - B
\(A \oplus B\) 한쪽에만 속한 학생 \(\{1,2,5\}\) A ^ B

원소가 집합에 속하는지를 참·거짓으로 보면, 합집합은 “또는”, 교집합은 “그리고”, 여집합은 “아니다”다. 그래서 논리의 동치 법칙이 그대로 집합의 항등식이 된다.

정의

정의

\(x \in A\)는 “\(x\)가 집합 \(A\)의 원소”라는 뜻이다. 집합은 원소로 정해진다: 원소가 모두 같으면 같은 집합이다. 전체집합 \(U\) 안에서1

  • 부분집합: \(A \subseteq B \iff \forall x\,(x \in A \to x \in B)\)(\(\forall\)은 “모든”). 진부분집합 \(A \subsetneq B\)는 \(A \subseteq B\)이고 \(A \ne B\).
  • 공집합 \(\varnothing\): 원소가 없는 집합. 모든 집합의 부분집합이다.
  • \(A \cup B = \{x : x \in A \vee x \in B\}\), \(\ A \cap B = \{x : x \in A \wedge x \in B\}\), \(\ A - B = \{x : x \in A \wedge x \notin B\}\), \(\ \bar A = U - A\)
  • 멱집합 \(\mathcal{P}(A)\): \(A\)의 모든 부분집합의 집합. \(\vert A\vert = n\)이면 \(\vert \mathcal{P}(A)\vert = 2^n\).
  • 곱집합 \(A \times B = \{(a, b) : a \in A, b \in B\}\). 순서쌍이라 \((a, b) \ne (b, a)\)일 수 있다. \(\vert A \times B\vert = \vert A\vert \,\vert B\vert\).

\(\{x : \text{조건}\}\) 꼴을 조건제시법이라 한다. 조건을 아무렇게나 쓰면 모순이 생긴다. \(R = \{X : X \notin X\}\)라 하면 \(R \in R\)이든 아니든 모순이다(러셀의 역설). 그래서 수학에서는 이미 있는 집합에서 원소를 골라내는 방식으로만 조건제시를 허용한다2.

증명 방법: 양쪽 포함. 두 집합이 같음을 보이려면 \(A \subseteq B\)와 \(B \subseteq A\)를 각각 보인다. 원소 하나를 잡고 따라가며 보이므로 원소 추적이라고도 한다.

집합의 드모르간 법칙

\(A - (B \cup C) = (A - B) \cap (A - C)\), \(\quad A - (B \cap C) = (A - B) \cup (A - C)\)

증명

첫째 식을 원소 추적으로 보인다. \(x \in A - (B \cup C)\) \(\iff\) \(x \in A \wedge \neg(x \in B \vee x \in C)\) \(\iff\) \(x \in A \wedge x \notin B \wedge x \notin C\) (논리의 드모르간) \(\iff\) \((x \in A \wedge x \notin B) \wedge (x \in A \wedge x \notin C)\) \(\iff\) \(x \in (A - B) \cap (A - C)\). 각 단계가 \(\iff\)이므로 양쪽 포함이 한 번에 된다. 둘째 식도 같다. ∎

예제

\(A = \{1,2,3,4\}\), \(B = \{3,4,5\}\)에서 \(\mathcal{P}(A \cap B)\)를 구한다.

  1. 교집합: \(A \cap B = \{3, 4\}\).
  2. 부분집합 늘어놓기: 원소마다 넣을지 뺄지 두 가지씩이다. \(\varnothing, \{3\}, \{4\}, \{3,4\}\).
  3. 개수 확인: \(2^2 = 4\)개다. 공집합과 자기 자신도 부분집합이다.
flowchart TD
  R["시작: 아무것도 안 고름"] -->|"3 넣음"| A["3"]
  R -->|"3 뺌"| B["없음"]
  A -->|"4 넣음"| L1["{3, 4}"]
  A -->|"4 뺌"| L2["{3}"]
  B -->|"4 넣음"| L3["{4}"]
  B -->|"4 뺌"| L4["∅"]

원소마다 갈림길이 둘이라 한 단계 내려갈 때마다 갈래가 두 배가 된다. 맨 아래 잎 네 개가 부분집합 넷이고, 원소가 \(n\)개면 잎이 \(2^n\)개다3.

검증: 무작위 부분집합 3,000조에서 드모르간·분배, \(\vert \mathcal{P}(A)\vert = 2^n\), \(\vert A \times B\vert\), 예시와 예제, 비트마스크 연산, \(\varnothing \ne \{\varnothing\}\) — 06_sets_verify.py

활용

  • 비트 집합. \(\{0, 1, \dots, n - 1\}\)의 부분집합을 \(n\)비트 정수로 쓴다. \(i\)가 들어 있으면 \(i\)번째 비트가 1이다. 합집합은 |, 교집합은 &, 차집합은 & ~로 한 번에 계산한다. \(\{0, 2, 3\}\)은 \(1101_2 = 13\)이다. 0부터 \(2^n - 1\)까지 세면 모든 부분집합을 돈다.
  • 데이터베이스. SQL의 UNION, INTERSECT, EXCEPT가 집합 연산이다. 관계형 모델의 표 하나는 곱집합의 부분집합이다(관계).
  • 자료구조. 해시 집합(set)은 원소 확인을 평균 상수 시간에 한다. 중복 제거는 리스트를 집합으로 바꾸는 것이다.
  • 알고리즘에서: 해시 집합이 원소를 빨리 찾는 원리는 딕셔너리와 집합에 있다. 위의 비트 집합을 코딩테스트에서 쓰는 법은 비트 연산과 비트마스크에 있고, 비밀지도는 두 지도의 벽 칸 집합을 줄마다 a | b(합집합)로 겹친다. 순위 검색은 네 칸마다 그 값과 - 중 하나를 고르는 곱집합으로, 지원자마다 조건 모양 \(2^4 = 16\)개를 만든다. 그 밖에 미로 탈출, 뉴스 클러스터링, 완주하지 못한 선수, 신고 결과 받기, 완전탐색, 이분 매칭, 리스트와 문자열에서도 쓴다.

연결

자주 하는 오해

“∅와 {∅}는 같다”

틀렸다. 둘 다 “비어 있는” 느낌이라 같아 보인다. \(\varnothing\)은 원소가 없는 집합이고, \(\{\varnothing\}\)은 공집합 하나를 원소로 가진 집합이다. 크기가 0과 1로 다르다. 빈 상자와 “빈 상자가 하나 든 상자”의 차이다. \(\mathcal{P}(\varnothing) = \{\varnothing\}\)이라 크기가 \(2^0 = 1\)인 것으로도 확인된다.

과목별 관점

컴파일러 (3-2학기). 멱집합이 기계를 바꾸는 데 쓰인다. 글자를 읽으며 칸을 옮겨 다니는 기계(유한 오토마타) 가운데 갈림길이 있는 것을 갈림길 없는 것으로 바꿀 때, 원래 기계의 상태 집합 \(Q\)의 부분집합 하나를 새 기계의 상태 하나로 삼는다. 그래서 이 방법을 부분집합 구성법 또는 멱집합 구성법이라 부른다. 원래 상태가 \(n\)개면 새 기계의 상태는 많아야 \(\vert \mathcal{P}(Q)\vert = 2^n\)개다. 빈 집합은 상태로 삼지 않으므로 정확히는 \(2^n - 1\)개 이하다. 실제로는 시작 상태에서 닿는 부분집합만 쓰여 대개 훨씬 적다: 부분집합 구성법4.

데이터베이스 설계 (2-2학기). 집합은 같은 원소를 한 번만 친다. SQL의 표는 그렇지 않다. 똑같은 행이 여러 번 들어 있을 수 있어서, 원소마다 “몇 번 들어 있는가”까지 따지는 모음이다. 이런 모음을 다중집합(multiset)이라 부른다. 직원 여덟 명의 월급을 꺼내면 25000이 세 번 나와 여덟 행이다. 질의에 DISTINCT를 적어야 겹친 것이 지워져 서로 다른 여섯 값의 집합이 된다. 행마다 값이 달라야 하는 키가 걸린 표는 똑같은 행이 있을 수 없어 처음부터 집합이다: 다중집합인 표와 DISTINCT.

이 문서의 합집합·차집합·교집합은 SQL에서 UNION, EXCEPT, INTERSECT다. 그대로 쓰면 집합의 연산이라 결과에서 겹친 행이 지워진다. 뒤에 ALL을 붙이면 다중집합의 연산이 되어 횟수를 계산에 넣는다. 어떤 값이 앞 결과에 \(m\)번, 뒤 결과에 \(n\)번 들어 있을 때 UNION ALL은 그 값을 \(m + n\)번, EXCEPT ALL은 \(\max(m - n, 0)\)번, INTERSECT ALL은 \(\min(m, n)\)번 남긴다. 합칠 때는 횟수를 더하고, 뺄 때는 횟수를 빼되 0 아래로는 안 내려가고, 겹치는 것을 구할 때는 작은 쪽을 딴다는 뜻이다5.

집합은 횟수가 0 아니면 1뿐인 다중집합이다. 그때 빼기와 겹치기의 식은 위 정의의 \(A - B\), \(A \cap B\)와 똑같다. 합치기만 다르다. 양쪽에 다 있는 원소는 \(1 + 1 = 2\)번이 되므로, 집합의 합집합은 더한 뒤 2를 1로 줄인 것, 곧 \(\max(m, n)\)이다5: 집합 연산 UNION·EXCEPT·INTERSECT.

확인 문제

C1 A = {1,2,3,4}, B = {3,4,5}일 때 A ∪ B, A ∩ B, A − B, B − A와 𝒫(A ∩ B)의 크기를 구하라.

답: \(\{1,2,3,4,5\}\), \(\{3,4\}\), \(\{1,2\}\), \(\{5\}\), \(2^2 = 4\).

C2 A − (B ∪ C) = (A − B) ∩ (A − C)를 원소 추적으로 증명하고, 어느 단계에서 논리의 드모르간 법칙을 쓰는지 밝혀라.

답: \(x \in A - (B \cup C) \iff x \in A \wedge \neg(x \in B \vee x \in C) \iff x \in A \wedge x \notin B \wedge x \notin C \iff x \in (A - B) \cap (A - C)\). 두 번째 \(\iff\)에서 \(\neg(p \vee q) \equiv \neg p \wedge \neg q\)를 쓴다.

C3 {0,1,2,3}의 부분집합을 4비트 정수로 쓴다. A = {0,2,3}, B = {1,2}를 정수로 쓰고, A ∪ B와 A ∩ B를 비트 연산으로 구하라.

답: \(A = 1101_2 = 13\), \(B = 0110_2 = 6\). \(A \cup B\) = 13 | 6 \(= 1111_2 = 15\) = \(\{0,1,2,3\}\). \(A \cap B\) = 13 & 6 \(= 0100_2 = 4\) = \(\{2\}\).

C4 표 R의 한 칸에 a1, a2, a2, a3이, 표 S의 한 칸에 a1, a2, a4, a5가 들어 있다(R에는 a2가 두 번 있다). SQL의 R UNION ALL S, R EXCEPT ALL S, R INTERSECT ALL S의 결과를 쓰라. ALL을 뗀 R EXCEPT S의 결과는 어떻게 다른가?

답: UNION ALL은 a1, a1, a2, a2, a2, a3, a4, a5의 8행. EXCEPT ALL은 a2, a3의 2행. INTERSECT ALL은 a1, a2의 2행. ALL을 뗀 R EXCEPT S는 a3 한 행이다.
이유: a2는 R에 2번, S에 1번 있다. ALL이 붙으면 횟수로 계산해 더하면 3번, 빼면 \(2 - 1 = 1\)번, 겹치는 것은 작은 쪽인 1번이다. ALL이 없으면 먼저 집합 \(\{a1, a2, a3\}\)과 \(\{a1, a2, a4, a5\}\)로 본 뒤 빼므로, a2는 S에 한 번이라도 있어서 통째로 빠진다5.

  1. Lehman·Leighton·Meyer, Mathematics for Computer Science, 4장 “Mathematical Data Types”(집합). Rosen, Discrete Mathematics and Its Applications 7판, 2장(집합, 집합 연산). ↩

  2. 러셀의 역설과 이를 피하는 분리 공리는 공리적 집합론(ZFC)의 내용이다. ↩

  3. ‘예제’ 2단계의 ‘원소마다 넣을지 뺄지 두 가지씩’을 갈림길로 그렸다. ↩

  4. 무작위 기계 300개에서 \(2^n - 1\)개를 넘지 않는 것, 상태 10개짜리가 4개로 바뀌는 예, 정확히 \(2^n\)개가 되는 예를 09_subset-construction_impl.py로 확인했다. ↩

  5. 그림의 값과 무작위 집합 500쌍은 57_sql-set-operations_verify.py로, EXCEPT ALL과 INTERSECT ALL 문장은 PostgreSQL 16에서 57_sql-set-operations_verify.sql로 확인했다. ↩ ↩2 ↩3