# Power set

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 {and}} \ 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 {and}} \ 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 .