Prove by Induction (Cardinality)

1. Feb 6, 2010

sessomw5098

If S1 and S2 are finite sets, show that |S1 x S2| = |S1||S2|.

Here is what I've tried:

Let |S1| = m and |S2| = n.
Let P(k) be true. That is, P(k) = |S1 x S2| = km.

P(1) is true since, if |S1| = 1 and |S2| = 1, |S1 x S2| = 1.

Now, let |S1| = k+1 and |S2| = m. Then, P(k+1) = |S1 x S2| = (k+1)m ??

This is as far as I have gotten.

2. Feb 6, 2010

Landau

Well, you just wrote down the thing you want to prove, so you haven't really done anything :P

Somewhere you're going to have to use the definition of the cartesian product. We assume P(k) to be true, so for |S1|=k we have |S1 x S2|=km. Now we want to show that for |S1'|=k+1 we have |S1' x S2|=(k+1)m. Write $$S_1'=S_1 \cup \{x\}$$, where x is some element not in S1.

By definition, $$S_1'\times S_2=\{(a,b)|a\in S_1',b\in S_2\}$$.

But this is equal to $$\{(a,b)|a\in S_1,b\in S_2\}\ \cup\ \{(x,b)|b\in S_2\}=(S_1\times S_2)\ \cup\ \{(x,b)|b\in S_2\}$$, where the union is disjoint. Therefore,

$$|S_1'\times S_2|=|S_1\times S_2|+|\{(x,b)|b\in S_2\}|=km+m=(k+1)m$$, where we have applied the induction hypothesis $$|S_1 \times S_2|=km$$.

Do you understand this? Are we finished with the induction proof?

3. Feb 6, 2010

sessomw5098

I understand it now. My problem was that I wasn't using the definition of the Cartesian product.

Thanks!

4. Feb 6, 2010

Landau

You're welcome. You have used induction on the cardinality of S1. Do you also need to use induction on the cardinality of S2? In other words, do you think the proof is finished now?

5. Feb 6, 2010

sessomw5098

Well, I think the proof is complete because we hold one constant while "inducting" the other. We can assume the converse is true due to "without loss of generality."

Am I right?