# Proof by induction: multiplication of two finite sets.

## 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 Helper

## 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 = {(a0,b0)} and B = {(c0,d0)} and go from here.

Last edited:
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
Homework Helper
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.