Difference between revisions of "Power set"
(hm) |
(expand lead) |
||
Line 1: | Line 1: | ||
− | The '''power set''' of a given [[set]] <math>S</math> is the set <math>\mathcal{P}(S)</math> of all [[subset]]s of that set. | + | The '''power set''' of a given [[set]] <math>S</math> is the set <math>\mathcal{P}(S)</math> of all [[subset]]s of that set This is denoted, other than by the common <math>\math{P}(S)</math>, by <math>2^{S}</math><math> (which has to do with the number of elements in the power set of a given set). |
==Examples== | ==Examples== | ||
− | The [[empty set]] has only one subset, itself. Thus <math>\mathcal{P}(\emptyset) = \{\emptyset\}< | + | The [[empty set]] has only one subset, itself. Thus </math>\mathcal{P}(\emptyset) = \{\emptyset\}<math>. |
− | A set <math>\{a\}< | + | 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\}< | + | 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< | + | Similarly, for any [[finite]] set with </math>n<math> elements, the power set has </math>2^n<math> elements. |
==Size Comparison== | ==Size Comparison== | ||
− | Note that for any [[nonnegative]] [[integer]] <math>n< | + | 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=== | ||
− | There is a natural [[injection]] <math>S \hookrightarrow \mathcal P (S)< | + | 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)|< | + | 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< | + | 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. |
Line 23: | Line 23: | ||
==Size for Finite Sets== | ==Size for Finite Sets== | ||
− | The number of [[element|elements]] in a [[power set]] of a set with n elements is <math>2^n< | + | The number of [[element|elements]] in a [[power set]] of a set with n elements is </math>2^n<math> for all finite sets. THis can be proven in a number of ways: |
===Method 1=== | ===Method 1=== | ||
− | Either an element in the power set can have 0 elements, one element, ... , or n elements. There are <math>\binom{n}{0}< | + | Either an element in the power set can have 0 elements, one element, ... , or n elements. There are </math>\binom{n}{0}<math> ways to have no elements, </math>\binom{n}{1}<math> ways to have one element, ... , and </math>\binom{n}{n}<math> ways to have n elements. We add: |
− | <math>\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=2^n< | + | </math>\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=2^n<math> |
as desired. | as desired. | ||
Line 39: | Line 39: | ||
Let S be the set with n elements. If n=0, then S is the empty set. Then | Let S be the set with n elements. If n=0, then S is the empty set. Then | ||
− | <math>P(S)=\{\emptyset \}< | + | </math>P(S)=\{\emptyset \}<math> |
− | and has <math>2^0=1< | + | and has </math>2^0=1<math> element. |
Line 48: | Line 48: | ||
Let's say that Q has k+1 elements. | Let's say that Q has k+1 elements. | ||
− | In set Q, if we leave element x out, there will be <math>2^k< | + | In set Q, if we leave element x out, there will be </math>2^k<math> elements in the power set. Now we include the sets that do include x. But that's just </math>2^k<math>, since we are choosing either 0 1, ... or k elements to go with x. Therefore, if there are </math>2^k<math> elements in the power set of a set that has k elements, then there are </math>2^{k+1}<math> elements in the power set of a set that has k+1 elements. |
− | Therefore, the number of elements in a power set of a set with n elements is <math>2^n< | + | Therefore, the number of elements in a power set of a set with n elements is </math>2^n<math>. |
===Method 3=== | ===Method 3=== | ||
Line 58: | Line 58: | ||
Now let's say that S has at least one element. | Now let's say that S has at least one element. | ||
− | For an element x, it can be either in or out of a subset. Since there are n elements, and each different choice of in/out leads to a different subset, there are <math>2^n | + | For an element x, it can be either in or out of a subset. Since there are n elements, and each different choice of in/out leads to a different subset, there are </math>2^n$ elements in the power sum. |
Revision as of 20:34, 25 January 2008
The power set of a given set is the set
of all subsets of that set This is denoted, other than by the common $\math{P}(S)$ (Error compiling LaTeX. Unknown error_msg), by
$(which has to do with the number of elements in the power set of a given set).
==Examples== The [[empty set]] has only one subset, itself. Thus$ (Error compiling LaTeX. Unknown error_msg)\mathcal{P}(\emptyset) = \{\emptyset\}$.
A set$ (Error compiling LaTeX. Unknown error_msg)\{a\}\mathcal{P}(\{a\}) = \{\emptyset, \{a\}\}$.
A set$ (Error compiling LaTeX. Unknown error_msg)\{a, b\}\mathcal{P}(\{a, b\}) = \{\emptyset, \{a\}, \{b\}, \{a, b\}\}$.
Similarly, for any [[finite]] set with$ (Error compiling LaTeX. Unknown error_msg)n2^n$elements.
==Size Comparison==
Note that for any [[nonnegative]] [[integer]]$ (Error compiling LaTeX. Unknown error_msg)n2^n > n
S
|\mathcal P (S)| > |S|
S
|\mathcal P (S)|
|S|$of the set itself.
===Proof===
There is a natural [[injection]]$ (Error compiling LaTeX. Unknown error_msg)S \hookrightarrow \mathcal P (S)x \mapsto \{x\}
|S| \leq |\mathcal P(S)|
|S| = |\mathcal P(S)|
f: \mathcal P(S) \to S
T \subset S
T = \{x \in S \;|\; x \not\in f(x) \}
T \in \mathcal P(S)
f
\exists y\in S \;|\; T = f(y)$.
Now, note that$ (Error compiling LaTeX. Unknown error_msg)y \in Ty \not\in f(y)
y \in T
y \not \in T
f
|\mathcal P (S)| \neq |S|
|\mathcal P(S)| > |S|$, 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]].
==Size for Finite Sets==
The number of [[element|elements]] in a [[power set]] of a set with n elements is$ (Error compiling LaTeX. Unknown error_msg)2^n$for all finite sets. THis can be proven in a number of ways:
===Method 1===
Either an element in the power set can have 0 elements, one element, ... , or n elements. There are$ (Error compiling LaTeX. Unknown error_msg)\binom{n}{0}\binom{n}{1}
\binom{n}{n}
\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=2^n$as desired.
===Method 2===
We proceed with [[induction]].
Let S be the set with n elements. If n=0, then S is the empty set. Then$ (Error compiling LaTeX. Unknown error_msg)P(S)=\{\emptyset \}2^0=1$element.
Now let's say that the theorem stated above is true or n=k. We shall prove it for k+1.
Let's say that Q has k+1 elements.
In set Q, if we leave element x out, there will be$ (Error compiling LaTeX. Unknown error_msg)2^k2^k
2^k
2^{k+1}$elements in the power set of a set that has k+1 elements.
Therefore, the number of elements in a power set of a set with n elements is$ (Error compiling LaTeX. Unknown error_msg)2^n$.
===Method 3===
We demonstrated in Method 2 that if S is the empty set, it works.
Now let's say that S has at least one element.
For an element x, it can be either in or out of a subset. Since there are n elements, and each different choice of in/out leads to a different subset, there are$ (Error compiling LaTeX. Unknown error_msg)2^n$ elements in the power sum.
See Also
External Links
- Power Set at Wolfram MathWorld.