[이산수학]집합의 기본 개념

1. 기본 용어 정리

수학에서 집합이란 어떠한 대상들의 모임이다. 흔히 말하는 집합과 같은 것이라고 생각하면 된다.

물론 수학에서의 집합은 서로 다른 대상들의 모임을 의미하기 때문에 집합이 하나의 대상이 집합에 몇 개 존재하는지는 관심이 없다.

(대상이 몇 개가 있든 한 개만 있는 것으로 보겠다는 뜻이다. 아래에서 자세히 설명하겠다.)

 

1-1. 원소

집합 안에 있는 것들은 원소라 하며, 만약 숫자 1이 집합 X의 원소이면 다음과 같이 표기한다.

$$1\in X$$

원소가 아닌 것은 다음과 같이 표기한다.

$$2\notin X$$

 

1-2. 집합을 나타내는 방법

집합을 나타내는 방법은 크게 2가지가 있다.

첫 번째는 원소나열법이다. 집합에 속하는 모든 원소를 집합기호 { }안에 나열하여 나타내는 방법이다.

예를 들어 집합 $A$가 $1,2,3$을 원소로 갖는다고 하면 다음과 같이 표기한다.

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

또한 아까 위에서 설명했듯이 집합은 하나의 대상이 몇 개가 있는지에는 관심이 없기 때문이 $\{1,1,2,3\}$으로 표기하면 안된다.

중복되게 표기하지 않는다. 또한 순서에도 관심이 없기 때문에 $A=\{1,2,3\}=\{2,3,1\}=\{1,3,2\}$이다.

 

두 번째는 조건제시법이다. 조건제시법은 집합에 포함되는 원소들의 공통된 성질(조건)을 서술(제시)함으로써 집합을 나타내는 방법이다.

$$\{원소| 원소의\ 조건\}$$

예를 들어 집합 $A$가 1이상 100이하의 자연수들을 원소로 갖는다고 하면 다음과 같이 표기한다.

$$A=\{x|x는\ 1이상\ 100이하의\ 자연수 \}$$

 

1-3. 공집합

이러한 집합들 이외에도 원소를 하나도 갖지 않는 빈 집합을 생각해볼 수 있는데, 이러한 집합을 공집합이라 하며, $\varnothing$로 표기한다. 원소나열법으로 표기하면 $\{\}$이다.

 

1-4. 전체집합

공집합과는 반대로 모든 대상을 원소로 갖는 집합을 의미하며, $U$로 표기한다.

 

2. 집합간의 용어

2-1. 부분집합

집합 $B$가 집합 $A$의 부분집합이라는 것은 $B$의 원소가 모두 $A$에도 포함된다는 것을 의미하며, 다음과 같이 표기한다.

$$B\subset A$$

예를 들어 집합 $\{1,2\}$는 $\{1,2,3\}$의 부분집합이다.

$$\{1,2\}\subset \{1,2,3\}$$여기서 자시 자신을 제외한 부분집합을 진부분집합이라 한다.예를 들어 집합 $\{1,2,3\}$는 자기 자신의 부분집합이지만 진부분집합은 아니다.반면에 집합 $\{1,2\}$는 집합 $\{1,2,3\}$의 진부분집합이다.또한 자기보다 큰 집합을 초집합이라 한다.$B$가 $A$의 진부분집합이면 $A$는 $B$의 초집합이다.

 

2-2. 합집합과 교집합

합집합은 집합들의 원소를 하나의 집합으로 모은 더 큰 집합이며, 다음과 같이 정의된다.$$A\cup B=\{x|x\in A \vee x\in B\}$$예를 들어 집합 $A=\{1,2\}$와 집합 $B\{1,2,3\}$의 합집합은 다음과 같다.$$A\cup B=\{1,2,3,4\}$$

 

교집합은 집합들의 공통된 원소들을 모은 집합을 의미하며, 다음과 같이 정의된다.$$A\cap B=\{x|x\in A \wedge x\in B\}$$예를 들어 집합 $A=\{1,2,3,4\}$와 집합 $B=\{2,3,5\}$의 교집합은 다음과 같다.$$A\cap B=\{2,3\}$$

 

2-3. 여집합

집합 $A$의 여집합은 $A^C$로 표기하며, 다음과 같이 정의된다.$$A^C=\{x|x\in U,\ x\notin A\}$$즉, 전체집합 $U$의 원소중에서 집합 $A$의 원소가 아닌 것들의 집합이다.

 

2-4. 차집합

집합 $A$와 집합 $B$에 대해서 차집합 $A-B$는 다음과 같이 정의된다.$$A-B=\{x|x\in A \wedge x\notin B\}$$즉, A의 원소이지만 B의 원소가 아닌 것들의 집합이다.예를 들어 집합 $A=\{1,2,3,4\}$와 집합 $B=\{1,2\}$의 차집합은 다음과 같다.$$A-B=\{3,4\}$$

 

3. 집합족

집합족이란 집합을 원소로 갖는 집합을 의미한다.예를 들어 다음과 같은 집합을 의미한다.$$F=\{\{1,2,3\}\}$$

 

3-1. 집합족의 연산

$$\bigcup F=\bigcup _{A\in F}A=A_1\cup A_2\cup \cdots \cup A_n=\{x|\exists A\in F,\ x\in A\}$$집합족은 집합들을 원소로 갖는다 하였는데, 그 집합들의 합집합을 의미한다.

$$\bigcap F=\bigcap _{A\in F}A=A_1\cap A_2\cap \cdots \cap A_n=\{x|\forall A\in F,\ x\in A\}$$

마찬가지로 집합족의 원소들의 교집합을 의미한다.

 

3-2. 법칙들

드 모르간 법칙

$$\left(\bigcup _{A\in F}A\right)^C=\bigcap _{A\in F}A^C$$

$$\left(\bigcap _{A\in F}A\right)^C=\bigcup _{A\in F}A^C$$

 

분배법칙

$$A\cap \bigcup _{B\in F} B=\bigcup _{B\in F}\left( A\cap B\right)$$

$$A\cup \bigcap _{B\in F} B=\bigcap _{B\in F}\left( A\cup B\right)$$

 

위 법칙들의 증명은 꼭 직접 해보길 바란다.

 

3-3. 첨수족

첨수족은 첨수번호가 부여된 대상들로 이루어진 집합을 의미한다. 예를 들어 다음과 같다.

$$A_1=\{6\}$$

$$A_2=\{1,2,3,4,5\}$$

$$A_3=\{7,8,9\}$$

$$F=\{A_1, A_2, A_3\}$$

집합 $F$는 집합을 원소로 갖기 때문에 집합족이면서 첨수족이다.

위 집합족의 연산은 첨수족에서는 다음과 같이 표기한다.

$$I=\{1,2,3\}$$

$$\bigcup F=\bigcup _{i\in I}A_i=A_1\cup A_2\cup A_3=\{1,2,3,4,5,6,7,8,9\}$$

$$\bigcap F=\bigcap _{i\in I}A_i=A_1\cap A_2\cap A_3=\varnothing$$

4. 곱집합

곱집합은 순서쌍들의 집합이며, 다음과 같이 정의된다. (순서쌍 $(a,b)=\{\{a\}, \{a,b\}\}$)

$$A\times B=\{(a,b)|a\in A,\ b\in B\}$$

예를 들어 집합 $A=\{1,2\}$와 $B=\{3,4\}$의 곱집합 $A\times B$는 다음과 같다.

$$A\times B=\{(1,3),(1,4),(2,3),(2,4)\}$$

n개의 집합들의 곱집합은 위 첨수족을 이용해서 정의한다.

$$\prod_{i\in I}A_i=A_1\times A_2\times \cdots \times A_n = \{\left(a_i \right)_{i\in I}|\forall i \in I,\ a_i\in A_i \}$$

n-튜플의 집합이 된다.

3개의 집합들의 곱집합으로 예를 들자면 다음과 같다.

$$A_1=\{1,2\}$$

$$A_2=\{3,4\}$$

$$A_3=\{5,6\}$$

$$I=\{1,2,3\}$$

$$\prod_{i\in I}A_i=A_1\times A_2\times A_3=\{(1,3,5), (1,3,6), (1,4,5),(1,4,6),(2,3,5),(2,3,6),(2,4,5),(2,4,6)\}$$