Power Set

Family of Sets

Definition

Given a set , a collection of subsets of is called a family of subsets of (or family of sets over ).

Example

Let . An example of a family of sets over is

A family of subsets over is a subset of the power set of (an "incomplete" power set if you will).

Power Set

Definition

A power set (powerset) of a set is the set of all subsets of , including the empty set and the set itself.

The power set is a special case of a family of subsets: family of subsets of a set is a subset of the power set of .
In other words, a power set is a family of sets containing all combinations of subsets of any length.

Notation

The power set of is often denoted as:

Axiom - Power Set

(see Set Builder Notation)

Example

If is the set , then all the subsets of are:

So the power set of is

Below is the Hasse diagram for this powerset:

Remark

If is a finite set with cardinality , then . This is why the power set is sometimes denoted as .

Property

(see universal quantifier)

Proof

Using Natural Deduction (Predicate Logic):

proof

Cantor's Theorem

Theorem

Let be a function which maps from set to its power set . Then is not surjective. As a result, holds for any set ,

Proof

Consider the set (set builder notation). Suppose for contradiction sake that is surjective.
Then there exists such that .
Our set is defined such that . But , so we would have . This is a contradiction, thus cannot be surjective.
On the other hand, is injective, so we must have .

Relation to the Binomial Theorem

See binomial theorem

Info

Given a set with elements, the number of subsets with elements is

(see combination)

Example

A power set of a set with 3 elements has:

subset with 0 elements (empty set)
subsets with 1 element (singleton subsets)
subsets with 2 elements (the complements of the singleton subsets)
subset with 3 elements (the original set)

Using this relationship, we can compute :

Equation