Maps
Introduction
Let $X$ and $Y$ be sets. A function $f: X \to Y$ is a rule which assigns to each element of $x$ an element $f(x)$ of $Y$.
When $X$ and $Y$ are spaces, a map $f: X \to Y$ is a function from $X$ to $Y$ which “preserves the (geometric) structure of $X$”.
Since I haven’t said what “space” means, this is kind of meaningless. Once we encounter precise definitions of various types of spaces, they’ll be accompanied by precise notions of “map”. Still, I’m going to use the word “map” more than “function” because it’s shorter and more evocative. Also, sets are one kind of space (with no additional structure), and in that case map does mean any function.
Terminology
In the above definition:
- $X$ is called the domain of $f$
- $Y$ is called the codomain of $f$
-
the image of $f$ is the set of all values taken by $f$,
\[ \im(f) \Defeq \{ f(x) \mid x \in Y \} \] - if $x \in X$, we call the value $f(x)$ the image of $x$ under $f$. We also call $x$ a preimage of $y \in Y$ if $f(x) = y$.
The difference between codomain and range can be hard to appreciate at first. The domain and codomain are part of the “type” of $f$, wheras the image might be something difficult to determine.
In terms of vibes, the notation $f: X \to Y$ is approximately equivalent to
f: (x: X) => Y;
A more accurate (though still imperfect) translation would be
f: Map<X, Y>;
This is because in math, two functions $f$ and $g$ are considered equal if
- they have the same domain and codomain
- they map each input to the same output: $f(x) = g(x)$ for all $x \in X$
The second point is an important difference between functions in math and functions in programming (which are really algorithms). For mathematical functions, there’s no such thing as a “function body” or “runtime”.
Some more terminology. A function is:
- injective if it never sends two different inputs to the same output. This can be phrased as \[ x \ne y \implies f(x) \ne f(y) \] or equivalently as \[ f(x) = f(y) \implies x = y. \] The first form is maybe easier to think about, but the second is easier to work with.
- surjective if every element of $Y$ is the image of some $x\in X$.
- bijective if it is both injective and surjective.
Exponential interpretation
When we introduced products of spaces, we saw that that concept was related to multiplication of numbers. Functions are also related to a numeric concept: exponentiation.
For example, say we have two balls which can be painted any of three colors, red, green, blue. We can represent the possibilities as functions from $\{B_1, B_2\}$ to $\{\red r,\green g,\blue b\}$, e.g. \[ \vcenter{\LARGE{\red\bullet}{\blue\bullet}} \quad\text{corresponds to}\quad f(B_1) = \red r, \quad f(B_2) = \blue b. \] There are $9=3^2$ possibilities in total:
In general, if $X$ and $Y$ are finite sets with $|X|$ and $|Y|$ elements respectively, then the number of functions from $X$ to $Y$ is $|Y|^{|X|}$: there are $|Y|$ options where to send each $x \in X$, and we can choose those values independently of one another.
This suggests defining $Y^X$ as the set of functions from $X$ to $Y$, so that
This is called the function set or mapping space from $X$ to $Y$. Although this can be hard to think about, it’s very powerful to go from thinking about
- individual elements of $X$ and $Y$, to
- individual functions $f: X \to Y$, to
- considering all functions $X \to Y$ as a single object.
Another notation for the mapping space (more common in CS than in math) is $X \to Y$, in which case the notation $f: X \to Y$ is literally a type declaration. In any case, the mapping space from $X$ to $Y$ is approximately equivalent to the type (x: X) => Y or Map<X, Y>.
I’ll try to avoid using the concept of mapping space except when we have precise definitions of “space” and “map”, since
-
the precise definition of “map” will affect what the actual elements of $Y^X$ are. For example,
\begin{align*} f&\colon \R \to \R\\ f(x) &= x+1 \end{align*}is considered an affine map but not a linear map.
-
depending on the precise meaning of “space”, it may be easy, difficult, or impossible to turn the set of maps $X \to Y$ into a “space”.
Maps and products
Let’s see how this interacts with the other way we’ve seen of combining spaces, namely products.
Repeated multiplication
When $x$ is a natural number ($0,1,2,…)$ and $y$ is any number, the exponential $y^x$ is defined as repreated multiplication:
Something similar is true for function spaces. Recall that three-dimensional space $\R^3$ can be understood as the threefold product of $\R$ with itself,
\[ \R^3 = \R \times \R \times \R. \]
We can also view $\R^3$ as the function space $\R^{\{0,1,2\}}$. In code, this is saying that the types
[number, number, number];
and
{
0: number;
1: number;
2: number;
}
are “equivalent”.
Depending on your application, you might prefer to have types like
{
x: number;
y: number;
z: number;
}
or
{
height: number;
width: number;
}
These can be encoded as the mapping spaces $\R^{\{\r x,\r y,\r z\}}$ and $\R^{\{\r{height},\r{width}\}}$.
Maps into a product
Let $X$, $Y$, and $Z$ be spaces. We can form the product $Y \times Z$, and then ask what maps $f\colon X \to Y \times Z$ look like.
By definition, $f$ needs to send each element $x$ of $X$ to an element of $Y \times Z$. An element of $Y \times Z$ is a pair $(y, z)$ with $y\in Y$ and $z\in Z$. So can define maps $g: X \to Y$ and $h: X \to Z$ as the first and second components of $f$:
\[ f(x) = (g(x), h(x)) \]
In other words, a function from $X$ to $Y \times Z$ is equivalent to two separate functions $X \to Y$ and $X \to Z$. In terms of mapping spaces, we can express this as
\[ (Y \times Z)^X \qeq Y^X \times Z^X. \]
(I’ll say more about $\qeq$ in a future post.) This parallels the identity for numbers
\[ (yz)^x = y^x z^x. \]
Here’s what this equivalence looks like in code:
/** Projection onto first factor */
const pr1 = <X, Y>([x, y]: [X, Y]): X => x;
/** Projection onto second factor */
const pr2 = <X, Y>([x, y]: [X, Y]): Y => y;
/** Convert a function into a product to a pair of functions **/
const split = <X, Y, Z>(f: (x: X) => [Y, Z]): [(x: X) => Y, (x: X) => Z] => [
(x) => pr1(f(x)),
(x) => pr2(f(x)),
];
/** Convert a pair of functions to a function into a product */
const combine =
<X, Y, Z>(g: (x: X) => Y, h: (x: X) => Z): ((x: X) => [Y, Z]) =>
(x) =>
[g(x), h(x)];
Maps out of a product
What about maps out of a product? That is, for spaces $X$, $Y$, $Z$, let’s think about what maps $X \times Y \to Z$ look like.
These correspond to “functions of two variables”: for example, the function
\[ f(x, y) = x^2 + y^2 \]
is a map $\R^2 \to \R$.
There is another way of encoding a function of two variables: for a fixed value of $x$, we can get a function $f_x: Y \to Z$ by defining
\[ f_x(y) = f(x, y) \]
For instance, if $f(x, y) = x^2 + y^2$ as above, then $f_2(y) = 4+y^2$. This is saying that a function of two variables can also be expressed as a function from $X$ to the set of functions from $Y$ to $Z$. Symbolically, this is
\[ Z^{X\times Y} \qeq (Z^Y)^X \]
or
\[ (X \times Y) \to Z \qeq X \to (Y \to Z) \]
This “lifts” the numeric identity
\[ z^{xy} = (z^y)^x. \]
In programming, this equivalence is called “currying”.
/** Convert a function of two variables into a function returning a function. */
const curry =
<X, Y, Z>(f: ([x, y]: [X, Y]) => Z): ((x: X) => (y: Y) => Z) =>
(x) =>
(y) =>
f([x, y]);
/** Convert a function returning a function to a function of two variables. */
const uncurry =
<X, Y, Z>(f: (x: X) => (y: Y) => Z): (([x, y]: [X, Y]) => Z) =>
([x, y]) =>
f(x)(y);
Coproducts
There’s one more exponential identity remaining,
\[ z^{x + y} = z^x z^y \]
To get an analogue of this for mapping spaces, we need the concept of the coproduct $X \amalg Y$. I don’t want to really get into this concept right now, but it corresponds to the union type X | Y. The relevant identity is
Or if you prefer, this is saying that the types Map<X | Y, Z> and [Map<X, Z>, Map<Y, Z>] are “equivalent”.