부분집합

Main article: Subset

부분집합(subset) $A$는, 모든 원소가 $B$에도 속하는 집합을 말합니다. 이런 관계를 기호로 $A\subset B$(또는$B\supset A$)로 나타냅니다. 예를 들어 집합 {1, 2, 3}은 {1, 2, 3, 4, 5}의 부분집합입니다. 벤 다이어그램에서는 어떤 집합 내에 부분집합이 포함된 두 원으로 나타냅니다. $A=B$인 경우에도 $A$는 $B$의 부분집합이라고 말하며, 그렇지 않은 부분집합을 진부분집합(proper subset)이라고 부릅니다. 진부분집합은 기호로 '$A\subset B$이고 $A\neq B$'로 나타낼 수 있습니다.

반면에 집합 $A$가 집합 $B$의 부분집합이 아닐 때, $A\not \subset B$와 같이 나타냅니다.

집합의 모든 부분집합을 모아놓은 집합을 멱집합이라고 합니다.

집합의 상등

두 집합 $A,B$가 서로 같은 원소들로 이루어져 있을 때, 집합 $A$와 집합 $B$는 서로 같다고 합니다. 즉, 집합 $A$의 모든 원소가 집합 $B$에 속하고, 집합 $B$의 모든 원소가 집합 $A$에 속하는 경우입니다.

기호를 사용해서 나타내면, $A\subset B$ 이고 $A\supset B$인 경우이며, 줄여서 $A=B$라고 표현합니다.

부분집합의 개수

어떤 집합의 부분집합을 구할 때에는 원소의 개수가 0개, 1개, 2개, $\cdots$인 경우로 구분해서 구하는 것이 좋습니다. 특히, 규칙이 일관되지 않은 경우에 실수를 줄이는 유일한 방법일지도 모릅니다. 그러나 규칙이 있을 때에는 다른 방법을 이용하는 것도 좋겠습니다.

원소가 $n$개인 집합의 부분집합의 개수는 몇개 일까요?

규칙이 있는 부분집합의 개수를 구할 때에는 벤 다이어그램을 이용하는 것이 편리합니다. 벤 다이어그램은 어떤 집합의 영역이 집합 내부와 집합 외부의 두 가지 영역으로 나뉩니다. 그렇기 때문에 각각의 원소가 가질 수 있는 경우의 수가 2가지입니다. 또한, 어떤 집합의 부분집합을 구성할 때에는 모든 원소를 다 시험했을 때에 끝납니다. 즉, 원소 각각이 2가지의 경우를 가지기 때문에, 경우의 수의 곱의 법칙에 의해서, $2^{n}$개의 부분집합을 가집니다. 여기서 진부분집합은 자기자신을 제외해야 하기 때문에, $2^{n}-1$개의 부분집합을 가집니다.

반면에 특정한 원소 $m$를 포함하는 경우에는 $2^{n-m}$개의 부분집합을 가집니다. 왜냐하면, 특정한 원소 $m$개는 집합 내부에만 들어가야 하기 때문에 경우의 수가 1로 줄기 때문입니다. 나머지 원소인 $n-m$개만 2가지 경우를 가집니다.

마찬가지로 특정한 원소 $m$를 포함하지 않는 경우에도 $2^{n-m}$개의 부분집합을 가집니다. 왜냐하면, 특정한 원소 $m$개는 집합 외부에만 들어가야 하기 때문에 경우의 수가 1로 줄기 때문입니다.

한편, 특정한 원소 $m$를 포함하는 경우의 진부분집합의 개수는 $2^{n-m}-1$개 입니다. 그러나 특정한 원소 $m$를 포함하는 않는 경우의 진부분집합의 개수는 $2^{n-m}$개 입니다. 전자는 자신과 같은 부분집합이 생기기 때문에 1개를 감소시켜야 하지만, 후자는 자기자신과 같은 집합의 부분집합을 애초에 못만드는 경우입니다.

만약, $n$개의 원소를 갖는 전체집합에서 이 원소들로 구성할 수 있는 집합 $A,B$의 순서쌍은 몇개일까요? 이때에는 벤 다이어그램의 영역이 4가지가 있습니다. 그렇기 때문에 전체 순서쌍은 $4^{n}$개를 가집니다. 또한, $A\cup B$의 원소의 개수가 $n$개일 때, 이 원소들로 구성할 수 있는 집합 $A,B$의 순서쌍은 몇개일까요? 이 경우에는 벤 다이어그램의 영역이 3개입니다. 그러므로 순서쌍은 $3^{n}$개를 만들 수 있습니다.

응용예제

응용예제1

집합 $A=\{1,2,3,4,5,6\}$에서 짝수가 두 개만 포함되는 부분집합을 $A_{1},A_{2},\cdots ,A_{n}$이라 하고, 집합 $A_{n}$의 원소의 총합을 $S(A_{n})$이라고 놓습니다. 이때, $S(A_{1})+S(A_{2})+\cdots +S(A_{n})$의 값은 얼마일까요?

해설: mowoum:부분집합#응용예제1

응용예제2

집합 $S=\left\{1,{\frac {1}{2}},{\frac {1}{4}},{\frac {1}{8}},{\frac {1}{16}}\right\}$의 공집합이 아닌 서로 다른 부분집합을 $A_{1},A_{2},A_{3},\cdots ,A_{31}$이라고 놓습니다. 이때, 각각의 집합 $A_{1},A_{2},A_{3},\cdots ,A_{31}$에서 크기가 최소인 원소를 하나씩 뽑아 이들을 모두 더한 값은?

해설: mowoum:부분집합#응용예제2

응용예제3

전체집합 $U=\left\{{\frac {1}{2^{2}}},\;{\frac {1}{2^{4}}},\;{\frac {1}{2^{6}}},\;\cdots ,\;{\frac {1}{2^{20}}}\right\}$의 두 부분집합 $A,B$에 대하여 $A=\left\{{\frac {1}{2^{2}}},\;{\frac {1}{2^{4}}},\;{\frac {1}{2^{6}}}\right\}$일 때, $n(A\cap B)=2$를 만족시키는 집합 $B$를 $B_{1},\;B_{2},\;\cdots \;B_{n}$ (n은 자연수)이라 하자. 집합 $B_{i}$의 원소 중에서 최소인 것을 $b_{i}\;(i=1,2,3,\cdots ,n)$라 할 때, $2^{14}\cdot (b_{1}+b_{2}+b_{3}+\cdots +b_{n})+1$의 값은?

해설: mowoum:부분집합#응용예제3