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

1. (i) Let A = {a, b, c}
2.       B = {r, s, t}
3. Then R = {(a, r), (b, r), (b, t), (c, s)}
4. is a relation from A to B.
5.
6. (ii) Let A = {1, 2, 3} and B = A
7.          R = {(1, 1), (2, 2), (3, 3)}
8. 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 n2 elements. So, there are 2n2 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 2m x n relations from A to A.

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

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

1.      {(1, 2), (2, 1), (1, 1), (2, 2)}, {(1, 2), (2, 1)}, {(1, 2), (1, 1)}, {(1, 2), (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),
3. (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:

1. Let A = {1, 2, 3, 4}
2.     B = {a, b, c, d}
3.     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:

1. Consider the relation R from X to Y
2.         X = {1, 2, 3}
3.         Y = {8, 9}
4.         R = {(1, 8) (2, 8) (1, 9) (3, 9)}
5. 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 = [a1,a2,a3,…….am] and Q = [b1,b2,b3……bn] 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 = [Mij], defined as

```Mij = 0      if  (ai,bj) ∉ R
1     if   (ai,bj )∈ R
Example ```
1. Let     P = {1, 2, 3, 4}, Q = {a, b, c, d}
2. 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

1. A = {1, 2, 3, 4}
2. 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

1. Let P = {1, 2, 3, 4}
2.     Q = {a, b, c, d}
3.     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

1. Let P = {1, 2, 3, 4}
2.     Q = {x, y, z, k}
3.     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:

1. a (R◦S)c if for some b ∈ B we have aRb and bSc.
2. is,
3. 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 R2. Similarly, R3 = R2◦R = R◦R◦R, and so on. Thus Rn is defined for all positive n.

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

``` R1 = {(4, a), (4, b), (5, c), (6, a), (6, c)}
R2 = {(a, l), (a, n), (b, l), (b, m), (c, l), (c, m), (c, n)}
```

Find the composition of relation (i) R1 o R2 (ii) R1o R1-1

Solution:

(i) The composition relation R1 o R2 as shown in fig:

R1 o R2 = {(4, l), (4, n), (4, m), (5, l), (5, m), (5, n), (6, l), (6, m), (6, n)}

(ii) The composition relation R1o R1-1 as shown in fig:

R1o R1-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 MR and MS denote respectively the matrix representations of the relations R and S. Then

Example

1. Let P = {2, 3, 4, 5}. Consider the relation R and S on P defined by
2.     R = {(2, 2), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5), (5, 3)}
3.     S = {(2, 3), (2, 5), (3, 4), (3, 5), (4, 2), (4, 3), (4, 5), (5, 2), (5, 5)}.
4.
5.         Find the matrices of the above relations.
6. Use matrices to find the following composition of the relation R and S.
7.   (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 MR with MS to obtain the matrix MR x MS as shown in fig:

The non zero entries in the matrix MR x MS tells the elements related in RoS. So,

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

1. 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 MR by itself, as shown in fig

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

1. 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 MS with MR to obtain the matrix MS x MR as shown in fig:

The non-zero entries in matrix MS x MR tells the elements related in S o R.

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

1. 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:

1. Relation ⊥r is symmetric since a line a is ⊥r to b, then b is ⊥r to a.
2. 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.

#### ⊥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

1. 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:

1. Let A = {k, l, m}. Let R is a relation on A defined by
2.     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,

```RF = 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

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

```RS = 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 R2 = R◦ R and Rn = Rn-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 ∪R2  ∪.....∪ Rn
```

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

```Transitive (R) = R ∪ R2∪.....∪ Rn
```

Example1: Consider the relation R = {(1, 2), (2, 3), (3, 3)} on A = {1, 2, 3}. Then
R2 = R◦ R = {(1, 3), (2, 3), (3, 3)} and R3 = R2 ◦ 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 MR as in fig:

Hence, the transitive closure of MR is MR* as shown in Fig (where MR* is the ORing of a power of MR).

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

# Equivalence Relations

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

1. Relation R is Reflexive, i.e. aRa ∀ a∈A.
2. Relation R is Symmetric, i.e., aRb ⟹ bRa
3. 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 R1and R2 are equivalence relation then R1∩ R2 is also an equivalence relation.

Example: A = {1, 2, 3}
R1 = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}
R2 = {(1, 1), (2, 2), (3, 3), (2, 3), (3, 2)}
R1∩ R2 = {(1, 1), (2, 2), (3, 3)}

#### Note2: If R1and R2 are equivalence relation then R1∪ R2 may or may not be an equivalence relation.

Example: A = {1, 2, 3}
R1 = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}
R2 = {(1, 1), (2, 2), (3, 3), (2, 3), (3, 2)}
R1∪ R2= {(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)}

# Partial Order Relations

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

1. Relation R is Reflexive, i.e. aRa ∀ a∈A.
2. Relation R is Antisymmetric, i.e., aRb and bRa ⟹ a = b.
3. 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:

1. A ⊆ A for any set A.
2. If A ⊆ B and B ⊆ A then B = A.
3. 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 Sn is called an n-ary relation on S. In particular, a subset of S3 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.

## Binary Operation and Postulates: Best Answers 007EH

Welcome to Lesson Twelve – Binary Operation and Postulates. You can also join the Discrete Mathematics Forum to interact and share ideas, also you can…

## Testing XAMPP Installation

Testing XAMPP Installation Xampp allows us to work on a local server and test a local copy of websites using PHP code and mysql database.…

## Testing XAMPP Installation

Testing XAMPP Installation Xampp allows us to work on a local server and test a local copy of websites using PHP code and mysql database.…

## Testing XAMPP Installation

Testing XAMPP Installation Xampp allows us to work on a local server and test a local copy of websites using PHP code and mysql database.…

## Ordered Sets and Lattices: Best Answers 007EH

Welcome to Lesson Fourteen – Ordered Sets and Lattices. You can also join the Discrete Mathematics Forum to interact and share ideas, also you can…