Power set

2020 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