Difference between revisions of "Power set"

Revision as of 20:34, 25 January 2008

The power set of a given set $S$ is the set $\mathcal{P}(S)$ of all subsets of that set This is denoted, other than by the common $\math{P}(S)$ (Error compiling LaTeX. Unknown error_msg), by $2^{S}$ $(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\} $with a single element has two subsets, the empty set and the entire set. Thus$ \mathcal{P}(\{a\}) = \{\emptyset, \{a\}\}$.

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

Similarly, for any [[finite]] set with$ (Error compiling LaTeX. Unknown error_msg)n $elements, the power set has$ 2^n$elements.

==Size Comparison== Note that for any [[nonnegative]] [[integer]]$ (Error compiling LaTeX. Unknown error_msg)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]]$ (Error compiling LaTeX. Unknown error_msg)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$ (Error compiling LaTeX. Unknown error_msg)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.

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} $ways to have no elements,$ \binom{n}{1} $ways to have one element, ... , and$ \binom{n}{n} $ways to have n elements. We add:$ \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 \} $and has$ 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^k $elements in the power set. Now we include the sets that do include x. But that's just$ 2^k $, since we are choosing either 0 1, ... or k elements to go with x. Therefore, if there are$ 2^k $elements in the power set of a set that has k elements, then there are$ 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.

External Links

Power Set at Wolfram MathWorld.

@@ 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==
-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>.
-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\}<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\}</math> with two elements has four subsets, and <math>\mathcal{P}(\{a, b\}) = \{\emptyset, \{a\}, \{b\}, \{a, b\}\}</math>.
+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</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.
 ===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>.
+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>.
+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.
+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==
-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:
+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===
-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:
+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>
+</math>\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=2^n<math>
 as desired.
@@ Line 39: / Line 39: @@
 Let S be the set with n elements. If n=0, then S is the empty set. Then
-<math>P(S)=\{\emptyset \}</math>
+</math>P(S)=\{\emptyset \}<math>
-and has <math>2^0=1</math> element.
+and has </math>2^0=1<math> element.
@@ Line 48: / Line 48: @@
 Let's say that Q has k+1 elements.
-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.
+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</math>.
+Therefore, the number of elements in a power set of a set with n elements is </math>2^n<math>.
 ===Method 3===
@@ Line 58: / Line 58: @@
 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</math> elements in the power sum.
+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.

Page

Toolbox

Search

Difference between revisions of "Power set"

Revision as of 20:34, 25 January 2008

See Also

External Links