Prove the size of the result of a cartesian product is equal to the product of the size of the two sets. We want to show:
$$|S_1 \times S_2| = |S_1| \cdot |S_2|$$
I am not sure how to go about showing this in general terms. I believe that we will need to use the definition of the cartesian product during this, so that is where I am at right now.
$$S_1 \times S_2 = \{(a,b): a \in S_1 \; \text{and} \; b \in S_2\}$$
These are finite sets.
 A: Say $S_1 = \{a,b\}$ and $S_2=\{x,y,z\}$.  Then
$$
S_1\times S_2= \big\{ (a,x),\ (a,y),\ (a,z),\ (b,x),\ (b,y),\ (b,z) \big\}.
$$
So you can look at it in either of two ways:
$$
\big\{ \underbrace{(a,x),\ (a,y),\ (a,z)},\ \underbrace{(b,x),\ (b,y),\ (b,z)} \big\}.
$$
$$
\big\{ \underbrace{(a,x),\ (b,x)},\ \underbrace{(a,y),\ (b,y)},\ \underbrace{(a,z),\ (b,z)} \big\}
$$
The first is a sum of two $3$s; the second is a sum of three $2$s.  So the first is $2\times3$ and the second is $3\times 2$.  That's one way of knowing that $2\times3$ is the same number as $3\times2$.
$$
|S_1|\times|S_2| = \sum_{a\in S_1}\ \sum_{x\in S_2}\ 1 = \sum_{(a,x)\in S_1\times S_2} \  1.
$$
A: If $|S_1| = m$ and $S_2 =n$, you could show this by creating a bijection,
$$\phi : S_1 \times S_2 \mapsto \{1, 2, \ldots, mn \} $$
If you're familiar with the concept of row/column - major ordering for storing matrices as a flat array, there is a natural mapping to use. Denote the elements of $S_1$ as $a_1, \ldots, a_m$, and elements of $S_2$ as $b_1, \ldots, b_n$. Then imagining the pairs of elements in an $m \times n$ matrix, use the column-major mapping:
$$\phi(a_i,b_j) = n(i-1) + j$$
You'll have to fool around with some modular arithmetic to give the inverse.
