집합 사이의 포함관계

피자 토핑이 4가지 있고, 그 가운데 원하는 것만 골라 올릴 수 있다. 아무것도 올리지 않는 것까지 포함하면 만들 수 있는 피자는 몇 가지일까? 토핑의 집합에서 고른 토핑의 집합은 원래 집합과 어떤 관계일까?

원소의 개수 \(n\) =

2.2.1부분집합

토핑의 집합을 \(U = \{\text{치즈}, \text{버섯}, \text{햄}, \text{올리브}\}\)라 하자. 치즈와 햄만 올린 피자의 토핑 집합 \(A = \{\text{치즈}, \text{햄}\}\)은 원소가 모두 \(U\)에 들어 있다. 이렇게 \(A\)의 모든 원소가 \(B\)의 원소일 때 \(A\)를 \(B\)의 부분집합이라 하고 \(A \subset B\)로 쓴다.

\(A\)가 \(B\)의 부분집합이 아니라는 것은 \(A\)에 \(B\) 밖의 원소가 하나라도 있다는 뜻이다. 따라서 \(A \not\subset B\)임을 보이려면 그런 원소를 하나 찾으면 된다. 반대로 \(A \subset B\)임을 보이려면 \(A\)의 원소를 빠짐없이 확인해야 한다.

정의에 따라 모든 집합은 자기 자신의 부분집합이다. 또 공집합은 모든 집합의 부분집합이다. 공집합에는 원소가 없으므로 '다른 집합 밖에 있는 원소'도 없기 때문이다.¹ 피자로 말하면 토핑을 하나도 올리지 않은 피자도 한 가지 경우로 세는 것이다.

2.2.2부분집합은 몇 개일까

처음 질문은 \(U\)의 부분집합의 개수를 묻는다. 부분집합을 하나 만드는 일은 원소 하나하나에 대해 '넣는다' 또는 '뺀다'를 정하는 일이다. 치즈를 넣을지 정하는 방법이 2가지, 그 각각에 대해 버섯을 넣을지 정하는 방법이 2가지이다. 따라서 곱의 법칙에 따라 원소가 4개이면 \(2 \times 2 \times 2 \times 2 = 16\)가지이다.

그림 1의 슬라이더로 \(n\)을 하나씩 늘려 보면, 원소 하나가 늘 때마다 부분집합의 수가 두 배가 된다. 새 원소를 넣은 쪽과 뺀 쪽으로 기존의 부분집합이 하나씩 복사되기 때문이다.

2.2.3예제 풀이

원소마다 넣을지 뺄지를 정한다고 생각하자. 1과 2는 반드시 넣으므로 선택이 1가지씩이고, 5는 반드시 빼므로 역시 1가지이다. 남은 3과 4만 넣거나 뺄 수 있으므로 \(2 \times 2 = 4\)가지이다.

즉 정해진 원소를 빼고 남은 원소 2개로 만든 집합 \(\{3, 4\}\)의 부분집합의 개수 \(2^2 = 4\)와 같다. 직접 쓰면 \(\{1, 2\}\), \(\{1, 2, 3\}\), \(\{1, 2, 4\}\), \(\{1, 2, 3, 4\}\)로 정말 4개이다.

원소가 \(n\)개인 집합에서 \(k\)개의 원소를 반드시 넣거나 반드시 빼기로 하면, 남은 \(n - k\)개만 자유롭게 고를 수 있으므로 \(2^{n-k}\)개가 된다. 아래 탐구 카드에서 벤 다이어그램과 부분집합 세기를 직접 해 보자.

1. '\(\varnothing\)의 모든 원소가 \(A\)에 속한다'는 문장은 확인할 원소가 하나도 없으므로 거짓이 될 수 없다. 반례를 찾을 수 없는 명제는 참으로 본다.