Difference between revisions of "Power set"
| Line 9: | Line 9: | ||
Similarly, for any [[finite]] set with <math>n</math> elements, the power set has <math>2^n</math> elements. | Similarly, for any [[finite]] set with <math>n</math> elements, the power set has <math>2^n</math> elements. | ||
| − | Note that for any set <math>\displaystyle S</math> such that <math>\displaystyle a \in S</math>, <math>\displaystyle \{ a \} \subseteq S </math>, so the power set of any set <math>\displaystyle S</math> has a [[cardinality]] at least as large as that of <math>\displaystyle S</math> itself. | + | Note that for any set <math>\displaystyle S</math> such that <math>\displaystyle a \in S</math>, <math>\displaystyle \{ a \} \subseteq S </math>, so the power set of any set <math>\displaystyle S</math> has a [[cardinality]] at least as large as that of <math>\displaystyle S</math> itself. Specifically, sets of cardinality 1 or 0 are the only sets that have power sets of the same cardinality, since if <math>\displaystyle S</math> is a finite set with cardinality at least 2, then <math>\displaystyle \mathcal{P}( S )</math> clearly has cardinality greater than 2. A similar result holds for [[infinite]] sets: for no infinite set <math>\displaystyle S</math> is there a [[bijection]] between <math>\displaystyle S</math> and <math>\displaystyle \mathcal{P} (S) </math>. |
===Proof=== | ===Proof=== | ||
Revision as of 15:13, 27 August 2006
The power set of a given set 
is the set 
of subsets of that set.
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.
Note that for any set 
such that 
, 
, so the power set of any set has a cardinality at least as large as that of itself. Specifically, sets of cardinality 1 or 0 are the only sets that have power sets of the same cardinality, since if is a finite set with cardinality at least 2, then 
clearly has cardinality greater than 2. A similar result holds for infinite sets: for no infinite set is there a bijection between and 
.
Proof
See Also
This article is a stub. Help us out by expanding it.
