Power set
The power set of a given set is the set
of all subsets of that set This is denoted, other than by the common $\math{P}(S)$ (Error compiling LaTeX. Unknown error_msg), by
$(which has to do with the number of elements in the power set of a given set).
==Examples== The [[empty set]] has only one subset, itself. Thus$ (Error compiling LaTeX. Unknown error_msg)\mathcal{P}(\emptyset) = \{\emptyset\}$.
A set$ (Error compiling LaTeX. Unknown error_msg)\{a\}\mathcal{P}(\{a\}) = \{\emptyset, \{a\}\}$.
A set$ (Error compiling LaTeX. Unknown error_msg)\{a, b\}\mathcal{P}(\{a, b\}) = \{\emptyset, \{a\}, \{b\}, \{a, b\}\}$.
Similarly, for any [[finite]] set with$ (Error compiling LaTeX. Unknown error_msg)n2^n$elements.
==Size Comparison==
Note that for any [[nonnegative]] [[integer]]$ (Error compiling LaTeX. Unknown error_msg)n2^n > n
S
|\mathcal P (S)| > |S|
S
|\mathcal P (S)|
|S|$of the set itself.
===Proof===
There is a natural [[injection]]$ (Error compiling LaTeX. Unknown error_msg)S \hookrightarrow \mathcal P (S)x \mapsto \{x\}
|S| \leq |\mathcal P(S)|
|S| = |\mathcal P(S)|
f: \mathcal P(S) \to S
T \subset S
T = \{x \in S \;|\; x \not\in f(x) \}
T \in \mathcal P(S)
f
\exists y\in S \;|\; T = f(y)$.
Now, note that$ (Error compiling LaTeX. Unknown error_msg)y \in Ty \not\in f(y)
y \in T
y \not \in T
f
|\mathcal P (S)| \neq |S|
|\mathcal P(S)| > |S|$, as desired.
Note that this proof does not rely upon either the [[Continuum Hypothesis]] or the [[Axiom of Choice]]. It is a good example of a [[diagonal argument]], a method pioneered by the mathematician [[Georg Cantor]].
==Size for Finite Sets==
The number of [[element|elements]] in a [[power set]] of a set with n elements is$ (Error compiling LaTeX. Unknown error_msg)2^n$for all finite sets. THis can be proven in a number of ways:
===Method 1===
Either an element in the power set can have 0 elements, one element, ... , or n elements. There are$ (Error compiling LaTeX. Unknown error_msg)\binom{n}{0}\binom{n}{1}
\binom{n}{n}
\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=2^n$as desired.
===Method 2===
We proceed with [[induction]].
Let S be the set with n elements. If n=0, then S is the empty set. Then$ (Error compiling LaTeX. Unknown error_msg)P(S)=\{\emptyset \}2^0=1$element.
Now let's say that the theorem stated above is true or n=k. We shall prove it for k+1.
Let's say that Q has k+1 elements.
In set Q, if we leave element x out, there will be$ (Error compiling LaTeX. Unknown error_msg)2^k2^k
2^k
2^{k+1}$elements in the power set of a set that has k+1 elements.
Therefore, the number of elements in a power set of a set with n elements is$ (Error compiling LaTeX. Unknown error_msg)2^n$.
===Method 3===
We demonstrated in Method 2 that if S is the empty set, it works.
Now let's say that S has at least one element.
For an element x, it can be either in or out of a subset. Since there are n elements, and each different choice of in/out leads to a different subset, there are$ (Error compiling LaTeX. Unknown error_msg)2^n$ elements in the power sum.
See Also
External Links
- Power Set at Wolfram MathWorld.