# Mathematical Proof and the Principles of Mathematics/Sets/Power sets

## Power sets[edit | edit source]

Power sets allow us to discuss the class of all subsets of a given set , i.e. . That this is a set is the subject of the Power Set Axiom.

**Axiom**

Given a set there exists a set of sets such that iff .

**Theorem** Given a set , there exists a unique set whose elements are the subsets of .

**Proof** If and are two such sets of subsets then if and only if . But the same is true of . Thus iff , and so by the Axiom of Extensionality.

**Definition** Given a set , the set of all subsets of is called the *power set* of . It is denoted .

**Example** If then .

## Cartesian products[edit | edit source]

Recall the Kuratowski definition of an ordered pair, for and elements of a set . Note that and are both subsets of , i.e. they are elements of the power set .

This means that is a subset of , i.e. .

We can generalise this slightly with a simple trick. We can define with and for sets and . In order to do this, we simply take the elements and from the union of sets .

In other words, we have with and .

**Theorem** The class of all ordered pairs of elements of with and , is a set.

**Proof** The set in question is given by . This is a set by the axioms of Power Set, Union and the Axiom Schema of Comprehension.

**Definition** The set of ordered pairs with and is called the *cartesian product* of and , and is denoted .

## Exercises[edit | edit source]

- Show that for sets we have .

- Show that for sets we have .

- Show that for sets we have .

- Show that for sets with we have .