Power set ($\mathcal{P}(X)$)

The power set $\mathcal{P}(X)$ is the set of all subsets of $X$, including the empty set and $X$ itself. It is useful whenever an object is a selection rather than an individual member: a possible collection of active vertices in a graph, for example, belongs to the power set of the vertex set.

For $X=\{a,b,c\}$, the power set has eight members:Each of the three set elements is either included or excluded. More generally, if $|X|=n<\infty$, these $n$ independent binary choices give $|\mathcal{P}(X)|=2^n$. This is a bijection between subsets and binary strings of length $n$, not a probabilistic independence assumption.

Ordering the subsets by inclusion gives a Boolean lattice. In the picture an upward edge adds one member. Complementation reverses inclusion, and union and intersection combine selections. The empty-input case is worth checking: $\mathcal{P}(\varnothing )=\{\varnothing \}$ has one member, not zero, consistently with $2^0=1$.

There is no surjection from a set $X$ onto its power set $\mathcal{P}(X)$. Consequently $\mathcal{P}(X)$ has strictly greater cardinality than $X$.

For any candidate function $f:X\to \mathcal{P}(X)$, form $D=\{x\in X:x\notin f(x)\}$. This is a subset of $X$ by set comprehension. If $f(d)=D$, then $d\in D$ holds exactly when $d\notin D$, a contradiction. Thus $D$ is missing from the image of $f$. On the other hand, $x\mapsto \{x\}$ is an injection from $X$ into its power set, establishing the strict comparison of cardinalities. For $X=\mathbb{N}$, the omitted selection is the subset version of Cantor's diagonal argument.