멱집합

집합론에서 멱집합(冪集合, 영어: power set)은 주어진 집합의 모든 부분 집합들로 구성된 집합이다.

정의 편집

집합 $S$ 의 멱집합 ${\mathcal {P}}(S)$ 또는 $2^{S}$ 는 $S$ 의 모든 부분 집합들로 구성된 집합이다. 즉, 이는 다음과 같다.

{\mathcal {P}}(S)=\{A\colon A\subseteq S\}

성질 편집

집합론적 성질 편집

집합 $S$ 의 멱집합 ${\mathcal {P}}(S)$ 의 크기는

|{\mathcal {P}}(S)|=2^{|S|}

이다. 여기서 $|S|$ 는 $S$ 의 크기를 나타내며, $2^{|S|}$ 는 기수의 거듭제곱을 나타낸다. 만약 $S$ 가 유한 집합일 경우, $|S|$ 는 ( $S$ 의 원소 개수를 나타내는) 자연수이며, 기수의 거듭제곱 연산은 자연수의 거듭제곱 연산과 일치한다. 특히, 유한 집합의 멱집합은 유한 집합이다.

집합 $S$ 의 멱집합 ${\mathcal {P}}(S)$ 의 크기는 항상 원래 집합 $S$ 의 크기보다 크다. 즉,

|{\mathcal {P}}(S)|=2^{|S|}>|S|

이다. 이를 칸토어의 정리라고 한다. 특히, 무한 집합의 멱집합은 항상 비가산 집합이다. 선택 공리를 가정할 경우, 임의의 주어진 기수 $\kappa$ 에 대하여, 그보다 큰 최소의 기수 $\kappa ^{+}$ 를 찾을 수 있으며, 이 경우 위 칸토어의 정리는 다음과 같이 쓸 수 있다.

|{\mathcal {P}}(S)|=2^{|S|}\geq |S|^{+}

만약 $S$ 가 가산 무한 집합일 경우 (즉, $|S|=\aleph _{0}$ 일 경우), 위 부등식을 등식으로 바꿔 얻는 명제를 연속체 가설이라고 한다. 이는 선택 공리를 추가한 체르멜로-프렝켈 집합론과 독립적이다. 즉, 만약 선택 공리를 추가한 체르멜로-프렝켈 집합론이 무모순적 이론일 경우, 연속체 가설과 그 부정은 모두 이 이론에서 증명될 수 없으며, 이 이론은 연속체 가설을 만족시키는 모형과 그렇지 않은 모형을 동시에 갖는다.

순서론적 성질 편집

집합 $S$ 의 멱집합 ${\mathcal {P}}(S)$ 는 부분 집합 관계 $\subseteq$ 에 대하여 완비 불 대수 $({\mathcal {P}}(S),\subseteq )$ 를 이룬다. 최소 원소는 공집합 $\varnothing \in {\mathcal {P}}(S)$ , 최대 원소는 원래의 집합 $S\in {\mathcal {P}}(S)$ , 이음은 합집합 $\cup$ , 만남은 교집합 $\cap$ 이다. 또한, 각 ${\mathcal {A}}\subseteq {\mathcal {P}}(S)$ 의 상한은 합집합