Crossproduct (aka Cartesian product)

  • sets (cardinality)
  • tuples (basics)

One often wants to define an entire set of tuples. This can be done in various ways, but one of the most common is the crossproduct, also known as the Cartesian product.

Motivation and definition

Consider the colored objects depicted below: a blue square, a red square, a blue circle, and a red circle.

shapes.svg

We can represent each object as a pair \(\left \langle s,c \right \rangle\) where \(s\) and \(c\) are drawn from a set \(S \mathrel{\mathop:}=\left \{ \mathrm{square}, \mathrm{circle} \right \}\) of shapes and a set \(C \mathrel{\mathop:}=\left \{ \mathrm{blue}, \mathrm{red} \right \}\) of colors, respectively. The figure above contains every possible combination of those shapes and colors.

For any two sets \(A\) and \(B\), their crossproduct \(A \times B\) is defined as the set of all pairs \(\left \langle a,b \right \rangle\) such that \(a \in A\) and \(b \in B\). Generalizing from that, \(A_1 \times A_2 \times \cdots \times A_n\) is the set of all \(n\)-tuples \(\left \langle a_1, a_2, \ldots, a_n \right \rangle\) such that \(a_i \in A_i\) for every \(1 \leq i \leq n\).

Given \(S \mathrel{\mathop:}=\left \{ \mathrm{square}, \mathrm{circle} \right \}\) and \(C \mathrel{\mathop:}=\left \{ \mathrm{blue}, \mathrm{red} \right \}\), the crossproduct \(S \times C\) contains the pairs

  • \(\left \langle \mathrm{square}, \mathrm{blue} \right \rangle\),
  • \(\left \langle \mathrm{circle}, \mathrm{blue} \right \rangle\),
  • \(\left \langle \mathrm{square}, \mathrm{red} \right \rangle\), and
  • \(\left \langle \mathrm{circle}, \mathrm{red} \right \rangle\).

This is different from \(C \times S\), which contains

  • \(\left \langle \mathrm{blue}, \mathrm{square} \right \rangle\),
  • \(\left \langle \mathrm{blue}, \mathrm{circle} \right \rangle\),
  • \(\left \langle \mathrm{red}, \mathrm{square} \right \rangle\), and
  • \(\left \langle \mathrm{red}, \mathrm{circle} \right \rangle\).

Suppose \(S\) consists of John, Mary, and the old man, whereas \(V\) contains only slept and left. Compute \(S \times V\).

Now suppose that we also have a set \(A \mathrel{\mathop:}=\left \{ \mathrm{awesome} \right \}\). Then \(S \times C \times A\) would be a set containing the following triples:

  • \(\left \langle \mathrm{square}, \mathrm{blue}, \mathrm{awesome} \right \rangle\)
  • \(\left \langle \mathrm{circle}, \mathrm{blue}, \mathrm{awesome} \right \rangle\)
  • \(\left \langle \mathrm{square}, \mathrm{red}, \mathrm{awesome} \right \rangle\)
  • \(\left \langle \mathrm{circle}, \mathrm{red}, \mathrm{awesome} \right \rangle\)

List all 8 members of \(A \times C \times S \times A \times C \times A\).

If \(A\) has \(m\) members and \(B\) has \(n\) members, then the number of tuples in \(A \times B\) is \(m\) multiplied by \(n\). Explain why.

Exponent notation

Consider once more the general case of the crossproduct of \(n\) sets, i.e. \(A_1 \times \cdots \times A_n\). When all these sets are identical (i.e. \(A_i \mathrel{\mathop:}=A\) for all \(1 \leq i \leq n\)), then we may simply write \(A^n\) instead. In other words, \(A^n\) for the set of all \(n\)-tuples whose elements are drawn from \(A\).

Suppose \(A \mathrel{\mathop:}=\left \{ a,b \right \}\).

  • \(A^2 = A \times A = \left \{ a,b \right \} \times \left \{ a,b \right \} = \left \{ \left \langle a,a \right \rangle, \left \langle a,b \right \rangle, \left \langle b,a \right \rangle, \left \langle b,b \right \rangle \right \}\)
  • \(A^1 = A = \left \{ \left \langle a \right \rangle, \left \langle b \right \rangle \right \}\)

If \(A \mathrel{\mathop:}=\left \{ a \right \}\), then what is \(A^5\)?

If \(A \mathrel{\mathop:}=\left \{ \left \{ a \right \} \right \}\), then what is \(A^1\)?

Our definition only considers cases where \(n\) is at least \(1\). What should \(A^0\) be?

One motivation for the exponent notation is the following equivalence: \(\left | A^n \right | = \left | A \right |^n\). Explain what this means and why this holds.

In the previous unit, we observed that strings over \(\Sigma\) are the special case where all components of all tuples are drawn from a fixed alphabet \(\Sigma\). Explain why it makes sense under this view that we used \(\Sigma^n\) to denote the set of all strings of length \(n\).

Crossproduct \(\neq\) concatenation

You might think that crossproduct is the same thing as concatenation. And the two are indeed similar in the sense that neither is commutative — in general, \(A \times B\) is not the same as \(B \times A\), and \(u \cdot v\) is not the same as \(v \cdot v\).

Let \(A \mathrel{\mathop:}=\left \{ a,b \right \}\) and \(B \mathrel{\mathop:}=\left \{ 1 \right \}\). Then \(A \times B = \left \{ \left \langle a,1 \right \rangle, \left \langle b,1 \right \rangle \right \}\) whereas \(B \times A = \left \{ \left \langle 1,a \right \rangle, \left \langle 1,b \right \rangle \right \}\).

But while tuple concatenation is associative, the crossproduct operation is not. Most of the time, \(A \times B \times C\) and \(A \times (B \times C)\) and \((A \times B) \times C\) yield different results.

Let \(A \mathrel{\mathop:}=\left \{ a,b,c \right \}\), \(B \mathrel{\mathop:}=\left \{ T,F \right \}\), and \(C \mathrel{\mathop:}=\left \{ 1 \right \}\). Then \(A \times (B \times C)\) contains 6 pairs:

  • \(\left \langle a, \left \langle T,1 \right \rangle \right \rangle\)
  • \(\left \langle a, \left \langle F,1 \right \rangle \right \rangle\)
  • \(\left \langle b, \left \langle T,1 \right \rangle \right \rangle\)
  • \(\left \langle b, \left \langle F,1 \right \rangle \right \rangle\)
  • \(\left \langle c, \left \langle T,1 \right \rangle \right \rangle\)
  • \(\left \langle c, \left \langle F,1 \right \rangle \right \rangle\)

While \((A \times B) \times C\) also contains 6 pairs, they are different pairs:

  • \(\left \langle \left \langle a, T \right \rangle, 1 \right \rangle\)
  • \(\left \langle \left \langle a, F \right \rangle, 1 \right \rangle\)
  • \(\left \langle \left \langle b, T \right \rangle, 1 \right \rangle\)
  • \(\left \langle \left \langle b, F \right \rangle, 1 \right \rangle\)
  • \(\left \langle \left \langle c, T \right \rangle, 1 \right \rangle\)
  • \(\left \langle \left \langle c, F \right \rangle, 1 \right \rangle\)

And these, in turn, are completely different from \(A \times B \times C\), which contains 6 triples instead of 6 pairs:

  • \(\left \langle a, T, 1 \right \rangle\)
  • \(\left \langle a, F, 1 \right \rangle\)
  • \(\left \langle b, T, 1 \right \rangle\)
  • \(\left \langle b, F, 1 \right \rangle\)
  • \(\left \langle c, T, 1 \right \rangle\)
  • \(\left \langle c, F, 1 \right \rangle\)

Crossproduct = concatenation over sets of tuples

In a certain sense, though, there is still a principled connection between crossproduct and concatenation: crossproduct is the result of generalizing concatenation from tuples to sets of tuples. Given two such sets \(A\) and \(B\), we define \(A \cdot B\) as the set of all tuples \(a \cdot b\), where \(a \in A\) and \(b \in B\).

Consider the sets \(S' \mathrel{\mathop:}=\left \{ \left \langle \mathrm{square} \right \rangle, \left \langle \mathrm{circle} \right \rangle \right \}\) and \(C \mathrel{\mathop:}=\left \{ \left \langle \mathrm{blue} \right \rangle, \left \langle \mathrm{red} \right \rangle \right \}\). By our definition, \(S' \cdot C'\) is a new set \(SC'\) that consists of the following tuples:

  • \(\left \langle \mathrm{square} \right \rangle \cdot\left \langle \mathrm{blue} \right \rangle = \left \langle \mathrm{square}, \mathrm{blue} \right \rangle\),
  • \(\left \langle \mathrm{circle} \right \rangle \cdot\left \langle \mathrm{blue} \right \rangle = \left \langle \mathrm{square}, \mathrm{blue} \right \rangle\),
  • \(\left \langle \mathrm{square} \right \rangle \cdot\left \langle \mathrm{red} \right \rangle = \left \langle \mathrm{square}, \mathrm{red} \right \rangle\),
  • \(\left \langle \mathrm{circle} \right \rangle \cdot\left \langle \mathrm{red} \right \rangle = \left \langle \mathrm{square}, \mathrm{red} \right \rangle\).

And then \(SC' \cdot A'\), where \(A' \mathrel{\mathop:}=\left \{ \left \langle \mathrm{awesome} \right \rangle \right \}\), yields:

  • \(\left \langle \mathrm{square}, \mathrm{blue} \right \rangle \cdot\left \langle \mathrm{awesome} \right \rangle = \left \langle \mathrm{square}, \mathrm{blue}, \mathrm{awesome} \right \rangle\),
  • \(\left \langle \mathrm{circle}, \mathrm{blue} \right \rangle \cdot\left \langle \mathrm{awesome} \right \rangle = \left \langle \mathrm{circle}, \mathrm{blue}, \mathrm{awesome} \right \rangle\),
  • \(\left \langle \mathrm{square}, \mathrm{red} \right \rangle \cdot\left \langle \mathrm{awesome} \right \rangle = \left \langle \mathrm{square}, \mathrm{red}, \mathrm{awesome} \right \rangle\),
  • \(\left \langle \mathrm{circle}, \mathrm{red} \right \rangle \cdot\left \langle \mathrm{awesome} \right \rangle = \left \langle \mathrm{circle}, \mathrm{red}, \mathrm{awesome} \right \rangle\).

But if you compare these to the relevant examples above, you’ll notice that \(S' \cdot C' = S \times C\), and \(SC' \cdot A = S' \cdot C' \cdot A' = S \times C \times A'\).

The crossproduct \(A \times B\) is the empty set if at least one of \(A\) and \(B\) is empty. Explain why this makes sense both under our original definition of crossproduct and the view of crossproduct as concatenation over sets of tuples.

If \(S' \cdot C' \cdot A' = S \times C \times A\), then what does \((S \times C) \times A\) correspond to?

Why “Cartesian product”

As mentioned above, the crossproduct is also known as the Cartesian product. Why is that?

Consider the special case of \(\mathbb{N} \times \mathbb{N}\), i.e. \(\mathbb{N}^2\). Here \(\mathbb{N} \mathrel{\mathop:}=\left \{ 0, 1, 2, 3, \ldots \right \}\) is the set of all natural numbers. So \(\mathbb{N} \times \mathbb{N}\) is the set of all possible pairs of natural numbers. We can take these two components to represent \((x,y)\)-coordinates in the upper right quadrant of a coordinate system.

Now suppose that we replace \(\mathbb{N}\) with \(\mathbb{R}\), the set of all real numbers (this includes 0, 1, -1, -3.5723, \(\pi\), \(\sqrt{2}\), and much more). Then \(\mathbb{R}^2\) is the familiar coordinate system with an infinite negative \(x\)-axis centered around 0, and an infinite \(y\)-axis centered around 0. Such a coordinate system is also called a Cartesian plane, and that is why the crossproduct is sometimes called the Cartesian product.

By the way, this notation is also used a lot in machine learning, where \(\mathbb{R}^n\) is a coordinate system with \(n\) axes. For example, \(\mathbb{R}^3\) is the result of adding a \(z\)-axis to \(\mathbb{R}^2\). Then \(\mathbb{R}^4\) adds a fourth axis, which can no longer be visualized in the usual way because humans’ spatial thinking isn’t well-adapted to dealing with more than three dimensions. Modern machine learning techniques often operate with systems that have hundreds of axes.

Recap

Given sets \(A_1\), , \(A_n\), their crossproduct \(A_1 \times A_2 \times \cdots \times A_n\) is the set of all \(n\)-tuples \(\left \langle a_1, a_2, \ldots, a_n \right \rangle\) such that \(a_i \in A_i\) for every \(1 \leq i \leq n\).