Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove by Induction (Cardinality)

  1. Feb 6, 2010 #1
    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. jcsd
  3. Feb 6, 2010 #2


    User Avatar
    Science Advisor

    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 [tex]S_1'=S_1 \cup \{x\}[/tex], where x is some element not in S1.

    By definition, [tex]S_1'\times S_2=\{(a,b)|a\in S_1',b\in S_2\}[/tex].

    But this is equal to [tex]\{(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\}[/tex], where the union is disjoint. Therefore,

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

    Do you understand this? Are we finished with the induction proof?
  4. Feb 6, 2010 #3
    I understand it now. My problem was that I wasn't using the definition of the Cartesian product.

  5. Feb 6, 2010 #4


    User Avatar
    Science Advisor

    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?
  6. Feb 6, 2010 #5
    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?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook