Section 7.4 Cartesian Products and Relations

All mathematics can be built from sets. A key step is to use sets to define relations. Functions and operations are examples of relations, but that is just the tip of the iceberg. Almost every mathematical symbol you know is either the name of a set or a relation. For example, each of the following mathematical symbols represents a relation

\begin{equation*} + \hspace{.05 in} \times \hspace{.05 in} \sqrt{~} \hspace{.05 in} \mid \hspace{.05 in} = \hspace{.05 in} \neq \hspace{.05 in} \le \hspace{.05 in} > \hspace{.05 in} \land \hspace{.05 in} \lor \hspace{.05 in} \cap \hspace{.05 in} \cup \hspace{.05 in} \oplus \hspace{.05 in} \in \hspace{.05 in} \subseteq \hspace{.05 in} \sim \hspace{.05 in} \cong \hspace{.05 in} \equiv \| \hspace{.05 in} \perp \end{equation*}

Relations are built from the Cartesian product of sets, so we begin there.

Subsection 7.4.A The Cartesian Product of Sets

The Cartesian product of sets is another set operation that we can use to build new sets from known sets. The Cartesian product of two sets is defined using ordered pairs, which we define in Definition 6.3.1. It is useful to form the Cartesian product of any finite number of sets. For that, we need to extend the definition to ordered tuples of any finite length.

Definition 7.4.1 Ordered tuples.

For sets \(X_1\text{,}\) \(X_2\text{,}\) \(X_3\text{,}\)…, \(X_n\) and elements \(x_1\in X_1\text{,}\) \(x_2\in X_2\text{,}\) \(x_3\in X_3\text{,}\) …, \(x_n\in X_n\text{,}\) the ordered \(n\) tuple \((x_1,x_2,x_3, \ldots, x_n)\) is defined by

\begin{equation*} (x_1,x_2, x_3, \ldots, x_n) = \{\{x_1\}, \{x_1,x_2\}, \{x_1,x_2,x_3\}, \ldots, \{x_1,x_2,x_3,\ldots, x_n\}\} \end{equation*}

For example, if \(X_1=X_2=X_3=\mathbb{Z}\text{,}\) then

\begin{equation*} (1,5,2) = \{\{1\}, \{1,5\}, \{1,2,5\}\} \end{equation*}

whereas

\begin{equation*} (2,1,5) = \{\{2\}, \{1,2\}, \{1,2,5\}\}\text{.} \end{equation*}
In the ordered tuple \((x_1,x_2,x_3, \ldots, x_n)\text{,}\) we say that \(x_1\) is the first coordinate, \(x_2\) is the second coordinate, \(x_3\) is the third coordinate, …, \(x_n\) is the \(n^{\text{ th } }\) coordinate. For example, in \((1,5,2)\text{,}\) the first coordinate is 1, the second coordiante is 5, and the third coordinate is 2.

In applications to databases, the coordinates often come from different sets.

Example 7.4.2 Ordered tuples of data.

Create 4-tuples to represent each student at a university where the first coordinate is the student’s first name, the second coordinate is that student’s family name, the third coordinate is the number of credit hours the student has completed, and the fourth coordinate indicates if the student lives on-campus or off-campus.

Solution.

Let \(X_1=X_2\) be the set of all alphabetic strings of length up to ten (for the names), let \(X_3=\{0,1,2,3,\ldots, 999\}\) (for the completed credit hours), and \(X_4=\{\bs{0},\bs{1}\}\) (for off-campus and on-campus, in that order). For example, the student Elizabeth Anderson who has completed 48 credit hours and currently lives off-campus might be represented by the the 4-tuple

\begin{equation*} (\str{Elizabeth}, \str{Anderson}, 48,\bs{0}) \end{equation*}

We are now ready to define the Cartesian product of sets.

Definition 7.4.3 Cartesian product of sets.

Given sets \(X\) and \(Y\text{,}\) the Cartesian product, denoted \(X \times Y\text{,}\) is the set of all ordered pairs of the form \((x,y)\) where \(x \in X\) and \(y\in Y\text{.}\) That is,

\begin{equation*} X \times Y = \{ (x,y) \mid x \in x \text{ and } y \in Y \}\text{.} \end{equation*}

For example, if \(X = \{2,3,5\}\) and \(Y = \{0,1\}\text{,}\) then

\begin{equation*} X \times Y = \{ (2,0), (2,1), (3,0), (3,1), (5,0), (5,1)\}\text{.} \end{equation*}
Similarly, given sets \(X_1\text{,}\) \(X_2\text{,}\) \(X_3\text{,}\) …, \(X_n\text{,}\) the Cartesian product, denoted \(X_1 \times X_2 \times X_3 \times \cdots \times X_n\text{,}\) is the set of all ordered \(n\)-tuples of the form \((x_1, x_2, x_3,\ldots, x_n)\) where \(x_1 \in X_1\text{,}\) \(x_2 \in X_2\text{,}\) \(x_3 \in X_3\text{,}\) …, \(x_n \in X_n\text{.}\) That is,

\begin{equation*} X_1 \times X_2 \times X_3 \times \cdots \times X_n = \{(x_1, x_2, x_3, \ldots, x_n) \mid x_1 \in X_1, x_2 \in X_2, x_3 \in X_3, \ldots, x_n \in X_n\}\text{.} \end{equation*}

For example, if \(X_1=\{0,1\}\text{,}\) \(X_2=\{a,b\}\text{,}\) and \(X_3 = \{1,2\}\text{,}\) then

\begin{equation*} X_1 \times X_2 \times X_3= \{ (0,a,1), (0,a,2), (0,b,1), (0,b,2), (1,a,1), (1,a,2), (1,b,1), (1,b,2)\}\text{.} \end{equation*}
We are often interested in the Cartesian product of a set with itself. Given a set \(X\) we write

\begin{equation*} X^n=\underbrace{X \times X \times X \times \cdots \times X}_{n \text{ times } }\text{.} \end{equation*}

For example, \(\mathbb{R}^2\) is the usual \(xy\)-plane and \(\mathbb{R}^3\) is the usual \(xyz\)-space.

If the elements of the sets \(X\) and \(Y\) are real numbers, then \(S \times T \subseteq \mathbb{R}^2\) and so we can draw \(X \times Y\) as points in the \(xy\)-plane.

Example 7.4.4 Drawing the Cartesian product of two sets of real numbers as points in the \(xy\)-plane.

Consider the sets \(X = \{2,3,5\}\) and \(Y = \{0,1\}\) from Definition 7.4.3. Draw \(X \times Y\) as points in the \(xy-\)plane.

Solution.

We plot the points of \(X \times Y\) in Figure 7.4.5.

Figure 7.4.5. Representing \(\{2,3,5\} \times \{0,1\}\) as points in the \(xy\)-plane.

Your turn to work with ordered pairs, ordered tuples, and the Cartesian product of sets.

Activity 7.4.A Cartesian product.

Consider the sets \(P = \{0,1,2,3\}\) and \(Q = \{1,5,7\}\text{.}\) Give an example of an element in \(P \times Q\) and an element in \(Q \times P\text{.}\) Is there any ordered pair in both \(P \times Q\) and \(Q \times P\text{?}\)
Again, consider the sets \(P = \{0,1,2,3\}\) and \(Q = \{1,5,7\}\text{.}\) Represent \(P \times Q\) as points in the \(xy\)-plane and then represent \(Q \times P\) as a set of points in the \(xy\)-plane.
Conjecture how \(|X \times Y|\) is related to \(|X|\) and \(|Y|\) when \(X\) and \(Y\) are finite sets.
For the set \(Q = \{1,5,7\}\text{,}\) list the elements of \(Q^2\) and represent \(Q^2\) as a set of points in the \(xy\)-plane.
For the set \(P = \{0,1,2,3\}\text{,}\) give an example of an element of \(P^3\text{.}\) How many elements does \(P^3\) have?
Conjecture how \(|X^n|\) is related to \(|X|\) when \(X\) is a finite set.

Subsection 7.4.B Functions Involving Cartesian Products

Note that the domain and/or codomain of a function can be a Cartesian product. A quick note on notation when the domain is a Cartesian product

Remark 7.4.7 Notation for Functions on Cartesian products.

For sets \(X_1\text{,}\) \(X_2\text{,}\) … \(X_n\text{,}\) if we have a function \(f\) with domain \(X_1 \times X_2 \times \cdots \times X_n\text{,}\) then we should write \(f((x_1,x_2, \ldots, x_n))\) where each \(x_i \in X_i\text{,}\) but the double parentheses look silly, so we often write \(f(x_1,x_2, \ldots, x_n)\) instead.

Here are some examples of functions involving Cartesian products of sets.

Example 7.4.8 Functions involving Cartesian products of sets.

Consider the function \(f: \mathbb{R}^2 \to \mathbb{R}\) defined by \(f(x,y) = x+y\text{.}\) Identify the domain and codomain of \(f\text{,}\) evaluate \(f(3,4)\text{,}\) and describe the set of all ordered pairs \((x,y)\) with \(f(x,y)=0\) as a set of points in the \(xy\)-plane.
Solution.

The domain of \(f\) is \(\mathbb{R}^2\) and the codomain is \(\mathbb{R}\text{.}\) Next, \(f(3,4) = 3+4 = 7\text{.}\) To find all points with \(f(x,y)=7\) we solve \(x+y=7\) to get \(y = 7-x\) which is the line with slope -1 and \(y\)-intercept 7.
Consider the function \(g: \{0,1,2,3\} \to \{1,2,3,4\} \times \{0,1,2,\ldots,10\}\) defined by \(g(a) = (a+1,a^2)\text{.}\) Identify the domain and codomain of \(g\text{,}\) evaluate \(g(0)\) and \(g(3)\text{,}\) and describe the image of \(g\text{.}\)
Solution.

The domain is \(\{0,1,2,3\}\) and the codomain is \(\{1,2,3,4\} \times \{0,1,2,\ldots,10\}\text{.}\) We evaluate \(g(0) = (0+1,0^2)=(1,0)\) and \(g(3) = (3+1,3^2)=(4,9)\text{.}\) There are only finitely many integers in the domain so we can find the image by listing the values

\begin{equation*} \{g(0), g(1), g(2), g(3) \} = \{ (1,0), (2,1), (3,4), (4,9)\}\text{.} \end{equation*}

You can confirm each of these ordered pairs is in the codomain, as required.
Consider the function \(h: \mathbb{Z}^2 \to \mathbb{Z}^2\) defined by \(h(a,b) = (c,d)\) where \(d=\fn{gcd}(a,b)\) and \(m =\fn{lcm}(a,b)\text{,}\) the least (smallest) integer that it a common multiple of \(a\) and \(b\text{.}\) Identify the domain and codomain of \(h\text{,}\) evaluate \(h(4,6)\text{,}\) and describe all fixed points of the function \(h\text{.}\)
Solution.

The domain is \(\mathbb{Z}^2\) and the codomain is also \(\mathbb{Z}^2\text{.}\) We evaluate \(h(4,6)=(2,12)\text{.}\) The fixed points of \(h\) are the points \((a,b)\) where \(h(a,b) = (a,b)\text{.}\) It follows that \(a\) is a common divisor of \(a\) and \(b\) and \(b\) is a common multiple of \(a\) and \(b\text{.}\) That happens exactly when \(a \mid b\text{,}\) so \((a,b)\) is a fixed point exactly when \(a \mid b\text{.}\)

As usual, the domain and codomain of functions can involve any type of discrete object.

Example 7.4.9 Functions involving Cartesian products and discrete objects.

Let \(S = \{0,1,2,3\}\) and, as usual, let \(\mathscr{P}(S)\) denote the set of all subsets of \(S\text{.}\) Consider the function \(\fn{int}: \mathscr{P}(S)^2 \to \mathscr{P}(S)\) defined by \(\fn{int}(A,B) = A \cap B\text{.}\) Evaluate \(\fn{int}(\{0,1,2\},\{2,3\})\text{.}\)
Solution.

We have \(\fn{int}(\{0,1,2\},\{2,3\}) = \{0,1,2\} \cap \{2,3\} = \{2\}\text{.}\)
Let \(D=\{0,1,2,\ldots,9\}\) be the set of digits and let

\begin{equation*} T=\{000,001,002,\ldots, 998, 999\} \end{equation*}

be the set of all strings of digits of length three, the numbers 0-999 written as three-digit numbers. Consider the function \(\fn{split}:T \to \mathbb{D}^3\) defined by \(\fn{split}(abc)= (a,b,c)\text{.}\) Evaluate \(\fn{split}(486)\text{.}\)
Solution.

We get \(\fn{split}(486)=(4,8,6)\text{.}\)

Try to work with functions involving Cartesian products

Activity 7.4.B Functions involving Cartesian products.

Consider the function \(f: \mathbb{Z}^2 \to \mathbb{Z}\) defined by \(f(a,b) = ab\text{.}\)

State the domain and codomain of \(f\) and evaluate \(f(3,4)\text{.}\)
Give an example of an ordered pair \((a,b)\) different from \((3,4)\) with \(f(a,b) = f(3,4)\text{.}\) What does that tell you about the function \(f\text{?}\)
Given any real number \(n\text{,}\) find an ordered pair \((a,b)\) such that \(f(a,b)=n\text{.}\) Hint: Write \(a\) and \(b\) in terms of \(n\text{.}\) What does that tell you about the function \(f\text{?}\)
For a given integer \(n\text{,}\) how many ordered pairs \((a,b)\) have \(f(a,b)=n\text{?}\) Hint: Do not forget the negative divisors.

Subsection 7.4.C Relations and Their Representations

We are now ready to define a relation.

Definition 7.4.11 Relation.

For any sets \(X\) and \(Y\text{,}\) a relation (from X to Y) is a subset of \(X \times Y\text{.}\) For example, the set \(R=\{(a,0),(a,1),(b,1),(b,2)\}\) is a relation from \(\{a,b\}\) to \(\{0,1,2\}\text{.}\)
In many of the important examples, \(X=Y\text{,}\) and we just say \(R\) is a relation on \(X\). For example, the set \(R=\{(0,0),(0,1),(0,2),(1,1),(1,2),(2,2)\}\) is relation on \(\{0,1,2\}\text{.}\) We could equivalently define \(R = \{(a,b) \mid a, b \in \{0,1,2\} \text{ and } a \le b\}\text{.}\)

Note that the graph of any function is a relation.

Definition 7.4.12 Graph of a function.

For sets \(X\) and \(Y\) and function \(f: X \to Y\text{,}\) the graph of the function \(f\) is the relation

\begin{equation*} \{(x,y) \mid x \in X, y \in Y, \text{ and } y = f(x)\} \end{equation*}

or, equivalently, the graph of \(f\) is

\begin{equation*} \{(x,f(x)) \mid x \in X\}\text{.} \end{equation*}

For example, if \(f: \mathbb{R} \to \mathbb{R}\) is the function defined by \(f(x) = 2x+1\text{,}\) then the graph of \(f\) is the line \(y=2x+1\) that has slope two and intercept one.

More generally, any graph in the \(xy\)-plane is a relation on \(\mathbb{R}\text{.}\) For example, the unit circle \(U = \{ (x,y) \mid x^2+y^2=1\}\) shown in Figure 6.3.9 is a relation.

Although every function has a graph that is a relation, not every relation is the graph of a function. For example, we see in Example 6.3.5 that the unit circle is not the graph of a function.

Let’s look at another example of the graph of a function.

Example 7.4.13 The graph of a function on \(\mathbb{Z}\).

Consider the function \(s: \mathbb{Z} \to \mathbb{Z}\) defined by \(s(n) = n^2+1\) and let \(R\) be the graph of \(s\text{.}\)

Is \((3,8) \in R\text{?}\) Is \((2,5) \in R\text{?}\)
Solution.

Since \(s(3) = 3^2+1=10 \neq 8\text{,}\) it follows that \((3,8)\) is not on the graph of \(s\) and so \((3,8) \notin R\text{.}\) On the other hand, since \(s(2) = 2^2+1=5\text{,}\) it follows that \((2,5)\) is on the graph of \(s\) and so \((2,5) \in R\text{.}\)
Find all integers \(m \in \mathbb{Z}\) such that \((2,m) \in R\) and find all integers \(n \in \mathbb{Z}\) such that \((n,5) \in R\text{.}\)
Solution.

First, if \((2,m) \in R\text{,}\) then \(m = s(2) = 5\text{.}\) No other value of \(m\) is possible because by the definition of function Definition 6.1.11 there is only one value for \(f(2)\text{.}\) Next, if \((n,5) \in R\text{,}\) then \(5 = f(n) = n^2 +1\text{.}\) Solving we get \(n^2=4\) and so \(n=2\) and \(n=-2\text{.}\)

When \(X\) and \(Y\) are finite sets or subsets of \(\mathbb{Z}\text{,}\) we have two ways to visually represent a relation from \(X\) to \(Y\text{.}\)

Definition 7.4.14 Drawing relations on finite sets or subsets of \(\mathbb{Z}\) using dot diagrams.

When \(X\) and \(Y\) are finite sets or subsets of \(\mathbb{Z}\text{,}\) we can represent a relation \(R\) from \(X\) to \(Y\) using a dot diagram where we draw a vertex for each element of \(X\) on the left and a vertex for each element of \(Y\) on the right. Then we draw an arrow from \(x\) to \(y\) if \((x,y) \in R\text{.}\) This is the same dot diagram we used to represent functions on a finite sets or subsets of \(\mathbb{Z}\text{.}\) For example, the relation \(R=\{(a,0),(a,1),(b,1),(b,2)\}\) from \(\{a,b\}\) to \(\{0,1,2\}\) can be represented using the dot diagram shown in Figure 7.4.15.

Figure 7.4.15. The dot diagram for a relation on finite sets.

When \(X=Y\text{,}\) there is another way we can represent the relation visually.

Definition 7.4.16 Drawing relations on a finite set or subset of \(\mathbb{Z}\) using a directed graph.

When \(R\) is a relation on a finite set \(X\) or subset of \(\mathbb{Z}\text{,}\) we can also represent \(R\) using a (possibly infinite) directed graph. We draw a vertex for each element of \(X\) and an arrow from \(x\) to \(y\) for each pair \((x,y) \in R\text{.}\) If \((x,y) \in R\) and \((y,x) \in R\text{,}\) then we draw a double-headed arrow. If \((x,x) \in R\text{,}\) then we draw a loop — an arrow beginning and ending at \(x\text{.}\)

Here are some examples.

Example 7.4.17 Directed graphs for three relations on \(\{1,2,3\}\).

Consider three different relations on the set \(X =\{1,2,3\}\) defined by

\begin{equation*} R_1 = \{(1,1), (2,3), (3,2)\} \end{equation*}

\begin{equation*} R_2 = \{(1,1), (1,2), (1,3), (2,2), (3,3)\} \end{equation*}

\begin{equation*} R_3 = \{ (1,3), (2,3),(3,1)\} \end{equation*}

Draw the directed graph for each relation.

Solution.

In each case our vertices are 1, 2, and 3. The directed graphs are drawn in Figure 7.4.18.

Figure 7.4.18. From left-to-right, the directed graphs for the relations \(R_1\text{,}\) \(R_2\text{,}\) and \(R_3\) from Example 7.4.17.

We can draw directed graphs for a relation on an infinite subset.

Example 7.4.19 Directed graph of a relation on \(\mathbb{Z}\).

Draw the directed graph of the relation on \(\mathbb{Z}\) defined by

\begin{equation*} R= \{ (a,b) \mid |a-b|=1\} \end{equation*}

where \(|~|\) denotes the absolute value.

Solution.

Note that \(|a-b|=1\) is true in two cases. First, if \(a-b=1\text{,}\) then \(b=a-1\text{.}\) Second, if \(a-b=-1\text{,}\) then \(b=a+1\text{.}\) Therefore

\begin{equation*} R = \{(a,b) \mid b = a \pm 1\}\text{.} \end{equation*}

For example, when \(a=1\) we have \((1,2) \in R\) and \((1,0)\in R\text{.}\) The directed graph is drawn in Figure 7.4.20.

Figure 7.4.20. The directed graph of a relation on \(\mathbb{Z}\text{.}\)

There are several shorthands for relations.

Remark 7.4.21 Alternative notation for relations.

It is sometimes convenient to write \(x \sim y\) instead of \((x,y) \in R\text{.}\) This notation is particularly helpful if \(X\) itself is a Cartesian product, so we can write \((a,b) \sim (c,d)\) instead of the potentially awkward ordered pair of ordered pairs \(((a,b),(c,d)) \in R\text{.}\)
We often define a symbol for commonly-used relations. For example, if \(R = \{ (a,b) \mid a,b \in \mathbb{Z} \text{ and } a \le b\}\text{,}\) then instead of \((a,b) \in R\text{,}\) we might just write \(a \le b\text{.}\)

Let’s see an example of the \(\sim\) notation.

Example 7.4.22 A relation on a Cartesian product.

Define a relation on \(X=\mathbb{Z} \times\mathbb{Z}^+\) by \((a_1,b_1) \sim (a_2,b_2)\) if \(a_1b_2 = a_2b_1\) or, equivalently, if \(\frac{a_1}{b_1}=\frac{a_2}{b_2}\text{.}\)

Show that \((4,6) \sim (2,3)\text{.}\)
Solution.

We check that \(4 \cdot3 = 12 = 2 \cdot 6\) or, equivalently, \(\frac{4}{6}=\frac{2}{3}\text{,}\) and so \((4,6) \sim (2,3)\text{.}\)
Describe the set of ordered pairs \((a,b)\) such that \((a,b)\sim(1,2)\text{.}\)
Solution.

If \((a,b)\sim(1,2)\text{,}\) then \(a(1) = b(2)\) or, equivalently, \(a=2b\text{.}\) The set of ordered pairs related to \((1,2)\) is \(\{ (2b,b) \mid b \in \mathbb{Z}^+\}\text{.}\)

It is your turn to work with relations.

Activity 7.4.C Relations.

Draw the dot diagram and the directed graph for the relation \(R=\{(0,0), (1,0), (1,1), (1,2)\}\) on \(X=\{0,1,2\}\text{.}\) Explain why \(R\) is not the rule for a function.
For the set \(Y = \{1,2,3,4,5,6\}\text{,}\) list the ordered pairs in the relation \(S\) on \(Y\) defined by

\begin{equation*} S = \{ (m,n) \mid m+n = 6 \} \end{equation*}

and draw the directed graph for \(S\text{.}\)
Consider the relation \(S\) defined on \(\mathbb{Z}\) by \(S=\{(a,b) \mid ab \text{ is even } \}\text{.}\) Is \((3,8) \in R\text{?}\) Is \((5,5) \in R\text{?}\)
Consider the relation \(\sim\) defined on \(\mathbb{R}\) by \(x \sim y\) if \(|x - y | \lt 3\text{.}\) First decide if \(1 \sim 3\) and then describe \(\{x \in \mathbb{R} \mid x \sim 0\}\) using interval notation.
Consider the relation \(\sim\) defined on \(\mathbb{R}^2\) by \((x_1,y_1) \sim (x_2,y_2)\) if

\begin{equation*} y_1-y_2=3(x_1-x_2)\text{.} \end{equation*}

Is \((1,2) \sim (2,4)\text{?}\) Is \((1,2) \sim (3,8)\text{?}\) Describe all points in the \(xy\)-plane such that \((x,y) \sim (0,2)\text{.}\)

Subsection 7.4.D Exercises

Subsubsection Exercises for 7.4.A The Cartesian Product of Sets

1. Practice.

Write each ordered tuple as a set of sets using Definition 7.4.1.

\(\displaystyle (3,7)\)
\(\displaystyle (3,7,5)\)
\(\displaystyle (3,7,5,1)\)

2. Practice.

Consider the sets \(K = \{0, 2, 4\}\text{,}\) \(L = \{1,3\}\) and \(M = \{2\}\text{.}\) For each Cartesian product, list the elements and represent the product as a set of points in the \(xy\)-plane.

\(\displaystyle K \times L\)
\(\displaystyle L \times K\)
\(\displaystyle K \times M\)
\(\displaystyle L^2\)

3. Practice.

Consider the sets \(A = \{1, 2, 3, 4, 5, 6\}\) and \(B = \{0, 1, 2\}\text{.}\)

Draw \(A \times B\) as set of points in the usual \(xy\)-plane. How many ordered pairs are in \(A \times B\text{?}\)
List the ordered pairs in \(B \times B\text{.}\)
How many elements does \(A^2\) have? Explain your reasoning.
How many elements does \(B^3\) have? Explain your reasoning.

Check.

Hint: There should be 18 points.
Hint: The list begins \((0,0), (0,1), (0,2), (1,0), \ldots\text{.}\)
Hint: The answer is greater than 30.
Hint: The answer is greater than 20.

4. Practice.

Consider the sets \(S = \{1,2,3\}\text{,}\) \(T = \{5,7\}\text{,}\) and \(V = \{3,7\}\text{.}\)

List the elements of \(S \times T \times V\text{.}\)
List the elements of \(T^3\text{.}\)
How many elements does \(V^{10}\) have? Explain.

5. Understand.

Conjecture how \(|X \times Y|\) is related to \(|X|\) and \(|Y|\) when \(X\) and \(Y\) are finite sets. Hint: This result is why the Cartesian product is called a “product” and written with ×.
Conjecture how \(|X^n|\) is related to \(|X|\) when \(X\) is a finite set.

Check.

Hint: Test your conjectures on the sets from Exercise 3.

6. Recap.

Do you know …

How to define an ordered pair and an ordered \(n\)-tuple?
What \(X \times Y\) and \(X^n\) mean if \(X\) and \(Y\) are sets?
How to represent \(X \times Y\) as points in the \(xy\)-plane, if \(X, Y \subseteq \mathbb{R}\text{?}\)
How many elements are in \(X \times Y\) or \(X^n\) if \(X\) and \(Y\) are finite sets?

Subsubsection Exercises for 7.4.B Functions Involving Cartesian Products

7. Practice.

Consider the function \(f: \mathbb{R}^2 \to \mathbb{R}\) defined by \(f(x,y) = x-2y\text{.}\)

Identify the domain of \(f\) and the codomain of \(f\text{.}\)
Evaluate \(f(3,1)\) and \(f(2,0)\text{.}\)
Find a point \((x,y)\) such that \(f(x,y) = 4\text{.}\)
Describe the set of points \((x,y)\) in the \(xy\)-plane such that \(f(x,y) = 0\text{.}\)

Check.

Hint: The domain is \(\mathbb{R}^2\text{.}\)
Hint: \(f(3,1)=1\text{.}\)
Hint: You can pick a value for \(y\) and solve for \(x\) in the equation \(x-2y=4\text{.}\)
Hint: The set of points form a line. Find its equation or say what the slope and \(y\)-intercept are.

8. Practice.

Consider the function \(\fn{dfive}: \mathbb{N} \to \mathbb{N} \times \mathbb{N}\) defined by \(\fn{dfive}(n) = (n ~\fn{div}~ 5, n ~\fn{mod}~ 5)\text{.}\)

Identify the domain and codomain of \(\str{dfive}\text{.}\)
Evaluate \(\fn{dfive}(47)\text{.}\)
If \(\fn{dfive}(n)=(3,2)\text{,}\) then find \(n\text{.}\)
If \(\fn{dfive}(n)=(q,2)\text{,}\) then find a formula for \(n\) in terms of \(q\text{.}\)

Check.

Hint: They are not the same set.
\(\displaystyle (9,2)\)
Hint: There is only one value of \(n\text{.}\) If you are still stuck, look at Theorem 4.2.2.
Hint: Follow the process you used for 8.(c).

9. Practice.

Consider the function \(\fn{gcd}: \mathbb{Z}^+ \times \mathbb{Z}^+ \to \mathbb{Z}^+\) defined by \(\fn{gcd}(a,b) = \fn{gcd}(a,b)\text{.}\) (Meaning \(\str{gcd}\) already was a function of two variables, we just had not made that observation formal yet.)

Identify the domain and codomain of \(\str{gcd}\text{.}\)
Evaluate \(\fn{gcd}(10,15)\text{.}\)
Give an example of positive integers \(a\) and \(b\) such that \(\fn{gcd}(a,b) = 1\text{.}\) What’s the name for how \(a\) and \(b\) are related?
Give an example of positive integers \(a\) and \(b\) such that \(\fn{gcd}(a,b) = 17\text{.}\)

Check.

Hint: The codomain is \(\mathbb{Z}^+ \to \mathbb{Z}^+\text{.}\)
5
Hint: \(a\) and \(b\) should not have any common (positive) divisors except 1.
Hint: Make sure \(17 \mid a\) and \(17 \mid b\) and that no larger integers divides both \(a\) and \(b\text{.}\)

10. Practice.

Let \(\mathbb{B}\) denote the set of all bit strings and let \(\mathbb{B}_k\) denote the bit strings of length \(k\text{.}\)

Consider the function \(\fn{concat}:\mathbb{B}_5 \times \mathbb{B}_5 \to \mathbb{B}_{10}\) defined by \(\fn{concat}(b,c)=bc\) the bit string that consists of \(b\) followed by \(c\) (the concatenation function). Evaluate \(\fn{concat}(\bs{01110},\bs{11100})\text{.}\)
Consider the function \(d:\mathbb{B}_5 \times \mathbb{B}_5 \to \{0,1,2,3,4,5\}\) defined by \(d(b,c)=\) the number of bits in which \(b\) and \(c\) differ. (This function finds the Hamming distance between two bit strings, as defined in Exercise 5.) Evaluate \(d(\bs{01110},\bs{11100})\text{.}\)

Check.

Hint: Your answer should be a bit string of length 10 that starts and ends with \(\bs{0}\text{.}\)
Hint: They differ in the first and fourth bits.

11. Understand.

Consider the function \(s: \mathbb{Z}^2 \to \mathbb{Z}^2\) defined by \(s(a,b) = (a+b,a-b)\text{.}\)

Evaluate \(s(1,2), s(-2,5)\text{,}\) and \(s(0,0)\text{.}\)
Find integers \(a,b \in \mathbb{Z}\) such that \(s(a,b) = (8,2)\text{.}\) Repeat for \(s(a,b) = (-3,5)\text{.}\)
Show that there do not exist integers \(a,b\) such that \(s(a,b) = (2,1)\text{.}\)

Check.

Hint: \(s(1,2)=(3,-1)\text{.}\)
Hint: For \(s(a,b) = (8,2)\) we want integers \(a\) and \(b\) such that \(a+b=8\) and \(a-b=2\text{.}\) The second equation tells us \(a = b+2\text{.}\) Either guess from here or plug into the first equation to get \((b+2)+b=8\text{.}\) Solve for \(b\text{.}\)
Hint: For \(s(a,b) = (2,1)\) we want integers \(a\) and \(b\) such that \(a+b=2\) and \(a-b=1\text{.}\) The second equation tells us \(a = b+1\text{.}\) Plug into the first equation to get \((b+1)+b=2\text{.}\) Solve for \(b\text{.}\)

12. Understand.

Consider the function \(g: \mathbb{Z}^2 \to \mathbb{Z}\) defined by \(g(a,b) = a+b\text{.}\)

Is \(g\) onto? Briefly justify your answer.
Is \(g\) one-to-one? Briefly justify your answer.

13. Understand.

Consider the function \(\fn{gcd}: \mathbb{Z}^+ \times \mathbb{Z}^+ \to \mathbb{Z}^+\) defined by \(\fn{gcd}(a,b)\) is the greatest common divisor of \(a\) and \(b\text{.}\)

Is \(\fn{gcd}\) onto? Briefly justify your answer.
Is \(\fn{gcd}\) one-to-one? Briefly justify your answer.

14. Understand.

Let \(\mathscr{A}\) be the set of all 5-element subsets of \(\mathbb{R}\text{.}\) Consider the function \(f: \mathscr{A} \to \mathbb{R}^3\) defined by

\begin{equation*} f(A) = (\fn{min}(A), \fn{max}(A), \fn{median}(A)) \end{equation*}

where \(\fn{min}(A)=\) the smallest element of \(A\text{,}\) \(\fn{max}(A)=\) the largest element of \(A\text{,}\) and \(\fn{median}(A) =\) the median of the set \(A\text{.}\) To find the median of a set of five real numbers, list the sets in nondecreasing order (smallest to largest). The third number on that ordered list is the median. Evaluate \(f(\{1.1, 5.3, 2.7, 1.6, 6.1\})\text{.}\)
Let \(\mathbb{G}_5\) be the set of all graphs with five vertices. Consider the function \(g: \mathbb{G}_5 \to \mathbb{N}^5\) defined by \(g(G) = (n,m,\Delta,\delta,\chi)\) where \(n=\) the number of vertices of \(G\text{,}\) \(m=\) the number of edges in \(G\text{,}\) \(\Delta=\) the max degree of a vertex in \(G\text{,}\) \(\delta=\) the min degree of a vertex in \(G\text{,}\) and \(\chi=\) the chromatic number of \(G\text{.}\) Evaluate \(g(P_5)\) for the path \(P_5\text{.}\)

Check.

Hint: The answer is a 3-tuple with second coordinate equal to 6.1.
Hint: The answer is a 5-tuple with second coordinate equal to four.

15. Recap.

Do you know …

Why we write \(f(x,y)\) instead of \(f((x,y))\) when the domain of \(f\) is the Cartesian product \(X \times Y\text{?}\)
How to evaluate functions whose domain or codomain are Cartesian products?
How to find or describe input values that produce a given output value for a function whose domain or codomain are Cartesian products?
How to determine the domain, codomain, and image of functions whose domain or codomain are Cartesian products?
How to determine if a function is onto or one-to-one when the domain or codomain of the function are Cartesian products?

16. Explore.

Consider the function \(s: \mathbb{Z}^2 \to \mathbb{Z}^2\) defined by \(s(a,b) = (a+b,a-b)\) from Exercise 11.

If \(a,b\) are both even integers or both odd integers, what can you say about the coordinates of \(s(a,b)\text{?}\)
If one of \(a,b\) is an even integer and the other is an odd integer, what can you say about the coordinates of \(s(a,b)\text{?}\)
Explain why it follows if \(c\) is an even integer and \(d\) is an odd integer, then there cannot exist integers \(a,b\) such that \(s(a,b) = (c,d)\text{.}\)
What is the image of \(s\text{?}\)

17. Explore.

Consider the function

If you have studied linear algebra, \(T\) is the linear transformation corresponding to the matrix \(\left[ \begin{array}{rr} 0 \amp -1 \\ 1 \amp 0 \end{array} \right]\) which rotates the \(xy\)-plane by 90\(^\circ\) counterclockwise, except we are restricting it to points where both coordinates are integers.

\(f: \mathbb{Z}^2 \to \mathbb{Z}^2\) defined by \(f(a,b) = (-b,a)\text{.}\) For example, \(f(2,3) = (-3,2)\text{.}\) The function \(f\) is a bijection, so it has an inverse function.

Evaluate \(f^{-1}(-3,2)\text{.}\)
What’s \(f^{-1}(5,7)\text{?}\) Check by evaluating \(f\) of your answer to make sure you get \((5,7)\text{.}\)
Find a rule for \(f^{-1}(c,d)\text{.}\)

Subsubsection Exercises for 7.4.C Relations and Their Representations

18. Practice.

Draw the directed graph for each relation on the set \(X=\{0,1,2\}\text{.}\)

\(\displaystyle \{(0,0), (0,1), (1,0), (1,2), (2,2)\}\)
\(\displaystyle X^2\)
\(\displaystyle \phi\)

Check.

Hint: The directed graph has two loops, one double-headed arrow, and one single-headed arrow.
Hint: The directed graph has three loops and three double-headed arrows.
Hint: The directed graph consists of three points with no loops and no arrows.

19. Practice.

Draw the directed graph of each relation defined on the set \(Y = \{1,2,3,4,5,6\}\text{.}\)

\(\displaystyle \{ (m,n) \mid m>n \}\)
\(\{ (m,n) \mid m\ge n \}\) Don’t forget the loops!
\(\displaystyle \{ (m,n) \mid m=n \}\)

Check.

The directed graph is drawn in Figure 7.4.43.

Figure 7.4.43. The directed graph of the relation on \(\{1,2,3,4,5,6\}\) defined by \(\{(m,n) \mid m > n\}\text{.}\)
Hint: The directed graph has the same arrows as 19.(a), but it also has loops at each point.
Hint: The graph has loops but no arrows.

20. Practice.

Consider the relation \(\sim\) defined on \(\mathbb{R}\) by \(x \sim y\) if \(y = x+2\text{.}\)

Is \(1 \sim 3\text{?}\) Explain.
Is \(3 \sim 1\text{?}\) Explain.
Find a real number \(x\) such that \(x \sim 0\text{.}\)
Find a real number \(y\) such that \(0 \sim y\text{.}\)

21. Practice.

For each relation \(R\) defined on the integers \(\mathbb{Z}\text{,}\) first decide if \((3,8) \in R\) and then give an example of an ordered pair of the form \((a,a) \in R\) for some \(a \in \mathbb{Z}\text{.}\)

\(\displaystyle R= \{(a,b) \mid ab =0 \}\)
\(\displaystyle R=\{(a,b) \mid a \mid b \}\)
\(\displaystyle R=\{(a,b) \mid b ~\fn{mod}~ 5 = a ~\fn{mod}~ 5 \}\)
\(\displaystyle R=\{(a,b) \mid \fn{gcd}(a,b)=1 \}\)

Check.

Hint: \((3,8)\) is in two of the four relations.

22. Understand.

Find all relations on \(\{0,1\}\) and draw the directed graph for each relation. Save a little time by not labeling the vertices — just draw the vertex that represents 0 on the left and the vertex that represents 1 on the right. For example, the relation \(\{(1,0),(1,1)\}\) can be drawn quickly as shown in Figure 7.4.47.

Figure 7.4.47. Quick drawing of the directed graph for the relation \(\{(1,0),(1,1)\}\) on \(\{0,1\}\text{.}\)
How many relations are there on \(\{0,1\}\text{?}\)

23. Understand.

Draw the directed graph of each relation on \(\mathbb{Z}^+\text{.}\) Show the vertices \(0,1,2,3,\ldots, 10\) and make sure to include the … on the right.

\(\displaystyle R = \{ (a,b) \mid b = a+1\}\)
\(\displaystyle R = \{ (a,b) \mid b^2=a\}\)
\(\displaystyle R = \{(a,b) \mid 2a\lt b\}\)

24. Understand.

Define a relation on \(\mathbb{R}^2\) by \((x_1,y_1) \sim (x_2,y_2)\) if

\begin{equation*} \sqrt{(x_1-x_2)^2 + (y_1-y_2)^2} \le 5 \end{equation*}

Is \((1,2) \sim (4,6)\text{?}\)
Is \((4,6) \sim (0,0)\text{?}\)
Is \((1,2) \sim (0,0)\text{?}\)
Draw a graph showing the set of points \((x,y) \in \mathbb{R}^2\) such that \((x,y) \sim (0,0)\text{.}\)

Check.

Hint: Two answers are yes and one answer is no. For the graph, \(\sqrt{x^2 + y^2}\) is the distance between the point \((x,y)\) and the origin \((0,0)\text{,}\) so the points in the relation are at most five units from the origin. The region should be shaded.

25. Understand.

Consider the relation \(\sim\) defined on \(\mathbb{R}^2\) by \((x_1,y_1) \sim (x_2,y_2)\) if

\begin{equation*} y_1-y_3=3(x_1-x_2) \end{equation*}

which we saw in Activity 7.4.C.

Describe the set of points \((x,y)\) such that \((x,y) \sim (0,0)\text{.}\)
Describe the set of points \((x,y)\) such that \((x,y)\sim (1,2)\text{.}\)

Check.

Hint: If \((x,y) \sim (0,0)\text{,}\) then \(y-0=3(x-0)\text{.}\) Simplify and explain what line that is (slope and \(y\)-intercept.)
Hint: The answer is a different line.

26. Understand.

For each relation, decide if the relation is the graph of a function or not.

\(R = \{(0,a), (2,c)\}\) from \(X = \{0,1,2\}\) to \(Y= \{a,b,c\}\)
\(R = \{(0,a), (0,b), (1,c), (2,b)\}\) from \(X = \{0,1,2\}\) to \(Y= \{a,b,c\}\)
\(R = \{ (x,x^2) \mid x \in \mathbb{R}\}\) Note: the point \((x,y) \in R\) exactly when \(y = x^2\text{.}\)
\(R = \{ (y^2,y) \mid y \in \mathbb{R}\}\) Note: the point \((x,y) \in R\) exactly when \(x = y^2\text{.}\)

27. Recap.

Do you know …

What a relation is?
Why every graph of a function is a relation but not every relation is the graph of a function?
How to draw the dot diagram and the directed graph for a relation on a finite set or a subset of \(\mathbb{Z}\text{?}\)
What \(x \sim y\) stands for in the context of relations?

28. Explore.

As usual, let \(\mathbb{B}^*\) denote the set of all (non-empty) bit strings. Define a relation on \(\mathbb{B}^*\) by \(b \sim c\) if \(b\) is a substring of \(c\text{;}\) that is, if the bit string \(b\) appears in consecutive order within the bit string \(c\text{.}\) For example, \(\bs{101} \sim \bs{11}\underline{\bs{101}}\bs{0}\) but \(\bs{00} \not\sim \bs{111010}\) because \(\bs{111010}\) does not contain two consecutive \(\bs{0}\) s.

Is \(11 \sim 101\text{?}\) Explain.
List all bit strings \(b\) such that \(b \sim \bs{101}\text{.}\) Note: \(\bs{101}\) should be on your list.
Find a bit string \(c\) such that \(00 \sim c\text{,}\) \(01 \sim c\text{,}\) \(10 \sim c\text{,}\) and \(11 \sim c\text{?}\)
Find a bit string \(c\) that is as short as possible with \(00 \sim c\text{,}\) \(01 \sim c\text{,}\) \(10 \sim c\text{,}\) and \(11 \sim c\text{.}\) Note: you might have found one in 28.(c) or there might be a shorter one.

Check.

Hint: The answer is no.
Hint: The list begins \(\bs{0}\text{,}\) \(\bs{1}\text{,}\) \(\bs{01}\text{,}\) ….
Hint: One answer is \(\bs{00011011}\text{.}\)
Hint: Find a bit string of length five meeting the conditions.

29. Explore.

For the set \(S = \{1, 2, 3\}\text{,}\) consider the following relations on \(\mathscr{P}(S)\text{,}\) the power set of \(S\text{.}\) For each relation, decide if \(\{1,2\} \sim \{2,3\}\) and decide if \(\varnothing \sim S\text{.}\)

\(A \sim B\) if \(A \subseteq B\text{.}\)
\(A \sim B\) if \(|A|=|B|\text{.}\)
\(A \sim B\) if \(A \cap B = \varnothing\text{.}\)
\(A \sim B\) if \(A \cup B = S\text{.}\)

Check.

Hint: Two of the relations have \(\{1,2\} \sim \{2,3\}\) and three of the relations have \(\varnothing \sim S\text{.}\)

30. Explore.

For a finite set \(X\) with \(|X|=n\text{,}\) how many relations are there on \(X\text{?}\) Your conjecture should involve \(n\text{.}\) Explain how you figured out your answer.

Prev Top Next