Difference between revisions of "Power set"
m |
|||
| 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 [[nonnegative]] [[integer]]s, <math>2^n > n</math> so the power set of any set | + | Note that for [[nonnegative]] [[integer]]s, <math>2^n > n</math> so the power set of any set has a [[cardinality]] at least as large as the set itself. An analogous result holds for [[infinite]] sets: for any set <math>S</math>, there is no [[bijection]] between <math>S</math> and <math>\mathcal{P}(S)</math> (or equivalently, there is no [[injection]] from <math>\mathcal{P}(S)</math> to <math>S</math>). |
===Proof=== | ===Proof=== | ||
| − | |||
Revision as of 20:07, 26 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 nonnegative integers, 
so the power set of any set has a cardinality at least as large as the set itself. An analogous result holds for infinite sets: for any set , there is no bijection between and (or equivalently, there is no injection from to ).
Proof
See Also
This article is a stub. Help us out by expanding it.
