멱집합

주어진 집합의 모든 부분집합을 원소로 가지는 집합. 즉, 다음과 같이 정의되는 집합이다.

세 여성, 폰은정, 박근혜, 혜정이가 있다고 가정하자. 이들이 톡방을 만드는 것은 멱집합에 해당한다.

$C = {text{폰은정}, text{박근혜}, text{혜정이}}$

$P(C) = {varnothing, {text{폰은정}}, {text{박근혜}}, {text{혜정이}}, {text{폰은정}, text{박근혜}}, {text{폰은정}, text{혜정이}}, {text{박근혜}, text{혜정이}}, {text{폰은정}, text{박근혜}, text{혜정이}}}$

$|P(C)| = 2^{|C|} = 2^3 = 8$

ZFC에서는 멱집합 공리(axiom of power set)를 통해 멱집합의 존재성을 보장한다. 보통 ZFC에서 철저하게 subset이나 succ을 위주로 명백한 집합을 정의하는 것과 다르게 다소 급격해(?) 보일 수 있는 공리. 다만 멱집합이 없으면 집합론에서 대부분의 정리가 사실상 쓰레기이기 때문에 필수적으로 필요하다. 생각보다 많은 object들이 멱집합으로 만들어지는 편.

집합 문서에 써있듯이 어떤 원소가 집합에 포함되는지는 포함되느냐($in$) 포함되지 않느냐($notin$) 두 가지 경우의 수만이 존재한다. 만약 크기 $n$짜리 유한집합 $A$의 모든 원소 $x$에 대해 특정 집합에 포함 여부를 기준으로 조건을 형성하면 이는 $A$의 모든 부분집합을 유일하게 결정하게 되고, 그 경우의 수는 각 원소마다 2가지이므로 총 $2^n$개가 된다.

멱집합 그 자체로 subset relation에 대해 poset을 이루기 때문에 맨날 집합론이나 lattice theory 초장에 멱집합 얘기가 나온다.

물론 멱집합의 모든 부분집합은 poset이지만 아무래도 멱집합이 하세 다이어그램으로 그렸을 때 가장 예쁘장하게(?) 나오기 때문인 듯. 특히 크기 8짜리 멱집합 다이어그램이 가장 자주 나온다. 집합론 시간에 졸지 않았다면 거의 외울 수 있을 수준.