Skip to main content

Discrete Mathematics An Active Approach to Mathematical Reasoning

Jennifer Firkins Nordstrom

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. Then
  1. R is reflexive if for all x∈A, xRx. In ordered pair notation, (x,x)∈R.
    🔗
  2. R is symmetric if for all x,y∈A, if xRy then yRx. In ordered pair notation, if (x,y)∈R then (y,x)∈R.
    🔗
  3. R is transitive if for all x,y,z∈A, if xRy and yRz then xRz. In ordered pair notation, if (x,y)∈R and (y,z)∈R then (x,z)∈R.
    🔗
🔗
🔗

Example 8.2.2. Reflexive, Symmetric, Transitive.

Let A={1,2,3}, define the relation on A by
R={(1,1),(2,2),(3,3)}.
🔗
R is reflexive since (x,x)∈R for each x∈A.
🔗
R is symmetric since if (x,y)∈R then (y,x)∈R. Note, this property does not mean (x,y)∈R, just that if a pair is in R, then the reverse is as well.
🔗
R is transitive since if (x,y)∈R and (y,z)∈R then (x,z)∈R. 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), so (x,z)=(1,1), which is in R.
🔗
🔗

Example 8.2.3. Another Look at the Properties.

Let A={1,2,3}, define the relation on A by
R={(1,2),(1,3),(2,3)}.
🔗
R is not reflexive since (1,1)∉R.
🔗
R is not symmetric since (1,2)∈R, but not (2,1).
🔗
R is transitive since if (x,y)∈R and (y,z)∈R then (x,z)∈R.
🔗
Check: (x,y)=(1,2),(y,z)=(2,3), so (x,z)=(1,3), which is in R. 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, there is a corresponding arrow going from u to v.
    🔗
    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, there is a corresponding arrow going from v to w.
    🔗
    Figure 8.2.6. Directed graph for transitive property
    🔗
    🔗
🔗

Activity 8.2.1.

Let A={1,2,3}. Let R={(1,1),(1,2),(1,3),(2,1),(3,1)}.
🔗

(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.
🔗
🔗
🔗

Activity 8.2.2.

Let A={1,2,3,4}. Let R={(1,1),(1,3),(2,2),(3,2),(3,3)}.
🔗

(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.
🔗
🔗
🔗
The transitive closure of a relation R, denoted Rt, 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)}. Then in Rt we need (4,2). You can check with a directed graph to see this is the only pair we need to add. Thus, Rt={(1,2),(3,2),(4,1),(4,3),(4,2)}.
🔗
🔗

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)}. 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)}. 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. 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∈A. Show (x,x)∈R.
    🔗
    🔗
  • Symmetric.
    Assume (x,y)∈R. Show (y,x)∈R.
    🔗
    🔗
  • Transitive.
    Assume (x,y),(y,z)∈R. Show (x,z)∈R.
    🔗
    🔗
🔗
To disprove a property, find a specific counterexample:
  • Reflexive.
    Find (x,x)∉R for some x∈A.
    🔗
    🔗
  • Symmetric.
    Find (x,y)∈R with (y,x)∉R.
    🔗
    🔗
  • Transitive.
    Find (x,y),(y,z)∈R with (x,z)∉R.
    🔗
    🔗
🔗
🔗

Example 8.2.8. Proving Reflexive, Symmetric, Transitive.

Let R be the relation on Z given by (m,n)∈R⇔3∣(m−n).
🔗
Reflexive: Show (m,m)∈R.
🔗
We know m−m=0, and 3∣0. So we get that 3∣m−m. Thus (m,m)∈R for all m∈Z.
🔗
Symmetric: Assume (x,y)∈R.
🔗
Then 3∣(x−y). This implies x−y=3k for some k∈Z. But then y−x=−3k=3(−k), where −k∈Z. Thus, 3∣(y−x). Hence, (y,x)∈R.
🔗
Transitive: Assume (x,y),(y,z)∈R.
🔗
Then 3∣(x−y) and 3∣(y−z). This implies x−y=3k for some k∈Z and y−z=3j for some j∈Z. But then x−z=x−y+y−z=3k+3j=3(j+k), where k+j∈Z. Thus, 3∣(x−z). Hence, (x,z)∈R.
🔗
🔗

Activity 8.2.4.

Define the relation on R by xRy⟺x=y.
🔗

(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 R by xRy⟺x<y.
🔗

(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
aRb⇔a≤b.
🔗
  • Reflexive
    🔗
  • We know a≤a.
  • Symmetric
    🔗
  • For example, 1≤2, but 2≰1.
  • Transitive
    🔗
  • If a≤b, and b≤c, then a≤c.
🔗

2.

Determine if the relation is reflexive, symmetric, transitive where R is the relation on C={0,1} given by
aRb⇔a+b is even.
🔗
  • Reflexive
    🔗
  • We know a+a=2a, which is even.
  • Symmetric
    🔗
  • If a+b is even, then b+a is even.
  • Transitive
    🔗
  • Since R={(0,0),(1,1)}, 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
aRb⇔a∣b.
🔗
  • Reflexive
    🔗
  • We know a∣a.
  • Symmetric
    🔗
  • For example, 2∣4, but 4∤2.
  • Transitive
    🔗
  • If a∣b, and b∣c, then a∣c.
🔗

4.

Determine if the relation is reflexive, symmetric, transitive where R is the relation on Z given by
aRb⇔a+b=0.
🔗
  • Reflexive
    🔗
  • For example, 1+1≠0.
  • Symmetric
    🔗
  • If a+b=0, then b+a=0.
  • Transitive
    🔗
  • For example, 1+(−1)=0, and (−1)+1=0, but 1+1≠0.
🔗
🔗

Exercises Exercises

1.

Let A={0,1,2,3}. Let R1={(0,0),(0,1),(0,3),(1,1),(1,0),(2,3),(3,3)}.
🔗
  1. Draw the directed graph for R1.
    🔗
    🔗
  2. Determine if R1 is reflexive. If it is not, give a counterexample.
    🔗
    🔗
  3. Determine if R1 is symmetric. If it is not, give a counterexample.
    🔗
    🔗
  4. Determine if R1 is transitive. If it is not, give a counterexample.
    🔗
    🔗
🔗

2.

Let A={0,1,2,3}. Let R2={(1,2),(2,1),(1,3),(3,1)}.
🔗
  1. Draw the directed graph for R2.
    🔗
    🔗
  2. Determine if R2 is reflexive. If it is not, give a counterexample.
    🔗
    🔗
  3. Determine if R2 is symmetric. If it is not, give a counterexample.
    🔗
    🔗
  4. Determine if R2 is transitive. If it is not, give a counterexample.
    🔗
    🔗
🔗

3.

Let A={0,1,2,3}. Let R3={(0,0),(0,1),(0,2),(1,2)}.
🔗
  1. Draw the directed graph for R3.
    🔗
    🔗
  2. Determine if R3 is reflexive. If it is not, give a counterexample.
    🔗
    🔗
  3. Determine if R3 is symmetric. If it is not, give a counterexample.
    🔗
    🔗
  4. Determine if R3 is transitive. If it is not, give a counterexample.
    🔗
    🔗
🔗

4.

Let G be the relation on R defined by
x G y⟺xy≥0.
🔗
  1. Determine if G is reflexive. Justify your answer.
    🔗
    🔗
  2. Determine if G is symmetric. Justify your answer.
    🔗
    🔗
  3. Determine if G is transitive. Justify your answer.
    🔗
    🔗
🔗

5.

Let D be the relation on Z+ defined by
m D n⟺m∣n.
🔗
  1. Determine if D is reflexive. Justify your answer.
    🔗
    🔗
  2. Determine if D is symmetric. Justify your answer.
    🔗
    🔗
  3. Determine if D is transitive. Justify your answer.
    🔗
    🔗
🔗

6.

Let F be the relation on R×R defined by
(x1,y1) F (x2,y2)⟺x1=x2.
🔗
  1. Determine if F is reflexive. Justify your answer.
    🔗
    🔗
  2. Determine if F is symmetric. Justify your answer.
    🔗
    🔗
  3. Determine if F is transitive. Justify your answer.
    🔗
    🔗
🔗

7.

Define the relation R on Z by
m R n⟺5∣(m−n).
🔗
  1. Prove or disprove R is reflexive.
    🔗
    🔗
  2. Prove or disprove R is symmetric.
    🔗
    🔗
  3. Prove or disprove R is transitive.
    🔗
    🔗
🔗

8.

Let X={a,b,c} and P(X) be the power set of X. Define the relation L on P(X) by
A L B⟺ the number of elements in A is less than the number of elements in B.
🔗
  1. Prove or disprove L is reflexive.
    🔗
    🔗
  2. Prove or disprove L is symmetric.
    🔗
    🔗
  3. Prove or disprove L is transitive.
    🔗
    🔗
🔗

9.

Let X be a nonempty set and P(X) be the power set of X. Define the “subset” relation S on P(X) by
A S B⟺A⊆B.
🔗
  1. Prove or disprove S is reflexive.
    🔗
    🔗
  2. Prove or disprove S is symmetric.
    🔗
    🔗
  3. Prove or disprove S is transitive.
    🔗
    🔗
🔗

10.

Let R be a relation on a set A. Prove or disprove if R is reflexive, then R−1 is reflexive.
🔗
🔗

11.

Let R be a relation on a set A. Prove or disprove if R is symmetric, then R−1 is symmetric.
🔗
🔗
🔗
You have attempted of activities on this page.
🔗
PrevTopNext