Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
What is Composition of Relations
3.
Composition of Relations
4.
Powers of Binary Relations
5.
Composition of Relations in Matrix Form
5.1.
For example,
5.2.
Solution
6.
Frequently Asked Questions
6.1.
What is the symbol for the composition of a relation?
6.2.
What is composition in set theory?
6.3.
How do you solve composition of relations?
6.4.
What is a relation composition with itself?
7.
Conclusion
Last Updated: Apr 19, 2024
Easy

Composition of Relations

Author GAZAL ARORA
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

In the mathematics of binary relations, the formation of a new binary relation R∘S from two given binary relations R and S is known as the composition of relations. The composition of relations is known as relative multiplication in the calculus of relations, and the result is called a relative product.

Composition of Relations

What is Composition of Relations

Let A, B, and C be three sets and let R be a relation from A to B and S be a relation from Q to R.

The composition of R and S: S∘R is a binary relation from A to C, if and only if there exists a b∈B such that aRb and bSc. 

Formally, the composition of S, R can be written as:

a(R◦S)c if for some b ∈ B we have aRb and bSc.   
R ◦ S = {(a, c)| there exists b ∈ B for which (a, b) ∈ R and (b, c) ∈ S}, 
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Composition of Relations

  1. The composition of binary relations is associative: R∘(S∘T) = (R∘S)∘T.
  2.  The composition of binary relations is not commutative: R∘S ≠ S∘R.
  3. The composition of relations R and S, R◦S is often thought of as their multiplication and is written as RS.

 

Here is an example of the composition of relations:

Relation R:

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

Relation S:

S = {(2, 5), (3, 6), (4, 7)}


Composed Relation R◦S:

R◦S = {(1, 5), (1, 6), (1, 7), (2, 5), (2, 6), (2, 7), (3, 5), (3, 6), (3, 7)}

This is because the composition of relations is associative, meaning that the arrangement of the relations does not matter.

Powers of Binary Relations

When a relation is defined on a set, it can always be composed of itself. As a result, we may have

R◦R is denoted by R2. Similarly, R3 = R2◦R = R◦R◦R, and so on. 

Hence Rn is defined for all n > 0.

Composition of Relations in Matrix Form

Let the relations R and S are defined by their matrices MR and MS. Then, the composition of relations S∘R = RS is calculated by the matrix product of MR and MS:

MS∘R = MRS = MR X MS.

For example,

Let P = {134}. Consider the relation R and S on P defined by  

R = {(11), (12), (13), (14), (23), (24), (34), (42)}  

S = {(12), (14), (23), (24), (31), (32), (34), (41), (44)}.  

Find the composition of R and S (R∘S).

Solution

The matrices of the relation R and S are:

matrices of the relation R and S

To calculate the composition of the R and S, multiply matrices MR by MS as shown:

calculation of Composition of Relations in Matrix Form

As we know, MS∘R = MRS = MR X MS.

The non-zero entries in the matrix R∘S determine the elements connected in R∘S. So, the composition of the relation R and S is:

R◦S = {(11), (12), (13), (21), (22), (31), (34), (41), (42), (43), (44)}.

Also read about - Representation of Relations

Frequently Asked Questions

What is the symbol for the composition of a relation?

A small circle () is positioned between the two relation names to represent the composition of a relation, such as R∘S, which symbolises the composition of relation R followed by relation S.

What is composition in set theory?

The composition of a function is a step-by-step process in mathematics. The functions f: A→ B & g: B→ C, for example, can be combined to generate a function that maps x in A to g(f(x)) in C. There are no empty sets in any of the sets. (g o f) (x) = g (f(x) denotes a composite function. The phrase g o f read as "g of f."

How do you solve composition of relations?

The composition of two relations is calculated by matrix product. Let the relations R and S are defined by their matrices MR and MS. Then, the composition of relations S∘R = RS is calculated by the matrix product of MR and MS 

What is a relation composition with itself?

Relation composition with itself, denoted as RR, refers to combining a relation R with itself. This operation yields a new relation consisting of pairs derived from composing elements of R with elements of R.

Conclusion

In this article, we learned to calculate the composition of relations. We learned that in the given three sets, A, B, and C and relations R be a relation from A to B and S be a relation from Q to R.

The composition of R and S: S∘R is a binary relation from A to C, if and only if there exists a b∈B such that aRb and bSc. 

We also learned about the properties of the composition of relations. We then calculated the composition of relations in matrix form with the help of an example.

Recomended articles:


Do check out The Interview guide for Product Based Companies as well as some of the Popular interview problems from top tech companies like Amazon, Adobe, Google, Uber, Microsoft, etc.

Refer to our guided paths on Coding Ninjas Studio to learn more about Competitive ProgrammingJavaScriptSystem Design, etc. Enroll in our courses and refer to the mock test and problems available; take a look at the interview experiences and interview bundle for placement preparations.

Previous article
Representation of Relations
Next article
Types of relation
Live masterclass