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$.

For arbitrary sets $A,B$ each containing at least two elements, the displayed inequality follows by explicitly encoding two subsets in disjoint parts of a Cartesian product. Choose $a_0\ne a_1$ and $b_0\ne b_1$, put $S$ along the row $A\times \{b_0\}$, put $T\setminus \{b_0\}$ along the column $\{a_0\}\times (B\setminus \{b_0\})$, and add the extra point $(a_1,b_1)$ precisely when $b_0\in T$. These regions are disjoint, so the encoding recovers both $S$ and $T$ and is an injection from $\mathcal{P}(A)\times \mathcal{P}(B)$ into $\mathcal{P}(A\times B)$. This proves the cardinality inequality even for infinite sets. For finite sizes $a,b\ge 2$, the same result is $2^{ab}\ge 2^{a+b}$, since $ab-a-b=(a-1)(b-1)-1\ge 0$. Mapping $(S,T)$ to $S\times T$ is insufficient because all pairs with an empty factor collapse.

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.

For each natural number $n$, the family $[A{]}^n$ of all $n$-element subsets is nonempty when $A$ is not finite. These families are pairwise distinct elements of $\mathcal{P}(\mathcal{P}(A))$, giving an explicit injection of the natural numbers. No representative from each family is selected. A power set cannot be countably infinite in ZF: if $\mathcal{P}(B)$ were countably infinite, singleton injection would make $B$ an infinite subset of a countable set and hence countably infinite; Cantor's theorem would then contradict countability of its power set. Apply this to $B=\mathcal{P}(A)$ to make the displayed lower bound strict.