Prove that $|S_1\times S_2|=|S_1|\times|S_2|$ I want to prove that $|S_1\times S_2|=|S_1|\times|S_2|$. Both $S_1$ and $S_2$ are finite sets.
I'm not very familiar with set theory and this kind of proofs, but this is what I've done:
I know $S_1 \times S_2$ contains $(x,y)$ pairs where $x \in S_1$ and $y \in S_2$. I should take every element in $S_1$ with all elements in $S_2$. So if $|S_1|=n$ and $|S_2|=m$, then $|S_1\times S_2|$ contains $mn$ elements which is equal to $|S_1|\times|S_2|$.
Is this reasoning right?
 A: The general idea is this: we take a partition (think of it as non-empty subsets of $\left |S_1 \times S_2 \right |$, but without overlaps) of $\left |S_1 \times S_2 \right |$. Prove that each partition has $\left |S_1 \right |$ elements, and there are $\left |S_2 \right |$ of such partitions, so intuitively, there are a total of $\left | S_1 \right | \times \left |S_2 \right |$ elements in $\left |S_1 \times S_2 \right |$. 
This is the simplified idea. The formal proof is this: 
Let $\left |S_1 \right | = x$ and $\left |S_2 \right | = y$. First we check the base case (that is, when either $x$ or $y$ is 0). If either $x$ or $y$ equals 0 then $S_1 \times S_2 = \emptyset$. Then $\left |S_1 \times S_2 \right |$ is definitely 0, hence the base case is true. 
Assuming $x,y > 0$, for any $s_1 \in S_1$, we define the map $f: S_2 \rightarrow \{s_1\} \times S_2$, with $S_2$ as the domain and the cross product $\{s_1\} \times S_2$ as the codomain, defined by the following: 
\begin{equation}
f(s_2)=(s_1,s_2), \quad s_2 \in S_2
\end{equation} 
So $f$ is a bijective map from $S_2$ to $\{s_1\} \times S_2$. Hence $\left | \{s_1\} \times S_2 \right | = \left | S_2 \right | = y$.
Now we define a new set $X := \left\{{\left\{{s_1}\right\} \times S_2: s_1 \in S_1}\right\}$. Define the map $g:S_1 \rightarrow X$, with $S_1$ as the domain and $X$ as the codomain, defined by the following: 
\begin{equation}
g(s_1) = \{ s_1 \} \times S_2, \quad s_1 \in S_1
\end{equation}
So $g$ is a bijective map from $S_1$ to $X$. Hence $\left | X \right | = \left | S_1 \right | = x$.
We note that each set $X$ is a partition of the cross product $S_1 \times S_2$, with each $X$ containing $x$ elements, and a total of $y$ of such $X$. Hence it follows that $\left |S_1 \times S_2 \right | = x \times y = \left | S_1 \right | \times \left |S_2 \right |$.
