이산수학의 가장 기초되는 집합에 대해서 공부합니다. 이산수학 포스팅 시리즈나 추후에 다룰 해석학 포스팅 시리즈를 잘 이해하기 위해서는 집합의 이해는 매우 필수적입니다. 이 포스팅에서 다루는 집합 내용의 난이도는 높지 않지만 꼼꼼하게 학습하시길 바랍니다.
집합의 개념
집합은 수학의 모든 분야에서 가장 기초가 되는 개념입니다. 수학의 모든 기초가 될 뿐 아니라 일상생활에서도 많이 사용되는 개념입니다. 집합을 정의하면 다음과 같습니다.
💡 (정의) 집합
공통적인 성질을 가진 객체들의 모임으로, 대문자 $A, \ B, \ C, \cdots$으로 표시한다. 그 집합을 구성하는 객체를 원소라고 하며 소문자 $a, \ b, \ c, \cdots$으로 표시한다. “$x$가 집합 $S$의 원소이다”는 $x \in S$로 표현하며 “$x$가 집합 $S$의 원소가 아니다”는 $x \notin S$로 표현한다.
집합의 표현 방법
집합을 표시하는 기본적인 방법에는 원소나열법과 조건제시법 이렇게 두 가지가 있습니다.
- 원소나열법: $S$의 원소들이 1, 3, 5, 7, 9라 할 때, $S = \{1, \ 3, \ 5,\ 7,\ 9 \}$로 표시하는 것 같이 집합의 원소를 나열하여 집합을 표시하는 방법이다.
- 조건제시법: 집합 내의 원소가 만족해야 하는 공통적인 성질을 통하여 집합을 표시하는 방법이다. $A= \{ x \ | \ \text{P}(x)\} \ (\text{단, P(x)는 명제})$ 같은 방식으로 정의한다.
수 체계 집합
자주 사용되는 집합들에는 수 체계 집합이 있습니다. 다음 6가지의 집합은 반드시 익혀두기를 권합니다.
- $\mathbb{Z}^+ = \{ x \ | \ x\text{는 양의 정수}\} = \{1, \ 2, \ 3, \ \cdots \}$
- $\mathbb{N} = \{ x \ | \ x\text{는 양의 정수 또는 }0\} = \{0, \ 1, \ 2, \ 3, \ \cdots \}$
- $\mathbb{Z} = \{ x \ | \ x\text{는 정수}\} = \{\cdots, \ -2, \ -1, \ 0, \ 1, \ 2, \ 3, \ \cdots \}$
- $\mathbb{Q} = \{ x \ | \ x\text{는 유리수}\}$
- $\mathbb{R} = \{ x \ | \ x\text{는 실수}\}$
- $\mathbb{C} = \{ x \ | \ x\text{는 복소수}\}$
집합의 크기와 종류
집합의 크기를 정의하면 다음과 같습니다.
💡 (정의) 집합의 크기
집합의 크기란 집합의 크기를 나타내는 수로 기수로 표현한다. 이때, 기수란 집합의 크기를 측정하기 위한 표준이 되는 수로 자연수를 말한다. 예를 들어, 집합 $A$가 $n$개의 원소를 가진 유한집합이라고 하면 (단, $n \in N$), $n$을 집합 $A$의 크기라 하고 $\lvert A \rvert = n$과 같이 표시한다.
집합의 종류를 결정하기 위해서는 집합이 셀 수 있는가 또는 셀 수 없는가, 집합이 유한한가 또는 무한한가를 살펴보아야 합니다. 어떤 집합이 셀 수 있다는 것은 “자연수와 $1 : 1$ 대응이 되는 것”을 말합니다. 그리고 무한하다는 것은 원소의 개수가 무한히 많다는 것으로 집합 $A$의 적당한 진부분집합 $S$가 존재해서 $A$와 $S$ 사이에 일대일 대응이 존재하면 $A$를 무한집합이라고 하는 것입니다.
결국, 여기서 중요한 것은 “무한집합과 셀 수 없다는 것은 다른 뜻이라는 것”입니다. 이 두 가지 조건에 따라 집합의 종류를 분류해보면 다음과 같습니다.
- 셀 수 있는 유한집합
- 셀 수 있는 무한집합 (Ex. 양의 정수 집합 $\text{Z}^+$)
- 셀 수 없는 유한집합 (집합의 종류로만 나눌 수 있고, 실제로 이 집합은 존재하지 않습니다.)
- 셀 수 없는 무한집합 (Ex. 실수 집합 $R$)
부분집합
💡 (정의) 부분집합
집합 $A$의 모든 원소가 집합 $B$의 원소이면 “집합 $A$는 집합 $B$의 부분집합이다”라고 말하며, $A \subseteq B$로 표현한다. 만약 집합 $A$가 집합 $B$의 부분집합이 아니면 $A \nsubseteq B$로 표현한다.
💡 (정의) 진부분집합
$A$의 원소들 중 자기 자신을 제외한 다른 원소들을 모두 포함한 집합을 말한다. 즉, 자기 자신을 제외한 부분집합을 말한다. $A \subset B$로 표현한다.
💡 (정의) 전체집합
모든 대상을 원소로 포함하는 집합을 말한다. $U$로 표현한다.
💡 (정의) 공집합
원소를 하나도 포함하지 않는 집합을 말한다. $\varnothing$로 표현한다. 공집합은 모든 집합의 부분집합이다.
💡 (정의) 멱집합
집합 $A$에 대해, $A$의 모든 부분집합을 모은 집합을 $A$의 멱집합이라고 하며 $\text{P}(A)$로 표시한다.
💡 (정리) 부분집합의 성질집합 $A, \ B, \ C$에 대해 다음이 성립한다.
- 모든 집합 $\text{A}$에 대해 $\text{A} \subseteq \text{A}$이다.
- 모든 집합 $\text{A}$에 대해 $\varnothing \subseteq \text{A} \subseteq \text{A}$이다.
- $\text{A} \subseteq \text{B}$이고 $\text{B} \subseteq \text{C}$이면 $\text{A} \subseteq \text{C}$이다.
- $\text{A} = \text{B}$일 필요충분조건은 $\text{A} \subseteq \text{B}$이고 $\text{B} \subseteq \text{A}$이다.&nbs
집합의 연산
집합의 연산은 주어진 집합의 원소들을 가지고 연산하여 새로운 집합을 만드는 것입니다.
합집합
💡 (정의) 합집합
두 집합 $A$와 $B$에 대한 합집합은 $A$에 속하든지 또는 $B$에도 속하는 모든 원소들의 집합이다. $A \cup B$ 로 표시하며, ‘$A \text{ union } B$’ 또는 ‘$A$와 $B$의 합집합’ 이라고 읽는다.
$$ A \cup B = \{ x \ | \ x \in A \text{ 또는 } x \in B \} $$
교집합
💡 (정의) 교집합
두 집합 $A$와 $B$에 대한 교집합은 $A$에도 속하고 $B$에도 속하는 모든 원소들의 집합이다. $A \cap B$ 로 표시하며, ‘$A \text{ intersection } B$’ 또는 ‘$A$와 $B$의 교집합’ 이라고 읽는다.
$$ A \cap B = \{ x \ | \ x \in A \text{ 이고 } x \in B \} $$
💡 (정의) 서로소
두 집합의 교집합이 $\varnothing$이면 두 집합은 서로소라고 한다.
💡 (정의) 상호 서로소
공집합이 아닌 집합 $A_1, \ A_2,\ \cdots \ A_n$에서 임의의 두 개 집합이 모두 서로소이면 $A_1, \ A_2,\ \cdots, \ A_n$을 상호 서로소라고 한다. 즉, $i, \ j = 1, \ 2, \ 3, \cdots, \ n$에 대해 $A_i \cap A_j = \varnothing$ (단, $i \neq j$)이다.
💡 (정의) 가족 집합
공집합이 아닌 두 개 이상의 집합들의 모임을 가족 집합이라고 한다.
💡 (정의) 분할
가족 집합 $S$의 분할은 다음을 만족하는 공집합이 아닌 $S$의 부분집합 $A_1, \ A_2,\ \cdots, \ A_n$의 모임이다. 즉, 분할이란 어떤 집합을 공집합이 아닌 상호 서로소인 부분집합으로 나누는 것을 말한다. 분할 내에 있는 부분집합을 블록이라고 한다.
(1) $S$ 안에 있는 모든 원소 $a$는 임의의 원소 $A_i$에 속한다.
$$ S = \bigcup_{i \in n}A_i = A_1 \cup A_2 \cup \cdots \cup A_n $$
(2) 임의의 $i, \ j$에 대해 $A_i \cap A_j = \varnothing$ (단, $i \neq j$)이다. 즉, $A_1, \ A_2,\ \cdots, \ A_n$은 상호 서로소이다.
차집합
💡 (정의) 차집합
두 집합 $A$와 $B$에 대한 차집합은 $A$에는 속하고 $B$에는 속하지 않는 원소들의 집합이다. $A - B$ 로 표시하며, ‘$A \text{ difference } B$’ 또는 ‘$A$와 $B$의 차집합’ 이라고 읽는다.
$$ A - B = \{ x \ | \ x \in A \text{ 이고 } x \notin B \} $$
여집합
💡 (정의) 여집합
여집합은 전체집합 $U$에는 속하지만 $A$에는 속하지 않는 원소들의 집합이다. $\overline{A}$ 로 표시하며, ‘$A \text{ complement }$ ’ 또는 ‘$A$의 여집합’ 이라고 읽는다.
$$ \overline{A} = \{ x \ | \ x \in U \text{이고 } x \notin A \} = U - A $$
대칭 차집합
💡 (정의) 대칭 차집합
대칭 차집합은 두 차집합은 $A - B$ 에 속하거나 $B - A$ 에 속하는 원소들의 집합이다. $A \oplus B$ 로 표시하며, ‘$A$ 와 $B$의 $\text{symmetric difference}$’ 또는 ‘$A$와 $B$의 대칭 차집합’ 이라고 읽는다.
$$ A \oplus B = \{ (x \ | \ x \in A \text{ 이고 } x \notin B) \ \text{ 또는 } \ (x \ | \ x \in B \text{ 이고 } x \notin A) \} $$
곱집합
곱집합을 배우기 전 순서쌍에 대한 개념을 알아야 합니다.
💡 (정의) 순서쌍
순서쌍은 원소들을 표현하는 방법으로 원소들 사이에 순서를 갖는 것을 말한다. 일반저긍로 순서쌍은 괄호를 이용하여 표현한다. 순서쌍 $(a, \ b)$는 두 집합 각각에서 원소를 하나씩 뽑아 표현한 것으로 $a$는 첫 번째 원소이고 $b$는 두 번째 원소이다.
💡 (정의) 곱집합
곱집합 $A \times B$는 공집합이 아닌 임의읭 두 집합, $A, \ B$에 대해 $a \in A$이고 $b \in B$인 모든 순서쌍 $(a, \ b)$들의 집합을 말한다.
$$ A \times B = \{ (a, \ b) \ | \ a \in A \text{이고 } \ b \in B \} $$
💡 (정리) 곱집합의 크기
$A$와 $B$를 공집합이 아닌 유한집합이라 할 때 $A$와 $B$의 곱집합에 대한 크기는 $\lvert A \times B \rvert = \lvert A \rvert \times \lvert B \rvert$ 가 된다.또한 유한 개의 집합에서도 개념을 확장할 수 있는데,
어떤 집합 $A_1, \ A_2,\ \cdots, \ A_n$에 대해서 $a_1 \in A_1, \ a_2 \in A_2, \ \cdots, \ a_n \in A_n$인 $n$차의 순서쌍 $(a_1, \ a_2,\ \cdots, \ a_n)$의 모임을 집합 $A_1, \ A_2,\ \cdots, \ A_n$의 곱집합이라고 한다.
$A_1 \times A_2 \times \cdots \times A_n$ 또는 $\prod\limits_{i = 1}^nA_i$ 로 나타낸다.
집합의 대수적 성질
집합의 대수 성질을 다룰 때, 주로 사용하는 증명 방법은 다음과 같습니다.
- 벤 다이어그램을 이용하는 방법
- 각 집합이 다른 집합의 부분집합이 되는 것을 보이는 방법
- 진리표를 이용하는 방법
집합의 연산 성질
집합의 연산 정질을 알아보기 전, 두 집합의 같음 조건에 대해서 알아보겠습니다.
💡 (정의) 두 집합의 같음
두 집합이 같다는 것은 두 집합이 같은 원소들로 이루어졌다는 것이다. 두 집합의 같음을 통하여 집합의 원소들은 순서에 상관없다는 것을 알 수 있다.
집합의 연산 성질 중 쌍대 개념에 대해서 알아보겠습니다.
💡 (정의) 쌍대
집합에 관한 명제에서 합집합($\cup$), 교집합($\cap$), 전체 집합($U$)과 공집합($\varnothing$)을 서로 바꾼 명제를 원래 명제의 쌍대라고 한다.
다음 정리의 왼쪽과 오른쪽의 식은 모두 쌍대 관계입니다.
💡 (정리) 집합의 연산 성질집합의 연산은 다음의 법칙들을 만족한다.
- 교환법칙 $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 \cap C) = (A \cap B ) \cap 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 A = A$ $A \cap A = A$
- 여법칙 $\overline{\overline{A}} = A$ $A \cup \overline{A} = U$ $A \cap \overline{A} = \varnothing$ $\overline{\varnothing} = U$ $\overline{U} = \varnothing$
- 드 모르간 법칙 $\overline{A \cup B} = \overline{A} \cap \overline{B}$ $\overline{A \cap B} = \overline{A} \cup \overline{B}$
- 항등법칙 $A \cup U = U$ $A \cap U = A$ $A \cup \varnothing = A$ $A \cap \varnothing = \varnothing$
여집합에 대해서 조금 더 자세히 알아보겠습니다.
💡 (정리) 여집합의 유일성
두 집합 $A, \ B$가 전체 집합 $U$의 부분집합일 때, $B = \overline{A}$이면 $A \cup B = U$이고 $A \cap B = \varnothing$이다. 또한 그 역도 성립한다.
포함배제의 원리
포함배제의 원리는 집합의 크기를 계산할 때 매우 유용한 기법 중 하나입니다. 지금부터 포함배제의 원리에 대해 알아보겠습니다.
💡 (정리) 두 개의 집합에 대한 포함배제의 원리
두 집합 $A, \ B$가 유한집합일 때 $A \cup B$의 집합의 크기는 다음과 같다.
$$ \lvert A \cup B \rvert = \lvert A \rvert + \lvert B \rvert - \lvert A \cap B \rvert $$
포함배제의 원리는 두 개의 집합 이상으로 유한 개의 집합으로 확장시킬 수 있습니다. 여기서는 3개의 집합에서의 포함배제의 원리로 확장시켜보겠습니다.
💡 (정리) 세 개의 집합에 대한 포함배제의 원리
세 개의 집합 $A, \ B, \ C$가 유한집합일 때 $A \cup B \cup C$의 집합의 크기는 다음과 같다.
$$ \lvert A \cup B \cup C \rvert = \\ \lvert A \rvert + \lvert B \rvert + \lvert B \rvert \\ - \lvert A \cap B \rvert - \lvert B \cap C \rvert - \lvert C \cap A \rvert \\ + \lvert A \cap B \cap C \rvert $$
참고자료 (래퍼런스)
https://ko.wikipedia.org/wiki/무한_집합
https://ko.wikipedia.org/wiki/전체집합
https://www.youtube.com/watch?v=YGKwkptYB7s
https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=simba222&logNo=196591415
