# Power set

2010 Mathematics Subject Classification: Primary: 03E [MSN][ZBL]

of a set $X$

The set of all subsets of $X$, denoted $\mathcal{P}(X)$. One has $A \in \mathcal{P}(X) \Leftrightarrow A \subseteq X$. The power set of a finite set of $n$ elements has $2^n$ elements. Cantor's theorem states that a set and its power set can never be put into one-to-one correspondence, hence cannot have the same cardinality.

The power set forms a Boolean algebra with the operations of union of sets, intersection of sets and relative complement.

If $f$ is a map from $X$ to $Y$ then there are associated maps $f_\vdash : \mathcal{P}(X) \rightarrow \mathcal{P}(Y)$ and $f^\dashv : \mathcal{P}(Y) \rightarrow \mathcal{P}(X)$ defined for $A \in \mathcal{P}(X)$, $B \in \mathcal{P}(Y)$ by $$f_\vdash(A) = \{ y \in Y : \exists a \in A\,,\, y = f(a) \} \ ;$$ $$f^\dashv(B) = \{ x \in X : \exists b \in B\,,\, b = f(x) \} \ .$$ Alternative notations are $f[A]$, $f^{-1}[B]$ respectively.

#### References

 [1] P. R. Halmos, Naive Set Theory, Springer (1960) ISBN 0-387-90092-6
How to Cite This Entry:
Power set. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Power_set&oldid=37939