1

Proposition 2.6 (Rule of Product). Let T be a set of ordered k-tuples ($a_1$, ..., $a_k$), with the property that there are $r_i$ choices for each coordinate between 1 $\leq$ i $\leq$ k. Then |T| = $r_1$$r_2$ ... $r_k$.

I am taking an introductory discrete mathematics course, and we are learning the cardinality of sets in the form of the product.

This is one of the propositions I read in my lecture notes, I am having a hard time understanding its content.

Suppose I have a set of an ordered 2-tuples called S, if I understand this correctly, S is like S = {(1, 1), (1, 2), (2, 1,), (2, 2)}, so in this case, |S| = 4. I don't understand the part in the propostion that says we have $r_i$ choices for each coordinate between 1 $\leq$ i $\leq$ k, what does this coordinate mean? Is it each tuple in my set S? In addition, what does "we have $r_i$ choices for each coordinate between 1 $\leq$ i $\leq$ k" mean? Why is it $r_i$ choices?

Thanks.

Metaozis
  • 177

1 Answers1

2

They are not coordinates in the sense you learn in calculus.

Suppose you have to count the pairs $(A,B)$ where $A$ is a color (red, white or blue) and $B$ is a shape, say circle or start. In the rectangle 

       circle   star
red       *       *
white     *       *
blue      *       *

you can think of "shape" as a coordinate on the horizontal axis and "color" as one on the vertical axis. With that picture it's easy to see $2 \times 3 = 6$.

Ethan Bolker
  • 95,224
  • 7
  • 108
  • 199
  • Correct me if I understand this incorrectly please and thanks.

    $A_1$ = {red, white, blue}, $A_2$ = {circle, star}. So based on the proposition above, T is just like the cartesian product $A_1$ x $A_2$, so in this case we have a set of ordered 2-tuples, which is T. The $r_i$ choices for each coordinate just means the cardinality of each $A_1$ and $A_2$, which in this case are 2 and 3. So |T| = 2 x 3.

     – Metaozis Jan 21 '19 at 02:10
  • That's right. $T$ isn't "just like" the cartesian product - it is the cartesian product. – Ethan Bolker Jan 21 '19 at 12:44