I'm really lost on how to do this proof:
If $S$ and $T$ are finite sets, show that $|S\times T| = |S|\times |T|$.
(where $|S|$ denotes the number of elements in the set)
I understand why it is true, I just can't seem to figure out how to prove it.
Any hints/help will be greatly appreciated!
Best Answer
OK here is my definition of multiplication:
$$m\cdot 0=0$$ $$m\cdot (n+1)=m\cdot n +m$$
(you need some such definition to prove something so basic.) Now let $|T|=m$ and $|S|=n$.
If $n=0$ then $S=\emptyset $ and so $T\times S=\emptyset$ and we are done by the first case. If $n=k+1$ let $s \in S$ be any element and let $R=S -\{s\}$ then $|R|=k$ and by induction we have $|T\times R|=m\cdot k$.
Now $$T\times S=T\times R \cup T\times \{s\}$$ Now $|T\times \{x\}|=m$ is easy to prove. Further $T\times R$ and $T\times \{s\}$ are disjoint, so the result follows from the second case and an assumed lemma about the cardinality of disjoint unions being the sum of the cardinalities of the sets.