Difference between revisions of "Power set"
m (→Proof) |
|||
| Line 26: | Line 26: | ||
{{stub}} | {{stub}} | ||
| + | |||
| + | [[Category:Set theory]] | ||
Revision as of 11:10, 3 December 2007
The power set of a given set 
is the set 
of all subsets of that 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.
See Also
This article is a stub. Help us out by expanding it.
