Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Power set"

(expand lead)
(oop)
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 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).
+
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> (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\}<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==
 
==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===
−
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==
 
==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===
 
===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.
 
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>
+
<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.
 
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===
 
===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$ 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</math> elements in the power sum.
  
  

Revision as of 19:35, 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 $\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.

Size Comparison

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.


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 elements in a power set of a set with n elements is $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 $\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

$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 $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 $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 $2^n$ elements in the power sum.


See Also

External Links

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Power_set&oldid=22782"