Power Set · aiwiki.page

In set theory, the power set of a set $S$ is the set whose elements are exactly the subsets of $S$ . It includes both the empty set and $S$ itself. Usually written $\mathcal P(S)$ , it converts a collection of objects into a collection of all possible selections from those objects. Power sets provide a basic construction for studying sets, functions, and different sizes of infinity. (plato.stanford.edu)

Definition and examples

The formal definition is

\mathcal P(S)=\{A\mid A\subseteq S\}.

Thus $A\in\mathcal P(S)$ means exactly that every element of $A$ belongs to $S$ . Membership and inclusion must be distinguished: a subset of $S$ is an element of its power set, rather than merely another element of $S$ . (web.stanford.edu)

For example, if $S=\{a,b,c\}$ , then

\mathcal P(S)= \{\varnothing,\{a\},\{b\},\{c\}, \{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}.

There are eight subsets, including those with zero or three elements. In particular,

\mathcal P(\varnothing)=\{\varnothing\},

which is not empty: it has one element. The original set is always included because $S\subseteq S$ . These examples follow directly from the definition. (web.stanford.edu)

Finite cardinality

If $S$ has $n$ elements, its power set has cardinality

|\mathcal P(S)|=2^n.

Each element presents two choices—include it or exclude it—and the choices determine a unique subset. Alternatively, mathematical induction proves the formula: adjoining one new element doubles the number of subsets, since every old subset occurs both without and with that element. The base case is $2^0=1$ . (cs.cornell.edu)

Subsets can also be counted by size:

|\mathcal P(S)|=\sum_{k=0}^{n}\binom nk=2^n.

Here $\binom nk$ counts the subsets containing exactly $k$ elements. The equality is a special case of the binomial theorem, obtained by expanding $(1+1)^n$ . (cs.pomona.edu)

Characteristic functions and binary representation

Every subset $A\subseteq S$ determines an indicator function, also called a characteristic function:

\chi_A:S\longrightarrow\{0,1\},\qquad \chi_A(s)= \begin{cases} 1,&s\in A,\\ 0,&s\notin A. \end{cases}

Conversely, any such function determines the subset on which it equals $1$ . This gives a bijection between $\mathcal P(S)$ and the set of functions $S\to\{0,1\}$ , explaining the alternative notation $2^S$ . This correspondence respects the Boolean operations on subsets and truth-valued functions. (home.uni-leipzig.de)

For an ordered finite set, these functions can be represented as strings of bits. A $1$ records inclusion and a $0$ exclusion. For $S=(a,b,c)$ , the string $101$ represents $\{a,c\}$ . Reading the strings as binary numbers permits enumeration by counting from $0$ to $2^n-1$ . (ics.uci.edu)

Infinite sets and Cantor’s theorem

Cantor’s theorem states that every set has strictly smaller cardinality than its power set:

|S|<|\mathcal P(S)|.

An injection $S\to\mathcal P(S)$ is supplied by $s\mapsto\{s\}$ . The essential result is that no surjection $S\to\mathcal P(S)$ exists. (math.arizona.edu)

The diagonal argument establishes this by considering any function $f:S\to\mathcal P(S)$ and defining

D=\{s\in S\mid s\notin f(s)\}.

If $f$ were surjective, some $d\in S$ would satisfy $f(d)=D$ . But then

d\in D\iff d\notin D,

a contradiction. Therefore $D$ is a subset missing from the image of $f$ . The argument applies to finite and infinite sets alike. (math.arizona.edu)

Consequently, the power set of the natural numbers is not a countable set. Repeatedly taking power sets produces successively larger infinite cardinalities, so there is no largest size of infinity. (math.arizona.edu)

Order and algebraic structure

Set inclusion defines a partial order on $\mathcal P(S)$ . Together with union, intersection, and complement relative to $S$ , the power set forms a Boolean algebra. The empty set is its least element and $S$ its greatest; union and intersection correspond to disjunction and conjunction, while complementation corresponds to negation. Under characteristic functions, these operations become pointwise Boolean operations. (home.uni-leipzig.de)

For a finite $n$ -element set, the resulting ordered structure is commonly denoted $B_n$ . Its levels group subsets according to their cardinality, with the empty set at the bottom and the whole set at the top. (math.mit.edu)

Foundations and applications

In Zermelo–Fraenkel set theory, the power set axiom guarantees that all subsets of any given set form a set. Power sets also generate successor stages of the cumulative hierarchy:

V_0=\varnothing,\qquad V_{\alpha+1}=\mathcal P(V_\alpha).

At limit stages, earlier stages are combined by union. (plato.stanford.edu)

In probability theory, events belong to a sigma-algebra contained in the power set of a sample space. For discrete models, all subsets can be events. Continuous models often use a smaller sigma-algebra, allowing probability to be defined consistently without assigning it to every subset. (math.cmu.edu)

In computing, an algorithm can enumerate a finite power set through bit patterns. Nevertheless, there are $2^n$ outputs for an $n$ -element input: compactly representing each subset does not remove the exponential number of subsets that full enumeration must produce. (web.eecs.utk.edu)