Closure of Relations

Combining Relations :

• Union – consists of all ordered pairs from both relations. Duplicate ordered pairs removed from Union.
• Intersection – consists of ordered pairs which are in both relations.
• Difference – consists of all ordered pairs only in , but not in .
• Symmetric Difference – consists of all ordered pairs which are either in or but not both.

• Example – What is the composite of the relations and where is a relation from to with and is a relation from to with ?
• Solution – By computing all ordered pairs where the first element belongs to and the second element belongs to , we get –

Composition of Relation on itself :

Let  be a relation on the set .
The powers  where  are defined recursively by -
 and .

Closure of Relations :

1. Reflexive Closure – is the diagonal relation on set . The reflexive closure of relation on set is .
2. Symmetric Closure – Let be a relation on set , and let be the inverse of . The symmetric closure of relation on set is .
3. Transitive Closure – Let be a relation on set . The connectivity relation is defined as – . The transitive closure of is .

Equivalence Relations :

1. Reflexive – For any element , is divisible by . . So, congruence modulo is reflexive.
2. Symmetric – For any two elements and , if or i.e. is divisible by , then is also divisible by . . So Congruence Modulo is symmetric.
3. Transitive – For any three elements , , and if then- Adding both equations,

      

   . So, is transitive.
Since the relation is reflexive, symmetric, and transitive, we conclude that is an equivalence relation.

Equivalence Classes :

Let be an equivalence relation on set . We know that if then and are said to be equivalent with respect to . The set of all elements that are related to an element of is called the equivalence class of . It is denoted by or simply if there is only one relation to consider. Formally, Any element is said to be the representative of . Important Note : All the equivalence classes of a Relation on set are either equal or disjoint and their union gives the set . The equivalence classes are also called partitions since they are disjoint and their union gives the set on which the relation is defined
• Example : What are the equivalence classes of the relation Congruence Modulo ?
• Solution : Let and be two numbers such that . This means that the remainder obtained by dividing and with is the same. Possible values for the remainder- Therefore, there are equivalence classes –

GATE CS Corner Questions

Practicing the following questions will help you test your knowledge. All questions have been asked in GATE in previous years or in GATE Mock Tests. It is highly recommended that you practice them. 1. GATE CS 2013, Question 1 2. GATE CS 2005, Question 42 3. GATE CS 2001, Question 2 4. GATE CS 2000, Question 28 References – Composition of Relations – Wikipedia Discrete Mathematics and its Applications, by Kenneth H Rosen