Difference between revisions of "Power set"

Revision as of 00:49, 28 August 2006

The power set of a given set $S$ is the set $\mathcal{P}(S)$ of subsets of that set.

The empty set has only one subset, itself. Thus $\mathcal{P}(\emptyset) = \{\emptyset\}$ .

A set $\{a\}$ with a single element has two subsets, the empty set and the entire set. Thus $\mathcal{P}(\{a\}) = \{\emptyset, \{a\}\}$ .

A set $\{a, b\}$ with two elements has four subsets, and $\mathcal{P}(\{a, b\}) = \{\emptyset, \{a\}, \{b\}, \{a, b\}\}$ .

Similarly, for any finite set with $n$ elements, the power set has $2^n$ elements.

Note that for any nonnegative integer $n$ , $2^n > n$ and so for any finite set $S$ , $|\mathcal P (S)| > |S|$ (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 $S$ , the cardinality $|\mathcal P (S)|$ of the power set is strictly larger than the cardinality $|S|$ of the set itself.

Proof

There is a natural injection $S \hookrightarrow \mathcal P (S)$ taking $x \mapsto \{x\}$ , so $|S| \leq |\mathcal P(S)|$ . Suppose for the sake of contradiction that $|S| = |\mathcal P(S)|$ . Then there is a bijection $f: \mathcal P(S) \to S$ . Let $T \subset S$ be defined by $T = \{x \in S \;|\; x \not\in f(x) \}$ . Then $T \in \mathcal P(S)$ and since $f$ is a bijection, $\exists y\in S \;|\; T = f(y)$ .

Now, note that $y \in T$ by definition if and only if $y \not\in f(y)$ , so $y \in T$ if and only if $y \not \in T$ . This is a clear contradiction. Thus the bijection $f$ cannot really exist and $|\mathcal P (S)| \neq |S|$ so $|\mathcal P(S)| > |S|$ , as desired.

@@ Line 9: / Line 9: @@
 Similarly, for any [[finite]] set with <math>n</math> elements, the power set has <math>2^n</math> elements.
-Note that for any set <math>\displaystyle S</math> such that <math>\displaystyle a \in S</math>, <math>\displaystyle \{ a \} \subseteq S </math>, so the power set of any set <math>\displaystyle S</math> has a [[cardinality]] at least as large as that of <math>\displaystyle S</math> itself.  Specifically, sets of cardinality 1 or 0 are the only sets that have power sets of the same cardinality, since if <math>\displaystyle S</math> is a finite set with cardinality at least 2, then <math>\displaystyle \mathcal{P}( S )</math> clearly has cardinality greater than 2.  A similar result holds for [[infinite]] sets: for no infinite set <math>\displaystyle S</math> is there a [[bijection]] between <math>\displaystyle S</math> and <math>\displaystyle \mathcal{P} (S) </math>.
+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===
+There is a natural [[injection]] <math>S \hookrightarrow \mathcal P (S)</math> taking <math>x \mapsto \{x\}</math>, so <math>|S| \leq |\mathcal P(S)|</math>.
+Suppose for the sake of contradiction that <math>|S| = |\mathcal P(S)|</math>.  Then there is a [[bijection]] <math>f: \mathcal P(S) \to S</math>.  Let <math>T \subset S</math> be defined by <math>T = \{x \in S \;|\; x \not\in f(x) \}</math>.  Then <math>T \in \mathcal P(S)</math> and since <math>f</math> is a bijection, <math>\exists y\in S \;|\; T = f(y)</math>.
+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.
 ==See Also==

Page

Toolbox

Search

Difference between revisions of "Power set"

Revision as of 00:49, 28 August 2006

Proof

See Also