Power set

수학(mathematics)에서, 집합(set) $S$ 의 거듭제곱 집합 (또는 거듭제곱집합)은 빈 집합(empty set)과 $S$ 자체를 포함하는 $S$ 의 모든 부분집합(subset)의 집합입니다.^[1] 공리적 집합 이론(axiomatic set theory) (예를 들어, ZFC 공리에서 개발됨)에서, 임의의 집합의 거듭제곱 집합의 존재는 거듭제곱 집합의 공리(axiom of power set)에 의해 공준(postulated)되었습니다.^[2] $S$ 의 거듭제곱집합은 $P (S)$ , $𝒫(S)$ , $P (S)$ , $\mathbb {P} (S)$ , $℘(S)$ ("바이어슈트라스 p"를 사용), 또는 $2 S$ 으로 다양하게 표시됩니다. $S$ 에서 두 원소의 주어진 집합 (예를 들어, {0, 1})로의 모든 함수의 집합을 의미하는, 표기법 $2 S$ 는 $S$ 의 거듭제곱집합이 $S$ 에서 주어진 두 원소 집합으로의 모든 함수의 집합으로 식별, 동등하거나, 또는 전단사가 될 수 있습니다.^[1]

$P (S)$ 의 임의의 부분집합은 $S$ 에 걸쳐 집합의 가족이라고 불립니다.

Example

만약 $S$ 가 집합 ${x, y, z}$ 이면, $S$ 의 모든 부분집합은 다음입니다:

${}$ (역시 $\varnothing$ 또는 $\emptyset$ 으로 표시됨, 빈 집합(empty set) 또는 널 집합)
${x}$
${y}$
${z}$
${x, y}$
${x, z}$
${y, z}$
${x, y, z}$

그리고 따라서 $S$ 의 거듭제곱 집합은 ${{}, {x}, {y}, {z}, {x, y}, {x, z}, {y, z}, {x, y, z}}$ 입니다.^[3]

Properties

만약 $S$ 가 카디널리티(cardinality) $| S | = n$ 를 갖는 유한 집합이면 (즉, 집합 $S$ 에서 모든 원소의 개수는 $n$ ), $S$ 의 모든 부분집합의 개수는 $| P (S)| = 2 n$ 입니다. 이 사실과 거듭제곱 집합 $P (S)$ 를 나타내는 표기법 $2 S$ 의 이유는 아래에 설명되어 있습니다:

카디널리티 |S| = n를 갖는 집합 S의 부분집합 A의 지시 함수(indicator function) 또는 특성 함수는 S에서 둘의 원소 집합 {0, 1}으로의 함수로, I_A: S → {0, 1}로 표시되고, S의 원소가 A에 속하는지 여부를 나타냅니다; 만약 S에서 x가 A에 속하면, I_A(x) = 1이고, 그렇지 않으면 0입니다. S의 각 부분집합 A는 지시 함수 I_A에 의해 식별되거나 동등하고, S에서

{0,1}

로의 모든 함수의 집합으로

{0,1} S

는 S의 모든 부분집합의 모든 지시 함수로 구성됩니다. 다시 말해서,

{0,1} S

는 거듭제곱 집합

P (S)

와 동등하거나 전단사입니다. S에서 각 원소는

{0,1} S

에서 임의의 함수 아래에서 0 또는 1에 해당하므로,

{0,1} S

에서 모든 함수의 개수는 2ⁿ입니다. 숫자 2는

{0,1}

로 정의될 수 있으므로 (예를 들어, 폰 노이만 순서-숫자를 참조),

P (S)

는 역시

2 S

로 표시됩니다. 분명하게

| 2 S | = 2 | S |

는 유지됩니다. 일반적으로 말해서, X^Y는 Y에서 X로의 모든 함수의 집합이고

| X Y | = | X | | Y |

입니다.

칸토어의 대각선 논증(Cantor's diagonal argument)은 집합의 거듭제곱 집합 (무한 여부이든 아니든)이 항상 집합 자체보다 엄격하게 더 높은 카디널리티(cardinality)를 갖는다는 것을 보여줍니다 (또는 비공식적으로, 거듭제곱 집합은 원래 집합보다 커야 합니다). 특히, 칸토어의 정리(Cantor's theorem)는 셀-수-있는 무한(countably infinite) 집합의 거듭제곱 집합이 셀-수-없는(uncountably) 무한임을 보여줍니다. 자연수(natural number) 집합의 거듭제곱 집합은 실수(real number) 집합과 일-대-일 대응(one-to-one correspondence)으로 넣어질 수 있습니다 (연속체의 카디널리티(Cardinality of the continuum)를 참조하십시오).

합집합(union), 교집합(intersection), 및 여집합(complement)의 연산과 함께, 집합 $S$ 의 거듭제곱 집합은 부울 대수(Boolean algebra)의 원형적 예제로 보일 수 있습니다. 사실, 임의의 유한 부울 대수는 유한 집합의 거듭제곱 집합의 부울 대수와 동형(isomorphic)임을 보일 수 있습니다. 무한 부울 대수에 대해, 이것은 더 이상 사실이 아니지만, 모든 각 무한 부울 대수는 거듭제곱 집합 부울 대수의 부분대수(subalgebra)로 나타낼 수 있습니다 (Stone의 표시 정리(Stone's representation theorem)를 참조하십시오).

집합 $S$ 의 거듭제곱 집합은 대칭 차이(symmetric difference)의 연산으로 고려될 때 아벨 그룹을 형성하고 (빈 집합을 항등 요소로 갖고 각 집합은 자체의 역임), 교집합 연산으로 고려하면 교환적(commutative) 모노이드(monoid)를 형성합니다. 따라서 분배 법칙(distributive laws)을 증명함으로써, 이들 연산의 둘 다와 함께 고려된 거듭제곱 집합이 부울 링(Boolean ring)을 형성한다는 것을 보여줄 수 있습니다.

Representing subsets as functions

집합 이론(set theory)에서, $X Y$ 는 $Y$ 에서 $X$ 로의 모든 함수(function)의 집합을 나타내는 표기법입니다. "2"는 ${0,1}$ 로 정의될 수 있기 때문에 (예를 들어, 폰 노이만 순서-숫자(von Neumann ordinals)를 참조), $2 S$ (즉, ${0,1} S$ )는 $S$ 에서 ${0,1}$ 로의 모든 함수(function)의 집합입니다. 위에서 보인(shown above) 것처럼, $2 S$ 와 $S$ 의 거듭제곱 집합, $P (S)$ 는 집합-이론적으로 동일하게 고려됩니다.

이 동등성은 위의 예제에 적용될 수 있으며, $S = {x, y, z}$ 에서 0에서 $2 n - 1$ 으로의 숫자의 이진 표시를 갖는 동형(isomorphism)을 얻기 위해, $n$ 이 집합 $S$ 에서 원소의 개수 또는 $| S | = n$ 입니다. 먼저, 열거된 집합 ${ (x, 1), (y, 2), (z, 3) }$ 이 정의되며, 이것에서 각 순서화된 쌍의 숫자는 ${x, y} = 011 (2)$ 와 같은 이진 자릿수의 수열에서 $S$ 의 쌍을 이루는 원소의 위치를 나타냅니다; $S$ 의 $x$ 는 이 수열의 오른쪽에서 첫 번째에 위치되고 $y$ 는 오른쪽에서 두 번째에 위치되고, 수열에서 1은 수열에서 그것의 위치에 해당하는 $S$ 의 원소가 수열에 대해 $S$ 의 부분집합에 있음을 의미하고 반면에 0은 그렇지 않음을 의미합니다.

$S$ 의 전체 거듭제곱 집합에 대해, 우리는 다음을 얻습니다:

부분집합	이진 자릿수의 수열	이진 해석	십진 동치
${ }$	$0, 0, 0$	$000 (2)$	$0 (10)$
${x}$	$0, 0, 1$	$001 (2)$	$1 (10)$
${y}$	$0, 1, 0$	$010 (2)$	$2 (10)$
${x, y}$	$0, 1, 1$	$011 (2)$	$3 (10)$
${z}$	$1, 0, 0$	$100 (2)$	$4 (10)$
${x, z}$	$1, 0, 1$	$101 (2)$	$5 (10)$
${y, z}$	$1, 1, 0$	$110 (2)$	$6 (10)$
${x, y, z}$	$1, 1, 1$	$111 (2)$	$7 (10)$

$P (S)$ 에서 정수로의 그러한 전단사 매핑(bijective mapping)은 임의적이므로, $S$ 의 모든 부분집합의 이러한 표시는 고유하지 않지만, 열거된 집합의 정렬 순서는 그것의 카디널리티를 변경하지 않습니다. (예를 들어, ${ (y, 1), (z, 2), (x, 3) }$ 는 일대일 대응의 개수를 변경없이 $P (S)$ 에서 정수로의 또 다른 전단사를 구성하기 위해 사용될 수 있습니다.)

어쨌든, 그러한 유한 이진 표시는 만약 S가 열거될 수 있으면 오직 가능합니다. (이 예제에서 $x$ , $y$ , 및 $z$ 는 이진 자릿수 수열의 위치로 각각 1, 2, 및 3으로 열거됩니다.) 열거는 심지어 $S$ 가 정수 또는 유리수의 집합과 같은 무한 카디널리티 (즉, $S$ 에서 원소의 개수가 무한대)를 가지더라도 가능하지만, 예를 들어 만약 S가 실수의 집합이면 가능하지 않는데, 왜냐하면 이 경우에서 우리는 모든 무리수를 열거할 수 없습니다.

Relation to binomial theorem

이항 정리(binomial theorem)는 거듭제곱 집합과 밀접하게 관련되어 있습니다. 어떤 집합에서 $k$ –원소 조합은 $k$ –원소 부분집합에 대해 또 다른 이름이므로, $C(n, k)$ 로 표시되는 (역시 이항 계수(binomial coefficient)라고 불리며) 조합(combination)의 숫자는 $n$ 원소를 갖는 집합에서 $k$ 원소를 갖는 부분집합의 개수입니다; 다시 말해서, 그것은 $n$ 원소를 갖는 집합의 거듭제곱 집합의 원소인 $k$ 원소를 갖는 부분집합의 개수입니다.

예를 들어, 세 원소를 갖는 집합의 거듭제곱 집합은 다음을 가집니다:

C(3, 0) = 0 원소를 갖는 1 부분집합 (빈 부분집합),
C(3, 1) = 1 원소를 갖는 3 부분집합 (한원소 부분집합),
C(3, 2) = 2 원소를 갖는 3 부분집합 (한원소 부분집합의 여집합),
C(3, 3) = 3 원소를 갖는 1 부분집합 (원래 집합 자체).

이 관례를 사용하여, 우리는 다음 공식을 사용하여 ${\textstyle \left|2^{S}\right|}$ 를 계산할 수 있습니다: $\left|2^{S}\right|=\sum _{k=0}^{|S|}{\binom {|S|}{k}}$

그러므로, 우리는 ${\textstyle |S|=n}$ 를 가정하여 다음 항등식을 추론할 수 있습니다: $\left|2^{S}\right|=2^{n}=\sum _{k=0}^{n}{\binom {n}{k}}$

Recursive definition

만약 $S$ 가 유한 집합(finite set)이면, $P(S)$ 의 재귀 정의(recursive definition)는 다음처럼 진행합니다:

만약 $S=\{\}$ 이면, $P(S)=\{\,\{\}\,\}$ 입니다.
그렇지 않으면, $e\in S$ 와 $T=S\setminus \{e\}$ 라고 놓습니다; 그런-다음 $P(S)=P(T)\cup \{t\cup \{e\}:t\in P(T)\}$ 입니다.

말로 하자면:

빈 집합(empty set)의 거듭제곱 집합은 그것의 유일한 원소가 빈 집합인 한원소(singleton)입니다.
비-빈 집합 $S$ 에 대해, $e$ 를 집합의 임의의 원소로 놓고 $T$ 를 그것의 상대적 여집합(relative complement)으로 놓습니다; 그런-다음 $S$ 의 거듭제곱 집합은 $T$ 의 거듭제곱 집합과 그것의 각 원소가 $e$ 원소로 확장된 $T$ 의 거듭제곱 집합의 합집합(union)입니다.

Subsets of limited cardinality

$κ$ 보다 작거나 같은 카디널리티(cardinality)의 $S$ 의 부분집합의 집합은 때때로 $P κ (S)$ 또는 $[S] κ$ 로 표시되고, $κ$ 보다 엄격하게 작은 카디널리티를 갖는 부분집합의 집합은 때때로 $P < κ (S)$ 또는 $[S] <κ$ 로 표시됩니다. 유사하게, $S$ 의 비-빈 부분집합의 집합은 $P \geq 1 (S)$ 또는 $P + (S)$ 로 표시될 수 있습니다.

Power object

집합은 비-자명한 연산 또는 정의하는 방정식을 가지지 않는 대수로 여길 수 있습니다. 이러한 관점에서, $X$ 의 부분집합의 집합으로 $X$ 의 거듭제곱 집합의 아이디어는 대수적 구조(algebraic structure) 또는 대수의 부분대수로 자연스럽게 일반화합니다.

포함에 의해 순서화될 때, 집합의 거듭제곱 집합은 항상 완전한 원자 부울 대수이고, 모든 각 완전한 원자 부울 대수는 일부 집합의 모든 부분집합의 격자(lattice)로 발생합니다. 임의 대수로의 일반화는 다시 포함에 의해 순서화된 대수의 부분대수의 집합이 항상 대수적 격자(algebraic lattice)이고, 모든 각 대수적 격자는 일부 대수의 부분대수의 격자로 발생한다는 것입니다. 따라서 그런 점에서, 부분대수는 부분집합과 유사하게 동작합니다.

어쨌든, 일반적으로 부분대수에 적용되지 않는 부분집합의 두 가지 중요한 속성이 있습니다. 첫째, 비록 집합의 부분집합이 집합 (마찬가지로 격자)을 형성하지만, 일부 클래스에서 대수의 부분대수를 해당 클래스에서, 비록 그것들이 항상 격자로 구성될 수 있을지라도, 대수 자체로 구성하는 것이 불가능할 수 있습니다. 둘째, 집합의 부분집합이 해당 집합에서 집합 {0,1} = 2로의 함수와 함께 전단사에 있지만, 반면에 대수의 클래스가 이러한 방식으로 2의 역할을 할 수 있는 대수를 포함한다는 보장은 없습니다.

특정 대수의 클래스는 이들 속성의 둘 다를 즐깁니다. 첫 번째 속성이 더 공통적이고, 둘 다를 가지는 경우는 상대적으로 드뭅니다. 둘 다를 가지고 있는 한 클래스는 다중그래프(multigraph)의 클래스입니다. 두 개의 다중그래프 $G$ 와 $H$ 가 주어지면, 준동형(homomorphism) $h : G \to H$ 는 두 개의 함수로 구성되며, 하나는 꼭짓점을 꼭짓점으로 매핑하고 다른 하나는 모서리를 모서리로 매핑합니다. $G$ 에서 $H$ 로의 준동형의 집합 $H G$ 는 그런-다음 그것의 꼭짓점과 가장자리가 각각 해당 집합에 나타나는 꼭짓점 가장자리 함수인 그래프로 구성될 수 있습니다. 게다가, 다중그래프 $G$ 의 부분그래프는 $G$ 에서 다중그래프 $Ω$ 로의 그래프 준동형을 다섯 번째 가장자리, 즉 꼭짓점 중 하나에서 둘의 자체-루프를 갖는 증가된 두 꼭짓점 (따라서 넷의 가장자리, 즉 둘의 자체-루프와 둘의 순환을 형성하는 추가 가장자리)에 대한 완전한 방향화된 그래프로 정의-가능한 전단사입니다. 우리는 따라서 $G$ 의 부분그래프를 $G$ 의 거듭제곱 대상이라고 불리는 다중그래프 $Ω G$ 로 조직할 수 있습니다.

대수로서의 다중그래프의 특별한 점은 그것의 연산이 단항이라는 것입니다. 다중그래프는 꼭짓점의 집합 $V$ 와 가장자리의 $E$ 를 형성하는 두 가지 종류의 원소를 가지고, 각 가장자리의 원천 (시작)과 목표 (끝) 꼭짓점을 제공하는 둘의 단항 연산 $s, t : E \to V$ 을 가집니다. 모든 연산이 단항인 대수는 이전-층(presheaf)라고 불립니다. 모든 각 이전-층의 클래스는 2가 부분집합에 대해 수행하는 것을 부분대수에 대해 역할을 하는 이전-층 $Ω$ 를 포함합니다. 그러한 클래스는 닫힌(closed) (및 게다가 데카르트 닫힌(cartesian closed)) 것이고 부분-대상 분류기(subobject classifier)라고 불리는 객체 $Ω$ 를 가지는 카테고리(category)로서 기본 토포스(topos)의 보다 일반적인 개념의 특별한 경우입니다. 비록 그 용어 "거듭제곱 대상"이 때때로 지수 대상(exponential object) $Y X$ 와 동의어로 사용될지라도, 토포스 이론에서 $Y$ 는 $Ω$ 이어야 합니다.

Functors and quantifiers

카테고리 이론(category theory)과 기본 토포스(elementary topoi)의 이론에서, 보편 한정어(universal quantifier)는 거듭제곱 집합 사이의 함수자(functor)와 집합 사이의 함수의 역 이미지(inverse image) 함수자의 오른쪽 인접(right adjoint)으로 이해될 수 있습니다; 마찬가지로 존재적 한정어(existential quantifier)는 왼쪽 인접(left adjoint)입니다.^[4]

References

^ ^a ^b Weisstein, Eric W. "Power Set". mathworld.wolfram.com. Retrieved 2020-09-05.
^ Devlin 1979, p. 50
^ Puntambekar 2007, pp. 1–2
^ Saunders Mac Lane, Ieke Moerdijk, (1992) Sheaves in Geometry and Logic Springer-Verlag. ISBN 0-387-97710-4 See page 58

Bibliography

Devlin, Keith J. (1979). Fundamentals of contemporary set theory. Universitext. Springer-Verlag. ISBN 0-387-90441-7. Zbl 0407.04003.
Halmos, Paul R. (1960). Naive set theory. The University Series in Undergraduate Mathematics. van Nostrand Company. Zbl 0087.04403.
Puntambekar, A. A. (2007). Theory Of Automata And Formal Languages. Technical Publications. ISBN 978-81-8431-193-8.

External links

[Weisstein-1] Weisstein, Eric W. "Power Set". mathworld.wolfram.com. Retrieved 2020-09-05.

[2] Devlin 1979, p. 50

[3] Puntambekar 2007, pp. 1–2

[4] Saunders Mac Lane, Ieke Moerdijk, (1992) Sheaves in Geometry and Logic Springer-Verlag. ISBN 0-387-97710-4 See page 58

[1]

[2]

[3]

[4]