[이산 수학] 집합의 종류

집합의 종류

• 집합은 구성되는 원소의 개수나 집합 간의 포함 관계에 따라 명칭이 정의된다.

 

전체 집합(Universal Set : $U$ )

논의 대상이 되는 원소 전체를 포함하는 집합

• 전체 집합은 논의 대상에 따라 달라질 수 있으므로, 주어지는 문제에 따라 달라질 수 있다.
  • 예) 집합 $A = \{ a \; | \; a > 13, \; a ∈ \mathbb{N} \}$ 가 주어질 때, 문제에 따라 집합 `A` 에 대한 전체 집합은 자연수 집합 $\mathbb{N}$ 이 될 수 있고, 집합 `A` 자체가 될 수 있다.
    • 그러므로 전체 집합에 대한 판단은 문제에 따라 달라진다.

 

공집합(Empty Set : $\varnothing$ )

원소를 하나도 포함하지 않는 집합으로 기수가 0인 집합 ($|\varnothing | = 0$)

• 예) $C = \{ z \; | \; z^{3} = 2, \; z ∈ \mathbb{Z} \}$ 는 기수가 0인 집합이다.
• 이와 같이 원소를 하나도 포함하지 않아 기수가 0인 집합은 공집합이다.

 

상등(Equal : $A = B$ )

두 집합 $A, B$ 각각에 속하는 원소들이 모두 동일할 때, '두 집합 `A` 와 `B` 가 서로 같다' 또는 '두 집합 `A` 와 `B` 는 서로 상등이다' 라고 한다.
$$A = B \quad \Leftrightarrow \quad \forall a \; (a ∈ A \; \Leftrightarrow \; a ∈ B)$$

 

부분 집합(Subset : $A ⊆ B$ )

집합 `A` 의 모든 원소가 집합 `B` 에 포함될 때, 집합 `A` 는 집합 `B` 의 부분 집합 ($|A| ≤ |B|$)
$$A ⊆ B \quad \Leftrightarrow \quad \forall a \; (a ∈ A \; \Rightarrow \; a ∈ B)$$

 

진부분 집합(Proper Subset : $A ⊂ B$ )

집합 `A` 의 모든 원소가 집합 `B` 에 포함되지만, 집합 `A` 와 집합 `B` 가 상등이 아닐 때, 집합 `A` 는 집합 `B` 의 진부분 집합 ($|A| < |B|$)
$$A ⊂ B \quad \Leftrightarrow \quad \forall a \; (a ∈ A \; \Rightarrow \; a ∈ B) \; \land \; \exists a \; (a ∈ B \Rightarrow a \not ∈ A)$$

• 진부분 집합은 부분 집합의 한 종류로 볼 수 있다.
• 부분 집합은 두 집합이 상등인 경우도 포함하지만, 진부분 집합은 두 집합이 상등이 아니면서 부분 집합 관계가 있는 경우를 의미하므로 두 집합의 기수가 같은 경우는 없다.

 

예

$A = \{a \; | \; a ∈ \mathbb{Z} \}$ $B = \{b \; | \; b ∈ \mathbb{N} \}$ $C = \{c \; | \; c \text{는 음수이거나 0이거나 양수} \}$

• 집합 `B` 는 집합 `A` 의 부분 집합이면서 진부분 집합이다.
• 집합 `C` 는 집합 `A` 의 부분 집합이지만, 진부분 집합은 아니다.

 

$∈$ 과 $⊂$ (또는 $⊆$)

• 종종 $∈$ 기호와 $⊂$ (또는 $⊆$) 기호를 혼동하여 사용하는 경우가 있다.
• 두 기호의 정의에 따라 명확히 구분하여 사용해야 한다.
  • $∈$ : 원소와 집합 간의 포함 관계 (원소 ∈ 집합)
  • $⊂$ (또는 $⊆$) : 집합과 집합 간의 포함 관계 (집합 ⊂(⊆) 집합)

 

집합 간의 포함 관계

① 모든 집합 `A` 에 대하여, $A ⊆ A$
② 모든 집합 `A` 에 대하여, $\varnothing ⊆ A$
③ 모든 집합 `A` 에 대하여, $A ⊆ U$
④ 집합 $A, B, C$ 에 대하여, $A ⊆ B$ 이고 $B ⊆ C$ 이면 $A ⊆ C$
⑤ 집합 $A, B$ 에 대하여, $A = B \Leftrightarrow (A ⊆ B) \land (B ⊆ A)$

 

증명

① 모든 집합 `A` 에 대하여, $A ⊆ A$

집합 `A` 에 속하는 모든 원소 `a` 에 대하여 $a ∈ A$ 이다. ∴ 모든 집합은 자기 자신의 부분 집합이 된다.

 

② 모든 집합 `A` 에 대하여, $\varnothing ⊆ A$

$\varnothing ⊆ A$ 를 증명하기 위해 어떤 원소 `a` 에 대하여 $a ∈ \varnothing \Rightarrow a ∈ A$ 임을 증명한다. 공집합은 원소가 하나도 없는 집합이므로 명제 $a ∈ \varnothing \Rightarrow a ∈ A$ 에서 조건에 해당하는 명제 $a ∈ \varnothing$ 은 거짓(F)이다. 조건이 거짓(F)인 조건 명제는 항상 참(T)이므로, $a ∈ \varnothing \Rightarrow a ∈ A$ 는 참(T) 이다. ∴ 공집합($\varnothing$) 은 모든 집합의 부분 집합이다.

 

③ 모든 집합 `A` 에 대하여, $A ⊆ U$

$A ⊆ U$ 를 증명하기 위해 어떤 원소 `a` 에 대하여 $a ∈ A \Rightarrow a ∈ U$ 임을 증명한다. 집합 $U$ 는 전체 집합이므로 논의 영역의 모든 원소를 포함한다.  따라서 논의 영역에 속하는 원소 `a` 에 대하여 `a ∈ A` 이면, `a ∈ U` 가 성립한다. ∴ 모든 집합은 전체 집합 $U$ 의 부분 집합이다.

 

④ 집합 $A, B, C$ 에 대하여, $A ⊆ B$ 이고 $B ⊆ C$ 이면 $A ⊆ C$

어떤 원소 `a` 에 대하여 `a ∈ A` 이면, $A ⊆ B$ 에 의해 $a ∈ B$ 이다. $a ∈ B$ 이면 $B ⊆ C$ 에 의해 $a ∈ C$ 이다.  그러므로 $a ∈ A$ 이면 $a ∈ C$  이다.  따라서 $A ⊆ C$ 가 성립한다. ∴ $A ⊆ B$ 이고 $B ⊆ C$ 이면, $A ⊆ C$

 

⑤ 집합 $A, B$ 에 대하여, $A = B \Leftrightarrow (A ⊆ B) \land (B ⊆ A)$

$A = B \Leftrightarrow (A ⊆ B) \land (B ⊆ A) ≡ \{ A = B \Rightarrow (A ⊆ B) \land (B ⊆ A) \} \land \{(A ⊆ B) \land (B ⊆ A) \Rightarrow A = B \}$ (i) $A = B \Rightarrow (A ⊆ B) \land (B ⊆ A)$ $A = B$ 이므로 모든 $a ∈ A, \; b ∈ B$ 에 대하여 $a = b$ 가 성립한다. 따라서 원소 `a` 에 대해 $a ∈ B$ 가 성립하므로 $A ⊆ B$ 가 참(T)이고, 원소 `b` 에 대해 $b ∈ A$ 가 성립하므로 $B ⊆ A$ 가 참(T)이다. ∴$A = B \Rightarrow (A ⊆ B) \land (B ⊆ A)$ 는 참(T)이다. (ii) $(A ⊆ B) \land (B ⊆ A) \Rightarrow A = B$ $A ⊆ B$ 이므로 모든 $a ∈ A$ 에 대하여 $a ∈ B$ 가 성립한다. 또한 $B ⊆ A$ 이므로 모든 $b ∈ B$ 에 대하여 $b ∈ A$ 가 성립한다. 따라서 모든 $a ∈ A, \; b ∈ B$ 에 대하여 $(A ⊆ B) \land (B ⊆ A)$ 이므로, $a = b$ 이다. ∴ $(A ⊆ B) \land (B ⊆ A) \Rightarrow A = B$ 는 참(T)이다. ∴ (i)과 (ii)에 의해 $A = B \Leftrightarrow (A ⊆ B) \land (B ⊆ A)$ 가 성립한다.