$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 6.2: Properties of Relations

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

Note: If we say $$R$$ is a relation "on set $$A$$" this means $$R$$ is a relation from $$A$$ to $$A$$; in other words, $$R\subseteq A\times A$$.

We will define three properties which a relation might have.

## Definition: Reflexive Property

A relation $$R$$ on $$A$$ is  reflexive  if and only if for all $$a\in A$$, $$aRa$$.

example: consider $$D: \mathbb{Z} \to \mathbb{Z}$$ by $$xDy \iff x|y$$. Since $$a|a$$ for all $$a \in \mathbb{Z}$$ the relation $$D$$ is reflexive.

## Definition: Symmetric Property

A relation $$R$$ on $$A$$ is  symmetric if and only if for all $$a,b \in A$$, if $$aRb$$, then $$bRa$$.

Clearly the relation $$=$$ is symmetric since $$x=y \rightarrow y=x.$$  However, divides is not symmetric, since $$5 \mid10$$ but $$10\nmid 5$$.

## Definition: Transitive Property

A relation $$R$$ on $$A$$ is  transitive if and only if for all $$a,b,c \in A$$, if $$aRb$$ and $$bRc$$, then $$aRc$$.

example: consider $$G: \mathbb{R} \to \mathbb{R}$$ by $$xGy \iff x > y$$.  Since if $$a>b$$ and $$b>c$$ then $$a>c$$ is true for all $$a,b,c \in \mathbb{R}$$, the relation $$G$$ is transitive.

Example $$\PageIndex{1}$$

$$B$$ is a relation on all people on Earth defined by $$xBy$$ if and only if $$x$$ is a brother of $$y.$$

Reflexive?

No, Jamal is not a brother to himself.

Symmetric?

No, Jamal can be the brother of Elaine, but Elaine is not the brother of Jamal.

Transitive?

Yes, if $$X$$ is the brother of $$Y$$ and $$Y$$ is the brother of $$Z$$ , then $$X$$ is the brother of $$Z.$$

Example $$\PageIndex{2}\label{eg:proprelat-02}$$

Consider the relation $$R$$ on the set $$A=\{1,2,3,4\}$$ defined by $R = \{(1,1),(2,3),(2,4),(3,3),(3,4)\}.$

Reflexive?

No, since $$(2,2)\notin R$$, the relation is not reflexive.

Symmetric?

No, we have $$(2,3)\in R$$ but $$(3,2)\notin R$$, thus $$R$$ is not symmetric.

Transitive?

Yes. By going through all the ordered pairs in $$R$$, we verify that whether $$(a,b)\in R$$ and $$(b,c)\in R$$, we always have $$(a,c)\in R$$ as well. This shows that $$R$$ is transitive.

Example $$\PageIndex{3}\label{eg:proprelat-03}$$

Define the relation $$S$$ on the set $$A=\{1,2,3,4\}$$ according to $S = \{(2,3),(3,2)\}.$

Reflexive?

No, since $$(2,2)\notin R$$, the relation is not reflexive.

Symmetric?

Yes.  Since we have only two ordered pairs, and it is clear that whenever $$(a,b)\in S$$, we also have $$(b,a)\in S$$. Hence, $$S$$ is symmetric.

Transitive?

Since $$(2,3)\in S$$ and $$(3,2)\in S$$, but $$(2,2)\notin S$$, the relation $$S$$ is not transitive.

hands-on exercise $$\PageIndex{1}\label{he:proprelat-01}$$

Define the relation $$R$$ on the set $$\mathbb{R}$$ as $a\,R\,b \,\Leftrightarrow\, a\leq b.$ Determine whether $$R$$ is reflexive, symmetric, or transitive.

hands-on exercise $$\PageIndex{2}\label{he:proprelat-02}$$

The relation $$S$$ on the set $$\mathbb{R}^*$$ is defined as $a\,S\,b \,\Leftrightarrow\, ab>0.$ Determine whether $$S$$ is reflexive, symmetric, or transitive.

Example $$\PageIndex{4}\label{eg:geomrelat}$$

Here are two examples from geometry. Let $${\cal T}$$ be the set of triangles that can be drawn on a plane. Define a relation $$S$$ on $${\cal T}$$ such that $$(T_1,T_2)\in S$$ if and only if the two triangles are similar. It is easy to check that $$S$$ is reflexive, symmetric, and transitive.

Let $${\cal L}$$ be the set of all the (straight) lines on a plane. Define a relation $$P$$ on $${\cal L}$$ according to $$(L_1,L_2)\in P$$ if and only if $$L_1$$ and $$L_2$$ are parallel lines. Again, it is obvious that $$P$$ is reflexive, symmetric, and transitive.

Example $$\PageIndex{5}\label{eg:proprelat-04}$$

The relation $$T$$ on $$\mathbb{R}^*$$ is defined as $a\,T\,b \,\Leftrightarrow\, \frac{a}{b}\in\mathbb{Q}.$

Since $$\frac{a}{a}=1\in\mathbb{Q}$$, the relation $$T$$ is reflexive.

The relation $$T$$ is symmetric, because if $$\frac{a}{b}$$ can be written as $$\frac{m}{n}$$ for some nonzero integers $$m$$ and $$n$$, then so is its reciprocal $$\frac{b}{a}$$, because $$\frac{b}{a}=\frac{n}{m}$$.

If $$\frac{a}{b}, \frac{b}{c}\in\mathbb{Q}$$, then $$\frac{a}{b}= \frac{m}{n}$$ and $$\frac{b}{c}= \frac{p}{q}$$ for some nonzero integers $$m$$, $$n$$, $$p$$, and $$q$$. Then $$\frac{a}{c} = \frac{a}{b}\cdot\frac{b}{c} = \frac{mp}{nq} \in\mathbb{Q}$$. Hence, $$T$$ is transitive.

Therefore, the relation $$T$$ is reflexive, symmetric, and transitive.

## Definition: Equivalence Relation

A relation is an equivalence relation if and only if the relation is reflexive, symmetric and transitive.

Example $$\PageIndex{6}\label{eg:proprelat-05}$$

The relation $$U$$ on $$\mathbb{Z}$$ is defined as $a\,U\,b \,\Leftrightarrow\, 5\mid(a+b).$

Is $$U$$ an equivalence relation?

If $$5\mid(a+b)$$, it is obvious that $$5\mid(b+a)$$ because $$a+b=b+a$$. Thus, $$U$$ is symmetric.
However,  $$U$$ is not reflexive, because $$5\nmid(1+1)$$.
Therefore $$U$$ is not an equivalence relation

hands-on exercise $$\PageIndex{3}$$

Determine whether the following relation $$V$$ on some universal set $$\cal U$$ is an equivalence relation: $(S,T)\in V \,\Leftrightarrow\, S\subseteq T.$

Example $$\PageIndex{7}\label{eg:proprelat-06}$$

Consider the relation $$V$$ on the set $$A=\{0,1\}$$ is defined according to $V = \{(0,0),(1,1)\}.$

Is $$V$$ an equivalence relation?

The relation $$V$$ is reflexive, because $$(0,0)\in V$$ and $$(1,1)\in V$$.
It is clearly symmetric, because $$(a,b)\in V$$ always implies $$(b,a)\in V$$.
Because $$V$$ consists of only two ordered pairs, both of them in the form of $$(a,a)$$, $$V$$ is transitive.
Therefore, $$V$$ is an equivalence relation.

hands-on exercise $$\PageIndex{4}$$

Determine whether the following relation $$W$$ on a nonempty set of individuals in a community is an equivalence relation: $a\,W\,b \,\Leftrightarrow\, \mbox{a and b have the same last name}.$

### Example $$\PageIndex{8}$$ Congruence Modulo 5

Consider the relation $$R$$ on $$\mathbb{Z}$$ defined by $$xRy \iff 5 \mid (x-y)$$.

Note:  (1) $$R$$ is called Congruence Modulo 5.  (2) We have proved  $$a\mod 5 = b\mod 5 \iff 5 \mid (a-b)$$.

Prove $$R$$ is an equivalence relation.

Proof:

Reflexive: Consider any integer $$a$$.  $$a-a=0$$.  $$5 \mid 0$$ by the definition of divides since $$5(0)=0$$ and $$0 \in \mathbb{Z}$$.
So, $$5 \mid (a=a)$$ thus $$aRa$$ by definition of $$R$$.
$$\therefore R$$ is reflexive.

Symmetric: Let $$a,b \in \mathbb{Z}$$ such that $$aRb.$$  We must show that $$bRa.$$
Since $$aRb$$,  $$5 \mid (a-b)$$ by definition of $$R.$$ By definition of divides, there exists an integer $$k$$ such that $5k=a-b. \nonumber$
By algebra: $-5k=b-a \nonumber$ $5(-k)=b-a. \nonumber$
$$-k \in \mathbb{Z}$$ since the set of integers is closed under multiplication. So, $$5 \mid (b-a)$$ by definition of divides. $$bRa$$ by definition of $$R.$$
$$\therefore R$$ is symmetric.

Transitive: Let $$a,b,c \in \mathbb{Z}$$ such that $$aRb$$ and $$bRc.$$  We must show that $$aRc.$$
$$5 \mid (a-b)$$ and $$5 \mid (b-c)$$ by definition of $$R.$$ By definition of divides, there exists an integers $$j,k$$ such that $5j=a-b. \nonumber$$5k=b-c. \nonumber$ Adding the equations together and using algebra: $5j+5k=a-c \nonumber$$5(j+k)=a-c. \nonumber$  $$j+k \in \mathbb{Z}$$ since the set of integers is closed under addition. So, $$5 \mid (a-c)$$ by definition of divides. $$aRc$$ by definition of $$R.$$
$$\therefore R$$ is transitive.

Thus, by definition of equivalence relation, $$R$$ is an equivalence relation.

## Summary and Review

• A relation from a set $$A$$ to itself is called a relation on set $$A$$.
• Given any relation $$R$$ on a set $$A$$, we are interested in three properties that $$R$$ may or may not have.
• The relation $$R$$ is said to be reflexive if every element is related to itself, that is, if $$x\,R\,x$$ for every $$x\in A$$.
• The relation $$R$$ is said to be symmetric if the relation can go in both directions, that is, if $$x\,R\,y$$ implies $$y\,R\,x$$ for any $$x,y\in A$$.
• Finally, a relation is said to be transitive if we can pass along the relation and relate two elements if they are related via a third element.
• More precisely, $$R$$ is transitive if $$x\,R\,y$$ and $$y\,R\,z$$ implies that $$x\,R\,z$$.

## Exercises

Exercise $$\PageIndex{1}$$

Let $$S$$ be a nonempty set and define the relation $$A$$ on $$\scr{P}$$$$(S)$$ by $(X,Y)\in A \Leftrightarrow X\cap Y=\emptyset.$ It is clear that $$A$$ is symmetric.

a) Explain why $$A$$ is not reflexive.

b) Is $$A$$ transitive? Explain.

c) Let $$S=\{a,b,c\}$$. Draw the directed (arrow) graph for $$A$$.

(a) Since set $$S$$ is not empty, there exists at least one element in $$S$$, call one of the elements $$x$$. The power set must include $$\{x\}$$ and $$\{x\}\cap\{x\}=\{x\}$$ and thus is not empty.  So we have shown an element which is not related to itself; thus $$S$$ is not reflexive.
(b) Consider these possible elements of the power set:  $$S_1=\{w,x,y\},\qquad S_2=\{a,b\},\qquad S_3=\{w,x\}$$.  $$S_1\cap S_2=\emptyset$$ and  $$S_2\cap S_3=\emptyset$$, but $$S_1\cap S_3\neq\emptyset$$. We have shown a counter example to transitivity, so $$A$$ is not transitive.
(c) Here's a sketch of some of the diagram should look:
-There are eight elements on the left and eight elements on the right
-This relation is symmetric, so every arrow has a matching cousin. i.e there is $$\{a,c\}\right arrow\{b}\}$$ and also $$\{b\}\right arrow\{a,c}\}$$.
-The empty set is related to all elements including itself; every element is related to the empty set.

Exercise $$\PageIndex{2}$$

For each of these relations on $$\mathbb{N}-\{1\}$$, determine which of the three properties are satisfied.

a) $$A_1=\{(x,y)\mid x \mbox{ and } y \mbox{ are relatively prime}\}$$

b) $$A_2=\{(x,y)\mid x \mbox{ and } y \mbox{ are not relatively prime}\}$$

Exercise $$\PageIndex{3}$$

For each of the following relations on $$\mathbb{N}$$, determine which of the three properties are satisfied.

a) $$B_1=\{(x,y)\mid x \mbox{ divides } y\}$$

b) $$B_2=\{(x,y)\mid x +y \mbox{ is even } \}$$

c) $$B_3=\{(x,y)\mid xy \mbox{ is even } \}$$

(a) reflexive, transitive
(b) reflexive, symmetric, transitive
(c) symmetric

Exercise $$\PageIndex{4}$$

For each of the following relations on $$\mathbb{N}$$, determine which of the three properties are satisfied.

a) $$D_1=\{(x,y)\mid x +y \mbox{ is odd } \}$$

b) $$D_2=\{(x,y)\mid xy \mbox{ is odd } \}$$

Exercise $$\PageIndex{5}$$

For each of the following relations on $$\mathbb{Z}$$, determine which of the three properties are satisfied.

a) $$U_1=\{(x,y)\mid 3 \mbox{ divides } x+2y\}$$

b) $$U_2=\{(x,y)\mid x - y \mbox{ is odd } \}$$

(a) reflexive, symmetric and transitive (try proving this!)
(b) symmetric

Exercise $$\PageIndex{6}$$

For each of the following relations on $$\mathbb{Z}$$, determine which of the three properties are satisfied.

a) $$V_1=\{(x,y)\mid xy>0\}$$

b) $$V_2=\{(x,y)\mid x - y \mbox{ is even } \}$$

c) $$V_3=\{(x,y)\mid x\mbox{ is a multiple of } y\}$$

This page titled 6.2: Properties of Relations is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Harris Kwong (OpenSUNY) .