# Difference between revisions of "Power set"

m (→Size for Finite Sets: typo) |
(→Method 2) |
||

Line 37: | Line 37: | ||

We proceed with [[induction]]. | We proceed with [[induction]]. | ||

− | Let S be the set with n elements. If n=0, then S is the empty set. Then | + | 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> | <math>P(S)=\{\emptyset \}</math> |

## Latest revision as of 11: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

## 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.