Concepts: Cartesian products and relations

2.1 Why order matters

A set does not care about order, but many everyday objects carry order inside them. A seat on a train is a row number together with a seat letter, and seat B3 is not the same as seat 3B. Mathematics captures this with the ordered pair, written inside round brackets. The first entry comes from the first set and the second entry comes from the second set.

Two ordered pairs are equal exactly when both positions agree. So (x + 1, y - 2) = (3, 1) gives two small equations, x + 1 = 3 and y - 2 = 1, and the solution is x = 2, y = 3. This equality rule turns many exam questions into simple linear equations.

A product can go beyond two sets. The ordered triple (a, b, c) collects one entry from each of three sets, and A x A x A is the collection of all such triples.

2.2 Cartesian products

The Cartesian product P x Q contains every ordered pair whose first entry lies in P and second entry lies in Q. For A = {red, blue} and B = {bag, coat, shirt}, the product has six pairs: red with each of the three objects, then blue with each of the three. Each choice from the first set pairs with every choice from the second, so the counts multiply. With p objects in the first set and q in the second, the product has pq members.

The product is not commutative. For P = {a, b, c} and Q = {r}, the product P x Q holds (a, r), (b, r) and (c, r), while Q x P holds (r, a), (r, b) and (r, c). Both contain three pairs, yet the entries are swapped, so the two products are different sets.

Products interact with set operations in a predictable way. The product distributes over union and intersection, so A x (B intersection C) equals the intersection of A x B and A x C, and the same holds with union. These two identities are stated as facts you should verify with small sets in Exercise 2.1.

2.3 From pairs to relations

A relation from A to B is a subset of A x B. Every pair in the relation satisfies some stated link between the two entries, and every pair outside it does not. The link might be a formula, a table or a sentence such as the first letter of the name.

Take P = {a, b, c} and Q as a set of five names. The product has fifteen pairs. Declare that a letter points to a name beginning with that letter. Then a pairs with Ali, b pairs with Bhanu and with Binoy, and c pairs with Chandra, while the other eleven pairs are dropped. The four kept pairs form the relation R.

Three sets describe a relation. The domain holds the first entries of the kept pairs, the range holds the second entries, and the codomain is the whole target set B. Because some elements of B may never appear as a second entry, the range can be a proper subset of the codomain. An arrow diagram shows the domain and codomain as two columns and draws an arrow for each kept pair.

2.4 Reading a relation backwards

A relation can also be handed to you as a picture, and the job is to translate it into set-builder form or roster form. Look at which points are joined. If the arrows run from each x in P to values in Q, read off the pairs first, then decide whether a formula links them.

In one standard picture the pairs are (9, 3), (9, -3), (4, 2), (4, -2), (25, 5) and (25, -5). Every second entry squares to the first, so a correct set-builder description is the set of pairs (x, y) with x equal to y squared. The domain is {4, 9, 25}, the range is {-5, -3, -2, 2, 3, 5}, and the codomain is the whole target set. One element of the target set may be paired with nothing, and that is allowed; a relation need not use every element.

Exercises on relations usually ask for the roster with a rule attached. Read the rule, list admissible first entries, then pair each with every second entry that satisfies the rule.

2.5 Counting relations

Because a relation is a subset of the product, counting relations is counting subsets. If the product has pq pairs, it has 2 to the power pq subsets, so that is the number of possible relations from A to B. For A = {1, 2} and B = {3, 4}, the product has four pairs and the number of relations is 16.

This count includes the empty relation and the full product. The empty relation pairs nothing, and the full product pairs everything with everything. A question that asks for relations with a particular property narrows the count, often by a direct listing instead of the power of two.

Exercise 2.2 also gives relations in formula form. With A = {1, 2}, the condition y = x + 5 needs x = 1 and x = 2, giving pairs (1, 6) and (2, 7), so the domain is {1, 2} and the range is {6, 7}. For divisibility relations, test each pair or fix the first entry and list its multiples inside the set.

2.6 Worked checks for this page

Three patterns appear in Exercise 2.1 and Exercise 2.2.

First, equal pairs. If (x/3 + 1, y - 2/3) = (5/3, 1/3), match entries to get x/3 + 1 = 5/3 and y - 2/3 = 1/3, which give x = 2 and y = 1.

Second, a product from a roster. Suppose the printed product lists two first values p and m combined with two second values q and r in every possible way. Then the first set is {p, m} and the second set is {q, r}. Read the first coordinates as one set and the second coordinates as the other, with repeats removed.

Third, when a rule is described in words, list the pairs that satisfy it. Take A = {1, 2, 3, 5} and the condition that one entry of the pair is even while the other is odd. Checking the choices gives the roster of valid pairs, and the domain and range are read from that roster.