2.6 Associations: tuples and Cartesian products
Consider an item of shopping that is weighed at the supermarket checkout, such as 335 grams of walnuts. This item of shopping has two features: the type of item purchased (walnuts), and the weight of that item (335 grams). To record a weighed item of shopping we need to note both these features. This can be done using an ordered pair: (“WALNUTS”, 335).
The first item in this ordered pair gives the type of item purchased. Let WeighedItems be the set of items stocked by the supermarket that need to be weighed. The first item comes from this set, while the second item in the ordered pair comes from the set Int.
We call the set containing all such pairs the Cartesian product of the two sets. (‘Cartesian’ after the famous French philosopher and mathematician René Descartes.) This set of pairs is written as WeighedItems × Int. So the set WeighedItems × Int consists of all pairs (w, n), where w comes from the set WeighedItems, and n comes from the set Int. We refer to (w, n) as an ordered pair. The word pair here indicates that there are two items grouped together. The word ordered indicates that the order in which the two items are given matters. The pair (“WALNUTS”, 335) is not the same as the pair (335, “WALNUTS”). Similarly, the set WeighedItems × Int is different from the set Int × WeighedItems, which consists of pairs giving: first an integer, then a type of weighed item.
Use of the symbol × here has nothing to do with multiplication of numbers!
We can form the Cartesian product of any two sets. The Cartesian product of sets X and Y is written as X × Y , and consists of all ordered pairs (x, y) where x is from the set X and y is from the set Y. X × Y can be read as “ X cross Y”.
An ordered pair gives an association between two items. There are situations where we may want to associate more than two things. Consider items stocked by the supermarket that have barcodes. The supermarket will be interested in a number of features associated with each item of this type. Three such features are:
The barcode (taken to be an integer).
The name of the item, to be printed on the till receipt (as a string).
The price of an item of this type (taken to be an integer number of pence).
A natural way to associate these three features is to write them together as an ordered triple, or 3-tuple, such as (13151, “ORGANIC SOUP”, 179). Note the use of round brackets here. These are used for tuples, in distinction to square brackets [ and ] for sequences, or curly brackets { and } for sets. The terminology ‘ordered triple’ indicates that we are now writing three items, each from a specified set, in a given order. We may want to associate four items, or five, or more. The terminology ‘tuple’ extends conveniently to this general case, where we talk about 4-tuples, or 5-tuples, and, in general, n-tuples (where n might be 2, or 3, or any larger integer).
The set of all 3-tuples of the same form as (13151, “ORGANIC SOUP”, 179) is again a Cartesian product, in this case a product of three sets. The barcode is from Int, the item name is a string (from SeqOfChar) and the price is an integer. So this 3-tuple comes from the set Int × SeqOfChar × Int.
Activity 8
Taking the code for olive oil as 43202, and referring to the receipt in Figure 2, write down the ordered triple from the set Int × SeqOfChar × Int that represents the association between the code, the description and the price of the olive oil.
Discussion
Making sure that the description is written as a string, and that the price is in pence, the triple should be (43202, “OLIVE OIL”, 178).
As another example, suppose that a shop has just three members of staff, Jo, Jessica and Wesley, and just two tills, T1 and T2. We could represent a situation where Jo is operating the till T2 by the ordered pair, or 2-tuple (T2, Jo). Clearly, there are a variety of ways in which a member of staff can be assigned to a till. If Tills is the set {T1, T2} and Staff is the set {Jo, Jessica, Wesley}, then the set of all possible assignments of a member of staff to a till is Tills × Staff . If we write this set out in full, we obtain:
Tills × Staff = {(T1, Jo), (T1, Jessica), (T1, Wesley), (T2, Jo), (T2, Jessica), (T2, Wesley)}.
Note the use of different brackets: curly brackets delimit the set, round brackets delimit each of the tuples. Note also that the use of Tills × Staff to represent assignment of a staff member to a till means that we must write the till first in each ordered pair.
Activity 9
(a) Give an example of a member of the set Staff × Tills.
(b) If the supermarket were to install another till, and recruit two more members of staff, and we redefine the sets Staff and Tills to include these, how many ordered pairs would be in the set Tills × Staff?
Discussion
(a) In Staff × Tills, the member of staff should be given first. Suitable examples would be (Jo, T1), or (Wesley, T2).
(b) There would then be 3 tills and 5 staff. Each till can appear with each member of staff in an ordered pair, so there would be 3 × 5 = 15 ordered pairs in Tills × Staff.