Prove by Induction (Cardinality)

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

 

[Landau]

Let P(k) be true. (...)
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.

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?

 

[sessomw5098]

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

Thanks!

 

[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?

 

[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?