Difference between revisions of "Power set"
m |
m (→Size comparison) |
||
Line 11: | Line 11: | ||
==Size comparison== | ==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. |
===Proof=== | ===Proof=== |
Revision as of 23:52, 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.