Proof by induction: multiplication of two finite sets.

[whyme1010]

Homework Statement

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

Homework Equations

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

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.

 

[STEMucator]

Homework Statement

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

Homework Equations

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

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.

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 = {(a₀,b₀)} and B = {(c₀,d₀)} and go from here.

 

[whyme1010]

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.

 

[STEMucator]

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.

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.