1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – megas Dec 10 '14 at 2:10
  • 2
    $\begingroup$ More to the point is how have you defined multiplication $m\cdot n$ ? $\endgroup$ – Rene Schipperus Dec 10 '14 at 2:25
  • $\begingroup$ 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. $\endgroup$ – Zoë Soriano Dec 10 '14 at 2:29
  • $\begingroup$ 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. $\endgroup$ – skyking Oct 27 '15 at 7:42
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ +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? $\endgroup$ – flakmonkey May 24 '15 at 18:54
  • $\begingroup$ @flakmonkey: I don't , sorry. $\endgroup$ – copper.hat May 25 '15 at 0:09
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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$

$\endgroup$
-1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.