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).
Contents
Examples
The empty set has only one subset, itself. Thus .
A set with a single element has two subsets, the empty set and the entire set. Thus
.
A set with two elements has four subsets, and
.
Similarly, for any finite set with elements, the power set has
elements.
Size Comparison
Note that for any nonnegative integer ,
and so for any finite set
,
(where absolute value signs here denote the cardinality of a set). The analogous result is also true for infinite sets (and thus for all sets): for any set
, the cardinality
of the power set is strictly larger than the cardinality
of the set itself.
Proof
There is a natural injection taking
, so
.
Suppose for the sake of contradiction that
. Then there is a bijection
. Let
be defined by
. Then
and since
is a bijection,
.
Now, note that by definition if and only if
, so
if and only if
. This is a clear contradiction. Thus the bijection
cannot really exist and
so
, 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 elements in a power set of a set with n elements is 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 ways to have no elements,
ways to have one element, ... , and
ways to have n elements. We add:
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
and has 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 elements in the power set. Now we include the sets that do include x. But that's just
, since we are choosing either 0 1, ... or k elements to go with x. Therefore, if there are
elements in the power set of a set that has k elements, then there are
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 .
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 elements in the power sum.
See Also
External Links
- Power Set at Wolfram MathWorld.