Difference between revisions of "Power set"
m |
|||
Line 1: | Line 1: | ||
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 '''power set''' of a given [[set]] <math>S</math> is the set <math>\mathcal{P}(S)</math> of [[subset]]s of that set. | ||
+ | ==Examples== | ||
The [[empty set]] has only one subset, itself. Thus <math>\mathcal{P}(\emptyset) = \{\emptyset\}</math>. | The [[empty set]] has only one subset, itself. Thus <math>\mathcal{P}(\emptyset) = \{\emptyset\}</math>. | ||
Line 9: | Line 10: | ||
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. | ||
+ | ==Size comparison== | ||
Note that for any [[nonnegative]] [[integer]] <math>n</math>, <math>2^n > n</math> and so for any finite set <math>S</math>, <math>|\mathcal P (S)| > |S|</math> (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 <math>S</math>, the cardinality <math>|\mathcal P (S)|</math> of the power set is strictly larger than the cardinality <math>|S|</math> of the set itself. | Note that for any [[nonnegative]] [[integer]] <math>n</math>, <math>2^n > n</math> and so for any finite set <math>S</math>, <math>|\mathcal P (S)| > |S|</math> (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 <math>S</math>, the cardinality <math>|\mathcal P (S)|</math> of the power set is strictly larger than the cardinality <math>|S|</math> of the set itself. | ||
Revision as of 23:50, 27 August 2006
The power set of a given set is the set of subsets of that set.
Contents
[hide]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.
See Also
This article is a stub. Help us out by expanding it.