Please Login to access more options.
Problem 50: (Induction And Cardinality Of Cartesian Products)
If $A$ and $B$ are finite sets, then we have discussed in class why the cardinality of $A\times B$ is given by $$|A\times B|=|A|\cdot |B|.$$ Use induction to prove that for every $n\in \mathbb{N}$ if $A_1, A_2, \ldots, A_n$ are finite sets, then we have $$|A_1\times A_2\times\cdots\times A_n|=|A_1|\cdot|A_2|\cdots|A_n|.$$
The first part of your proof should begin something like the following:
For each $n\in\mathbb{N}$ let $P(n)$ be the statement $$\text{"if $A_1, A_2, \ldots, A_n$ are finite sets, then we have }
|A_1\times A_2\times\cdots\times A_n|=|A_1|\cdot|A_2|\cdots|A_n|."$$ We know that $P(1)$ is true because .... Now assume that for some $k\in \mathbb{N}$ that $P(k)$ is true. This means we have assumed that "if ... then ...". We must prove that "if ... then ...". We've got to prove an if-then statement is true, so we should start by assuming the antecedent is true. So assume that $A_1, A_2, \ldots, A_k, A_{k+1}$ are finite sets. We now have to show that ... is true. (Then continue your work. Clearly I've left some holes to be filled in above.)
The following pages link to this page.
Here are the old pages.