﻿ Cartesian Product

Readings for Session 9 – (Continued)

The Language of Sets — Cartesian Product

Consider the following array of ordered pairs of numbers where the first number is the row number and the second number in the pair is the column number. Note the shaded box is in the second row and fourth column represented with the ordered pair (2, 4).

 (1, 1) (1, 2) (1, 3) (1, 4) (1, 5) (2, 1) (2, 2) (2, 3) (2, 4) (2, 5) (3, 1) (3, 2) (3, 3) (3, 4) (3, 5)

We note that the table has 3(5) = 15 small rectangular regions. We develop this concept in terms of a set operation that will be used to define multiplication.

Ordered Pair:  An ordered pair is a pair of objects where one element is designated first and the other element is designated second, denoted (a, b).

Cartesian Product: The Cartesian product of two sets A and B, denoted A × B, is the set of all possible ordered pairs where the elements of A are first and the elements of B are second.

In set-builder notation,  A × B = {(a, b) : a A and b B}.

Example:  Let A = {H, T} and B = {1, 2, 3, 4, 5, 6}.

A × B  = {(H, 1), (H, 2), (H, 3), (H, 4), (H, 5), (H, 6), (T, 1), (T, 2), (T, 3), (T, 4), (T, 5), (T, 6)}

B × A = {(1, H), (2, H), (3, H), (4, H), (5, H), (6, H), (1, T), (2, T), (3, T), (4, T), (5, T), (6, T)}

Note that in this case A × B B × A, i.e., the Cartesian product is not commutative.
Also, note that n(A)
n(B) = 2(6) = 12 = n(A × B).

Example:  A ×   =   since no ordered pairs can be formed when one of the sets is empty.

Also, note that n(A) n() = 2(0) = 0 = n(A × ).

Cartesian Product Definition for Multiplication of Whole Numbers.  Let A and B be two finite sets with a = n(A) and b = n(B). Then ab = n(A ´ B).   The numbers a and b are called factors and ab is the product.

Two common methods for illustrating a Cartesian product are an array and a tree diagram.

Example:  A small village has four streets and five avenues laid out in a rectangular grid. How many intersections are there?

We have two sets, streets (S) and avenues (A). The elements from the two sets form a list of ordered pairs such as the intersection of 1st Street and 2nd Avenue, (1, 2). We have

4(5) = n(S) n(A) = n(S × A) = 20.

There are twenty intersections in the small town.

Example:  In algebra the rectangular or Cartesian coordinate plane is an example of the Cartesian product. We consider the set of all the ordered pairs describing locations in the plane. Example:   A couple is planning their wedding. They have four nieces (Ann, Betty, Cathy, and Deanne) and three nephews (Ed, Fred, and Gill). How many different pairings are possible to have one boy and one girl as a ring bearer and flower girl? Note that this problem may be considered as either a repeated addition problem or a Cartesian product problem.

Repeated addition:  Each niece may be considered to be a set that contains three nephews, so 4(3) = 3 + 3 + 3 + 3 = 12.

Cartesian product: {(A, E), (A, F), (A, G), (B, E), (B, F), (B, G), (C, E), (C, F), (C, G), (D, E), (D, F), (D, G)}

4(3) = n(nieces) n(nephews) = n(nieces × nephews) = 12

The couple has twelve choices for one ring bearer and one flower girl. 