[Discrete Mathematics] 집합(Set)의 개념과 성질

---

집합 표기법

 

집합(set)은 객체들, 즉 원소(element, member)의 모임이다. 원소의 순서는 상관없으며 중복도 가능하다. 집합은 중괄호 {} 로 묶어서 표현하며 집합 내 원소를 표현하는 방법은 다음 세 가지가 있다.

• 원소 나열법

집합 내 원소들을 일일이 나열하여 집합을 표기한다.

$$ A = \{ 1, 2, 3, 4 \} $$

• 조건 제시법

집합의 원소가 될 수 있는 조건을 조건식으로 표기한다.

$$ A = \{ x \in \mathbb{R} \mid 0 \leq x < 5 \} $$

• 벤다이어그램

집합과 원소의 포함관계를 그림으로 표기한다.

 

---

기본 용어

 

• $ | X | $ | 기수 (Cardinality)

집합이 유한집합일 때 원소의 개수를 말한다. 예를 들어 유한집합 $ X $ 가 있다고 할 때 $ |X| $ 는 $ X $ 의 원소 개수를 의미한다.

• $ \in $   $ \notin $

집합이 원소를 포함하는지, 포함하지 않는지 나타낸다. 예를 들어 집합 $ X $ 가 원소 $ x $ 를 포함한다면 $ x \in X $ 라고 할 수 있으며 포함하지 않는다면 $ x \notin X $ 라고 할 수 있다.

• $ \emptyset $ | 공집합 (Emtpy Set)

원소를 가지고 있지 않은 집합을 공집합이라 한다. 즉 $ \emptyset = \{ \} $ 이고, $ |\emptyset| = 0 $ 이다.

• $ = $ | 동등하다 (Equivalent)

두 집합이 동일한 원소를 가질 때 동등하다고 말할 수 있다. 예를 들어 집합 $ X $ 와 집합 $ Y $ 가 동일한 원소를 가질 때 $ X = Y $ 라고 할 수 있다. 동등하지 않다면 $  X \neq Y $ 으로 표현할 수 있다.

• $ \subseteq  $ | 부분집합 (Subset)

어떤 집합의 모든 원소가 다른 어떤 집합의 원소일 때 부분집합이라고 한다. 예를 들어 집합 $ X $ 의 모든 원소가 집합 $ Y $ 의 원소일 때 $ X \subseteq Y $ 라 할 수 있다.

• $ \subset $ | 진부분집합 (Proper Subset)

어떤 집합이 다른 어떤 집합에 부분집합이면서 두 집합이 동등하지 않다면 진부분집합이라고 한다. 예를 들어 집합 $ X $ 와 집합 $ Y $ 가 $ X \subseteq Y $ 이면서 $ X \neq Y $ 라면 $ X \subset Y $ 라고 할 수 있다.

• $ \mathcal{P}(X) $ | 멱집합 (Power Set)

어떤 집합의 모든 부분집합의 집합을 어떤 집합의 멱집합이라 한다. 예를 들어 집합 $ X = \{ a, b \}$ 가 있을 때 $ X $ 의 멱집합 $ \mathcal{P}(X) $ 는 $ \{ \emptyset , \{ a \} , \{ b \} , \{ a , b \} \} $ 이고, 이 멱집합의 기수, 즉 $ | \mathcal{P}(X) | $ 는 $ 2^2 = 4 $ 이다.

• $ \cup $ | 합집합 (Union)

어떤 두 집합에 속하는 모든 원소들의 집합이다. 예를 들어 집합 $ X = \{ a, b \} $ 와 집합 $ Y = \{ c, d \} $ 가 있을 때 $ X \cup Y = \{ a, b, c, d \} $ 이다. 즉 $ X \cup Y = \{ x \mid x \in X \text{ or } x \in Y \} $ 이다.

• $ \cap $ | 교집합 (Intersection)

어떤 두 집합에 모두 속하는 원소들의 집합이다. 예를 들어 집합 $ X = \{ a, b \} $ 와 집합 $ Y = \{ a, c \} $ 가 있을 때 $ X \cap Y = \{ c \} $ 이다. 즉 $ X \cap Y = \{ x \mid x \in X \text{ and } x \in Y \} $ 이다.

• $ X - Y $ | 차집합 (Difference)

어떤 집합에는 속하지만 다른 어떤 진합에는 속하지 않는 집합이다. 예를 들어 집합 $ X = \{ a, b \} $ 와 집합 $ Y = \{ a, c \} $ 가 있을 때 $ X - Y = \{ b \} $ 이다. 즉 $ X - Y = \{ x \mid x \in X \text{ and } x \notin Y \} $ 이다.

 

---

서로소

 

• 집합족 (Family of Sets)

원소가 집합인 집합을 집합들의 모임(collection of sets) 또는 집합족(family of sets)이라 한다. 예를 들어서 집합 $ \mathcal{S} = \{ \{ a, b \} , \{ c, d \} , \{ e, f , g, d \} \} $ 는 집합의 원소가 모두 집합이므로 집합족이다.

• 서로소 (Disjoint)

어떤 두 집합의 교집합이 공집합일 때 서로소라고 한다. 예를 들어 집합 $ X = \{ a, b \} $ 와 $ Y = \{ c, d \} $ 는 $ X \cap Y = \emptyset $ 이므로 서로소이다.

• 쌍마다 서로소 혹은 쌍으로 소 (Pairwise Disjoint)

집합들의 모임인 집합족에서 집합족 내 모든 집합들이 서로소이면, 즉 집합 내 서로 다른 모든 집합의 교집합이 공집합이라면 이 집합족을 쌍마다 서로소라 한다. 예를 들어 $ \mathcal{S} = \{ \{ a, b, c \} , \{ d, e \} , \{ f \} \} $ 라면 쌍마다 서로소이다.

• $ U $ | 전체집합 (Universal Set)

어떤 집합들을 하나의 집합의 부분집합으로 다룬다면 그 집합들을 포함하는 집합을 전체집합이라 한다. 이때 전체집합 $ U $ 는 분명히 제시되거나 추론되어야 한다.

• $ \overline{X} $ | 여집합 (Complement)

전체집합과 그 전체집합의 부분집합이 주어졌을 때 전체집합에서 부분집합을 제외한 것을 부분집합의 여집합이라 한다. 즉 전체집합 $ U $ 와 부분집합 $ X $ 가 있을 때 $ U - X $ 를 $ X $ 의 여집합 $ \overline{X} $ 라 한다.

 

---

집합의 성질

 

$ U $ 를 전체집합이라 하고, $ A, B, C $ 를 $ U $ 의 부분집합이라 가정한다.

• 결합법칙 (Associative Laws)

$$ ( A \cup B ) \cup C = A \cup ( B \cup C ) $$

• 교환법칙 (Commutative Laws)

$$ A \cup B = B \cup A $$

$$ A \cap B = B \cap A $$

• 분배법칙 (Distributive Laws)

$$ A \cap ( B \cup C ) = ( A \cap B ) \cup ( A \cap C ) $$

$$ A \cup ( B \cap C ) = ( A \cup B ) \cap ( A \cup C ) $$

• 항등법칙 (Identity Laws)

$$ A \cap U = A $$

$$ A \cup \emptyset = A $$

• 여집합법칙 (Complement Laws)

$$ A \cup \overline{A} = U $$

$$ A \cap \overline{A} = \emptyset $$

• 멱등법칙 (Idempotent Laws)

$$ A \cup A = A $$

$$ A \cap A = A $$

• 경계법칙 (Bound Laws)

$$ A \cup U = U $$

$$ A \cap \emptyset = \emptyset $$

• 흡수법칙 (Absorption Laws)

$$ A \cup ( A \cap B ) = A $$

$$ A \cap ( A \cup B ) = A $$

• 대합법칙 (Involution Laws)

$$ \overline{\overline{A}} = A $$

• 0/1 법칙 (0/1 Laws)

$$ \overline{\emptyset} = U $$

$$ \overline{U} = \emptyset $$

• 드모르간의 법칙 (De Morgan's Laws)

$$ \overline{A \cup B} = \overline{A} \cap \overline{B} $$

$$ \overline{A \cap B} = \overline{A} \cup \overline{B} $$

 

---

집합족 표현

 

• 집합족의 합집합

임의의 집합족 $ \mathcal{S} $ 의 합집합은 집합족 $ \mathcal{S} $ 에 포함된 모든 집합의 합집합을 말한다. 수학적으로는 $ \bigcup_{A \in \mathcal{S}} A $ 로 표기할 수 있다. 혹은 $ \bigcup \mathcal{S} = \{ x \mid \exists X \in \mathcal{S} , x \in X \} $ 으로도 표현할 수 있다.

• 집합족의 교집합

임의의 집합족 $ \mathcal{S} $ 의 교집합은 집합족 $ \mathcal{S} $ 내의 모든 집합에 속하는 원소들로 구성된 집합을 말한다. 수학적으로는 $ \bigcap_{A \in \mathcal{S}} A $ 로 표기할 수 있다. 혹은 $ \bigcap \mathcal{S} = \{ x \mid \forall X \in \mathcal{S} , x \in X \} $ 으로도 표현할 수 있다.

• 유한집합족과 무한집합족에서

만약 집합족 $ \mathcal{S} $ 가 $ n $ 개의 집합을 가진 유한집합족이라면 합집합은 $ \bigcup \mathcal{S} = \bigcup^{n}_{i = 1} A_i $ , 교집합은 $ \bigcap \mathcal{S} = \bigcap^{n}_{i = 1} A_i $ 으로 표현할 수 있고, 무한집합족이라면 합집합은 $ \bigcup \mathcal{S} = \bigcup^{\infty}_{i = 1} A_i $ , 교집합은 $ \bigcap \mathcal{S} = \bigcap^{\infty}_{i = 1} A_i $ 으로 표현할 수 있다.

 

---

분할과 순서쌍, 카테시안 곱

 

• 분할 (Partition)

어떤 집합을 겹치지 않는, 즉 서로소인 부분집합들로 나누는 것을 말한다. 즉 다음 두 조건을 만족하는 부분집합들을 만드는 것을 분할이라 한다. 이때 집합 $ X $ 를 분할하여 $ A_n $ 을 만든다 가정한다.

$$ \bigcup_{i=1}^{n} A_i = X $$

$$ A_i \cap A_j = \emptyset \quad (i \neq j) $$

• 순서쌍 (Ordered Pair)

원소 $ ( a, b ) $ 로 작성된 순서쌍은 $ ( b, a ) $ 와 다르다고 간주한다. 즉 $ ( a, b ) = ( c, d ) $ 는 오직 $ a = c $ 이고 $ b = d $ 일 때 성립한다. 즉 순서에 맞게 동일해야 같은 순서쌍이라 간주한다.

• 카테시안 곱 (Cartesian Product)

집합 $ X $ 과 $ Y $ 가 있을 때 카테시안 곱은 다음으로 정의된다.

$$ X \times Y = \{ ( x, y ) \mid x \in X , y \in Y \} $$

이를 기수와 연결 지으면 아래와 같은 결과가 나온다.

$$ | X \times Y | = | X | \cdot | Y | $$

• $ n $-튜플 ($ n $-tuple)

$ n $-튜플은 순서쌍이 확장된 형태라 생각하면 편하다. 예를 들어 $ ( a_1, a_2, \ldots , a_n ) = ( b_1, b_2, \ldots , b_n ) $ 은 $ a_1 = b_1 , a_2 = b_2 , \ldots , a_n = b_n $ 일 때만 성립한다. 즉 $ n $ 개의 원소를 순서 있게 나열한 것을 말한다.

집합 $ X_1, X_2, \ldots , X_n $ 의 카테시안 곱은 이들 집합에서 각 요소를 하나씩 택하여 만든 $ n $-튜플들의 집합으로 정의된다. 즉 집합 $ X_1, X_2, \ldots , X_n $ 의 카테시안 곱은 모든 n-튜플 $ ( x_1, x_2, \ldots , x_n ) $ 의 집합으로 정의되며, 여기서 $ x_i \in X_i $ 는 $ i = 1, 2, \ldots, n $ 에 대해 성립하며 이 카테시안 곱은 $ X_1 \times X_2 \times \cdots \times X_n $ 으로 표기된다. 예를 들어 집합 $ X_1 = \{ 1, 2 \} $ 와 $ X_2 = \{ a, b \} $ 의 카테시안 곱은 $ X_1 \times X_2 = \{ (1, a), (1, b), (2, a), (2, b) \} $ 라 말할 수 있다.