## Sets of Functions

This post will introduce sets whose elements are functions and explain the notation for these sets. If you aren't familiar with basic notations for sets, please take a look at this post.

Suppose $f$ is a function mapping inputs from a set $X$ (the domain of $f$) to outputs (called values) in a set $Y$ (the range of $f$). Note that each input is mapped to exactly one output (this is the definition of a function), but numerous inputs are allowed map to one output value. We record this relationship by writing $f : X \rightarrow Y$.

 An example of a function; in this case, two inputs map to a single output.

### The set of all functions $X \rightarrow Y$

Recall that the Cartesian product of two sets $A$ and $B$, denoted $A \times B$, is the set of ordered pairs $(a,b)$ where $a \in A$ and $b \in B$. In particular, the Cartesian product of a set $Y$ with itself, $Y \times Y$, is the set of ordered pairs $(y_1, y_2)$ where both $y_1$ and $y_2$ are elements of $Y$.

Extending this a bit further, for a positive integer $n$, we can write $Y^{n}$ (also written $\underbrace{Y \times Y \times \dotsb \times Y}_{n \rm \ times}$ or $\prod_{i=1}^{n}{Y}$) to denote the set of ordered $n$-tuples $(y_1, y_2, \dotsc , y_n)$ where all of the $y_i$'s are elements of $Y$.

Suppose $X$ is a finite set with $|X|=n$ (i.e. $X$ has $n$ elements), $\{ x_1, x_2, \dotsc, x_n \}$. If we have some function $f: X \rightarrow Y$, then $f(x_{1})$ will be some element $y_1$ of $Y$, $f(x_{2})$ will be some element $y_2$ of $Y$, etc. Therefore, specifying the function amounts to specifying an $n$-tuple of elements of $Y$, $(y_1, y_2, \dotsc, y_n)$, one for each input from the domain $X$. In other words, specifying $f$ amounts to specifying an element of $Y^n$.

Similarly, any $n$-tuple $(y_1, y_2, \dotsc , y_n)$ from $Y^n$ gives us a function from $X$ (or any other set with $n$ elements, such as $\{ 1, 2, \dotsc , n \}$), namely \begin{align} f(x_1) &= y_1 \\ f(x_2) &= y_2 \\ & \vdots \\ f(x_n) &= y_n \end{align} Thus we can identify functions $X \rightarrow Y$ one-to-one with elements of $Y^n$ if $|X|=n$. For this reason, we use the notation $Y^X$ for the set of all functions $X \rightarrow Y$.

This notation is also used when $X$ is not a finite set. For example, if $X = {\Bbb N}$, the set of natural numbers $\{ 1,2,3, \dotsc \}$ and $Y={\Bbb R}$, the real numbers, then functions ${\Bbb N} \rightarrow {\Bbb R}$ can be viewed as sequences of real numbers $(r_1, r_2, r_3, \dotsc)$. By the same logic as above, we can view ${\Bbb R}^{\Bbb N}$ as the Cartesian product $\prod_{n \in {\Bbb N}}{{\Bbb R}} = {\Bbb R} \times {\Bbb R} \times {\Bbb R} \times \dotsb$.

Analogously, we use the same notation when $X$ is not even countably infinite, e.g. $X = {\Bbb R}$, the real numbers. The set ${\Bbb R}^{\Bbb R}$ of all functions ${\Bbb R} \rightarrow {\Bbb R}$ can be thought of as the set of "vectors" with one component for each real number $x \in {\Bbb R}$. There are too many real numbers to write these out as tuple as we could in the finite and countably infinite cases above, but we can still write a Cartesian product of an uncountable infinity of copies of ${\Bbb R}$, and thus we write the set of all functions as ${\Bbb R}^{\Bbb R}$, identifying it with $\prod_{x \in {\Bbb R}}{{\Bbb R}}$.

The next few posts will show how we can define a vector space structure and a notion of convergence of a sequence of functions (i.e. a sequence of points in $Y^X$), extending our intuition from vectors in ${\Bbb R}^n$. We need this rigorous definition of convergence of functions to a limit function in order to develop models of random phenomena in physics, finance, etc. using stochastic processes.