6.2: Properties of Relations

Last updated
Save as PDF

Page ID: 31164

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\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]{\| #1 \|}$ $ \newcommand{\inner}[2]{\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]{\| #1 \|}$ $ \newcommand{\inner}[2]{\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?

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