 Show Question
Math and science::Analysis::Tao::03: Set theory

# Power set axiom

Let $$X$$ and $$Y$$ be sets. Then there exists a set, denoted $$Y^X$$, which consists of all the functions from $$X$$ to $$Y$$ , thus

$f \in Y^X \iff f \text{ is a function with domain } X \text{ and range } Y$

#### Notation

The reason for the notation $$Y^X$$ is that if $$Y$$ as $$n$$ elements and $$X$$ has $$m$$ elements, then it can be shown that $$Y^X$$ has $$n^m$$ elements.

### Interpretation using function graphs

A function can be viewed as a subset of $$X \times Y$$. Imagine $$X \times Y$$ as a grid, and a function being a set of markings on the grid, with certain restrictions. The set of elements that are marked are the elements of the function's "graph", which defines the function. Then, $$Y^X$$ can be viewed as the set of all subsets of $$X \times Y$$ that represent valid functions.

### The power set, $$2^X$$

A consequence of this axiom is that the set:

$\{Y : Y \text{ is a subset of } X\}$
is a set!

This set is known as the power set of $$X$$ and is denoted as $$2^X$$. This set can be thought of as $$\{ \{x : x \in X \text{ and } f(x) = 1 \} : f \in \{0,1\}^X\}$$. There is no notational conflict, as 2 is not a set, so does not have any meaning according to the power set axiom above.

### Example

Let $$X = {4, 7}$$ and $$Y = {0, 1}$$. Then the set $$Y^X$$ consists of four functions:

• the function that maps $$4 \mapsto 0$$ and $$7 \mapsto 0$$
• the function that maps $$4 \mapsto 0$$ and $$7 \mapsto 1$$
• the function that maps $$4 \mapsto 1$$ and $$7 \mapsto 0$$
• the function that maps $$4 \mapsto 1$$ and $$7 \mapsto 1$$

p59