# 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

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

*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 \)