Reflexive, Symmetric, Transitive Properties

Section 8.2 Reflexive, Symmetric, Transitive Properties

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.

Definition 8.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{.}$

Example 8.2.2. Reflexive, Symmetric, Transitive.

Let $A=\{1, 2, 3\}\text{,}$ define the relation on $A$ by

\begin{equation*} R=\{(1, 1), (2, 2), (3, 3)\}. \end{equation*}

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

Example 8.2.3. Another Look at the Properties.

Let $A=\{1, 2, 3\}\text{,}$ define the relation on $A$ by

\begin{equation*} R=\{(1, 2), (1, 3), (2, 3)\}. \end{equation*}

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

Figure 8.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{.}$

Figure 8.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{.}$

Figure 8.2.6. Directed graph for transitive property

Activity 8.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{.}$

Activity 8.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.

Example 8.2.7. Transitive Closure.

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

Activity 8.2.3.

For the relations in Activity 8.2.1 and Activity 8.2.2, find the transitive closure.

(a)

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.

Proving Reflexive, Symmetric, Transitive Properties.

To prove a property of a relation:

Reflexive.
Let $x\in A\text{.}$ Show $(x, x)\in R\text{.}$
Symmetric.
Assume $(x, y)\in R\text{.}$ Show $(y, x)\in R\text{.}$
Transitive.
Assume $(x, y), (y, z)\in R\text{.}$ Show $(x, z)\in R\text{.}$

To disprove a property, find a specific counterexample:

Reflexive.
Find $(x, x)\notin R$ for some $x\in A\text{.}$
Symmetric.
Find $(x, y)\in R$ with $(y, x)\notin R\text{.}$
Transitive.
Find $(x, y), (y, z)\in R$ with $(x, z)\notin R\text{.}$

Example 8.2.8. Proving Reflexive, Symmetric, Transitive.

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

Transitive: Assume $(x, y), (y, z)\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{.}$

Activity 8.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.

Activity 8.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 Questions Check 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{.}$

Exercises Exercises

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

\begin{equation*} x\ G\ y\iff xy\geq 0. \end{equation*}

Determine if $G$ is reflexive. Justify your answer.
Determine if $G$ is symmetric. Justify your answer.
Determine if $G$ is transitive. Justify your answer.

5.

Let $D$ be the relation on $\mathbb{Z}^+$ defined by

\begin{equation*} m\ D\ n\iff m\mid n. \end{equation*}

Determine if $D$ is reflexive. Justify your answer.
Determine if $D$ is symmetric. Justify your answer.
Determine if $D$ is transitive. Justify your answer.

6.

Let $F$ be the relation on $\mathbb{R}\times \mathbb{R}$ defined by

\begin{equation*} (x_1, y_1)\ F\ (x_2, y_2)\iff x_1=x_2. \end{equation*}

Determine if $F$ is reflexive. Justify your answer.
Determine if $F$ is symmetric. Justify your answer.
Determine if $F$ is transitive. Justify your answer.

7.

Define the relation $R$ on $\mathbb{Z}$ by

\begin{equation*} m\ R\ n \iff 5\mid(m-n). \end{equation*}

Prove or disprove $R$ is reflexive.
Prove or disprove $R$ is symmetric.
Prove or disprove $R$ is transitive.

8.

Let $X=\{a, b, c\}$ and ${\cal P}(X)$ be the power set of $X\text{.}$ Define the relation $L$ on ${\cal P}(X)$ by

\begin{equation*} A\ L\ B \iff \text{ the number of elements in $A$ is less than the number of elements in $B$.} \end{equation*}

Prove or disprove $L$ is reflexive.
Prove or disprove $L$ is symmetric.
Prove or disprove $L$ is transitive.

9.

Let $X$ be a nonempty set and ${\cal P}(X)$ be the power set of $X\text{.}$ Define the “subset” relation $S$ on ${\cal P}(X)$ by

\begin{equation*} A\ S\ B \iff A\subseteq B. \end{equation*}

Prove or disprove $S$ is reflexive.
Prove or disprove $S$ is symmetric.
Prove or disprove $S$ is transitive.

10.

Let $R$ be a relation on a set $A\text{.}$ Prove or disprove if $R$ is reflexive, then $R^{-1}$ is reflexive.

11.

Let $R$ be a relation on a set $A\text{.}$ Prove or disprove if $R$ is symmetric, then $R^{-1}$ is symmetric.

You have attempted of activities on this page.

Prev Top Next