9.1 Relations and Their Properties

p594
Ex: 1-16, 20

Example 1
Let $A$ be the set of students in your school, and let $B$ be the set of courses. Let $R$ be the relation that consists of those pairs $(a, b)$, where $a$ is a student enrolled in course $b$. For instance, if Jason Goodfriend and Deborah Sherman are enrolled in CS518, the pairs (Jason Goodfriend, CS518) and (Deborah Sherman, CS518) belong to $R$. If Jason Goodfriend is also enrolled in CS510, then the pair (Jason Goodfriend, CS510) is also in $R$. However, if Deborah Sherman is not enrolled in CS510, then the pair (Deborah Sherman, CS510) is not in $R$.
Note that if a student is not currently enrolled in any courses there will be no pairs in $R$ that have this student as the first element. Similarly, if a course is not currently being offered there
will be no pairs in $R$ that have this course as their second element.

Example 2
Let $A$ be the set of cities in the U.S.A., and let $B$ be the set of the 50 states in the U.S.A. Define the relation $R$ by specifying that $(a, b)$ belongs to $R$ if a city with name $a$ is in the state $b$. For instance, (Boulder, Colorado), (Bangor, Maine), (Ann Arbor, Michigan), (Middletown, New Jersey), (Middletown, New York), (Cupertino, California), and (Red Bank, New Jersey) are in $R$.

Properties of Relations

• Reflexive
• Symmetric
• Antisymmetric
• Transitive

EXAMPLE 7
Consider the following relations on $\{1, 2, 3, 4\}$:
$R_1 = \{(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)\}$,
$R_2 = \{(1, 1), (1, 2), (2, 1)\}$,
$R_3 = \{(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)\}$,
$R_4 = \{(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)\}$,
$R_5 = \{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)\}$,
$R_6 = \{(3, 4)\}$.
Which of these relations are reflexive?

EXAMPLE 12
Is the “divides” relation on the set of positive integers symmetric? Is it antisymmetric?
Solution: This relation is not symmetric because $1 \mid 2$, but $2 \nmid 1$. It is antisymmetric, for if a and b are positive integers with $a \mid b$ and $b \mid a$, then a = b (the verification of this is left as an exercise for the reader).

Definition
A relation $R$ on a set $A$ is called transitive if whenever $(a, b) \in R$ and $(b, c) \in R$, then $(a, c) \in R$, for all $a, b, c \in A$.

$\begin{aligned} \forall a \forall b \forall c (((a, b) \in R \land (b, c) \in R) \to (a, c) \in R) \end{aligned}$

EXAMPLE 15
Is the “divides” relation on the set of positive integers transitive?
Solution: Suppose that $a$ divides $b$ and $b divides c$. Then there are positive integers $k$ and $l$ such that $b = ak$ and $c = bl$. Hence, $c = a(kl)$, so $a$ divides $c$. It follows that this relation is transitive.

EXAMPLE 16
How many reflexive relations are there on a set with $\mathsf{n}$ elements?
Solution: A relation $R$ on a set $A$ is a subset of $A\times A$. Consequently, a relation is determined by specifying whether each of the $n^2$ ordered pairs in $A \times A$ is in $R$. However, if $R$ is reflexive, each of the $n$ ordered paries $(a, a)$ for $a \in A$ must be in $R$. Each of the other $n(n-1)$ ordered pairs of the form $(a, b)$, where $a\ne b$, may or may not be in $R$. Hence, by the product rule form counting, there are $2^{n(n-1)}$ reflexive relations [this is the number of ways to choose whether each element (a, b), with $a \ne b$, belongs to $R$].

Combining relations

Definition
Let $R$ be a relation from a set $A$ to a set $B$ and $S$ a relation from $B$ to a set $C$. The composite of $R$ and $S$ is the relation consisting of ordered pairs $(a, c)$, where $a \in A, c \in C$, and for which there exists an element $b \in B$ such that $(a, b) \in R$ and $(b, c) \in S$. We denote the composite of R and S by $S \circ R$.

EXAMPLE 20
What is the composite of the relations R and S, where R is the relation from $\{1, 2, 3\}$ to $\{1, 2, 3, 4\}$ with $R = \{(1, 1), (1, 4), (2, 3), (3, 1), (3, 4)\}$ and $S$ is the relation from $\{1, 2, 3, 4\}$ to $\{0, 1, 2\}$ with $S = \{(1, 0), (2, 0), (3, 1), (3, 2), (4, 1)\}$?
Solution: $S \circ R$ is constructed using all ordered pairs in $R$ and ordered pairs in $S$, where the second element of the ordered pair in $R$ agrees with the first element of the ordered pair in $S$. For example, the ordered pairs $(2, 3)$ in $R$ and $(3, 1)$ in $S$ produce the ordered pair $(2, 1)$ in $S \circ R$. Computing all the ordered pairs in the composite, we find

$\begin{aligned} S \circ R = \{(1,0), (1, 1), (2, 1), (2, 2), (3, 0), (3, 1)\} \end{aligned}$

Homework

p602: 3c-f, 9, 25, 32

3. For each of these relations on the set $\{1, 2, 3, 4\}$, decide whether it is reflexive, whether it is symmetric, whether it is antisymmetric, and whether it is transitive.
c) $\{(2, 4), (4, 2)\}$

d) $\{(1, 2), (2, 3), (3, 4)\}$

e) $\{(1, 1), (2, 2), (3, 3), (4, 4)\}$

f) $\{(1, 3), (1, 4), (2, 3), (2, 4), (3, 1), (3, 4)\}$
Let $R$ be the relation.

9. Show that the relation $R = \emptyset$ on the empty set $S = \emptyset$ is reflexive, symmetric, and transitive.

25. How many different relations are there from a set with $m$ elements to a set with $n$ elements?

32. Let $R$ be the relation $\{(1, 2), (1, 3), (2, 3), (2, 4), (3, 1)\}$, and let $S$ be the relation $\{(2, 1), (3, 1), (3, 2), (4, 2)\}$. Find $S \circ R$.