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.
\(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 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{.}\)
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.
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{.}\)
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{.}\)
There are three points, labeled \(x_1\text{,}\)\(x_2\text{,}\) and \(x_3\text{.}\) There is an arrow from \(x_1\) to \(x_2\text{,}\) an arrow from \(x_1\) to \(x_3\text{,}\) and an arrow from \(x_2\) to \(x_3\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{.}\)
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.
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{.}\)
