1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Proof by induction: multiplication of two finite sets.

  1. Oct 6, 2012 #1
    1. The problem statement, all variables and given/known data

    prove by induction that if A and B are finite sets, A with n elements and B with m elements, then AxB has mn elements

    2. Relevant equations
    AxB is the Cartesian product. AxB={(a,b) such that a is an element of A and b is an element of B}

    3. The attempt at a solution
    normally, proof by induction involves one variable. here it includes two. I guess I could say that mn=nm and therefore proving it for n+1 is the same thing as proving it for m+1. Then any increase in m or n after that is just the same thing. But somehow I still feel this isn't really justifiable.
  2. jcsd
  3. Oct 6, 2012 #2


    User Avatar
    Homework Helper

    So induction has three steps. Where you assume the case n = 1, the induction assumption and then the proof for the n+1 case.

    Case : n = 1 = m

    Assume that A and B have one element in each corresponding set. Say A = {(a0,b0)} and B = {(c0,d0)} and go from here.
    Last edited: Oct 6, 2012
  4. Oct 6, 2012 #3
    yeah, but how do I prove that if it is true for the n+1 case, it is also true for the m+1 case. and what if m+1 and n+1 are occurring at the same time?

    I guess what I'm asking is, if I prove it true for the n+1 case (which is pretty easy), then how do I show that this means I can add one element to A and B as desired and the result mn would still be valid.
  5. Oct 6, 2012 #4


    User Avatar
    Homework Helper

    That's the beauty of induction. Imagine if you held the amount of elements in B constant the whole time. Would it change your outcome?

    Remember that proving something n+1 times is sufficient when thinking about this.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook