Operations on Relations

Operations on Relations

A relation is a subset of the Cartesian product of two sets.

Suppose

$$R, S \subseteq A \times A$$

Since relations are simply sets of ordered pairs, we can perform all standard set operations on them, such as union, intersection, difference, and complement. We can also define two special operations unique to relations: composition and inverse.

These operations are frequently tested in GATE CSE, especially in questions involving relation properties and graph-based representations.

1. Union of Relations

Definition

The union of two relations contains every ordered pair that belongs to either relation.

Mathematically,

$$R \cup S = \{(a,b)\mid (a,b)\in R \text{ or } (a,b)\in S\}$$

The word or means:

• Present in R
• Present in S
• Present in both

Example

Let

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

and

$$S=\{(2,3),(3,2),(1,1)\}$$

Then

$$R\cup S= \{ (1,1), (1,2), (2,3), (3,1), (3,2) \}$$

Notice that

$$(2,3)$$

appears only once because sets never contain duplicate elements.

Venn Diagram Interpretation

R       S

 ●●●●●●●●
●   R∩S  ●
 ●●●●●●●●

Union = Everything inside both circles.

Important Properties

• Commutative

$$R\cup S=S\cup R$$

• Associative

$$(R\cup S)\cup T=R\cup(S\cup T)$$

• Identity

$$R\cup\varnothing=R$$

2. Intersection of Relations

Definition

The intersection contains only the ordered pairs that appear in both relations.

Mathematically,

$$R\cap S= \{ (a,b)\mid (a,b)\in R \text{ and } (a,b)\in S \}$$

Example

Let

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

and

$$S=\{(2,3),(3,2),(1,1)\}$$

Then

$$R\cap S= \{ (2,3) \}$$

Only one ordered pair belongs to both relations.

Venn Diagram Interpretation

R       S

 ●●●●●●●●
●   X    ●
 ●●●●●●●●

Intersection = Common region.

Properties

• Commutative

$$R\cap S=S\cap R$$

• Associative

$$(R\cap S)\cap T= R\cap(S\cap T)$$

• Identity

$$R\cap\varnothing= \varnothing$$

3. Difference of Relations

Definition

The difference of two relations consists of ordered pairs that belong to the first relation but not to the second.

Mathematically,

$$R-S= \{ (a,b)\mid (a,b)\in R \text{ and } (a,b)\notin S \}$$

Example

Let

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

and

$$S= \{ (2,3), (3,2) \}$$

Then

$$R-S= \{ (1,2), (3,1) \}$$

The pair

$$(2,3)$$

is removed because it appears in both relations.

Important Note

Difference is not commutative.

Generally,

$$R-S \neq S-R$$

4. Complement of a Relation

Definition

The complement of a relation contains every ordered pair that does not belong to the relation.

Suppose

$$R\subseteq A\times A$$

Then

$$R^c= (A\times A)-R$$

Example

Let

$$A=\{1,2\}$$

Then

$$A\times A= \{ (1,1), (1,2), (2,1), (2,2) \}$$

Suppose

$$R= \{ (1,1), (2,2) \}$$

Then

$$R^c= \{ (1,2), (2,1) \}$$

Important Observation

The complement depends on the universal relation (Cartesian product).

Without knowing

$$A\times A$$

the complement cannot be determined.

Property

Applying complement twice gives the original relation.

$$(R^c)^c=R$$

5. Composition of Relations

Definition

Composition combines two relations into a new relation.

Suppose

$$R\subseteq A\times B$$

and

$$S\subseteq B\times C$$

Their composition is written as

$$S\circ R$$

and is defined by

$$S\circ R= \{ (a,c) \mid \exists b : (a,b)\in R \text{ and } (b,c)\in S \}$$

The order is important:

• First apply R
• Then apply S

Intuition

Think of composition as following a path.

A ----R----> B ----S----> C

If you can travel from

$$A$$

to

$$C$$

through

$$B$$

then include

$$(A,C)$$

in the composition.

Example

Let

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

and

$$S= \{ (2,4), (3,5) \}$$

Using

$$(1,2)\in R$$

and

$$(2,4)\in S$$

we obtain

$$(1,4)$$

Using

$$(2,3)\in R$$

and

$$(3,5)\in S$$

we obtain

$$(2,5)$$

Therefore,

$$S\circ R= \{ (1,4), (2,5) \}$$

Graph Interpretation

1 → 2 → 4

becomes

1 → 4

Similarly,

2 → 3 → 5

becomes

2 → 5

Important Notes

Composition is generally

• Not commutative

$$S\circ R \neq R\circ S$$

Composition is

• Associative

$$(T\circ S)\circ R = T\circ(S\circ R)$$

6. Inverse of a Relation

Definition

The inverse of a relation is obtained by reversing every ordered pair.

If

$$R= \{ (a,b) \}$$

then

$$R^{-1}= \{ (b,a) \}$$

More formally,

$$R^{-1} = \{ (b,a) \mid (a,b)\in R \}$$

Example

Suppose

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

Then

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

Every ordered pair has simply been reversed.

Graph Interpretation

Original graph

1 → 2
2 → 3
3 → 1

Inverse graph

1 ← 2
2 ← 3
3 ← 1

Every arrow changes direction.

Important Properties

Inverse of inverse

$$(R^{-1})^{-1}=R$$

Inverse distributes over union

$$(R\cup S)^{-1} = R^{-1}\cup S^{-1}$$

Inverse distributes over intersection

$$(R\cap S)^{-1} = R^{-1}\cap S^{-1}$$

Inverse of composition

$$(S\circ R)^{-1} = R^{-1}\circ S^{-1}$$

Notice that the order is reversed.

Summary Table

Operation	Definition
Union	Ordered pairs present in either relation
Intersection	Ordered pairs common to both relations
Difference	Ordered pairs present in the first relation but not the second
Complement	Ordered pairs not present in the relation
Composition	Connect two relations through an intermediate element
Inverse	Reverse every ordered pair

Common GATE Questions

• Compute $R \cup S$
• Compute $R \cap S$
• Find $R-S$
• Find the complement of a relation
• Compute $S \circ R$
• Find the inverse of a relation
• Determine whether composition is commutative
• Use matrix multiplication to compute composition
• Verify identities involving inverse and composition

Memory Tricks

Operation	Easy Way to Remember
Union	Everything from both relations
Intersection	Only common ordered pairs
Difference	Remove common pairs from the first relation
Complement	Everything outside the relation
Composition	Follow arrows through an intermediate vertex
Inverse	Reverse every arrow