Basic set theory proof about cardinality of cartesian product of two finite sets 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!
 A: 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.  
A: Let $\underline{n} = \{ 1,\dots,n\}$.
Define $\phi: \underline{|S||T|} \to \underline{|S|} \times \underline{|T|}$ by
$\phi(n) = \left(1+\frac{n-(n \mod |T|)}{|T|},1+(n \mod |T|) \right)  $.
This corresponds to dividing $n$ by $|T|$, taking the quotient and remainder, and adding one to both.
A little work shows that $\phi$ is a bijection – specifically, $\phi^{-1} (s,t) = (s-1)|T|+(t-1)$.
By definition of cardinality, there exists bijections $\sigma:\underline{|S|} \to S$,
$\tau:\underline{|T|} \to T$, so we define
$\xi: \underline{|S||T|} \to S \times T$ by
$\xi(n) = (\sigma([\phi(n)])_1, \tau([\phi(n)])_2 ) $.
It is straightforward to establish that $\xi \text{ is a bijection}$.
A: I would use a combinatorial argument. Note that $S \times T = \{ (s, t) : s \in S, t \in T \}$. So how many options are there for $s$? We choose one from $|S|$, giving us $|S|$ such options. Then for the $t$ element, there are $\binom{|T|}{1} = |T|$ option. Choosing $s$ and $t$ are done independently, so by rule of product, we multiply: $|S| \cdot |T|$. And so $|S \times T| = |S| \cdot |T|$. 
A: proof: First 
suppose that $S$ and $T$ are finite sets such that $|S| = n$ and $|T| = m$. Then the Cartesian product $S\times T$ is a finite set and $|S \times T| = mn$.
If either of $S$ and $T$ is empty then so is $S \times T$ and the result follows. So suppose that both sets are non-empty. 
Let $f:$ $\mathbb{N}_{n} \rightarrow S $ be a bijection and write $s_{i} = f(i)$ . Then
$ S$ = {$s_{1} , s_{2}, ...., s_{n}$} = $ \big\{s_{1}\big\}\cup \big\{s_{2}\big\} \cup ...\cup \big\{s_{n}\big\} $
and so $S\times T = (\big\{s_{1}\big\} \times T) \cup (\big\{s_{2}\big\} \times T) \cup ...\cup (\big\{s_{n}\big\} \times T).  $
But now, if $g: \mathbb{N}_{m} → T$ is a bijection, then $i \mapsto ( x_{k}, g(i))$ gives a bijection $ \mathbb{N}_{m} → T$ so that $|(\big\{s_{k}\big\} \times T)| = m$. 
Thus, these finite sets are pairwise disjoint, then the cardinality of these disjoint unions is equal  the sum of the cardinalities of these finite sets. Hence, it follows $|S \times T| = mn$
A: What is your definition of finite set?

Definition 1. Let $X$ be a set. Then the set $X$ is finite iff exists a $n\in \Bbb N$ such that $f\colon X\to \{i\in \Bbb N : 1\le i\le n\}$ is a bijection for some function $f$.

Hint. Let $|S|=n$ and $|T|=m$. Then use induction on $n$ (with $m$ fixed)
Note that for $n=0$, it is vacuously true.
Maybe you need the following lemma:
Lemma 2. Let $X$ be a finite set, and let $x$ be an object which is not an element of $X$. Then $X\cup \{x\}$ is finite and $|X\cup\{x\}|=|X|+1$. 
