Power set

The power of { x , y , z }, represented as a Hasse diagram .

In set theory, the power set is the set of all subsets of a given basic set .

The power set of a set is usually noted as . The nature of the power set was already examined by Ernst Zermelo . The compact term “power set” on the other hand - which is useful in connection with the arithmetic power - was not used by Gerhard Hessenberg in his 1906 textbook either; he uses the phrase “set of subsets” for this. ${\displaystyle X}$ ${\displaystyle {\mathcal {P}}(X)}$

definition

The power set of a set is a new set that consists of all subsets of . The power set is therefore a system of sets , that is, a set whose elements are themselves sets. In formula notation, the definition of a power set is ${\displaystyle {\mathcal {P}}(X)}$ ${\displaystyle X}$ ${\displaystyle U}$ ${\displaystyle X}$

${\displaystyle {\mathcal {P}}(X):=\{U\mid U\subseteq X\}}$.

It should be noted that the empty set and the set are also subsets of , i.e. elements of the power set . Other common notations for the power set are and . ${\displaystyle \emptyset }$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle {\mathcal {P}}(X)}$ ${\displaystyle {\mathfrak {p}}(X),\ 2^{X},\ \mathrm {Pot} (X),\ \Pi (X),\ \wp (X)}$ ${\displaystyle {\mathfrak {P}}(X)}$

Examples

• ${\displaystyle {\mathcal {P}}(\emptyset )=\{\emptyset \}}$
• ${\displaystyle {\mathcal {P}}(\{a\})={\bigl \{}\emptyset ,\{a\}{\bigr \}}}$
• ${\displaystyle {\mathcal {P}}(\{a,b\})={\bigl \{}\emptyset ,\{a\},\{b\},\{a,b\}{\bigr \}}}$
• ${\displaystyle {\mathcal {P}}(\{a,b,c\})={\bigl \{}\emptyset ,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}{\bigr \}}}$
• ${\displaystyle {\mathcal {P}}({\mathcal {P}}(\emptyset ))={\bigl \{}\emptyset ,\{\emptyset \}{\bigr \}}}$
• ${\displaystyle {\mathcal {P}}({\mathcal {P}}(\{a\}))={\bigl \{}\emptyset ,\{\emptyset \},\{\{a\}\},\{\emptyset ,\{a\}\}{\bigr \}}}$

Structures on the power set

Partial order

The inclusion relation is a partial order on (and not a total order , if at least two elements). The smallest element of order is , the greatest element is . ${\displaystyle \subseteq }$ ${\displaystyle {\mathcal {P}}(X)}$ ${\displaystyle X}$ ${\displaystyle \emptyset }$ ${\displaystyle X}$

Full association

The partial order is a complete association . This means that for every subset of there is an infimum and a supremum (in ). Concretely, for a set the infimum of is equal to the intersection of the elements of , and the supremum of is equal to the union of the elements of , thus ${\displaystyle ({\mathcal {P}}(X),\subseteq )}$ ${\displaystyle {\mathcal {P}}(X)}$ ${\displaystyle {\mathcal {P}}(X)}$ ${\displaystyle T\subseteq {\mathcal {P}}(X)}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle T}$ ${\displaystyle T}$

${\displaystyle \inf(T)=\bigcap _{M\in T}M\quad {\text{ und }}\quad \mathrm {sup} (T)=\bigcup _{M\in T}M.}$

The largest and the smallest element are obtained as the infimum or supremum of the empty set, i.e.

${\displaystyle \inf(\emptyset )=X\quad {\text{ und }}\quad \sup(\emptyset )=\emptyset .}$

Boolean association

If you also use the complement map, it is a Boolean lattice , i.e. a distributive and complementary lattice. ${\displaystyle {}^{\mathrm {c} }:{\mathcal {P}}(X)\rightarrow {\mathcal {P}}(X)}$ ${\displaystyle ({\mathcal {P}}(X),\cap ,\cup ,^{\mathrm {c} },\emptyset ,X)}$

Commutative ring

Each Boolean lattice clearly induces a commutative ring structure, the so-called Boolean ring . Here on , the ring addition is given by the symmetrical difference of quantities, the ring multiplication is the average. The empty set is neutral for addition and is neutral for multiplication. ${\displaystyle {\mathcal {P}}(X)}$ ${\displaystyle X}$

Characteristic functions

Each subset can be assigned the characteristic function , where applies ${\displaystyle T\subseteq X}$ ${\displaystyle \chi _{T}\colon X\to \{0,1\}}$

${\displaystyle \chi _{T}(x):={\begin{cases}1,&x\in T\\0,&x\not \in T\end{cases}}}$

This assignment is a bijection between and (using the notation for the set of all functions from to ). This also motivates the notation , because in von Neumann's model of natural numbers is (in general:) . ${\displaystyle {\mathcal {P}}(X)}$ ${\displaystyle \{0,1\}^{X}}$ ${\displaystyle B^{A}}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle {\mathcal {P}}(X)}$ ${\displaystyle 2^{X}}$ ${\displaystyle 2=\{0,1\}}$ ${\displaystyle n=\{0,...,n-1\}}$

The correspondence is initially a pure bijection, but can easily be demonstrated as an isomorphism with respect to each of the structures considered above on the power set. ${\displaystyle {\mathcal {P}}(X)\cong \{0,1\}^{X}}$

The size of the power set (cardinality)

${\displaystyle |M|}$denotes the power of a crowd . ${\displaystyle M}$

• For finite sets applies: . ${\displaystyle X}$ ${\displaystyle |{\mathcal {P}}(X)|=2^{|X|}}$
• Always applicable Cantor's theorem : . ${\displaystyle |X|<|{\mathcal {P}}(X)|}$

The transition to the power set always provides greater power. Analogously to finite sets, one also writes for the cardinality of the power set of an infinite set . The generalized continuum hypothesis (GCH) says for infinite sets that the next greater thickness is: ${\displaystyle 2^{|X|}}$ ${\displaystyle |{\mathcal {P}}(X)|=\left|2^{X}\right|}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle |{\mathcal {P}}(X)|}$ ${\displaystyle |X|}$ ${\displaystyle \mathrm {GCH} \implies (|X|<|Y|\implies |{\mathcal {P}}(X)|\leq |Y|).}$

Restriction to smaller subsets

With the set of those subsets of which contain fewer than elements. For example : The set itself is missing because it has no less than elements. ${\displaystyle {\mathcal {P}}_{\kappa }(X)=\{U\subseteq X:|U|<\kappa \}}$ ${\displaystyle X}$ ${\displaystyle \kappa }$ ${\displaystyle {\mathcal {P}}_{3}(\{a,b,c\})=\{\emptyset ,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\}\}}$ ${\displaystyle \{a,b,c\}}$ ${\displaystyle 3}$

Potency class

The concept of the power set can be extended to classes , whereby it should be noted that real classes cannot be on the left side of the membership relation . The power (power class) of a class K is given by the class of all sets whose elements are all contained in K. The elements of the power class of K are therefore the subsets of K. The power of a real class K is again a real class, because it contains the units {x} for all elements x of K. It always contains the empty set ∅, but not the real class K itself. ${\displaystyle \in }$

Others

• The existence of the power set for every set is required in the Zermelo-Fraenkel set theory as a separate axiom, namely by the power set axiom .
• A system of sets such as a topology or a σ-algebra over a basic set is a subset of the power set , i.e. an element of . ${\displaystyle X}$ ${\displaystyle {\mathcal {P}}(X)}$ ${\displaystyle {\mathcal {P}}({\mathcal {P}}(X))}$

literature

• Oliver Deiser: Introduction to set theory. Georg Cantor's set theory and its axiomatization by Ernst Zermelo. 2nd, improved and enlarged edition. Springer, Berlin a. a. 2004, ISBN 3-540-20401-6 .

Web links

Wikibooks: Math for Non-Freaks: Potency Set  - Learning and Teaching Materials

Wikibooks: Evidence archive: set theory  - learning and teaching materials

Wiktionary: power set  - explanations of meanings, word origins, synonyms, translations