6.2: Properties of Relations
 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}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{\!\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{\!\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
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 xy\). Since \(aa\) 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:proprelat02}\)
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:proprelat03}\)
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.
handson exercise \(\PageIndex{1}\label{he:proprelat01}\)
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.
handson exercise \(\PageIndex{2}\label{he:proprelat02}\)
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:proprelat04}\)
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:proprelat05}\)
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
handson 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:proprelat06}\)
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.
handson 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 (xy)\).
Note: (1) \(R\) is called Congruence Modulo 5. (2) We have proved \(a\mod 5 = b\mod 5 \iff 5 \mid (ab)\).
Prove \(R\) is an equivalence relation.
 Proof:

Reflexive: Consider any integer \(a\). \(aa=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 (ab)\) by definition of \(R.\) By definition of divides, there exists an integer \(k\) such that \[5k=ab. \nonumber\]
By algebra: \[5k=ba \nonumber\] \[5(k)=ba. \nonumber\]
\(k \in \mathbb{Z}\) since the set of integers is closed under multiplication. So, \(5 \mid (ba)\) 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 (ab)\) and \(5 \mid (bc)\) by definition of \(R.\) By definition of divides, there exists an integers \(j,k\) such that \[5j=ab. \nonumber\]\[5k=bc. \nonumber\] Adding the equations together and using algebra: \[5j+5k=ac \nonumber\]\[5(j+k)=ac. \nonumber\] \(j+k \in \mathbb{Z}\) since the set of integers is closed under addition. So, \(5 \mid (ac)\) 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\}\)