맨위로가기

멱집합

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

멱집합은 집합 X의 모든 부분 집합으로 구성된 집합으로, 𝒫(X) 또는 2X로 표기한다. 멱집합 공리는 임의의 집합 X에 대해 X의 모든 부분 집합을 포함하는 집합 𝒴가 존재한다는 것을 ZFC 공리로 정의하며, 멱집합의 크기는 원래 집합의 크기보다 항상 크다. 멱집합은 포함 관계에 따라 완비 불 대수를 이루며, 합집합, 교집합, 여집합 연산과 함께 불 대수의 전형적인 예로 볼 수 있다. 멱집합과 상은 집합의 범주 위의 함자를 이루며, 멱집합의 크기는 2|X|로 계산된다. 멱집합은 이항 정리와 관련이 있으며, 조합의 수와 밀접한 관계를 갖는다. 멱집합은 순서론적 성질과 함자성을 가지며, 제한된 기수를 갖는 부분집합과 멱 대상, 그리고 함자와 수량자와의 관계를 갖는다.

2. 정의

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

:\begin{align}\mathcal P(X)

& =\{S|S\subseteq X\} \\

& =\{S|\forall s\in S\colon s\in X\}

\end{align}



선택 공리를 추가한 체르멜로-프렝켈 집합론(ZFC)의 '''멱집합 공리'''(axiom of power set영어)는 임의의 집합 X에 대하여, X의 모든 부분 집합을 원소로 포함하는 집합 \mathcal Y가 존재한다는 명제이다. 구체적으로는 다음과 같다.


  • 임의의 집합 X에 대하여, 다음 조건을 만족시키는 집합 \mathcal Y가 존재한다.
  • * 임의의 집합 S에 대하여, 만약 (임의의 s\in S에 대하여 s\in X)라면, S\in\mathcal Y이다.


멱집합 공리는 ZFC의 공리 중 하나이며, 이 공리와 다른 ZFC 공리들을 통해 임의의 집합 X의 멱집합의 존재를 증명할 수 있다. 위 조건을 만족시키는 집합 \mathcal Y에 대해 분류 공리꼴을 적용하면, 다음과 같은 집합을 정의할 수 있다.

:\mathcal Y'=\{S\in\mathcal Y|\forall s\in S\colon s\in X\}

이때 \mathcal Y'는 X의 멱집합이 되며, 확장 공리에 따라 임의의 집합의 멱집합은 유일하다.

예를 들어, 집합 S = \{x, y, z\}의 모든 부분 집합은 다음과 같다.

  • \varnothing (공집합)
  • \{x\}
  • \{y\}
  • \{z\}
  • \{x, y\}
  • \{x, z\}
  • \{y, z\}
  • \{x, y, z\}


따라서 집합 S의 멱집합은 다음과 같다.

:\mathcal P(S) = \{\varnothing, \{x\}, \{y\}, \{z\}, \{x, y\}, \{x, z\}, \{y, z\}, \{x, y, z\}\}

다른 예시는 다음과 같다.

  • \mathcal P(\varnothing) = \{\varnothing\}
  • \mathcal P(\{a\}) = \{\varnothing, \{a\}\}
  • \mathcal P(\{x,y\}) = \{\varnothing, \{x\}, \{y\}, \{x,y\}\}
  • \mathcal P(\{1,2,3\}) = \{\varnothing, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}


공집합의 멱집합은 공집합을 유일한 원소로 갖는 일원 집합이며, 공집합 자체와는 다르다.

정의에 따라 다음이 성립한다.

: A \in \mathcal{P}(S) \iff A \subseteq S

3. 성질

멱집합은 여러 중요한 수학적 성질을 가진다.

우선, 집합 X의 멱집합 \mathcal P(X)의 크기는 항상 원래 집합 X의 크기보다 엄격하게 크다. 이를 칸토어 정리라고 하며, 무한 집합의 경우에도 성립한다(칸토어의 대각선 논법). 만약 X가 유한 집합이라면, 멱집합의 크기는 |\mathcal P(X)|=2^

이다. (자세한 내용은 크기 참조)

멱집합 \mathcal P(X)는 부분 집합 관계 \subseteq를 순서 관계로 가질 때 완비 불 대수를 이룬다. 이는 합집합과 교집합 연산을 통해 격자 구조를 형성하며, 특히 최소 원소(공집합\varnothing)와 최대 원소(원래 집합 X)를 포함하는 유계 격자이다. (자세한 내용은 순서론적 성질 참조)

또한, 멱집합 연산은 집합들의 범주\operatorname{Set}에서 자기 자신으로 가는 함자를 정의한다. 함수의 상을 이용한 공변 함자와 원상을 이용한 반변 함자가 존재한다. (자세한 내용은 함자성 참조)

대수적으로, 집합 S의 멱집합은 합집합, 교집합, 여집합 연산에 대해 시그마 대수를 형성하며, 불 대수의 대표적인 예시가 된다. 모든 유한 불 대수는 어떤 유한 집합의 멱집합으로 구성된 불 대수와 동형이라는 사실이 알려져 있다(스톤의 표현 정리).

멱집합은 다른 대수 구조도 가진다. 대칭 차이 연산(\Delta)에 대해서는 아벨 군을 이루는데, 이때 항등원은 공집합 \varnothing이고 모든 원소(부분집합)는 자기 자신이 역원이다. 또한, 교집합 연산(\cap)에 대해서는 가환모노이드를 이루며, 이때 항등원은 전체 집합 S이다. 이 두 연산(대칭 차이와 교집합)을 함께 고려하면, 멱집합은 분배 법칙이 성립하는 불 링 구조를 형성한다.

멱집합 \mathcal P(S)는 집합 S에서 두 원소 집합 \{0, 1\}로 가는 함수들의 집합과 자연스럽게 대응될 수 있다. 구체적으로, S의 각 부분집합 A는 그 지시 함수\chi_A: S \to \{0, 1\} (원소가 A에 속하면 1, 아니면 0을 반환)와 유일하게 대응된다.[2] 이러한 일대일 대응 관계 때문에 멱집합을 2^S (또는 \{0, 1\}^S)로 표기하기도 하며, 이는 멱집합의 크기가 2^

가 되는 이유를 설명해 준다.

마지막으로, 멱집합은 조합론의 이항 정리와도 밀접한 관련이 있다. 크기가 n인 집합 S에서 k개의 원소를 가지는 부분집합의 개수는 조합의 수, 즉 이항 계수\binom{n}{k}와 같다. 멱집합은 모든 크기의 부분집합들을 포함하므로, 그 총 원소의 개수는 모든 k(0 \le k \le n)에 대한 이항 계수의 합과 같다:

\left|\mathcal P(S) \right| = \sum_{k=0}^

\binom

{k} = 2^



이는 이항 정리 (1+1)^n = \sum_{k=0}^{n} \binom{n}{k} 1^k 1^{n-k}의 결과와 일치한다.

3. 1. 크기

집합 X의 멱집합 \mathcal P(X)의 크기는 다음과 같이 정의된다.

:|\mathcal P(X)|=2^



여기서 |X|는 X의 크기를 나타내며, 2^

는 기수의 거듭제곱을 의미한다. 만약 X가 유한 집합이라면, |X|는 X의 원소 개수를 나타내는 자연수이고, 기수의 거듭제곱은 자연수의 거듭제곱과 같다. 따라서 유한 집합의 멱집합은 항상 유한 집합이다. 예를 들어, 원소 3개짜리 집합의 멱집합은 2^3=8개의 원소를 가진다.

칸토어 정리에 따르면, 어떤 집합의 멱집합의 크기는 항상 원래 집합의 크기보다 크다. 이를 수식으로 표현하면 다음과 같다.

:|\mathcal P(X)|=2^

\ge|X|^+>|X|

여기서 |X|^+는 |X|보다 큰 가장 작은 기수를 나타낸다 (선택 공리를 가정하면 항상 존재한다). 이 정리는 칸토어의 대각선 논법을 사용하여 증명할 수 있다.

칸토어 정리에 따라, 멱집합 \mathcal P(X)의 크기는 항상 원래 집합 X의 크기보다 크다. 특히, X가 가산 무한 집합(예: 자연수 전체의 집합 \mathbb{N})인 경우, 그 크기는 |\mathbb{N}| = \aleph_0 (알레프 0)으로 표기하며, 멱집합의 크기는 |\mathcal P(\mathbb{N})| = 2^{\aleph_0}이다. 칸토어 정리에 의해 2^{\aleph_0} > \aleph_0이며, 구체적으로 2^{\aleph_0}\ge\aleph_1이 성립한다. 여기서 \aleph_1은 \aleph_0보다 큰 가장 작은 기수이다. 2^{\aleph_0}=\aleph_1이라는 가설을 연속체 가설이라고 부르는데, 이 가설과 그 부정은 모두 현재 수학 공리계(ZFC) 내에서는 증명하거나 반증할 수 없는 것으로 알려져 있다.

집합 S의 멱집합 \mathcal P(S)는 S의 각 원소가 특정 부분집합에 속하는지 여부를 나타내는 함수와 자연스럽게 대응될 수 있다. 구체적으로, S의 부분집합 A는 각 원소 s \in S에 대해 s \in A이면 1, s \notin A이면 0의 값을 갖는 지시 함수\chi_A: S \to \{0, 1\}와 유일하게 대응된다.[2] 이 때문에 멱집합 \mathcal P(S)와 S에서 \{0, 1\}로 가는 모든 함수들의 집합 \{0, 1\}^S 사이에는 일대일 대응 관계가 성립한다. 이는 멱집합의 크기가 |\mathcal P(S)| = |\{0, 1\}^S| = 2^

가 되는 이유를 설명해 준다.

3. 2. 순서론적 성질

집합 X의 멱집합 \mathcal P(X)는 부분 집합 관계 \subseteq에 대하여 완비 불 대수(\mathcal P(X),\subseteq)를 이룬다. 이 순서 구조에서 최소 원소는 공집합\varnothing이고, 최대 원소는 원래의 집합 X이다. 또한, 두 부분 집합의 이음(join)은 합집합\cup으로, 만남(meet)은 교집합\cap으로 정의된다.

멱집합은 포함 관계 \subseteq를 순서로 하는 순서 집합이며, 이는 완비 격자의 구조를 가진다. 즉, 임의의 부분 집합족 \mathcal S\subseteq\mathcal P(X)에 대해, 그 상한은 합집합

:\sup(\mathcal S) = \bigcup\mathcal S=\bigcup_{S\in\mathcal S}S\in\mathcal P(X)

으로 주어지며, 하한은 교집합

:\inf(\mathcal S) = \bigcap\mathcal S=\bigcap_{S\in\mathcal S}S\in\mathcal P(X)

으로 주어진다. 특히, 공집합족 \mathcal S = \varnothing의 경우에도 상한은 \sup(\varnothing) = \varnothing, 하한은 \inf(\varnothing) = X로 멱집합 \mathcal P(X) 안에 존재한다.

포함 관계 \subseteq를 순서로 하는 순서 집합 (\mathcal P(X), \subseteq) (여기서 \subseteq는 집합이 일치하는 경우도 포함)에 순서 동형인 순서 집합은 '''simplex-like Poset|단순체 유사 반순서 집합영어'''이라고도 불린다.

또한, 멱집합 \mathcal P(X)에 포함 관계와 반대 순서 \subset^{\mathrm{opp}}

:A \subset^{\mathrm{opp}} B \iff A \supset B

를 부여한 순서 집합 (\mathcal P(X), \subset^{\mathrm{opp}})는 원래의 순서 집합 (\mathcal P(X), \subset)에 순서 동형이다. 이 동형 관계는 각 부분 집합 A를 그 여집합A^c = X\smallsetminus A으로 대응시키는 조작을 통해 이루어진다.

:(\mathcal P(X),\subset^{\mathrm{opp}}) \ni A \ \stackrel{\simeq}{\longmapsto}\ A^c = X\smallsetminus A \in (\mathcal P(X),\subset)

이 대응 관계를 통해 집합의 합집합과 교집합이 서로 바뀌는 성질(드 모르간 법칙) 등을 확인할 수 있다.

3. 3. 함자성

멱집합과 상은 집합의 범주\operatorname{Set} 위의 함자

:\operatorname{Set}\to\operatorname{Set}

:X\to\mathcal P(X)

:(f\colon X\to Y)\mapsto(S\mapsto f(S))

를 이룬다. 여기서 함수 f는 집합 S \subseteq X를 그 상 f(S) \subseteq Y로 대응시킨다. 이를 공변 멱집합 함자 라고도 한다.[1]

멱집합과 원상은 함자

:\operatorname{Set}^{\operatorname{op}}\to\operatorname{Set}

:X\to\mathcal P(X)

:(f\colon X\to Y)\mapsto(T\mapsto f^{-1}(T))

를 이룬다. 여기서 함수 f는 집합 T \subseteq Y를 그 원상 f^{-1}(T) \subseteq X로 대응시킨다. 이를 반변 멱집합 함자 라고도 한다.[1] 멱집합을 S에서 두 원소 집합 \{0, 1\}으로 가는 함수의 집합으로 정의하면, 이는 자연 동형 \overline{\mathsf{P}} \cong \text{Set}(-,2)를 정의한다.[1]

범주론에서 전칭 기호는 집합 간 함수의 역상 함자의 오른쪽 수반으로 이해될 수 있으며, 존재 기호는 왼쪽 수반이다.

4. 표기법

집합 S의 멱집합은 '멱(冪)'을 뜻하는 power|파워영어에서 이름을 따왔으며, 다양한 기호로 표기된다. 가장 일반적인 표기법은 \mathcal P(S) 또는 \mathfrak P(S)이다. 이 외에도 다음과 같은 표기법들이 사용된다.


  • \mathfrak{pow}(S)
  • \mathrm{Power}(S)
  • \Pi(S)
  • \mathbb P(S)
  • \wp(S) (바이어슈트라스 타원 함수의 기호와 유사함)
  • 2^S


표기법 2^S는 집합론에서 X^Y가 Y에서 X로 가는 모든 함수의 집합을 나타내는 관례에서 유래했다. 집합 S의 각 부분집합 A는 S의 원소가 A에 속하는지 여부를 나타내는 지시 함수 I_A: S \to \{0, 1\}와 일대일 대응 관계에 있다. 즉, S의 멱집합 \mathcal P(S)는 S에서 \{0, 1\}로 가는 모든 함수의 집합과 집합론적으로 동일하게 간주될 수 있다. 집합 \{0, 1\}은 숫자 2로 표현될 수 있으므로(예: 폰 노이만 순서수 정의), S에서 \{0, 1\}로 가는 모든 함수의 집합을 \{0, 1\}^S 또는 간단히 2^S로 표기하며, 이는 멱집합 \mathcal P(S)를 나타내는 표기법으로도 사용된다. 이 표기법은 유한 집합 S의 원소 개수가 n일 때 멱집합의 원소 개수가 |\mathcal P(S)| = 2^n = |2^S|라는 사실과도 일관된다.

5. 예

공집합의 멱집합은 공집합 \varnothing을 원소로 가지는 한원소 집합이다.

:\mathcal P(\varnothing)=\{\varnothing\}

한원소 집합 \{x\}의 멱집합은 공집합 \varnothing과 자기 자신 \{x\}를 원소로 가진다.

:\mathcal P(\{x\})=\{\varnothing,\{x\}\}

원소가 두 개인 집합 \{a,b\}의 부분 집합은 \varnothing, \{a\}, \{b\}, \{a,b\}이다. 따라서 그 멱집합은 다음과 같다.

:\mathcal P(\{a,b\})=\{\varnothing,\{a\},\{b\},\{a,b\}\}

원소가 세 개인 집합 \{a,b,c\}의 부분 집합은 \varnothing, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\}이다. 따라서 그 멱집합은 다음과 같다.

:\mathcal P(\{a,b,c\})=\{\varnothing,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}

6. 구조

집합 S의 멱집합 \mathcal P(S)는 그 자체로 다양한 수학적 구조를 형성한다.

멱집합은 부분 집합 관계 \subseteq를 통해 순서 집합의 구조를 가지며, 특히 완비 격자를 이룬다.

또한, 집합 연산들과 함께 대수적 구조를 형성한다. 합집합, 교집합, 여집합 연산에 대해서는 불 대수의 대표적인 예시가 된다. 모든 유한 불 대수는 어떤 유한 집합 멱집합의 불 대수와 동형이며, 스톤의 표현 정리에 따르면 모든 불 대수는 멱집합 불 대수의 부분 대수로 나타낼 수 있다.

대칭차 연산에 대해서는 아벨 군을 이루며, 대칭차와 교집합 연산을 함께 고려하면 불 링 구조를 가진다.

6. 1. 포함 관계에 의한 순서

집합 X의 멱집합 \mathcal P(X)는 부분 집합 관계 \subseteq를 기준으로 순서 집합을 이룬다. 이 순서 집합 (\mathcal P(X),\subseteq)는 다음과 같은 특징을 가진다.

  • 완비 불 대수: 멱집합은 부분 집합 관계에 대해 완비 불 대수 구조를 가진다.
  • 최소 원소는 공집합 \varnothing이다.
  • 최대 원소는 원래의 집합 X이다.
  • 두 부분 집합의 이음 (join)은 합집합 \cup이다.
  • 두 부분 집합의 만남 (meet)은 교집합 \cap이다.
  • 상한과 하한: 멱집합의 임의의 부분 집합족 \mathcal S\subseteq\mathcal P(X)에 대해,
  • 상한 (supremum)은 합집합 \bigcup\mathcal S=\bigcup_{S\in\mathcal S}S이다.
  • 하한 (infimum)은 교집합 \bigcap\mathcal S=\bigcap_{S\in\mathcal S}S이다.
  • 만약 \mathcal S가 공집합 \varnothing이면, 그 하한은 \bigcap\varnothing=X로 정의된다.


예를 들어, 집합 S = \{x, y, z\}의 멱집합 \mathcal P(S)는 다음과 같은 원소들로 이루어진다.



\mathcal P(S) = \{ \varnothing, \{x\}, \{y\}, \{z\}, \{x, y\}, \{x, z\}, \{y, z\}, \{x, y, z\} \}



이 멱집합은 포함 관계 \subseteq에 따라 순서가 매겨진다. 예를 들어 \{x\} \subseteq \{x, y\} 와 같은 관계가 성립한다.

이처럼 멱집합과 포함 관계 \subseteq로 이루어진 순서 집합 (\mathcal P(S), \subseteq)과 순서 동형인 순서 집합을 단순체 유사 반순서 집합(simplex-like Poset영어)이라고 부르기도 한다. 이는 단순체의 조합론적 특징 중 하나를 나타낸다. (때로는 \mathcal P(S)에서 공집합을 제외한 순서 집합을 가리키기도 한다.)

또한, 멱집합 \mathcal P(S)에 포함 관계와 반대 순서 \supseteq (즉, A \supseteq B \iff A \subseteq^{\mathrm{opp}} B)를 부여한 순서 집합 (\mathcal P(S), \supseteq)는 원래의 순서 집합 (\mathcal P(S), \subseteq)과 순서 동형이다. 이 동형 관계는 각 부분 집합 A를 그 여집합 A^c = S\setminus A으로 대응시키는 함수를 통해 이루어진다.

:(\mathcal P(S),\supseteq) \ni A \ \stackrel{\simeq}{\longmapsto}\ A^c = S\smallsetminus A \in (\mathcal P(S),\subseteq)

이 대응 관계를 통해 합집합과 교집합 연산이 서로 뒤바뀌는 것을 확인할 수 있으며, 이는 드 모르간 법칙으로 알려진 쌍대성(duality)을 보여준다. 반면, 대칭차 연산은 이 대응에 의해 변하지 않는다(자기 쌍대성, self-duality).

순서 집합 (\mathcal P(S), \subseteq)의 부분 집합인 집합족 \mathfrak{M} \subset \mathcal P(S)이 주어졌을 때, 이 집합족의 합집합 \bigcup \mathfrak{M}과 교집합 \bigcap \mathfrak{M}은 각각 \mathfrak{M}의 상한과 하한이 된다.

:\sup(\mathfrak{M}) = \bigcup_{m\in\mathfrak{M}}m, \quad \inf(\mathfrak{M}) = \bigcap_{m\in\mathfrak{M}}m

특히, S의 두 부분 집합 A, B에 대해 이음(\vee)과 만남(\wedge) 연산을 다음과 같이 정의하면,

:A\vee B := \sup\{A,B\} = A\cup B

:A\wedge B := \inf\{A,B\} = A\cap B

멱집합 (\mathcal P(S), \wedge, \vee)는 완비 격자 구조를 이룬다. 완비 격자는 공집합이 아닌 부분 집합족에 대한 상한과 하한의 존재를 요구하지만, 멱집합의 격자에서는 공집합족 \mathfrak M = \varnothing에 대해서도 상한과 하한이 멱집합 \mathcal P(S) 안에 존재한다.

:\sup(\varnothing) = \varnothing,\quad \inf(\varnothing) = S

6. 2. 집합 대수계

멱집합에 정의된 다양한 집합 연산은 멱집합을 대수계로 취급하는 수단을 제공한다.

집합의 합집합 \cup이나 교집합 \cap은 교환 가능하고 결합적인 연산이므로, 멱집합 \mathcal P(S)는 이들 연산에 대해 각각 반군으로서의 구조를 가진다. 또한, 합집합에 관한 항등원은 공집합 \emptyset이고, 전체 집합 S가 교집합에 관한 항등원이 되므로, (\mathcal P(S), \cup, \emptyset)와 (\mathcal P(S), \cap, S)는 모노이드이다.

대칭차 \Delta 연산을 고려하면, (\mathcal P(S), \Delta)는 아벨 군을 형성한다. 이 군에서 항등원은 공집합 \emptyset이며, 각 집합은 자기 자신을 역원으로 가진다 (A \Delta A = \emptyset).

교집합 \cap 연산은 대칭차 \Delta 연산에 대해 분배적이다. 따라서 이 두 연산(\Delta, \cap)과 함께 멱집합을 고려하면 불 환을 형성한다.

또한, 멱집합 \mathcal P(S)는 합집합, 교집합, 여집합 연산과 함께 불 대수의 전형적인 예가 된다. 이를 대수계로 표현하면 (\mathcal P(S), \cap, \cup, ^\mathrm{c}, \varnothing, S)와 같다. 실제로, 모든 유한 불 대수는 어떤 유한 집합의 멱집합으로 만들어지는 불 대수와 동형임이 알려져 있다. 무한 불 대수의 경우에도, 모든 무한 불 대수는 멱집합 불 대수의 부분 대수로 나타낼 수 있다(스톤 표현 정리).

집합 X의 멱집합은 부분 집합 관계 \subseteq에 대하여 완비 불 대수 (\mathcal P(X),\subseteq)를 이룬다. 이 구조에서 최소 원소는 공집합 \varnothing, 최대 원소는 원래의 집합 X이며, 이음(상한)은 합집합 \cup, 만남(하한)은 교집합 \cap에 해당한다. 임의의 부분 집합족 \mathcal S\subseteq\mathcal P(X)의 상한은 합집합 \bigcup\mathcal S으로, 하한은 교집합 \bigcap\mathcal S으로 주어진다 (\textstyle\bigcap\varnothing=X).

7. 이항 정리와의 관계

이항 정리는 멱집합과 밀접한 관련이 있다. 어떤 집합에서 k개의 원소를 선택하는 조합은 k개의 원소로 이루어진 부분집합을 다른 방식으로 표현한 것이므로, 조합의 수인 \binom{n}{k}(이항 계수)는 n개의 원소를 가진 집합에서 k개의 원소를 가진 부분집합의 수이다. 다시 말해, n개의 원소를 가진 집합의 멱집합에 속하는 k개의 원소를 가진 집합의 수이다.

예를 들어, 세 개의 원소를 가진 집합의 멱집합은 다음과 같다.


  • \binom{3}{0} = 1개의 0개 원소를 가진 부분집합 (공집합)
  • \binom{3}{1} = 3개의 1개 원소를 가진 부분집합 (단일 집합 부분집합)
  • \binom{3}{2} = 3개의 2개 원소를 가진 부분집합
  • \binom{3}{3} = 1개의 3개 원소를 가진 부분집합 (원래 집합 자체)


이 관계를 사용하여, 다음 공식을 통해 멱집합의 크기 |2^S|를 계산할 수 있다.

\left|2^S \right | = \sum_{k=0}^

\binom

{k}

따라서, |S| = n이라고 가정하면, 다음 등식을 유추할 수 있다.

\left |2^S \right| = 2^n = \sum_{k=0}^{n} \binom{n}{k}

8. 재귀적 정의

만약 S가 유한 집합이라면, 멱집합 \mathcal{P}(S)는 다음과 같이 재귀적으로 정의될 수 있다.


  • 공집합 \emptyset의 멱집합은 공집합을 유일한 원소로 가지는 단일 집합이다. 즉, \mathcal{P}(\emptyset) = \{ \emptyset \}이다.
  • 공집합이 아닌 집합 S에 대해, e를 S의 임의의 한 원소라고 하고, T를 S에서 e를 제외한 상대 여집합(즉, T = S \setminus \{e\})이라고 하자. 이때 S의 멱집합은 T의 멱집합 \mathcal{P}(T)와, \mathcal{P}(T)에 속하는 각 집합 t에 원소 e를 추가하여 만든 집합 t \cup \{e\}들의 모임의 합집합이다. 이를 수식으로 표현하면 다음과 같다.

\mathcal{P}(S) = \mathcal{P}(T) \cup \{ t \cup \{e\} \mid t \in \mathcal{P}(T) \}

9. 제한된 기수를 갖는 부분집합

기수가 ''κ'' 이하인 집합 ''S''의 부분 집합 집합은 때때로 P''κ''(''S'') 또는 [''S'']''κ''로 표시되며, 기수가 ''κ''보다 엄격하게 작은 부분 집합의 집합은 P<''κ''(''S'') 또는 [''S'']<''κ''로 표시되기도 한다. 마찬가지로, ''S''의 공집합이 아닌 부분 집합의 집합은 P≥1(''S'') 또는 P+(''S'')로 표시될 수 있다.

10. 멱 대상

집합은 특별한 연산이나 정의하는 방정식이 없는 대수 구조로 볼 수 있다. 이런 관점에서 보면, 집합 ''X''의 멱집합을 ''X''의 부분 집합들의 모임으로 보는 생각은 대수적 구조나 대수의 부분 대수 개념으로 자연스럽게 확장될 수 있다.

포함 관계에 따라 정렬된 집합의 멱집합은 항상 완전 원자성을 가진 부울 대수이며, 모든 완전 원자 부울 대수는 어떤 집합의 모든 부분 집합들의 격자로 표현될 수 있다. 이를 임의의 대수로 일반화하면, 포함 관계에 따라 정렬된 대수의 부분 대수들의 집합은 항상 대수적 격자가 되며, 모든 대수적 격자는 어떤 대수의 부분 대수들의 격자로 나타낼 수 있다는 사실로 이어진다. 따라서 부분 대수는 부분 집합과 유사한 방식으로 작동한다고 볼 수 있다.

하지만 부분 집합이 갖는 중요한 속성 두 가지는 일반적인 부분 대수로 그대로 이어지지 않는다. 첫째, 집합의 부분 집합들은 그 자체로 집합(이자 격자)을 이루지만, 어떤 종류의 대수에서는 부분 대수들이 모여 같은 종류의 대수를 이루지 못할 수도 있다. 다만, 격자를 이루는 것은 항상 가능하다. 둘째, 집합의 부분 집합은 그 집합에서 {0, 1} 집합으로 가는 함수와 일대일 대응 관계에 있지만, 대수의 부분 대수에서는 {0, 1}과 같은 역할을 하는 특별한 대수가 항상 존재한다고 보장할 수 없다.

특정 대수 클래스는 이 두 속성을 모두 만족하기도 한다. 첫 번째 속성(부분 대수가 격자를 이루는 것)은 비교적 일반적이지만, 두 속성을 모두 갖는 경우는 드물다. 두 속성을 모두 만족하는 대표적인 예는 멀티그래프이다. 두 멀티그래프 ''G''와 ''H''가 있을 때, 준동형 사상 ''h'' : ''G'' → ''H''는 정점을 정점으로, 변을 변으로 대응시키는 두 함수로 구성된다. ''G''에서 ''H''로 가는 모든 준동형 사상의 집합을 ''H''''G''라고 할 때, 이 집합 자체를 하나의 멀티그래프로 구성할 수 있다. 즉, 준동형 사상에 포함된 정점 함수들을 새로운 정점으로, 변 함수들을 새로운 변으로 삼는 것이다. 또한, 멀티그래프 ''G''의 부분 그래프는 특별한 멀티그래프 Ω(두 개의 정점과 다섯 개의 변으로 구성됨: 두 정점을 잇는 두 변, 각 정점에서의 루프 변, 그리고 한 정점에서의 추가 루프 변)로 가는 그래프 준동형 사상과 일대일 대응 관계에 있다. 따라서 ''G''의 부분 그래프들은 Ω''G''라는 멀티그래프로 구성될 수 있으며, 이를 ''G''의 멱 객체(power object)라고 부른다.

멀티그래프가 대수 구조로서 특별한 점은 모든 연산이 단항 연산이라는 것이다. 멀티그래프는 정점 집합 ''V''와 변 집합 ''E'', 그리고 각 변의 시작점과 끝점을 지정하는 두 단항 연산 ''s'', ''t'' : ''E'' → ''V''로 이루어진다. 모든 연산이 단항인 대수를 전층(presheaf)이라고 한다. 모든 전층 클래스는 부분 집합에 대해 {0, 1} 집합이 하는 역할과 유사한 역할을 하는 특별한 전층 Ω를 포함하며, 이를 부분 객체 분류자라고 한다. 이러한 클래스는 범주론에서 닫힌 범주(특히 데카르트 닫힌 범주)이며, 부분 객체 분류자 Ω를 갖는 초등 토포스라는 더 일반적인 개념의 특수한 경우이다. "멱 객체"라는 용어는 때때로 지수 객체 ''Y''''X''와 같은 의미로 사용되기도 하지만, 토포스 이론에서는 ''Y''가 반드시 부분 객체 분류자 Ω여야 한다.

11. 함자와 수량자

멱집합 개념은 범주론의 함자와 연결될 수 있다. 집합과 함수들의 범주인 '''Set'''에서 두 종류의 멱집합 함자를 정의할 수 있다.

하나는 공변 함자 ''P'': '''Set''' → '''Set'''이다. 이 함자는 각 집합 ''S''를 그것의 멱집합 ''P''(''S'')로 보내고, 함수 ''f'': ''S'' → ''T''를 다음과 같은 이미지 사상 ''Pf''로 보낸다: ''A'' ⊆ ''S''에 대해, ''Pf''(''A'') = {''f''(''x'') | ''x'' ∈ ''A''} ⊆ ''P''(''T''). 즉, 부분집합 ''A''의 원소들을 함수 ''f''로 보낸 상(image)들의 집합이다.

다른 하나는 반변 함자 ''P̄'': '''Set'''op → '''Set'''이다. 이 함자는 함수 ''f'': ''S'' → ''T''를 역상 이미지 사상 ''P̄f''로 보낸다: ''B'' ⊆ ''T''에 대해, ''P̄f''(''B'') = {''x'' ∈ ''S'' | ''f''(''x'') ∈ ''B''} ⊆ ''P''(''S''). 즉, 부분집합 ''B''의 역상(''f''−1(''B''))이다. 멱집합 ''P''(''S'')를 ''S''에서 두 원소 집합 {0, 1}로 가는 함수들의 집합으로 보는 관점과 관련하여, 반변 함자는 자연 동형 ''P̄'' ≅ '''Set'''(-, {0, 1})을 정의한다.[1]

범주론 및 기초적인 토포스 이론에서는 수량자를 멱집합 함자의 수반으로 이해하기도 한다. 집합 간 함수의 역상 함자(위에서 설명한 반변 함자와 유사)를 생각할 때, 전칭 기호 (∀)는 이 함자의 오른쪽 수반으로, 존재 기호 (∃)는 왼쪽 수반으로 이해될 수 있다.

참조

[1] 서적 Category Theory in Context
[2] 문서 集合論の慣例で、自然数 2 を集合 {0,1} と同一視している。


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com