# 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}</ | + | 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 < | + | The [[empty set]] has only one subset, itself. Thus <math>\mathcal{P}(\emptyset) = \{\emptyset\}</math>. |

− | A set < | + | 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 < | + | 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 < | + | 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]] < | + | 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]] < | + | 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 < | + | 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 < | + | 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 < | + | 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 < | + | 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. | 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> |

− | and has < | + | 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 < | + | 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 < | + | 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 < | + | 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 is the set of all subsets of that set This is denoted, other than by the common $\math{P}(S)$ (Error compiling LaTeX. ! LaTeX Error: Bad math environment delimiter.), by (which has to do with the number of elements in the power set of a given set).

## Contents

## 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 S be the set with n elements. If n=0, then S 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.