# Relations: Best Answers 007EH

Welcome to **Lesson Four – Relations,** In this lesson, we shall understand what is discrete maths, why do we need it and how do we apply it in our day-to-day activities.

You can also join the **Discrete Mathematics Forum **to interact and share ideas, also you can navigate to any session using the **Table of Content **

Don’t forget to leave your comment, suggestions regarding the previous, and current lecture to help us improve.

# Introduction to Binary Relation

Let P and Q be two non-empty sets. A binary relation R is defined to be a subset of P x Q from a set P to Q. If (a, b) ∈ R and R ⊆ P x Q then a is related to b by R i.e., aRb. If sets P and Q are equal, then we say R ⊆ P x P is a relation on P e.g.

- (i) Let A = {a, b, c}
- B = {r, s, t}
- Then R = {(a, r), (b, r), (b, t), (c, s)}
- is a relation from A to B.
- (ii) Let A = {1, 2, 3} and B = A
- R = {(1, 1), (2, 2), (3, 3)}
- is a relation (equal) on A.

**Example1:** If a set has n elements, how many relations are there from A to A.

**Solution:** If a set A has n elements, A x A has n^{2} elements. So, there are 2^{n2} relations from A to A.

**Example2:** If A has m elements and B has n elements. How many relations are there from A to B and vice versa?

**Solution:** There are m x n elements; hence there are 2^{m x n} relations from A to A.

**Example3:** If a set A = {1, 2}. Determine all relations from A to A.

**Solution:** There are 2^{2}= 4 elements i.e., {(1, 2), (2, 1), (1, 1), (2, 2)} in A x A. So, there are 2^{4}= 16 relations from A to A. i.e.

- {(1, 2), (2, 1), (1, 1), (2, 2)}, {(1, 2), (2, 1)}, {(1, 2), (1, 1)}, {(1, 2), (2, 2)},
- {(2, 1), (1, 1)},{(2,1), (2, 2)}, {(1, 1),(2, 2)},{(1, 2), (2, 1), (1, 1)}, {(1, 2), (1, 1),
- (2, 2)}, {(2,1), (1, 1), (2, 2)}, {(1, 2), (2, 1), (2, 2)}, {(1, 2), (2, 1), (1, 1), (2, 2)} and ∅.

## Domain and Range of Relation

**Domain of Relation:** The Domain of relation R is the set of elements in P which are related to some elements in Q, or it is the set of all first entries of the ordered pairs in R. It is denoted by DOM (R).

**Range of Relation:** The range of relation R is the set of elements in Q which are related to some element in P, or it is the set of all second entries of the ordered pairs in R. It is denoted by RAN (R).

**Example:**

- Let A = {1, 2, 3, 4}
- B = {a, b, c, d}
- R = {(1, a), (1, b), (1, c), (2, b), (2, c), (2, d)}.

**Solution:**

DOM (R) = {1, 2} RAN (R) = {a, b, c, d}

## Complement of a Relation

Consider a relation R from a set A to set B. The complement of relation R denoted by R is a relation from A to B such that

R = {(a, b): {a, b) ∉ R}.

**Example:**

- Consider the relation R from X to Y
- X = {1, 2, 3}
- Y = {8, 9}
- R = {(1, 8) (2, 8) (1, 9) (3, 9)}
- Find the complement relation of R.

**Solution:**

X x Y = {(1, 8), (2, 8), (3, 8), (1, 9), (2, 9), (3, 9)} Now we find the complement relation R from X x Y R = {(3, 8), (2, 9)}

# Representation of Relations

Relations can be represented in many ways. Some of which are as follows:

**1. Relation as a Matrix:** Let P = [a_{1},a_{2},a_{3},…….a_{m}] and Q = [b_{1},b_{2},b_{3}……b_{n}] are finite sets, containing m and n number of elements respectively. R is a relation from P to Q. The relation R can be represented by m x n matrix M = [M_{ij}], defined as

M_{ij}= 0 if (a_{i},b_{j}) ∉ R 1 if (a_{i},b_{j})∈ RExample

- Let P = {1, 2, 3, 4}, Q = {a, b, c, d}
- and R = {(1, a), (1, b), (1, c), (2, b), (2, c), (2, d)}.

The matrix of relation R is shown as fig:

**2. Relation as a Directed Graph:** There is another way of picturing a relation R when R is a relation from a finite set to itself.

**Example**

- A = {1, 2, 3, 4}
- R = {(1, 2) (2, 2) (2, 4) (3, 2) (3, 4) (4, 1) (4, 3)}

**3. Relation as an Arrow Diagram:** If P and Q are finite sets and R is a relation from P to Q. Relation R can be represented as an arrow diagram as follows.

Draw two ellipses for the sets P and Q. Write down the elements of P and elements of Q column-wise in three ellipses. Then draw an arrow from the first ellipse to the second ellipse if a is related to b and a ∈ P and b ∈ Q.

**Example**

- Let P = {1, 2, 3, 4}
- Q = {a, b, c, d}
- R = {(1, a), (2, a), (3, a), (1, b), (4, b), (4, c), (4, d)

The arrow diagram of relation R is shown in fig:

**4. Relation as a Table:** If P and Q are finite sets and R is a relation from P to Q. Relation R can be represented in tabular form.

Make the table which contains rows equivalent to an element of P and columns equivalent to the element of Q. Then place a cross (X) in the boxes which represent relations of elements on set P to set Q.

**Example**

- Let P = {1, 2, 3, 4}
- Q = {x, y, z, k}
- R = {(1, x), (1, y), (2, z), (3, z), (4, k)}.

The tabular form of relation as shown in fig:

# Composition of Relations

Let A, B, and C be sets, and let R be a relation from A to B and let S be a relation from B to C. That is, R is a subset of A × B and S is a subset of B × C. Then R and S give rise to a relation from A to C indicated by R◦S and defined by:

- a (R◦S)c
**if****for**some b ∈ B we have aRb and bSc. - is,
- R ◦ S = {(a, c)| there exists b ∈ B
**for**which (a, b) ∈ R and (b, c) ∈ S}

The relation R◦S is known the composition of R and S; it is sometimes denoted simply by RS.

Let R is a relation on a set A, that is, R is a relation from a set A to itself. Then R◦R, the composition of R with itself, is always represented. Also, R◦R is sometimes denoted by R^{2}. Similarly, R^{3} = R^{2}◦R = R◦R◦R, and so on. Thus R^{n} is defined for all positive n.

**Example1:** Let X = {4, 5, 6}, Y = {a, b, c} and Z = {l, m, n}. Consider the relation R_{1} from X to Y and R_{2} from Y to Z.

R_{1}= {(4, a), (4, b), (5, c), (6, a), (6, c)} R_{2}= {(a, l), (a, n), (b, l), (b, m), (c, l), (c, m), (c, n)}

Find the composition of relation **(i)** R_{1} o R_{2} **(ii)** R_{1}o R_{1}^{-1}

**Solution:**

(i) The composition relation R_{1} o R_{2} as shown in fig:

**R _{1} o R_{2}** = {(4, l), (4, n), (4, m), (5, l), (5, m), (5, n), (6, l), (6, m), (6, n)}

(ii) The composition relation R_{1}o R_{1}^{-1} as shown in fig:

**R _{1}o R_{1}^{-1}** = {(4, 4), (5, 5), (5, 6), (6, 4), (6, 5), (4, 6), (6, 6)}

## Composition of Relations and Matrices

There is another way of finding R◦S. Let M_{R} and M_{S} denote respectively the matrix representations of the relations R and S. Then

**Example**

- Let P = {2, 3, 4, 5}. Consider the relation R and S on P defined by
- R = {(2, 2), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5), (5, 3)}
- S = {(2, 3), (2, 5), (3, 4), (3, 5), (4, 2), (4, 3), (4, 5), (5, 2), (5, 5)}.
- Find the matrices of the above relations.
- Use matrices to find the following composition of the relation R and S.
- (i)RoS (ii)RoR (iii)SoR

**Solution:** The matrices of the relation R and S are a shown in fig:

(i) To obtain the composition of relation R and S. First multiply M_{R} with M_{S} to obtain the matrix M_{R} x M_{S} as shown in fig:

The non zero entries in the matrix M_{R} x M_{S} tells the elements related in RoS. So,

Hence the composition R o S of the relation R and S is

- R o S = {(2, 2), (2, 3), (2, 4), (3, 2), (3, 3), (4, 2), (4, 5), (5, 2), (5, 3), (5, 4), (5, 5)}.

(ii) First, multiply the matrix M_{R} by itself, as shown in fig

Hence the composition R o R of the relation R and S is

- R o R = {(2, 2), (3, 2), (3, 3), (3, 4), (4, 2), (4, 5), (5, 2), (5, 3), (5, 5)}

(iii) Multiply the matrix M_{S} with M_{R} to obtain the matrix M_{S} x M_{R} as shown in fig:

The non-zero entries in matrix M_{S} x M_{R} tells the elements related in S o R.

Hence the composition S o R of the relation S and R is

- S o R = {(2, 4) , (2, 5), (3, 3), (3, 4), (3, 5), (4, 2), (4, 4), (4, 5), (5, 2), (5, 3), (5, 4), (5, 5)}.

# Types of Relations

**1. Reflexive Relation:** A relation R on set A is said to be a reflexive if **(a, a) ∈ R** for every **a ∈** A.

**Example:** If A = {1, 2, 3, 4} then R = {(1, 1) (2, 2), (1, 3), (2, 4), (3, 3), (3, 4), (4, 4)}. Is a relation reflexive?

**Solution:** The relation is reflexive as for every a ∈ A. (a, a) ∈ R, i.e. (1, 1), (2, 2), (3, 3), (4, 4) ∈ R.

**2. Irreflexive Relation:** A relation R on set A is said to be **irreflexive if (a, a) ∉ R** for every **a ∈ A**.

**Example:** Let A = {1, 2, 3} and R = {(1, 2), (2, 2), (3, 1), (1, 3)}. Is the relation R reflexive or irreflexive?

**Solution:** The relation R is not reflexive as for every a ∈ A, (a, a) ∉ R, i.e., (1, 1) and (3, 3) ∉ R. The relation R is not irreflexive as (a, a) ∉ R, for some a ∈ A, i.e., (2, 2) ∈ R.

**3. Symmetric Relation:** A relation R on set A is said to be symmetric iff (a, b) ∈ R ⟺ (b, a) ∈ R.

**Example:** Let A = {1, 2, 3} and R = {(1, 1), (2, 2), (1, 2), (2, 1), (2, 3), (3, 2)}. Is a relation R symmetric or not?

**Solution:** The relation is symmetric as for every (a, b) ∈ R, we have (b, a) ∈ R, i.e., (1, 2), (2, 1), (2, 3), (3, 2) ∈ R but not reflexive because (3, 3) ∉ R.

**Example of Symmetric Relation:**

- Relation ⊥r is symmetric since a line a is ⊥r to b, then b is ⊥r to a.
- Also, Parallel is symmetric, since if a line a is ∥ to b then b is also ∥ to a.

**Antisymmetric Relation:** A relation R on a set A is antisymmetric iff (a, b) ∈ R and (b, a) ∈ R then a = b.

**Example1:** Let A = {1, 2, 3} and R = {(1, 1), (2, 2)}. Is the relation R antisymmetric?

**Solution:** The relation R is antisymmetric as a = b when (a, b) and (b, a) both belong to R.

**Example2:** Let A = {4, 5, 6} and R = {(4, 4), (4, 5), (5, 4), (5, 6), (4, 6)}. Is the relation R antisymmetric?

**Solution:** The relation R is not antisymmetric as 4 ≠ 5 but (4, 5) and (5, 4) both belong to R.

**5. Asymmetric Relation:** A relation R on a set A is called an Asymmetric Relation if for every (a, b) ∈ R implies that (b, a) does not belong to R.

**6. Transitive Relations:** A Relation R on set A is said to be transitive iff (a, b) ∈ R and (b, c) ∈ R ⟺ (a, c) ∈ R.

**Example1:** Let A = {1, 2, 3} and R = {(1, 2), (2, 1), (1, 1), (2, 2)}. Is the relation transitive?

**Solution:** The relation R is transitive as for every (a, b) (b, c) belong to R, we have (a, c) ∈ R i.e, (1, 2) (2, 1) ∈ R ⇒ (1, 1) ∈ R.

#### Note1:

#### The Relation ≤, ⊆ and / are transitive, i.e., a ≤ b, b ≤ c then a ≤ c

(ii) Let a ⊆ b, b ⊆ c then a ⊆ c

(iii) Let a/b, b/c then a/c.

#### Note2:

#### ⊥r is not transitive since a ⊥r b, b ⊥r c then it is not true that a ⊥r c. Since no line is ∥ to itself, we can have a ∥ b, b ∥ a but a ∦ a.

Thus ∥ is not transitive, but it will be transitive in the plane.

**7. Identity Relation:** Identity relation I on set A is reflexive, transitive and symmetric. So identity relation I is an Equivalence Relation.

**Example:** A= {1, 2, 3} = {(1, 1), (2, 2), (3, 3)}

**8. Void Relation:** It is given by R: A →B such that R = ∅ (⊆ A x B) is a null relation. Void Relation R = ∅ is symmetric and transitive but not reflexive.

**9. Universal Relation:** A relation R: A →B such that R = A x B (⊆ A x B) is a universal relation. Universal Relation from A →B is reflexive, symmetric and transitive. So this is an equivalence relation.

# Closure Properties of Relations

Consider a given set A, and the collection of all relations on A. Let P be a property of such relations, such as being symmetric or being transitive. A relation with property P will be called a P-relation. The P-closure of an arbitrary relation R on A, indicated P (R), is a P-relation such that

- R ⊆ P (R) ⊆ S

**(1) Reflexive and Symmetric Closures:** The next theorem tells us how to obtain the reflexive and symmetric closures of a relation easily.

**Theorem:** Let R be a relation on a set A. Then:

- R ∪ ∆
_{A}is the reflexive closure of R - R ∪ R
^{-1}is the symmetric closure of R.

**Example1:**

- Let A = {k, l, m}. Let R is a relation on A defined by
- R = {(k, k), (k, l), (l, m), (m, k)}.

Find the reflexive closure of R.

**Solution:** R ∪ ∆ is the smallest relation having reflexive property, Hence,

R_{F}= R ∪ ∆ = {(k, k), (k, l), (l, l), (l, m), (m, m), (m, k)}.

**Example2:** Consider the relation R on A = {4, 5, 6, 7} defined by

- R = {(4, 5), (5, 5), (5, 6), (6, 7), (7, 4), (7, 7)}

Find the symmetric closure of R.

**Solution:** The smallest relation containing R having the symmetric property is R ∪ R^{-1},i.e.

R_{S}= R ∪ R^{-1}= {(4, 5), (5, 4), (5, 5), (5, 6), (6, 5), (6, 7), (7, 6), (7, 4), (4, 7), (7, 7)}.

**(2)Transitive Closures:** Consider a relation R on a set A. The transitive closure R of a relation R of a relation R is the smallest transitive relation containing R.

Recall that R^{2} = R◦ R and R^{n} = R^{n-1} ◦ R. We define

The following Theorem applies:

**Theorem1:** R^{*} is the transitive closure of R

Suppose A is a finite set with n elements.

R^{*}= R ∪R^{2}∪.....∪ R^{n}

**Theorem 2:** Let R be a relation on a set A with n elements. Then

Transitive (R) = R ∪ R^{2}∪.....∪ R^{n}

**Example1:** Consider the relation R = {(1, 2), (2, 3), (3, 3)} on A = {1, 2, 3}. Then

R^{2} = R◦ R = {(1, 3), (2, 3), (3, 3)} and R^{3} = R^{2} ◦ R = {(1, 3), (2, 3), (3, 3)} Accordingly,

Transitive (R) = {(1, 2), (2, 3), (3, 3), (1, 3)}

**Example2:** Let A = {4, 6, 8, 10} and R = {(4, 4), (4, 10), (6, 6), (6, 8), (8, 10)} is a relation on set A. Determine transitive closure of R.

**Solution:** The matrix of relation R is shown in fig:

Now, find the powers of M_{R} as in fig:

Hence, the transitive closure of M_{R} is M_{R*} as shown in Fig (where M_{R*} is the ORing of a power of M_{R}).

**Thus**, R^{*} = {(4, 4), (4, 10), (6, 8), (6, 6), (6, 10), (8, 10)}.

#### Note: While ORing the power of the matrix R, we can eliminate M_{Rn} because it is equal to M_{R*} if n is even and is equal to M_{R3} if n is odd.

# Equivalence Relations

A relation R on a set A is called an equivalence relation if it satisfies following three properties:

- Relation R is Reflexive, i.e. aRa ∀ a∈A.
- Relation R is Symmetric, i.e., aRb ⟹ bRa
- Relation R is transitive, i.e., aRb and bRc ⟹ aRc.

**Example:** Let A = {1, 2, 3, 4} and R = {(1, 1), (1, 3), (2, 2), (2, 4), (3, 1), (3, 3), (4, 2), (4, 4)}.

Show that R is an Equivalence Relation.

**Solution:**

**Reflexive:** Relation R is reflexive as (1, 1), (2, 2), (3, 3) and (4, 4) ∈ R.

**Symmetric:** Relation R is symmetric because whenever (a, b) ∈ R, (b, a) also belongs to R.

**Example:** (2, 4) ∈ R ⟹ (4, 2) ∈ R.

**Transitive:** Relation R is transitive because whenever (a, b) and (b, c) belongs to R, (a, c) also belongs to R.

**Example:** (3, 1) ∈ R and (1, 3) ∈ R ⟹ (3, 3) ∈ R.

So, as R is reflexive, symmetric and transitive, hence, R is an Equivalence Relation.

#### Note1: If R_{1}and R_{2} are equivalence relation then R_{1}∩ R_{2} is also an equivalence relation.

**Example:** A = {1, 2, 3}

R_{1} = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}

R_{2} = {(1, 1), (2, 2), (3, 3), (2, 3), (3, 2)}

R_{1}∩ R_{2} = {(1, 1), (2, 2), (3, 3)}

#### Note2: If R_{1}and R_{2} are equivalence relation then R_{1}∪ R_{2} may or may not be an equivalence relation.

**Example:** A = {1, 2, 3}

R_{1} = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}

R_{2} = {(1, 1), (2, 2), (3, 3), (2, 3), (3, 2)}

R_{1}∪ R_{2}= {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1), (2, 3), (3, 2)}

Hence, Reflexive or Symmetric are Equivalence Relation but transitive may or may not be an equivalence relation.

## Inverse Relation

Let R be any relation from set A to set B. The inverse of R denoted by R^{-1} is the relations from B to A which consist of those ordered pairs which when reversed belong to R that is:

R^{-1}= {(b, a): (a, b) ∈ R}

**Example1:** A = {1, 2, 3}

B = {x, y, z}

**Solution:** R = {(1, y), (1, z), (3, y)

R^{-1} = {(y, 1), (z, 1), (y, 3)}

Clearly **(R ^{-1})^{-1} = R**

#### Note1: Domain and Range of R^{-1} is equal to range and domain of R.

**Example2:** R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 3), (3, 2)}

R^{-1} = {(1, 1), (2, 2), (3, 3), (2, 1), (3, 2), (2, 3)}

#### Note2: If R is an Equivalence Relation then R^{-1} is always an Equivalence Relation.

**Example:** Let A = {1, 2, 3}

R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}

R^{-1} = {(1, 1), (2, 2), (3, 3), (2, 1), (1, 2)}

R^{-1} is a Equivalence Relation.

#### Note3: If R is a Symmetric Relation then R^{-1}=R and vice-versa.

**Example:** Let A = {1, 2, 3}

R = {(1, 1), (2, 2), (1, 2), (2, 1), (2, 3), (3, 2)}

R^{-1} = {(1, 1), (2, 2), (2, 1), (1, 2), (3, 2), (2, 3)}

#### Note4: Reverse Order of Law

(SOT)^{-1} = T^{-1} or S^{-1}

(ROSOT)^{-1} = T^{-1} or S^{-1} or R^{-1}.

# Partial Order Relations

A relation R on a set A is called a partial order relation if it satisfies the following three properties:

- Relation R is Reflexive, i.e. aRa ∀ a∈A.
- Relation R is Antisymmetric, i.e., aRb and bRa ⟹ a = b.
- Relation R is transitive, i.e., aRb and bRc ⟹ aRc.

**Example1:** Show whether the relation (x, y) ∈ R, if, x ≥ y defined on the set of +ve integers is a partial order relation.

**Solution:** Consider the set A = {1, 2, 3, 4} containing four +ve integers. Find the relation for this set such as R = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3), (1, 1), (2, 2), (3, 3), (4, 4)}.

**Reflexive:** The relation is reflexive as for every a ∈ A. (a, a) ∈ R, i.e. (1, 1), (2, 2), (3, 3), (4, 4) ∈ R.

**Antisymmetric:** The relation is antisymmetric as whenever (a, b) and (b, a) ∈ R, we have a = b.

**Transitive:** The relation is transitive as whenever (a, b) and (b, c) ∈ R, we have (a, c) ∈ R.

**Example:** (4, 2) ∈ R and (2, 1) ∈ R, implies (4, 1) ∈ R.

As the relation is reflexive, antisymmetric and transitive. Hence, it is a partial order relation.

**Example2:** Show that the relation ‘Divides’ defined on N is a partial order relation.

**Solution:**

**Reflexive:** We have a divides a, ∀ a∈N. Therefore, relation ‘Divides’ is reflexive.

**Antisymmetric:** Let a, b, c ∈N, such that a divides b. It implies b divides a iff a = b. So, the relation is antisymmetric.

**Transitive:** Let a, b, c ∈N, such that a divides b and b divides c.

Then a divides c. Hence the relation is transitive. Thus, the relation being reflexive, antisymmetric and transitive, the relation ‘divides’ is a partial order relation.

**Example3:** (a) The relation ⊆ of a set of inclusion is a partial ordering or any collection of sets since set inclusion has three desired properties:

- A ⊆ A for any set A.
- If A ⊆ B and B ⊆ A then B = A.
- If A ⊆ B and B ⊆ C then A ⊆ C

(b) The relation ≤ on the set R of real no that is Reflexive, Antisymmetric and transitive.

(c) Relation ≤ is a Partial Order Relation.

## n-Ary Relations

By an n-ary relation, we mean a set of ordered n-tuples. For any set S, a subset of the product set S^{n} is called an n-ary relation on S. In particular, a subset of S^{3} is called a ternary relation on S.

## Partial Order Set (POSET):

The set A together with a partial order relation R on the set A and is denoted by (A, R) is called a partial orders set or POSET.

## Total Order Relation

Consider the relation R on the set A. If it is also called the case that for all, a, b ∈ A, we have either (a, b) ∈ R or (b, a) ∈ R or a = b, then the relation R is known total order relation on set A.

**Example:** Show that the relation ‘<‘ (less than) defined on N, the set of +ve integers is neither an equivalence relation nor partially ordered relation but is a total order relation.

**Solution:**

**Reflexive:** Let a ∈ N, then a < a

⟹ ‘<‘ is not reflexive.

As, the relation ‘<‘ (less than) is not reflexive, it is neither an equivalence relation nor the partial order relation.

But, as ∀ a, b ∈ N, we have either a < b or b < a or a = b. So, the relation is a total order relation.

## Equivalence Class

Consider, an equivalence relation R on a set A. The equivalence class of an element a ∈ A, is the set of elements of A to which element a is related. It is denoted by [a].

**Example:** Let R be an equivalence relations on the set A = {4, 5, 6, 7} defined by

R = {(4, 4), (5, 5), (6, 6), (7, 7), (4, 6), (6, 4)}.

Determine its equivalence classes.

**Solution:** The equivalence classes are as follows:

{4} = {6} = {4, 6}

{5} = {5}

{7} = {7}.

## Circular Relation

Consider a binary relation R on a set A. Relation R is called circular if (a, b) ∈ R and (b, c) ∈ R implies (c, a) ∈ R.

**Example:** Consider R is an equivalence relation. Show that R is reflexive and circular.

**Solution:** Reflexive: As, the relation, R is an equivalence relation. So, reflexivity is the property of an equivalence relation. Hence, R is reflexive.

**Circular:** Let (a, b) ∈ R and (b, c) ∈ R

⇒ (a, c) ∈ R (∵ R is transitive)

⇒ (c, a) ∈ R (∵ R is symmetric)

Thus, R is Circular.

## Compatible Relation

A binary relation R on a set A that is Reflexive and symmetric is called Compatible Relation.

Every Equivalence Relation is compatible, but every compatible relation need not be an equivalence.

**Example:** Set of a friend is compatible but may not be an equivalence relation.

Friend Friend

a → b, b → c but possible that a and c are not friends.

## Responses