부분집합

원문 보기: https://dawoum.duckdns.org/wiki/부분집합

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)\)의 값은 얼마일까요?

응용예제2

집합 \(\displaystyle 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}\)에서 크기가 최소인 원소를 하나씩 뽑아 이들을 모두 더한 값은?

응용예제3

전체집합 \(\displaystyle U=\left\{\frac{1}{2^2},\;\frac{1}{2^4},\;\frac{1}{2^6},\;\cdots,\;\frac{1}{2^{20}}\right\}\)의 두 부분집합 \(A,B\)에 대하여 \(\displaystyle 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\)의 값은?