Cartesian Products and Relations — Worked Solutions

Ques­tion 1: Equal ordered pairs#

The prob­lem#

Find $x$ and $y$:

(a) $(2x + 1,\ y - 3) = (7,\ 5)$

(b) $\displaystyle \left(\frac{x}{3} + 1,\ y - \frac{2}{3}\right) = \left(\frac{5}{3},\ \frac{1}{3}\right)$

Under­stand­ing the prob­lem#

Two ordered pairs are equal only when their first entries are equal and their sec­ond entries are equal. Each part there­fore gives two sim­ple equa­tions.

The idea#

Use $(a, b) = (c, d) \iff a = c$ and $b = d$.

Step-by-step solu­tion#

Part (a)

Step 1. Equate the first entries and solve for $x$.

$$2x + 1 = 7 \;\Rightarrow\; 2x = 6 \;\Rightarrow\; x = 3$$

Step 2. Equate the sec­ond entries and solve for $y$.

$$y - 3 = 5 \;\Rightarrow\; y = 8$$

Part (b)

Step 1. First entries:

$$\displaystyle \frac{x}{3} + 1 = \frac{5}{3} \;\Rightarrow\; \frac{x}{3} = \frac{5}{3} - 1 = \frac{2}{3} \;\Rightarrow\; x = 2$$

Step 2. Sec­ond entries:

$$\displaystyle y - \frac{2}{3} = \frac{1}{3} \;\Rightarrow\; y = \frac{1}{3} + \frac{2}{3} = 1$$

Check­ing the answer#

(a) $(2 \cdot 3 + 1,\ 8 - 3) = (7, 5)$. (b) $\displaystyle \left(\tfrac{2}{3} + 1,\ 1 - \tfrac{2}{3}\right) = \left(\tfrac{5}{3}, \tfrac{1}{3}\right)$. Both match.

Answer#

(a) $x = 3$, $y = 8$ (b) $x = 2$, $y = 1$

Ques­tion 2: Writ­ing $A \times B$ and $B \times A$#

The prob­lem#

$A = \{-1, 1\}$, $B = \{0, 2, 4\}$. Write $A \times B$ and $B \times A$. Are they equal?

Under­stand­ing the prob­lem#

$A \times B$ is the set of all ordered pairs whose first entry comes from $A$ and sec­ond entry from $B$. $B \times A$ reverses the roles.

The idea#

List sys­tem­at­i­cally: fix the first entry, run through all sec­ond entries, then move to the next first entry. Expect $n(A)\,n(B) = 2 \times 3 = 6$ pairs each time.

Step-by-step solu­tion#

Step 1. Pair each ele­ment of $A$ with each ele­ment of $B$.

$$A \times B = \{(-1, 0), (-1, 2), (-1, 4), (1, 0), (1, 2), (1, 4)\}$$

Step 2. Pair each ele­ment of $B$ with each ele­ment of $A$.

$$B \times A = \{(0, -1), (0, 1), (2, -1), (2, 1), (4, -1), (4, 1)\}$$

Step 3. Com­pare. $(-1, 0)$ is in $A \times B$ but not in $B \times A$ (there, $-1$ never comes first). So the sets are dif­fer­ent.

Check­ing the answer#

Each list has $6$ pairs, which equals $2 \times 3$. No pair is repeated.

Answer#

$A \times B$ and $B \times A$ are as listed above (6 pairs each); they are not equal.

Com­mon mis­take to avoid#

Think­ing $(a, b)$ and $(b, a)$ are the same. In an ordered pair the order mat­ters.

Ques­tion 3: Count­ing pairs and rela­tions#

The prob­lem#

$A$ has $4$ ele­ments and $B$ has $3$. How many ele­ments are in $A \times B$? How many rela­tions are there from $A$ to $B$?

Under­stand­ing the prob­lem#

A rela­tion from $A$ to $B$ is any sub­set of $A \times B$, includ­ing the empty set and the whole of $A \times B$.

The idea#

$n(A \times B) = n(A)\,n(B)$. A set with $m$ ele­ments has $2^m$ sub­sets, because each ele­ment is either in or out.

Step-by-step solu­tion#

Step 1. Count the pairs.

$$n(A \times B) = 4 \times 3 = 12$$

Step 2. Each of the $12$ pairs can be included or left out of a rela­tion: $2$ choices each, inde­pen­dently.

$$\text{number of relations} = 2^{12} = 4096$$

Check­ing the answer#

Small case check: with $n(A) = 1$ and $n(B) = 1$ there is one pair and $2^1 = 2$ rela­tions: $\varnothing$ and $\{(a, b)\}$. The rule works.

Answer#

$12$ ele­ments; $4096$ rela­tions.

Ques­tion 4: Recov­er­ing $A$ from $A \times A$#

The prob­lem#

$A \times A$ has $9$ ele­ments, two of which are $(2, 5)$ and $(5, 7)$. Find $A$ and the remain­ing ele­ments.

Under­stand­ing the prob­lem#

$n(A \times A) = n(A)^2 = 9$, so $A$ has $3$ ele­ments. Every entry of a pair in $A \times A$ must belong to $A$.

The idea#

Read off the ele­ments of $A$ from the given pairs, then list all $9$ pairs and remove the two already given.

Step-by-step solu­tion#

Step 1. Find $n(A)$.

$$n(A)^2 = 9 \;\Rightarrow\; n(A) = 3$$

Step 2. From $(2, 5)$, both $2$ and $5$ are in $A$. From $(5, 7)$, $7$ is in $A$. That is three dif­fer­ent ele­ments, so

$$A = \{2, 5, 7\}$$

Step 3. List all of $A \times A$.

$$\{(2,2), (2,5), (2,7), (5,2), (5,5), (5,7), (7,2), (7,5), (7,7)\}$$

Step 4. Remove $(2, 5)$ and $(5, 7)$. The remain­ing seven are

$$(2, 2),\ (2, 7),\ (5, 2),\ (5, 5),\ (7, 2),\ (7, 5),\ (7, 7)$$

Check­ing the answer#

$2 + 7 = 9$ pairs in total, match­ing $n(A \times A) = 9$.

Answer#

$A = \{2, 5, 7\}$; the other ele­ments are $(2,2), (2,7), (5,2), (5,5), (7,2), (7,5), (7,7)$.

Ques­tion 5: Ver­i­fy­ing $A \times C \subset B \times D$#

The prob­lem#

$A = \{1, 2\}$, $B = \{1, 2, 3, 4\}$, $C = \{5, 6\}$, $D = \{5, 6, 7, 8\}$. Ver­ify $A \times C \subset B \times D$.

Under­stand­ing the prob­lem#

To show one set is a sub­set of another, we must show every ele­ment of the first set also lies in the sec­ond.

The idea#

Notice $A \subset B$ and $C \subset D$. Then any pair built from $A$ and $C$ is auto­mat­i­cally a pair built from $B$ and $D$. We can also check by list­ing.

Step-by-step solu­tion#

Step 1. List $A \times C$.

$$A \times C = \{(1, 5), (1, 6), (2, 5), (2, 6)\}$$

Step 2. Take any pair $(a, c)$ from this list. Its first entry $a$ is $1$ or $2$, both in $B$. Its sec­ond entry $c$ is $5$ or $6$, both in $D$.

Step 3. So $(a, c)$ has first entry in $B$ and sec­ond entry in $D$, which means $(a, c) \in B \times D$. This holds for all four pairs, so $A \times C \subset B \times D$.

Check­ing the answer#

$B \times D$ has $16$ pairs and includes $(1,5), (1,6), (2,5), (2,6)$ in its first rows.

Answer#

Every pair of $A \times C$ has its first entry in $A \subset B$ and sec­ond in $C \subset D$, so $A \times C \subset B \times D$.

Ques­tion 6: A rela­tion in ros­ter form#

The prob­lem#

On $A = \{1, 2, 3, \ldots, 12\}$ define $R = \{(a, b) : b = 2a - 1\}$. Write $R$ in ros­ter form; find its domain and range.

Under­stand­ing the prob­lem#

"On $A$" means both $a$ and $b$ must be in $A$. So $b = 2a - 1$ must itself be a num­ber from $1$ to $12$. Ros­ter form means list­ing every pair.

The idea#

Try $a = 1, 2, 3, \dots$ and keep only the pairs where $2a - 1 \le 12$.

Step-by-step solu­tion#

Step 1. Find which $a$ are allowed.

$$2a - 1 \le 12 \;\Rightarrow\; 2a \le 13 \;\Rightarrow\; a \le 6.5$$

So $a = 1, 2, 3, 4, 5, 6$.

Step 2. Com­pute $b$ for each.

Step 3. Write the rela­tion, domain (first entries) and range (sec­ond entries).

$$\begin{aligned} R &= \{(1, 1), (2, 3), (3, 5), (4, 7), (5, 9), (6, 11)\}\\ \text{Domain} &= \{1, 2, 3, 4, 5, 6\}\\ \text{Range} &= \{1, 3, 5, 7, 9, 11\} \end{aligned}$$

Check­ing the answer#

$a = 7$ would give $b = 13$, which is not in $A$, so stop­ping at $6$ is right. The codomain is all of $A$, but the range is only the odd num­bers up to $11$.

Answer#

$R = \{(1,1), (2,3), (3,5), (4,7), (5,9), (6,11)\}$; domain $\{1, \ldots, 6\}$; range $\{1, 3, 5, 7, 9, 11\}$.

Com­mon mis­take to avoid#

Includ­ing $(7, 13)$ and beyond. Both entries must lie in $A$.

Ques­tion 7: Primes and cubes#

The prob­lem#

$R = \{(x, x^3) : x \text{ is a prime less than } 8\}$. Write $R$ and its range.

Under­stand­ing the prob­lem#

We need the primes below $8$, and for each we pair it with its cube. Recall that $1$ is not a prime.

The idea#

List the primes, cube each, and write the pairs. The range is the set of sec­ond entries.

Step-by-step solu­tion#

Step 1. Primes less than $8$: $2, 3, 5, 7$.

Step 2. Their cubes: $2^3 = 8$, $3^3 = 27$, $5^3 = 125$, $7^3 = 343$.

Step 3. Write $R$ and the range.

$$\begin{aligned} R &= \{(2, 8), (3, 27), (5, 125), (7, 343)\}\\ \text{Range} &= \{8, 27, 125, 343\} \end{aligned}$$

Check­ing the answer#

$4$ primes give $4$ pairs. $7 \times 7 \times 7 = 49 \times 7 = 343$.

Answer#

$R = \{(2, 8), (3, 27), (5, 125), (7, 343)\}$; range $\{8, 27, 125, 343\}$.

Ques­tion 8: Read­ing an arrow dia­gram#

The prob­lem#

From an arrow dia­gram with $1 \to 4$, $2 \to 5$, $3 \to 4$, $3 \to 6$: write $R$, its domain and range.

Under­stand­ing the prob­lem#

Each arrow $a \to b$ stands for one ordered pair $(a, b)$ in $R$. An ele­ment can send more than one arrow (here $3$ sends two).

The idea#

Turn each arrow into a pair, then read off the first and sec­ond entries.

Step-by-step solu­tion#

Step 1. Write one pair per arrow.

$$R = \{(1, 4), (2, 5), (3, 4), (3, 6)\}$$

Step 2. Domain: the first entries, each listed once.

$$\text{Domain} = \{1, 2, 3\}$$

Step 3. Range: the sec­ond entries, each listed once ($4$ appears twice but is writ­ten once).

$$\text{Range} = \{4, 5, 6\}$$

Check­ing the answer#

Four arrows, four pairs. Every arrow's tail is in the domain and every head is in the range.

Answer#

$R = \{(1, 4), (2, 5), (3, 4), (3, 6)\}$; domain $\{1, 2, 3\}$; range $\{4, 5, 6\}$.

Ques­tion 9: Test­ing mem­ber­ship of a rela­tion#

The prob­lem#

On $\mathbf{Z}$, $R = \{(a, b) : a - b \text{ is a multiple of } 3\}$. Is $(7, 1) \in R$? $(5, -1)$? $(2, 6)$?

Under­stand­ing the prob­lem#

A pair belongs to $R$ exactly when the first entry minus the sec­ond entry is a mul­ti­ple of $3$ (such as $\dots, -6, -3, 0, 3, 6, \dots$).

The idea#

Com­pute $a - b$ for each pair and check divis­i­bil­ity by $3$.

Step-by-step solu­tion#

Step 1. $(7, 1)$: $7 - 1 = 6 = 3 \times 2$. A mul­ti­ple of $3$, so yes.

Step 2. $(5, -1)$: $5 - (-1) = 5 + 1 = 6$. A mul­ti­ple of $3$, so yes.

Step 3. $(2, 6)$: $2 - 6 = -4$. Not a mul­ti­ple of $3$, so no.

Check­ing the answer#

Be care­ful with the sign in Step 2: sub­tract­ing $-1$ means adding $1$.

Answer#

$(7, 1) \in R$: yes. $(5, -1) \in R$: yes. $(2, 6) \in R$: no.

Ques­tion 10: True or false#

The prob­lem#

True or false: if $(a, b) \in A \times B$ and $(b, c) \in B \times C$, then $(a, c) \in A \times C$.

Under­stand­ing the prob­lem#

We must decide whether the con­clu­sion always fol­lows. To show "true" we give a rea­son that works in every case; to show "false" one coun­terex­am­ple would be enough.

The idea#

Unpack what mem­ber­ship of a Carte­sian prod­uct means: $(a, b) \in A \times B$ says exactly $a \in A$ and $b \in B$.

Step-by-step solu­tion#

Step 1. From $(a, b) \in A \times B$ we get $a \in A$ (and $b \in B$).

Step 2. From $(b, c) \in B \times C$ we get $c \in C$ (and $b \in B$).

Step 3. Now $a \in A$ and $c \in C$, so by the def­i­n­i­tion of the Carte­sian prod­uct, $(a, c) \in A \times C$.

Check­ing the answer#

Exam­ple: $A = \{1\}$, $B = \{2\}$, $C = \{3\}$. $(1, 2) \in A \times B$, $(2, 3) \in B \times C$, and $(1, 3) \in A \times C$.

Answer#

True.