Difference between revisions of "Power set"
m |
(→Method 2) |
||
(11 intermediate revisions by 6 users not shown) | |||
Line 1: | Line 1: | ||
− | The '''power set''' of a given [[set]] <math>S</math> is the set <math>\mathcal{P}(S)</math> of [[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. It is also sometimes denoted by <math>2^S</math>. |
==Examples== | ==Examples== | ||
Line 10: | Line 10: | ||
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 | + | ==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=== | ||
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]]. | ||
+ | ==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: | ||
+ | |||
+ | ===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: | ||
+ | |||
+ | <math>\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=2^n</math> | ||
+ | |||
+ | as desired. | ||
+ | |||
+ | ===Method 2=== | ||
+ | |||
+ | We proceed with [[induction]]. | ||
+ | |||
+ | Let <math>S</math> be the set with <math>n</math> elements. If <math>n=0</math>, then <math>S</math> is the empty set. Then | ||
+ | |||
+ | <math>P(S)=\{\emptyset \}</math> | ||
+ | |||
+ | and has <math>2^0=1</math> 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 <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>. | ||
+ | |||
+ | ===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 <math>2^n</math> elements in the power sum. | ||
==See Also== | ==See Also== | ||
* [[Set theory]] | * [[Set theory]] | ||
+ | * [[Set]] | ||
+ | |||
+ | ==External Links== | ||
+ | *[http://mathworld.wolfram.com/PowerSet.html Power Set] at Wolfram MathWorld. | ||
+ | |||
− | + | [[Category:Set theory]] |
Latest revision as of 10:44, 8 March 2018
The power set of a given set is the set of all subsets of that set. It is also sometimes denoted by .
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.
Size for Finite Sets
The number of elements in a power set of a set with n elements is 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 ways to have no elements, ways to have one element, ... , and ways to have n elements. We add:
as desired.
Method 2
We proceed with induction.
Let be the set with elements. If , then is the empty set. Then
and has 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 elements in the power set. Now we include the sets that do include x. But that's just , since we are choosing either 0 1, ... or k elements to go with x. Therefore, if there are elements in the power set of a set that has k elements, then there are 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 .
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 elements in the power sum.
See Also
External Links
- Power Set at Wolfram MathWorld.