집합론 에서 멱집합 (冪集合, 영어 : power set )은 주어진 집합 의 모든 부분 집합 들로 구성된 집합이다.
하세 도형 으로 표현한
{
x
,
y
,
z
}
{\displaystyle \{x,y,z\}}
의 멱집합
집합
X
{\displaystyle X}
의 멱집합
P
(
X
)
{\displaystyle {\mathcal {P}}(X)}
또는
2
X
{\displaystyle 2^{X}}
는
X
{\displaystyle X}
의 모든 부분 집합 들로 구성된 집합이다. 즉, 이는 다음과 같다.
P
(
X
)
=
{
S
|
S
⊆
X
}
=
{
S
|
∀
s
∈
S
:
s
∈
X
}
{\displaystyle {\begin{aligned}{\mathcal {P}}(X)&=\{S|S\subseteq X\}\\&=\{S|\forall s\in S\colon s\in X\}\end{aligned}}}
선택 공리 를 추가한 체르멜로-프렝켈 집합론 (ZFC)의 멱집합 공리 (영어 : axiom of power set )는 다음과 같은 명제이다.
임의의 집합
X
{\displaystyle X}
에 대하여, 다음 조건을 만족시키는 집합
Y
{\displaystyle {\mathcal {Y}}}
가 존재한다.
임의의 집합
S
{\displaystyle S}
에 대하여, 만약 (임의의
s
∈
S
{\displaystyle s\in S}
에 대하여
s
∈
X
{\displaystyle s\in X}
)라면,
S
∈
Y
{\displaystyle S\in {\mathcal {Y}}}
이다.
이는 ZFC의 공리 이며, 특히 참이다. 멱집합 공리 및 다른 ZFC 공리들로부터, 임의의 집합
X
{\displaystyle X}
의 멱집합의 존재를 다음과 같이 증명할 수 있다. 위 조건을 만족시키는 집합
Y
{\displaystyle {\mathcal {Y}}}
를 잡자. 그렇다면, 분류 공리꼴에 따라, 다음과 같은 집합을 정의할 수 있다.
Y
′
=
{
S
∈
Y
|
∀
s
∈
S
:
s
∈
X
}
{\displaystyle {\mathcal {Y}}'=\{S\in {\mathcal {Y}}|\forall s\in S\colon s\in X\}}
또한,
Y
{\displaystyle {\mathcal {Y}}}
의 선택에 따라,
Y
′
{\displaystyle {\mathcal {Y}}'}
는
X
{\displaystyle X}
의 멱집합을 이룬다. 확장 공리에 따라, 임의의 집합의 멱집합은 유일하다.
집합
X
{\displaystyle X}
의 멱집합
P
(
X
)
{\displaystyle {\mathcal {P}}(X)}
의 크기 는
|
P
(
X
)
|
=
2
|
X
|
{\displaystyle |{\mathcal {P}}(X)|=2^{|X|}}
이다. 여기서
|
X
|
{\displaystyle |X|}
는
X
{\displaystyle X}
의 크기를 나타내며,
2
|
X
|
{\displaystyle 2^{|X|}}
는 기수 의 거듭제곱을 나타낸다. 만약
X
{\displaystyle X}
가 유한 집합 일 경우,
|
X
|
{\displaystyle |X|}
는 (
X
{\displaystyle X}
의 원소 개수를 나타내는) 자연수이며, 기수의 거듭제곱 연산은 자연수의 거듭제곱 연산과 일치한다. 특히, 유한 집합의 멱집합은 유한 집합이다.
다음과 같은 부등식이 성립한다.
|
P
(
X
)
|
=
2
|
X
|
≥
|
X
|
+
>
|
X
|
{\displaystyle |{\mathcal {P}}(X)|=2^{|X|}\geq |X|^{+}>|X|}
여기서
|
X
|
+
{\displaystyle |X|^{+}}
는
|
X
|
{\displaystyle |X|}
보다 큰 최소의 기수이다 (선택 공리 를 가정하면 이는 항상 존재한다). 이를 칸토어 정리 라고 한다. 이에 따라, 멱집합
P
(
X
)
{\displaystyle {\mathcal {P}}(X)}
의 크기는 항상 원래 집합
X
{\displaystyle X}
의 크기보다 크다. 특히,
X
{\displaystyle X}
가 가산 무한 집합 인 경우
2
ℵ
0
≥
ℵ
1
{\displaystyle 2^{\aleph _{0}}\geq \aleph _{1}}
이다. 명제
2
ℵ
0
=
ℵ
1
{\displaystyle 2^{\aleph _{0}}=\aleph _{1}}
는 연속체 가설 이라고 부른다. 연속체 가설과 그 부정 모두 ZFC 에서 증명할 수 없다.
집합
X
{\displaystyle X}
의 멱집합은 부분 집합 관계에 대하여 완비 불 대수
(
P
(
X
)
,
⊆
)
{\displaystyle ({\mathcal {P}}(X),\subseteq )}
를 이룬다. 최소 원소 는 공집합
∅
∈
P
(
X
)
{\displaystyle \varnothing \in {\mathcal {P}}(X)}
, 최대 원소 는 원래의 집합
X
∈
P
(
X
)
{\displaystyle X\in {\mathcal {P}}(X)}
, 이음은 합집합
∪
{\displaystyle \cup }
, 만남은 교집합
∩
{\displaystyle \cap }
이다. 또한, 임의의 부분 집합
S
⊆
P
(
X
)
{\displaystyle {\mathcal {S}}\subseteq {\mathcal {P}}(X)}
의 상한 은 합집합
⋃
S
=
⋃
S
∈
S
S
∈
P
(
X
)
{\displaystyle \bigcup {\mathcal {S}}=\bigcup _{S\in {\mathcal {S}}}S\in {\mathcal {P}}(X)}
으로 주어지며, 하한 은 교집합
⋂
S
=
⋂
S
∈
S
S
∈
P
(
X
)
{\displaystyle \bigcap {\mathcal {S}}=\bigcap _{S\in {\mathcal {S}}}S\in {\mathcal {P}}(X)}
으로 주어진다 (
⋂
∅
=
X
{\displaystyle \textstyle \bigcap \varnothing =X}
).
멱집합과 상 은 집합 의 범주
Set
{\displaystyle \operatorname {Set} }
위의 함자
Set
→
Set
{\displaystyle \operatorname {Set} \to \operatorname {Set} }
X
→
P
(
X
)
{\displaystyle X\to {\mathcal {P}}(X)}
(
f
:
X
→
Y
)
↦
(
S
↦
f
(
S
)
)
{\displaystyle (f\colon X\to Y)\mapsto (S\mapsto f(S))}
를 이룬다. 멱집합과 원상 은 함자
Set
op
→
Set
{\displaystyle \operatorname {Set} ^{\operatorname {op} }\to \operatorname {Set} }
X
→
P
(
X
)
{\displaystyle X\to {\mathcal {P}}(X)}
(
f
:
X
→
Y
)
↦
(
T
↦
f
−
1
(
T
)
)
{\displaystyle (f\colon X\to Y)\mapsto (T\mapsto f^{-1}(T))}
를 이룬다.
공집합 의 멱집합은 공집합을 원소로 가지는 한원소 집합이다.
P
(
∅
)
=
{
∅
}
{\displaystyle {\mathcal {P}}(\varnothing )=\{\varnothing \}}
한원소 집합
{
x
}
{\displaystyle \{x\}}
은 공집합과 자기 자신을 부분 집합으로 하므로 그 멱집합은
P
(
{
x
}
)
=
{
∅
,
{
x
}
}
{\displaystyle {\mathcal {P}}(\{x\})=\{\varnothing ,\{x\}\}}
이다.
두원소 집합
{
a
,
b
}
{\displaystyle \{a,b\}}
의 부분 집합들은 정확히 다음과 같다.
∅
{\displaystyle \varnothing }
{
a
}
{\displaystyle \{a\}}
{
b
}
{\displaystyle \{b\}}
{
a
,
b
}
{\displaystyle \{a,b\}}
따라서 그 멱집합은
P
(
{
a
,
b
}
)
=
{
∅
,
{
a
}
,
{
b
}
,
{
a
,
b
}
}
{\displaystyle {\mathcal {P}}(\{a,b\})=\{\varnothing ,\{a\},\{b\},\{a,b\}\}}
이다.
세원소 집합
{
a
,
b
,
c
}
{\displaystyle \{a,b,c\}}
의 부분 집합들은 정확히 다음과 같다.
∅
{\displaystyle \varnothing }
{
a
}
{\displaystyle \{a\}}
{
b
}
{\displaystyle \{b\}}
{
c
}
{\displaystyle \{c\}}
{
a
,
b
}
{\displaystyle \{a,b\}}
{
a
,
c
}
{\displaystyle \{a,c\}}
{
b
,
c
}
{\displaystyle \{b,c\}}
{
a
,
b
,
c
}
{\displaystyle \{a,b,c\}}
따라서 그 멱집합은
P
(
{
a
,
b
,
c
}
)
=
{
∅
,
{
a
}
,
{
b
}
,
{
c
}
,
{
a
,
b
}
,
{
a
,
c
}
,
{
b
,
c
}
,
{
a
,
b
,
c
}
}
{\displaystyle {\mathcal {P}}(\{a,b,c\})=\{\varnothing ,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}}
이다.