Powered by Blogger.

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 $$
f(x_1) &= y_1 \\
f(x_2) &= y_2 \\
& \vdots \\
f(x_n) &= y_n
$$ 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.


Post a Comment