집합의 기초 개념 (4) - 멱집합

집합의 개념이 단순한 원소들의 모임에서 출발하듯, 집합 간의 관계, 조작, 그리고 집합으로부터 파생되는 구조들은 논리적 사고의 기반이 됩니다. 이 글에서는 집합론의 핵심 개념 중 하나인 멱집합(Power Set)의 개념과, 그 크기를 설명하는 고전적인 정리에 대해 살펴보겠습니다.

---

멱집합

 

• 어떤 집합 A가 주어졌을 때, A의 멱집합(Power Set)이란 A의 모든 부분집합들의 집합을 의미합니다.
• 다시 말해, 멱집합은 집합 A로부터 구성할 수 있는 가능한 모든 조합의 집합들을 원소로 가진 새로운 집합입니다.
• 이러한 멱집합은 보통 P(A)로 표기합니다.

---

예를 들어, 집합 A={1, 2}라면, 그 멱집합은 다음과 같습니다.

P(A)={∅, {1}, {2}, {1, 2}}

---

Axiom of Power Set

• 공리적 집합론에서는 모든 집합의 존재를 자명하게 받아들이지 않습니다.
• 특히, 멱집합의 존재는 단순한 정의만으로는 보장되지 않으며, 이를 위해 별도의 공리가 필요합니다.
• 이를 멱집합 공리(Axiom of Power Set)라 하며, 다음과 같이 서술됩니다.

Axiom of Power Set

모든 집합 A에 대하여, A의 모든 부분집합들을 원소로 가지는 집합 P(A)가 존재합니다.

이 공리는 Zermelo-Fraenkel 집합론(ZF)의 기본 구성 요소 중 하나로, 집합의 구조와 위계를 논리적으로 구성하는 데 필수적입니다.

---

멱집합의 크기

멱집합의 이름이 'power set'인 이유는 바로 그 원소의 개수와 관련된 다음의 정리에 있습니다.

정리. 집합 A가 n개의 원소로 구성되어 있다면, 그 멱집합 P(A)는 정확히 2ⁿ개의 원소(부분집합)를 가집니다.

증명:

1. 기저 사례: 집합 A가 공집합일 때(A=∅), 부분집합은 오직 하나— 바로 공집합 자신 —뿐입니다.
   따라서 P(∅)은 2⁰ = 1개의 원소를 가집니다.
2. 일반적 경우: 집합 A={a₁, a₂, …, a_n}로 가정합시다.
   각 원소 a_k​에 대해, 하나의 부분집합은 해당 원소를 포함할 수도 있고, 포함하지 않을 수도 있습니다.
3. 이로 인해 부분집합 하나를 구성하는 문제는 n개의 빈 칸(각 칸은 0 또는 1로 채워짐)을 채우는 이진 선택 문제로 환원됩니다.
   1은 해당 원소가 부분집합에 포함됨을, 0은 포함되지 않음을 나타냅니다.
4. 이진수의 조합이 총 2ⁿ개 존재하므로, A의 부분집합의 수는 정확히 2ⁿ개 입니다.

---

예를 들어, 집합 A={1, 2}라면

∅ = { 1₀, 2₀ }
{1} = { 1₁, 2₀ }
{2} = { 1₀, 2₁ }
{1, 2} = { 1₁, 2₁ }

라는 방식으로 증명을 완성하는 것입니다.

2진법에 익숙하다면 이 증명을 이해하기에 한결 수월할 것입니다.