In the last post we encountered the notion of spaces, which are a way of thinking about situations numerically and geometrically. We saw a few examples of spaces:

  • $\R^n$ is the set of all $n$-tuples of real numbers, which we think of as $n$-dimensional space

  • $[a, b]$ is the interval of numbers between $a$ and $b$ (inclusive on both sides).

  • in particular, $\I\Defeq[0,1]$ consists of all $x$ with $0\le x\le 1$

  • $S^1$ is the unit circle in $\R^2$

In this post, we’ll discuss a way to combine two (or more) spaces $X$ and $Y$ into a new space $X\times Y$, called the product of $X$ and $Y$. There are two reasons to do this:

  • it gives us more interesting examples of spaces;

  • conversely, we understand complicated spaces by expressing them in terms of simpler “building block” spaces. Most questions about $X\times Y$ can be answered by answering the same question for the spaces $X$ and $Y$, and combining the answers somehow.

Definition.
Let $X$ and $Y$ be spaces. The product $X\times Y$ consists of all pairs of elements from $X$ and $Y$: \[ X \times Y \Defeq \{(x,y) \mid x\in X,\, y\in Y \}. \]

The space $X\times Y$ is analogous to the tuple type [X, Y].

Examples

  • Suppose a user’s screen is $w$ pixels wide by $h$ pixels tall. The screen can be modelled by the space $[0, w]\times[0,h]$. The usual convention is that $(0,0)$ corresponds to the top left corner, but this is arbitrary. The order of the coordinates is also arbitrary: $[0,h]\times[0,w]$ would work just as well.

  • The set of playing cards can be viewed as \[\{\spadesuit,\heartsuit,\clubsuit,\diamondsuit\}\times\{\mathrm A,2,3,4,5,6,7,8,9,10,\mathrm J,\mathrm Q,\mathrm K\}\]

  • $\R^2=\R\times\R,\ \R^3=\R\times\R\times\R$, and so on. (See below about products of more than two spaces.)

  • a cube is $I\times I\times I$; $I\times S^1$ is a (hollow) cylinder; $S^1\times S^1$ is a (hollow) torus:

  • the $n$-dimensional unit cube is \[ I^n = \underbrace{I\times\dotsb\times I}_{n\text{ times}} \] This is harder to visualize in the same way as the cube above. But we can visualize it as $n$ slider controls.

Multiplication

Let’s explain why this operation is called multiplication. If $X$ is a finite set, we write $|X|$ for the number of elements of $X$, also called the cardinality or size of $X.$ For example, $|\{a,b,c\}|=3.$

When $X$ and $Y$ are finite sets, the size of $X\times Y$ is the product of the sizes of $X$ and $Y:$

\[ |X\times Y| = |X||Y|. \]

For instance, say we have three possible colors and four shapes. The number of possible colored shapes is $3\times4=12:$

\[ \{{\red{red}},{\green{green}},{\blue{blue}}\} \times \{\blacktriangle,\blacksquare,\bigstar,\bullet\} = \left\{\begin{matrix} \red\blacktriangle&\red\blacksquare&\red\bigstar&\red\bullet\\ \green\blacktriangle&\green\blacksquare&\green\bigstar&\green\bullet\\ \blue\blacktriangle&\blue\blacksquare&\blue\bigstar&\blue\bullet \end{matrix}\right\} \]

Associativity

One of the most important properties of ordinary multiplication (of numbers) is associativity: this is the property \[ (ab)c = a(bc). \] which means that the expression $abc$ is unambiguous. For example, we could evaluate $2\cdot3\cdot4$ as

\begin{align*} (2\cdot3)\cdot4 &= 6\cdot4 = 24\\ 2\cdot(3\cdot4) &= 2\cdot12 = 24 \end{align*}

and both give the same result.

Something similar is true for the product of spaces, but we have to be more careful. We can give a direct definition of $X\times Y\times Z$ a space of 3-tuples \[ X\times Y\times Z \Defeq \{(x,y,z) \mid x\in X,\, y\in Y,\, z\in Z\}, \] or we can build it out of products of two spaces at a time:

\begin{align*} (X\times Y)\times Z &= \{((x, y), z) \mid x\in X,\, y\in Y,\, z\in Z\}\\[.5em] X\times (Y\times Z) &= \{(x, (y, z)) \mid x\in X,\, y\in Y,\, z\in Z\} \end{align*}

These three options aren’t “literally” equal. As an analogy, in TypeScript, [X, Y, Z], [[X, Y], Z], and [X, [Y, Z]] are all different types. But there is an obvious way to go between them: \[ (x,y,z) \longleftrightarrow ((x,y),z) \longleftrightarrow (x,(y,z)). \] In math, we generally leave these conversions implicit, so we will write \[ (X\times Y)\times Z = X\times Y\times Z = X\times(Y\times Z). \]

I’ll say a bit more about this expanded view of equality a few posts from now.

In my area of math, there’s often a lot of work that needs to be done to keep track of all these implicit conversions. One of the difficulties is that when converting between $(X\times X)\times X$ and $X\times(X\times X)$, you don’t want to accidentally use the “wrong” conversion \[ ((x,y),z) \longleftrightarrow (z,(y,x)) \] (which wouldn’t typecheck for $(X\times Y)\times Z$ versus $X\times(Y\times Z)$)