Definition :

**A relation R on a set A is called reflexive if (a, a) ∈ R for every element a ∈ A**

*Using quantifiers we see that the relation R on the set A is reflexive if ∀a((a, a) ∈ R),**where the universe of discourse is the set of all elements in A*

*A relation R on a set A is called***symmetric**if(b, a) ∈ R whenever(a, b) ∈ R, for all a, b ∈ A.

*A relation R on a set A such that for all a, b ∈ A, if (a, b) ∈ R and (b, a) ∈ R, then a = b**is called***antisymmetric**.

*Remark: Using quantifiers, we see that the relation R on the set A is symmetric if**∀a∀b((a, b) ∈ R → (b, a) ∈ R). Similarly, the relation R on the set A is antisymmetric if**∀a∀b(((a, b) ∈ R ∧ (b, a) ∈ R) → (a = b)).*

*That is, a relation is symmetric if and only if a is related to b implies that b is related to a.**A relation is antisymmetric if and only if there are no pairs of distinct elements a and b with a**related to b and b related to a. That is, the only way to have a related to b and b related to a is**for a and b to be the same element. The terms symmetric and antisymmetric are not opposites,**because a relation can have both of these properties or may lack both of them (see Exercise**10). A relation cannot be both symmetric and antisymmetric if it contains some pair of the form**(a, b), where a = b.*
A relation R on a set A is called

**transitive**if whenever (a, b) ∈ R and (b, c) ∈ R,
then (a, c) ∈ R, for all a, b, c ∈ A.

**Consider the following relations on {1, 2, 3, 4}:**

**R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)},**

**R2 = {(1, 1), (1, 2), (2, 1)},**

**R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)},**

**R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)},**

**R5 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)},**

**R6 = {(3, 4)}.**

**Reference**

Discrete Mathematics and Its Applications - Seventh Edition

Kenneth H. Rosen

## No comments:

## Post a Comment