Difference between revisions of "Power set"
m |
m |
||
| Line 1: | Line 1: | ||
| − | The '''power set''' of a given [[set]] <math>S</math> is the set <math>P(S)</math> of [[subset]]s of that set. | + | The '''power set''' of a given [[set]] <math>S</math> is the set <math>\mathcal{P}(S)</math> of [[subset]]s of that set. |
| − | The [[empty set]] has only one subset, itself. Thus <math>P(\emptyset) = \{\emptyset\}</math>. | + | The [[empty set]] has only one subset, itself. Thus <math>\mathcal{P}(\emptyset) = \{\emptyset\}</math>. |
| − | A set <math>\{a\}</math> with a single element has two subsets, the empty set and the entire set. Thus <math>P(\{a\}) = \{\emptyset, \{a\}\}</math>. | + | A set <math>\{a\}</math> with a single element has two subsets, the empty set and the entire set. Thus <math>\mathcal{P}(\{a\}) = \{\emptyset, \{a\}\}</math>. |
| − | A set <math>\{a, b\}</math> with two elements has four subsets, and <math>P(\{a, b\}) = \{\emptyset, \{a\}, \{b\}, \{a, b\}\}</math>. | + | A set <math>\{a, b\}</math> with two elements has four subsets, and <math>\mathcal{P}(\{a, b\}) = \{\emptyset, \{a\}, \{b\}, \{a, b\}\}</math>. |
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 is larger than 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>P(S)</math> (or equivalently, there is no [[injection]] from <math>P(S)</math> to <math>S</math>). | + | Note that for [[nonnegative]] [[integer]]s, <math>2^n > n</math> so the power set of any set is larger than 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 17:06, 23 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 is larger than 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.
