Proof by induction: multiplication of two finite sets.

  • Thread starter whyme1010
  • Start date
  • #1
16
0

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.
 

Answers and Replies

  • #2
STEMucator
Homework Helper
2,075
140

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:
  • #3
16
0
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.
 
  • #4
STEMucator
Homework Helper
2,075
140
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.
 

Related Threads on Proof by induction: multiplication of two finite sets.

  • Last Post
Replies
3
Views
1K
Replies
3
Views
10K
Replies
2
Views
1K
  • Last Post
Replies
6
Views
869
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
2
Views
753
  • Last Post
Replies
8
Views
1K
  • Last Post
Replies
16
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
912
Top