\( \newcommand{\cat}[1] {\mathrm{#1}} \newcommand{\catobj}[1] {\operatorname{Obj}(\mathrm{#1})} \newcommand{\cathom}[1] {\operatorname{Hom}_{\cat{#1}}} \newcommand{\multiBetaReduction}[0] {\twoheadrightarrow_{\beta}} \newcommand{\betaReduction}[0] {\rightarrow_{\beta}} \newcommand{\betaEq}[0] {=_{\beta}} \newcommand{\string}[1] {\texttt{"}\mathtt{#1}\texttt{"}} \newcommand{\symbolq}[1] {\texttt{`}\mathtt{#1}\texttt{'}} \)

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

\[ 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:

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

---

Source

p59