# 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!

• Why don't you start by the definition of $S \times T$? What are the elements of this set? How many such elements can you construct? – megas Dec 10 '14 at 2:10
• More to the point is how have you defined multiplication $m\cdot n$ ? – Rene Schipperus Dec 10 '14 at 2:25
• I don't really understand how we can know how many elements are in the set. I know we can say there there is a s∈S & t∈T but I don't know how to work with that. – Zoë Soriano Dec 10 '14 at 2:29
• Your definition of multiplication is crucial. There's different ways you could define it - you could even define multiplication using the formula you're trying to solve (with infinite cardinals you do it that way anyway). Then it would become trivial to prove the formula. – skyking Oct 27 '15 at 7:42

## 5 Answers

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.

Let $\underline{n} = \{ 1,...,n\}$.

Define $\phi: \underline{|S||T|} \to \underline{|S|} \times \underline{|T|}$ by $\phi(n) = (1+{n-(n \mod |T|) \over |T|}, n \mod |T|)$. A little work shows that $\phi$ is a bijection (specifically, $\phi^{-1} (s,t) = (s-1)|T|+t$).

There are 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$ is a bijection.

• +1 for giving a proof which doesn't involve a handwave; do you know of any books which give proofs of basic facts similar to this one in such a rigorous manner? – flakmonkey May 24 '15 at 18:54
• @flakmonkey: I don't , sorry. – copper.hat May 25 '15 at 0:09

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|$.

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$

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$.