In this section we look at some properties of relations. In particular, we define the reflexive, symmetric, and transitive properties. We will use directed graphs to identify the properties and look at how to prove whether a relation is reflexive, symmetric, and/or transitive.
Definition8.2.1.
Let \(R\) be a relation on \(A\text{.}\) Then
\(R\) is reflexive if for all \(x\in A\text{,}\)\(x R x\text{.}\) In ordered pair notation, \((x, x)\in R\text{.}\)
\(R\) is symmetric if for all \(x, y\in A\text{,}\) if \(x R y\) then \(y R x\text{.}\) In ordered pair notation, if \((x, y)\in R\) then \((y, x)\in R\text{.}\)
\(R\) is transitive if for all \(x, y, z\in A\text{,}\) if \(x R y\) and \(y R z\) then \(x R z\text{.}\) In ordered pair notation, if \((x, y)\in R\) and \((y, z)\in R\) then \((x, z)\in R\text{.}\)
\(R\) is reflexive since \((x, x)\in R\) for each \(x\in A\text{.}\)
\(R\) is symmetric since if \((x, y)\in R\) then \((y, x)\in R\text{.}\) Note, this property does not mean \((x, y)\in R\text{,}\) just that if a pair is in \(R\text{,}\) then the reverse is as well.
\(R\) is transitive since if \((x, y)\in R\) and \((y, z)\in R\) then \((x, z)\in R\text{.}\) Note, this property can be tedious to check by hand. In this example, though, the only pairs that fit the hypothesis are pairs like \((x, y)=(1, 1), (y, z)=(1, 1)\text{,}\) so \((x, z)=(1, 1)\text{,}\) which is in \(R\text{.}\)
\(R\) is not reflexive since \((1, 1)\notin R\text{.}\)
\(R\) is not symmetric since \((1, 2)\in R\text{,}\) but not \((2, 1)\text{.}\)
\(R\) is transitive since if \((x, y)\in R\) and \((y, z)\in R\) then \((x, z)\in R\text{.}\)
Check: \((x, y)=(1, 2), (y, z)=(2, 3)\text{,}\) so \((x, z)=(1, 3)\text{,}\) which is in \(R\text{.}\) This is the only set of ordered pairs where the second coordinate of the first pair matches the first coordinate of the second pair.
We can use directed graphs to help identify the properties.
Reflexive.
If a relation is reflexive, then the directed graph will have an arrow from the vertex to itself (a loop) at every vertex.
Figure8.2.4.Directed graph for reflexive property
Symmetric.
If a relation is symmetric, then whenever the directed graph has an arrow from vertex, \(v\) to vertex \(u\text{,}\) there is a corresponding arrow going from \(u\) to \(v\text{.}\)
Figure8.2.5.Directed graph for symmetric property
Transitive.
If a relation is transitive, then whenever the directed graph has an arrow from vertex, \(v\) to vertex \(u\) followed by an arrow from \(u\) to \(w\text{,}\) there is a corresponding arrow going from \(v\) to \(w\text{.}\)
Figure8.2.6.Directed graph for transitive property
Activity8.2.1.
Let \(A=\{1, 2, 3\}\text{.}\) Let \(R=\{(1, 1), (1, 2), (1, 3), (2, 1), (3, 1)\}\text{.}\)
(a)
Determine if \(R\) is reflexive.
(b)
Determine if \(R\) is symmetric.
(c)
Determine if \(R\) is transitive.
(d)
Draw the directed graph for \(R\text{.}\)
Activity8.2.2.
Let \(A=\{1, 2, 3, 4\}\text{.}\) Let \(R=\{(1, 1), (1, 3), (2, 2), (3, 2), (3, 3)\}\text{.}\)
(a)
Determine if \(R\) is reflexive.
(b)
Determine if \(R\) is symmetric.
(c)
Determine if \(R\) is transitive.
(d)
Draw the directed graph for \(R\text{.}\)
The transitive closure of a relation \(R\text{,}\) denoted \(R^{t}\text{,}\) is the set of ordered pairs in \(R\) as well as all additional ordered pairs to make the relation transitive.
Let \(R=\{(1, 2), (3, 2), (4, 1), (4, 3)\}\text{.}\) Then in \(R^{t}\) we need \((4, 2)\text{.}\) You can check with a directed graph to see this is the only pair we need to add. Thus, \(R^{t}=\{(1, 2), (3, 2), (4, 1), (4, 3), (4, 2)\}\text{.}\)
Let \(R=\{(1, 1), (1, 2), (1, 3), (2, 1), (3, 1)\}\text{.}\) What ordered pairs, if any, should you add to the relation to make \(R\) transitive?
(b)
Let \(R=\{(1, 1), (1, 3), (2, 2), (3, 2), (3, 3)\}\text{.}\) What ordered pairs, if any, should you add to the relation to make \(R\) transitive?
Checking that a relation is reflexive, symmetric, or transitive on a small finite set can be done by checking that the property holds for all the elements of \(R\text{.}\) But if \(A\) is infinite we need to prove the properties more generally.
Let \(R\) be the relation on \(\mathbb{Z}\) given by \((m, n)\in R\Leftrightarrow 3\mid(m-n)\text{.}\)
Reflexive: Show \((m, m)\in R\text{.}\)
We know \(m-m=0\text{,}\) and \(3\mid 0\text{.}\) So we get that \(3\mid m-m\text{.}\) Thus \((m, m)\in R\) for all \(m\in \mathbb{Z}\text{.}\)
Symmetric: Assume \((x, y)\in R\text{.}\)
Then \(3\mid (x-y)\text{.}\) This implies \(x-y=3k\) for some \(k\in\mathbb{Z}\text{.}\) But then \(y-x=-3k=3(-k)\text{,}\) where \(-k\in \mathbb{Z}\text{.}\) Thus, \(3\mid (y-x)\text{.}\) Hence, \((y, x)\in R\text{.}\)
Then \(3\mid (x-y)\) and \(3\mid (y-z)\text{.}\) This implies \(x-y=3k\) for some \(k\in\mathbb{Z}\) and \(y-z=3j\) for some \(j\in\mathbb{Z}\text{.}\) But then \(x-z=x-y+y-z=3k+3j=3(j+k)\text{,}\) where \(k+j\in \mathbb{Z}\text{.}\) Thus, \(3\mid (x-z)\text{.}\) Hence, \((x, z)\in R\text{.}\)
Activity8.2.4.
Define the relation on \(\mathbb{R}\) by \(xRy \iff x=y\text{.}\)
(a)
Prove or disprove \(R\) is reflexive.
(b)
Prove or disprove \(R\) is symmetric.
(c)
Prove or disprove \(R\) is transitive.
Activity8.2.5.
Define the relation on \(\mathbb{R}\) by \(xRy \iff x < y\text{.}\)
(a)
Prove or disprove \(R\) is reflexive.
(b)
Prove or disprove \(R\) is symmetric.
(c)
Prove or disprove \(R\) is transitive.
Reading QuestionsCheck Your Understanding
1.
Determine if the relation is reflexive, symmetric, transitive where \(R\) is the relation on \(A=\{1, 2, 3\}\) given by
\begin{equation*}
a R b \Leftrightarrow a\leq b.
\end{equation*}
Reflexive
We know \(a\leq a\text{.}\)
Symmetric
For example, \(1\leq 2\text{,}\) but \(2\nleq 1\text{.}\)
Transitive
If \(a \leq b\text{,}\) and \(b\leq c\text{,}\) then \(a\leq c\text{.}\)
2.
Determine if the relation is reflexive, symmetric, transitive where \(R\) is the relation on \(C=\{0, 1\}\) given by
\begin{equation*}
a R b \Leftrightarrow a+b \text{ is even}.
\end{equation*}
Reflexive
We know \(a+a=2a\text{,}\) which is even.
Symmetric
If \(a+b\) is even, then \(b+a\) is even.
Transitive
Since \(R=\{(0, 0), (1, 1)\}\text{,}\) it is straightforward to check reflexive by hand.
3.
Determine if the relation is reflexive, symmetric, transitive where \(R\) is the relation on \(B=\{2, 4, 6, 8\}\) given by
\begin{equation*}
a R b \Leftrightarrow a\mid b.
\end{equation*}
Reflexive
We know \(a\mid a\text{.}\)
Symmetric
For example, \(2\mid 4\text{,}\) but \(4\nmid 2\text{.}\)
Transitive
If \(a \mid b\text{,}\) and \(b\mid c\text{,}\) then \(a\mid c\text{.}\)
4.
Determine if the relation is reflexive, symmetric, transitive where \(R\) is the relation on \(\mathbb{Z}\) given by
\begin{equation*}
a R b \Leftrightarrow a+b=0.
\end{equation*}
Reflexive
For example, \(1+1\neq 0\text{.}\)
Symmetric
If \(a+b=0\text{,}\) then \(b+a=0\text{.}\)
Transitive
For example, \(1+(-1)=0\text{,}\) and \((-1)+1=0\text{,}\) but \(1+1\neq 0\text{.}\)
ExercisesExercises
1.
Let \(A=\{0, 1, 2, 3\}\text{.}\) Let \(R_1=\{(0, 0), (0, 1), (0, 3), (1, 1), (1, 0), (2, 3), (3, 3)\}\text{.}\)
Draw the directed graph for \(R_1\text{.}\)
Determine if \(R_1\) is reflexive. If it is not, give a counterexample.
Determine if \(R_1\) is symmetric. If it is not, give a counterexample.
Determine if \(R_1\) is transitive. If it is not, give a counterexample.
2.
Let \(A=\{0, 1, 2, 3\}\text{.}\) Let \(R_2=\{(1, 2), (2, 1), (1, 3), (3, 1)\}\text{.}\)
Draw the directed graph for \(R_2\text{.}\)
Determine if \(R_2\) is reflexive. If it is not, give a counterexample.
Determine if \(R_2\) is symmetric. If it is not, give a counterexample.
Determine if \(R_2\) is transitive. If it is not, give a counterexample.
3.
Let \(A=\{0, 1, 2, 3\}\text{.}\) Let \(R_3=\{(0, 0), (0, 1), (0, 2), (1, 2)\}\text{.}\)
Draw the directed graph for \(R_3\text{.}\)
Determine if \(R_3\) is reflexive. If it is not, give a counterexample.
Determine if \(R_3\) is symmetric. If it is not, give a counterexample.
Determine if \(R_3\) is transitive. If it is not, give a counterexample.
4.
Let \(G\) be the relation on \(\mathbb{R}\) defined by
