전원 세트

수학에서 집합 S의 전원 집합(또는 파워셋)은 빈 집합과 S 자체를 포함한 S의 모든 하위 집합의 집합이다.^[1] 자명 세트 이론에서(예를 들어, ZFC 공리에서 개발된 바와 같이), 어떤 세트의 동력 집합의 존재는 동력 집합의 공리에 의해 가정된다.^[2] S의 파워셋은 P(S), 𝒫(S),^[3] P(S), $P{\displaystyle \mathbb{}(S}$), P$($S${\displaystyle )}$ {\$displaystyle \mathb {P$S)}, )(S)("Weierstrass p" 사용) 또는 2로^S 다양하게 표시된다. S에서 주어진 두 원소의 집합(예: {0, 1)에 이르는 모든 기능의 집합을 의미하는 표기법 2는^S S의 파워셋을 S에서 주어진 두 원소 집합에 이르는 모든 함수의 집합과 동일하거나 또는 비거주적으로 식별할 수 있기 때문에 사용된다.^[1]

P(S)의 어떤 부분집합은 S에 대한 집합의 집합이라고 불린다.

예

S가 {x, y, z} 세트인 경우 S의 모든 하위 집합은

• {}(또한 $\varnothing {\displaystyle }$ ${\displaystyle \varnot }$ 또는$$ $\varnothing {\displaystyle \mathrm{}}$ ${\displaystyle \emptyset$ $\},$ 빈 집합 또는 null 집합으로 표시됨)^[3]
• {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}, {x, y, z}}^[4]이다.

특성.

S가 카디널리티 S = n(즉, 세트 S의 모든 원소의 수는 n)으로 유한 집합인 경우, S의 모든 하위 집합의 수는 P(S) = 2이다ⁿ. 이 사실뿐만 아니라 전력 집합 P(S)를 나타내는 표기법 2의^S 이유도 아래에 설명되어 있다.

카디널리티 S = n을 가진 S 집합의 부분 집합 A의 지표 함수 또는 특성 함수는 S에서 S_A → {0, 1}로 표기된 두 원소까지의 함수로서 S → {0, 1}로 표시되며, S의 요소가 A에 속하는지 여부를 표시하며, S의 x가 A에 속하면 I_A(x) = 1, 그 밖의 0을 나타낸다. S의 각 부분 집합 A는 표시기 함수 I에_A 의해 또는 동등한 것으로 식별되며, {0, 1}^S은 S에서 {0, 1}까지의 모든 함수의 집합으로서 S의 모든 하위 집합의 모든 표시기 함수로 구성된다. 즉, {0, 1}^S은(는) 전원 집합 P(S)와 동일하거나 비주사적이다. S의 각 원소는 {0, 1}^S의 어떤 함수에서도 0 또는 1에 해당하므로 {0, 1}^S의 모든 함수의 수는 2이다ⁿ. 숫자 2는 {0,1}(예: 폰 노이만 서수 참조), P(S)도 2로^S 표기된다. 분명히^S 2 = 2 홀드 ^S . 일반적으로 X는^Y Y에서 X까지, X^Y = X까지 모든 함수의 집합이다.

칸토어의 대각선 주장은 집합의 전원 집합(무제한인지 아닌지 여부)이 항상 집합 자체(또는 비공식적으로 전원 집합이 원래 집합보다 더 커야 함)보다 엄격히 높은 카디널리티를 갖는다는 것을 보여준다. 특히 칸토어의 정리를 보면 헤아릴 수 없이 무한한 집합의 동력 집합이 헤아릴 수 없이 무한하다는 것을 알 수 있다. 자연수 집합의 동력 집합은 실수의 집합과 일대일 대응으로 넣을 수 있다(연속체의 카디널리티 참조).

집합 S의 동력 세트는 조합, 교차로 및 보어의 작동과 함께 부울 대수의 원형적인 예로 볼 수 있다. 사실, 어떤 유한 부울 대수학이라도 유한 집합의 동력 집합의 부울 대수학과는 이형성이라는 것을 보여줄 수 있다. 무한 부울 알헤브라의 경우, 이것은 더 이상 사실이 아니지만, 모든 무한 부울 대수학은 동력 집합 부울 대수학의 아말게브라(Stone의 표현 정리 참조)로 나타낼 수 있다.

집합 S의 동력 집합은 대칭 차이의 작동으로 간주될 때(빈 집합은 ID 요소로 간주되고 각 집합은 자체 역), 교차로 작동과 함께 고려될 때 교호작용 단모형을 형성한다. 따라서 분배 법칙을 증명함으로써 이 두 운영과 함께 고려된 동력 집합이 부울 링을 형성한다는 것을 알 수 있다.

하위 집합을 함수로 표시

집합론에서 X는^Y Y에서 X까지의 모든 함수의 집합을 나타내는 표기법이다. "2"는 {0,1}(예: von Neumann 서수 참조), 2(예^S: {0,1})^S는 S에서 {0,1}까지의 모든 함수의 집합이다. 위와 같이 2와^S S, P(S)의 동력 세트는 이론적으로 동일한 세트로 간주된다.

이 동등한 당사자는 위에 있는 S){x, y, z}에서, 숫자의 이진 표현과 02n −에서 1까지, 요소의 집합 S와 S에서 n은 번호)n. 먼저 열거형 집합{(x1),(y, 2),(z, 3)}은 각 순서로 정렬된 숫자가 일자리를 나타내는 정의되여 유질 동상에 적용될 수 있다.n 중에서 S{), y} 같은 두 자리 숫자의 011(2)를 시퀀스에서 이루는 요소를 Sx처음으로 이 시퀀스의 오른쪽에서, y는 오른쪽에서 두번째에 있고 1는 시퀀스에 있는 동안 0은 그렇지 않다는 의미 S의 요소의 시퀀스에 있는 위치에 해당하는 S의 부분 집합의 순서를 위해 존재한다는 의미 위치해 있다..

S의 전체 파워셋에 대해 다음과 같은 정보를 얻는다.

Such a bijective mapping from P(S) to integers is arbitrary, so this representation of all the subsets of S is not unique, but the sort order of the enumerated set does not change its cardinality. (E.g., { (y, 1), (z, 2), (x, 3) } can be used to construct another bijective from P(S) to the integers without changing the number of one-to-one correspondenes.)

그러나 그러한 유한 이항 표현은 S를 열거할 수 있는 경우에만 가능하다. (이 예에서 x, y, z는 이진수 자릿수 시퀀스의 위치로 각각 1, 2, 3으로 열거된다.) 열거는 S가 정수나 이성 집합과 같이 무한한 카디널리티(즉, S에 있는 원소의 수가 무한하다)를 가지고 있어도 가능하지만, 예를 들어 S가 실수의 집합인 경우에는 불가능하며, 이 경우 불합리한 숫자를 모두 열거할 수 없다.

이항 정리와의 관계

이항 정리는 동력 집합과 밀접한 관련이 있다. 일부 집합의 k-요소 조합은 k-요소 하위 집합의 다른 이름이기 때문에 C(n, k)(이항계수라고도 함)로 표시된 조합의 수는 n개 원소가 있는 집합에서 k개 원소가 있는 하위 집합의 수, 즉 n개 원소가 있는 집합의 집합의 요소인 k개 원소가 있는 집합의 수입니다.

예를 들어 세 가지 요소가 있는 세트의 전원 집합에는 다음이 있다.

• C(3, 0) = 원소가 0인 부분 집합 1개(빈 부분 집합)
• C(3, 1) = 원소가 1개인 하위 집합 3개(싱글톤 하위 집합)
• C(3, 2) = 2개의 요소가 있는 3개의 하위 집합(싱글톤 하위 집합의 보완),
• C(3, 3) = 원소가 3개인 부분 집합 1개(원래 세트 자체)

이 관계를 사용하여 다음 공식을 사용하여$$ ${2S}^{}$ $textstyle \left 2^{S}\right }$을(를) 계산할 수 있다.

따라서 $S$= $n$ ${\textstyle S =n}$을(를) 가정하여 다음과 같은 정체성을 추론할 수 있다$.$

재귀적 정의

$S{\displaystyle }$ ${\displaystyle S}$이(${\displaystyle 가}$) 유한 집합인 경우 P (${\displaystyle }S{\displaystyle }$ )${\displaystyle P(S)}$의 재귀적 정의는 다음과$$ 같이 진행된다.

• $S{\displaystyle }$= {${\displaystyle \}}$ ${\displaystyle$ S$=\backslash \{\backslash \}\}$일 $경우{\displaystyle }$P${\displaystyle (S}$)${\displaystyle }$=${\displaystyle }${ {${\displaystyle \}}$ { $}$ {\$displaystyle$ P$(S$
• Otherwise, let ${\displaystyle e\in S}$ and ${\displaystyle T=S\setminus \{e\}}$; then ${\displaystyle P(S)=P(T)\cup \{t\cup \{e\}:t\in P(T)\}}$.

즉, 다음과 같다.

• 빈 세트의 전원 세트는 원소가 빈 세트인 싱글톤이다.
• 비어 있지 않은 $세트{\displaystyle }$ S ${\displaystyle S}$의 경우$,$ $e{\displaystyle }$ ${\displaystyle e}$을(를) 세트의 어떤 요소와$$ T ${\$$displaystyle$ $T}$의 상대적 보완 $요소$로서, $S{\displaystyle }$ ${\$$displaystyle S}$의 전원 세트는 $T$ ${\displaystystyle T$$}$의 $전원$ 세트와 $각{\displaystyle }$ 요소가$$ 확장된 조합이다.$e{\displaystyle }$ ${\displaystyle e}$ 요소$$.

제한된 카디널리티 하위 집합

카디널리티가 subs 이하인 S 하위 집합은 P(S_κ) 또는 [S]로 표시되기도 하고,^κ 카디널리티가 strictly 이하인 하위 집합은 P_{< κ}(S) 또는 [S]^<κ로 표시되기도 한다. 마찬가지로 S의 비어 있지 않은 부분 집합은 P_{≥ 1}(S) 또는 P⁺(S)로 나타낼 수 있다.

동력 객체

집합은 비교 연산이나 정의 방정식이 없는 대수라고 볼 수 있다. 이러한 관점에서 볼 때 X의 하위 집합으로서의 힘 집합의 생각은 대수구조나 대수학의 하위 게브라에 자연스럽게 일반화된다.

집합의 동력 집합은, 포함에 의해 정렬되었을 때, 항상 완전한 원자 부울 대수이며, 모든 완전한 원자 부울 대수 집합은 어떤 집합의 모든 하위 집합의 격자로 발생한다. 임의의 알헤브라에 대한 일반화는 다시 포함에 의해 순서가 정해진 대수 하위 게브라의 집합은 항상 대수 격자이며, 모든 대수 격자는 어떤 대수 하위 게브라의 격자로서 발생한다는 것이다. 그래서 그런 점에서 아발레브라는 서브셋과 비슷하게 행동한다.

그러나 하위 게브라에게 일반적으로 이월되지 않는 하위 세트의 두 가지 중요한 특성이 있다. 첫째로, 집합의 하위 집합이 집합(격자뿐만 아니라)을 형성하지만, 어떤 계급에서는 대수학의 하위 게브라를 그 자체로서 그 등급의 대수로서 조직하는 것이 불가능할 수도 있다. 둘째로, 집합의 하위 집합은 집합의 {0,1} = 2에 이르는 함수와 함께 편향되어 있는 반면에, 알헤브라의 한 클래스가 이러한 방식으로 2의 역할을 수행할 수 있는 대수학을 포함한다는 보장은 없다.

어떤 종류의 알헤브라는 이 두 가지 특성을 모두 즐긴다. 첫 번째 재산은 더 흔하고, 둘 다 갖는 경우는 비교적 드물다. 두 가지 모두를 가지고 있는 한 등급은 다중 글씨의 그것이다. 두 개의 다문자 G와 H가 주어질 때, 동형자 h: G → H는 정점에 정점을 매핑하는 것과 가장자리에 매핑하는 다른 가장자리의 두 가지 기능으로 구성된다. 그런 다음 G에서 H까지의 동형성들의 집합 H는^G 정점과 에지가 각각 그 집합에 나타나는 정점과 에지함수가 되는 그래프로 구성할 수 있다. 또한, 다중 그래프 G의 하위 그래프는 다섯 번째 에지, 즉 정점 중 하나에서 두 번째 자체 루프와 함께 증원된 두 개의 정점(즉, 주기를 형성하는 네 개의 가장자리, 즉 두 개의 가장자리와 두 개의 더 많은 가장자리)에 대한 완전한 방향 그래프로 G에서 다중 그래프 Ω으로 정의 가능한 그래프 동형성과 함께 바이어싱된다. 따라서 우리는 G의 서브그래프를 G의 전력 객체라고 불리는 멀티그래프 Ω으로^G 구성할 수 있다.

대수로서 다중 글씨가 특별한 것은 그 연산이 단수라는 점이다. 다중 글씨는 정점 V와 가장자리 E의 V를 형성하는 두 종류의 원소를 가지고 있으며, 각 가장자리의 소스(시작)와 대상(끝) 정점을 제공하는 두 개의 단항 연산 s,t → V를 가지고 있다. 수술이 단항인 대수학 모두를 프리쉐프라고 부른다. 모든 종류의 프리셰이브에는 2가 서브셋에 대해 하는 하위 게브라에 대한 역할을 하는 프리셰프 Ω이 포함되어 있다. 그러한 클래스는 닫히고(게다가 데카르트식 닫힘) 하위객체 분류기라 불리는 개체 Ω을 가진 범주로서 초등 토포들의 보다 일반적인 개념을 보여주는 특별한 경우다. "전원 객체"라는 용어가 지수 객체 Y와^X 동의어로 사용되기도 하지만 topos 이론에서 Y는 Ω이 되어야 한다.

펑터 및 정량자

범주 이론과 초등 토포이 이론에서, 보편적 정량자는 동력 집합 사이의 펑터의 오른쪽 맞춤, 집합 사이의 함수의 역 이미지 펑터의 직선으로 이해할 수 있다. 마찬가지로 실존적 정량자는 왼쪽 맞춤이다.^[5]

참고 항목

• 칸토르의 정리
• 세트 패밀리
• 세트 필드
• 조합

참조

참고 문헌 목록

• 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.

외부 링크

• PlanetMath에서 설정된 전원.
• nLab에서 설정된 전원
• 전원 개체(nLab)
• C++ 단위의 전원 집합 알고리즘