Difference between revisions of "Power set"
IntrepidMath (talk | contribs) m (added all- now states: set of all subsets) |
m (→Size comparison) |
||
Line 18: | Line 18: | ||
Now, note that <math>y \in T</math> by definition if and only if <math>y \not\in f(y)</math>, so <math>y \in T</math> if and only if <math>y \not \in T</math>. This is a clear contradiction. Thus the bijection <math>f</math> cannot really exist and <math>|\mathcal P (S)| \neq |S|</math> so <math>|\mathcal P(S)| > |S|</math>, as desired. | Now, note that <math>y \in T</math> by definition if and only if <math>y \not\in f(y)</math>, so <math>y \in T</math> if and only if <math>y \not \in T</math>. This is a clear contradiction. Thus the bijection <math>f</math> cannot really exist and <math>|\mathcal P (S)| \neq |S|</math> so <math>|\mathcal P(S)| > |S|</math>, as desired. | ||
+ | |||
+ | |||
+ | Note that this proof does not rely upon either the [[continuum hypothesis]] or the [[axiom of choice]]. It is a good example of a [[diagonal argument]], a method pioneered by the mathematician [[Georg Cantor]]. | ||
==See Also== | ==See Also== |
Revision as of 10:55, 7 September 2006
The power set of a given set is the set of all 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.
Note that this proof does not rely upon either the continuum hypothesis or the axiom of choice. It is a good example of a diagonal argument, a method pioneered by the mathematician Georg Cantor.
See Also
This article is a stub. Help us out by expanding it.