Discrete Mathematics: Problem that represents the following digraph that represe

Question

Discrete Mathematics:
Problem that represents the following digraph that represents a relation R on a set of points Consider R (a) Write out the elements of R (b) Is Ran equivalence relation? If it is not, which property or properties fail to hold? Problem 6 (Extra Credit; 5 points). Suppose that a relation R on a set X is a partial order (i.e., R is reflexive, antisymmetric, and transitive Recall that the inverse of R, denoted by R 1, is defined by (y, ar) (ar, y) E R Show that R is also a partial order on X (i.e., R is also reflexive, antisymmetric, and transitive)

Explanation / Answer

Problem 5.

(a)

R = {(a,a), (b,b), (c,c), (d,d), (a,b), (b,a), (b,c), (c,b), (c,d), (d,c), (d,a), (a,d)}

(b)

R is not an equivalence relation, because it is not transitive.

A given relation said to be an equivalence relation if and only if it is reflexive, symmetric and transitive.

X = {a, b, c, d}

Reflexive: aRa for all a X,

All the elements of X have their reflexive in R.

(a,a), (b,b), (c,c), (d,d) R.

2. Symmetric: aRb implies bRa for all a,b X

For all elements in R their symmetric are also available in R

(a,b), (b,a) R

(b,c), (c,b) R

(c,d), (d,c) R

(d,a), (a,d) R

3. Transitive: aRb and bRc imply aRc for all a,b,c X,

This relation is not transitive because

(a,b) and (b,c) R but (a,c) R

So this relation is not equivalence relation.

Problem 6.

R is a partial order. R is reflexive, anti-symmetry, and transitive.

Now for R-1,

1. R-1 is reflexive

If (a,a) R, then (a,a) R-1 by reflexivity of R

2. R-1 is anti-symmetric.

If (a,b) R, and a b, then (b,a) R

For R-1, (b,a) R-1 by inverse of R, (a,b) R-1 by inverse of R

So R-1 must be anti-symmetric.

3. R-1 is transitive.

If (a,b), (b,c) R (a,c) R, a,b,c X

By the inverse of R

(b,a), (c,b), (c,a) R-1

For all (c,b), (b,a) R-1 , (c,a) R-1, a,b,c X

so finally we can say that R-1 is also a partial order relation.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.