4강. 집합

집합은 수학의 거의 모든 대상을 담는 그릇입니다. 이 강에서는 집합 연산을 2강의 논리 연산과 짝지어 이해합니다. “$x \in A \cap B$”는 “$x \in A$ 그리고 $x \in B$”이고, 집합의 항등식은 논리적 동치를 원소 하나에 적용한 것입니다.

4.1 원소와 부분집합

정의 4.1 (집합). 잘 정의된 대상들의 모임을 집합(set), 그 대상을 원소(element)라 합니다. $x$가 $A$의 원소이면 $x \in A$, 아니면 $x \notin A$로 씁니다.

집합은 원소를 나열하거나($\{1, 2, 3\}$) 조건으로 씁니다($\{x \in \mathbb{Z} \mid x^2 < 10\}$). 순서와 중복은 상관없습니다: $\{1, 2, 2, 3\} = \{3, 1, 2\}$. 원소가 없는 집합을 공집합(empty set) $\varnothing$이라 합니다.

정의 4.2 (부분집합). $A$의 모든 원소가 $B$의 원소이면 $A \subseteq B$라 씁니다. 기호로는 $\forall x\, (x \in A \to x \in B)$입니다.

정의 4.3 (집합의 같음). $A \subseteq B$이고 $B \subseteq A$이면 $A = B$입니다.

두 집합이 같음을 보이는 표준 방법은 이 정의 그대로 양쪽 포함을 따로 보이는 것입니다. 또 공집합은 모든 집합의 부분집합입니다: $x \in \varnothing$인 $x$가 없으므로 조건문 $x \in \varnothing \to x \in A$는 항상 참입니다.

4.2 집합 연산

전체집합 $U$ 안에서 생각합니다.

정의 4.4 (집합 연산).

$A \cap B = \varnothing$이면 $A$와 $B$는 서로소(disjoint)입니다.

4.3 집합의 항등식

논리적 동치(1강)를 원소 하나에 적용하면 집합의 항등식이 나옵니다.

정리 4.5 (집합의 항등식). 집합 $A, B, C$에 대해

• 교환: $A \cup B = B \cup A$, $A \cap B = B \cap A$
• 결합: $(A \cup B) \cup C = A \cup (B \cup C)$, 교집합도 같음
• 분배: $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$, $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
• 드모르간: $(A \cup B)^c = A^c \cap B^c$, $(A \cap B)^c = A^c \cup B^c$
• 차집합: $A \setminus B = A \cap B^c$

증명 (드모르간 첫째 식). $x \in (A \cup B)^c \iff \neg(x \in A \lor x \in B) \iff (x \notin A) \land (x \notin B) \iff x \in A^c \cap B^c$. 가운데 단계가 논리의 드모르간 법칙입니다. □

4.4 멱집합과 곱집합

정의 4.6 (멱집합). $A$의 부분집합 전체의 집합을 멱집합(power set) $\mathcal{P}(A)$라 합니다.

예제 4.7. $\mathcal{P}(\{a, b\}) = \{\varnothing, \{a\}, \{b\}, \{a, b\}\}$. 원소가 4개입니다.

정리 4.8. 원소가 $n$개인 집합의 멱집합은 원소가 $2^n$개입니다.

증명. 부분집합 하나를 고르는 것은 각 원소마다 “넣는다/뺀다”를 정하는 것과 같습니다. 원소마다 2가지이므로 $2^n$가지입니다. □

정의 4.9 (곱집합). $A \times B = \{(a, b) \mid a \in A,\ b \in B\}$. 원소 $(a, b)$를 순서쌍(ordered pair)이라 하며, 순서가 중요하므로 $(1, 2) \ne (2, 1)$입니다. 예를 들어 $\{1, 2\} \times \{x, y\} = \{(1, x), (1, y), (2, x), (2, y)\}$입니다.

$|A \times B| = |A| \cdot |B|$입니다. 좌표평면 $\mathbb{R}^2 = \mathbb{R} \times \mathbb{R}$이 대표적인 곱집합입니다.

4.5 원소의 개수

유한집합 $A$의 원소 개수를 $|A|$로 씁니다.

정리 4.10 (합집합의 크기). $|A \cup B| = |A| + |B| - |A \cap B|$.

증명. $|A| + |B|$는 $A \cap B$의 원소를 두 번 셉니다. 한 번 빼면 모든 원소를 한 번씩 셉니다. □

세 집합으로 늘린 식(포함배제 원리)은 8강에서 다룹니다.

예제 4.11. 1부터 100까지 가운데 2 또는 3의 배수의 개수: 2의 배수 50개, 3의 배수 33개, 6의 배수 16개이므로 $50 + 33 - 16 = 67$개입니다.

쓰이는 곳. 확률의 사건은 집합이고, 데이터셋·특징 공간·가설 공간도 집합으로 씁니다. 교집합과 합집합의 크기 공식은 확률의 덧셈 법칙 $P(A \cup B) = P(A) + P(B) - P(A \cap B)$로 그대로 쓰입니다.

4.6 이 장의 요약

• 집합 연산은 논리 연산과 짝을 이룹니다: $\cup$–또는, $\cap$–그리고, $^c$–부정.
• 두 집합이 같음은 양쪽 포함으로 보입니다.
• $|\mathcal{P}(A)| = 2^{|A|}$, $|A \times B| = |A||B|$, $|A \cup B| = |A| + |B| - |A \cap B|$.

문제

7
2
3
3
5

22

686

1,2,4

64