6.2: Properties of Relations

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?

Answer

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?

Answer

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$.

Answer:

(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 } \}$

Answer:

(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 } \}$

Answer:

(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\}$