Properties of relations

Section 13.3 Properties of relations

As we study relations in the remaining chapters of this book there are a few properties that will make for valuable terminology. For the remainder of the chapter, every relation has the same domain and codomain.

🔗

Definition 13.3.1.

A relation $R$ on a set $X$ is reflexive if every element is related to itself, in other words $(x, x) \in R$ for all $x \in X .$ The pair $(x, x)$ is a diagonal pair. So, a reflexive relation contains the diagonal.

🔗

Definition 13.3.2.

A relation $R$ on a set $X$ is antireflexive if no element is related to itself, in other words $(x, x) \notin R$ for all $x \in X .$

🔗

So a relation is reflexive if every element is related to itself, and antireflexive if none are. A relation can be neither, if some elements are related to themselves and some aren't! (Only one relation is both, but that's an exercise.)

🔗

In all of this section's examples you should draw a digraph for each relation yourself and make sure you agree with which properties each relation has.

🔗

Example 13.3.3.

Let $X = \{a,b,c,d\}\text{.}$ Consider the relations

\begin{equation*} R_1 = \{ (a,b), (a,d), (b,c), (b,d), (d,b), (d,c) \}, \end{equation*}

\begin{equation*} R_2 = \{ (a,a), (a,d), (b,b), (b,d), (c,c), (c,d), (d,d) \}, \end{equation*}

\begin{equation*} R_3 = \{(a,b), (b,b), (b,c),(c,d),(d,a), (d,d)\}, \end{equation*}

as well as the full relation $X \times X$ and the empty relation $\varnothing\text{.}$

The relations $R_2$ and $X\times X$ are reflexive as they contain all pairs of the form $(x,x)\text{.}$ The relations $R_1$ and $\varnothing$ are likewise antireflexive. The relation $R_3$ is neither reflexive nor antireflexive, as it contains some of these diagonal pairs but not all.

🔗

Definition 13.3.4.

A relation $R$ on a set $X$ is symmetric if for all $x, y \in X$ where $(x, y) \in R,$ then $(y, x) \in R .$ Such a pair $(x, y)$ is said to be invertible if $(y, x)$ is also in the relation. Therefore, in a symmetric relation all pairs are invertible.

🔗

Definition 13.3.5.

A relation $R$ on a set $X$ is antisymmetric if for all $x, y \in X$ where $(x, y) \in R,$ then $(y, x) \notin R$ unless $x = y .$ Equivalently the only invertible pairs in an antisymmetric relation are the diagonal pairs.

🔗

It is crucial to understand that symmetry and antisymmetry are two ends of a spectrum, just like reflexive and antireflexive. Symmetry and antisymmetry measure how many of the pairs in the relation are invertible. If they all are, the relation is symmetric. We would like to begin the next sentence with “if none are” but this is actually impossible, because if

(x, x) \in R

then it is automatically invertible. In other words the smallest set of pairs that can be inverted are the diagonal pairs. So, an antisymmetric relation is one where the only invertible pairs are on the diagonal. Finally, a relation may be neither or both.

🔗

Example 13.3.6.

As before let $X = \{a,b,c,d\}$ and consider the relations

\begin{equation*} R_1 = \{ (a,b), (a,d), (b,c), (b,d), (d,b), (d,c) \}, \end{equation*}

\begin{equation*} R_2 = \{ (a,a), (a,d), (b,b), (b,d), (c,c), (c,d), (d,d) \}, \end{equation*}

\begin{equation*} R_3 = \{(a,b), (b,b), (b,c),(c,d),(d,a), (d,d)\}, \end{equation*}

as well as the full relation $X \times X$ and the empty relation $\varnothing\text{.}$

The relation $X \times X$ is symmetric, because it contains all the possible pairs; so every $(x,y)$ will find its $(y,x)\text{.}$ It is less obvious but equally true that $\varnothing$ is symmetric. The definition is that every pair must be invertible; if there are no pairs then the definition is satisfied automatically.

The relations $R_1\text{,}$ $R_2\text{,}$ and $R_3$ are each not symmetric because they contain a pair that is not invertible. The relation $R_1$ has $(a,d)$ but no $(d,a)\text{;}$ $R_2$ has $(b,d)$ but no $(d,b)\text{;}$ and $R_3$ has $(a,b)$ but no $(b,a)\text{,}$ for example.

Of these, $R_1$ is not antisymmetric, because it has “some” symmetry (the pairs $(b,d)$ and $(d,b)$). The relations $R_2$ and $R_3$ are antisymmetric. The empty set $\varnothing$ manages to be both symmetric and antisymmetric because just as there are no pairs to invert, there are also no pairs to not invert. Vacuousness!

🔗

The final property to discuss is transitivity. You have heard this word before, both without this book (transitivity of equality is used to solve equations in algebra) and within (inclusion, implication, and divisibility are all transitive).

🔗

Definition 13.3.7.

A relation is transitive if for all $x, y, z \in X,$ whenever $(x, y) \in R$ and $(y, z) \in R$ we also have $(x, z) \in R .$

🔗

There are two implications of this definition. The first is that any local symmetry within a transitive relation—that is, the presence of an invertible pair—must involve a loop. That is, suppose we have

(x, y) \in R

and

(y, x) \in R

in our relation. If we replace

z

with

x

in the above definition it forces us to include the loop

(x, x)

in our relation.

🔗

The next implication involves a new definition.

🔗

Definition 13.3.8.

Consider a relation $R$ on the set $X = {x_{1}, x_{2}, \dots, x_{n}} .$ A walk of length $n$ is a sequence $(x_{1}, x_{2}, \dots, x_{n}, x_{n + 1})$ where $(x_{i}, x_{i + 1}) \in R$ for all $1 \leq i \leq n .$

🔗

So, a walk is a sequence of successively related elements. The length of the walk is a measure of the number of arrows involved, not the number of elements in the sequence.

🔗

The second implication, therefore, is that in a transitive relation, if

(x_{i})

is a walk beginning at

x_{1}

and ending at

x_{n},

then

x_{1}

must be related to

x_{n} .

🔗

Example 13.3.9.

One more time: Let $X = \{a,b,c,d\}$ and consider the relations

\begin{equation*} R_1 = \{ (a,b), (a,d), (b,c), (b,d), (d,b), (d,c) \}, \end{equation*}

\begin{equation*} R_2 = \{ (a,a), (a,d), (b,b), (b,d), (c,c), (c,d), (d,d) \}, \end{equation*}

\begin{equation*} R_3 = \{(a,b), (b,b), (b,c),(c,d),(d,a), (d,d)\}, \end{equation*}

as well as the full relation $X \times X$ and the empty relation $\varnothing\text{.}$

The relation $R_1$ is missing the edge $(a,c)\text{,}$ for example, the loop $(b,b)\text{,}$ so it is not transitive.

However, $R_2$ is transitive. There are no pairs $(x,y)$ and $(y,z)$ missing their $(x,z)\text{.}$ A common mistake is to ask, “Shouldn't we require $(a,b)$ for transitivity?” but neither $a$ nor $b$ are actually related to each other. Both are related to $d\text{,}$ but the direction of the arrow matters. (If the $(b,d)$ arrow were reversed, then a $(a,b)$ arrow would be necessary.)

The relation $R_3$ is not transitive. It is missing many edges required for transitivity; $(b,d)$ is one example. As an exercise, try to find all of the missing edges that keep $R_1$ and $R_3$ from being transitive.

The relation $X\times X$ is transitive because it contains all possible pairs. No pairs can possibly be missing, so it is transitive “by default.” Likewise $\varnothing$ is transitive because there are no pairs $(x,y)$ and $(y,z)$ that can fail to have their $(x,z)\text{.}$

🔗

Here is another example where we look for all of the above five properties in a relation given via a rule, rather than a set of ordered pairs.

🔗

Example 13.3.10.

Consider the divisibility relation on $\{1,2,3,4,5,6,7\}\text{,}$ in other words, the relation where $m$ is related to $n$ if $m|n\text{.}$ What properties does this relation have?

First, it is useful to produce a set of ordered pairs and/or a directed graph. This isn't always possible. For example, if the set were the infinite set of positive integers or even the set $\{1,2,\ldots, 100\}\text{,}$ a directed graph would be impossible or too difficult to draw. However, you can always focus on a small sample of the set to give yourself an idea of how the relation as a whole works. Be careful; if you leave elements out, you may not get the whole picture. If you left $1$ out, for instance, you would miss a unique element.

The set of ordered pairs is

\begin{align*} \Big\{ \amp (1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (1,7)\\ \amp (2,2), (2,4), (2,6), (3,3), (3,6), (4,4), (5,5), (6,6), (7,7) \Big\} \end{align*}

The directed graph is

Figure 13.3.11.
Directed graph for the divisibility relation. $1$ is related to everything and everything is related to itself. $2$ is related to $4$ and $6\text{.}$ $3$ is related to itself and $6\text{.}$ $4\text{,}$ $5\text{,}$ $6\text{,}$ $7$ are each only related to themselves.

With the properties that the relation does not have, we can simply cite an example. If the relation does have a property, since it was given as a rule rather than a set of pairs, let's try to think of why the rule implies the property.

This relation is reflexive because every positive integer divides itself. (If $0$ were included in the set then the relation would not be reflexive, since $0$ does not divide anything, including itself.)
This relation is not antireflexive because, for example, $1|1\text{.}$
This relation is not symmetric because, for example, $2$ divides $4$ but $4$ does not divide $2\text{.}$
This relation is antisymmetric. Suppose that $a|b$ and $b|a\text{;}$ then, $a=b\text{.}$ (This is because if $b=aj$ and $a=bk\text{,}$ then $a=ajk\text{,}$ implying since everything is positive that $j=k=1$ so $a=b\text{.}$ However, if our domain included negative numbers, this would not have been true!)
This relation is transitive because if $a|b$ and $b|c\text{,}$ then $a|c\text{.}$ The proof of this fact is an exercise in the first proofs chapter.

So, the divisibility relation on a set of positive integers is reflexive, antisymmetric, and transitive. A relation with this set of properties is called a partial order and we will study those in detail shortly.

🔗

Finally, we close the chapter by summarizing all five of the above properties.

Reflexive	All elements related to themselves
Antireflexive	No elements related to themselves
Symmetric	Every pair is invertible
Antisymmetric	No pairs are invertible (except diagonal pairs)
Transitive	Every walk has an arrow relating its starting point to its endpoint