Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Relation
3.
Binary Relation
4.
Mathematical Definition of Binary Relation
4.1.
Domain of Relation
4.1.1.
Example of Domain
4.2.
Range of Relation
4.2.1.
Example of Range
5.
Inverse of Relations
6.
Complement of a Relation
7.
Categories of Binary relations
8.
Comparison of All Relations
9.
Equivalence Relations
10.
Partial Order Relation
11.
FAQs
12.
Key Takeaways
Last Updated: Mar 27, 2024

Binary Relations

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

We come across various links that describe relationships in our daily lives, such as the relationship between a parent and a son, brother, and sister, and so on. 

We also come across a various number of relationships in mathematics, such as x is less than y, line l is parallel to line m, etc.

Here we'll look at how to link pieces from two sets together and then define a relationship between them.

Relation

An association or connection between the components of one set and those of another is referred to as a relation. There are various forms of relationships, including:

  • Binary Relations:  Relationship between items
  • Equivalence relations: Breaking items into groups
  • Partial Order: Ranking items

In this article, we will be looking at the Binary Relationship.

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

Binary Relation

A binary relation from set M to set N is formally referred to as a subset of M X N. For any pair (m,n) in M X N, a is related to b by R, denoted mRn, if an only if (m,n) is an element of R.

But doesn't that seem a little puzzling?

Let's make this a little clearer. A relation depicts the relationship between things from one set and objects from other sets, or even objects from the same set. It denotes a connection. This link or association is represented as an ordered pair.

A set of ordered pairs (m,n) is a binary relation from a set M to a set N, where m is an element of M and n is an element of N, and R is the relation or identifying association for each m and n.

Mathematical Definition of Binary Relation

A subset of the Cartesian product M X N is a binary relation R from set M to set N: R ⊆ MXN.

We can say m is related to n by R if R ⊆ MXN and (m,n) ∈ R.

For example, If M=N and  R ⊆ MXN, the binary relation R is called a Homogeneous binary relation defined on set M.

Domain of Relation

The set of elements in M related to some elements in N, or the set of all initial entries of the ordered pairs in R, is the domain of relation R. 

It is represented by DOM(R).

Example of Domain

Let A = {123}  

B = {a, b, c}  

R = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c), (3,a), (3,b), (3,c)}

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

Range of Relation

The range of the relationship R is the set of all second entries of the ordered pairs in R. Alternatively; it is the set of all elements in N connected to some element in M.

It is represented by RAN(R).

Example of Range

Let A = {123}  

B = {a, b, c}  

R = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c), (3,a), (3,b), (3,c)}

RAN(R) = {a,b,c}

Inverse of Relations

We may steal property from functions in mathematics, namely calculating the inverse of a function, because the relation is said to be functional.

The exact inverse of the collection of ordered pairs in the original input is the inverse of a relationship.

Consider the sets (0, 2), (3, 4), (-3, -2) and (2, 4) 

All we have to do is flip the ordered pairs over to obtain the inverse of this relation. As a result, the inverse is (2, 0), (4, 3), (-2, -3), (4, 2)

Complement of a Relation

A relation's complement will comprise all pairs that do not belong to the relation but do belong to the Cartesian product, i.e, R = {(m, n): {m, n) ∉ R}

Example:

Consider the relation R from M to N  

        M = {1, 2, 3}  

        N = {a, b}  

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

We know that, M X N = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}

 So, the complement relation of R is {(2, a), (3, a)}

Categories of Binary relations

There are only a few qualities that all relations have in common.

We frequently divide relationships into different sorts to investigate relationships between specific properties.

  1. Reflexive Relation:
    Some relationships always hold for any element and itself, and these relations are called Reflexive relations.
     If (m, m) ∈ R for every m ∈ M, a relation R on set M is said to be reflexive.
    Example:
     M = {1, 2, 3} then R = {(1, 1) (2, 2), (1, 3), (3, 3)} is a reflexive relation.
     
  2. Irreflexive Relation:
    If (m,m ) ∉ R for every m ∈ M, a relation R on set M is said to be Irreflexive.
    Example:
     M = {1, 2, 3} then R = {(1, 2) (2, 1), (1, 3)} is a  irreflexive relation.
     
  3. Symmetric Relation:
    The relative order of the objects doesn't matter in Symmetric relations.
     Iff (m, n) ∈ R ⟺ (n, m) ∈ R,  a relation R on set M is said to be Symmetric.
    Example:
    M = {1, 2, 3} then R = {(1, 2) (2, 1), (1, 3), (3, 1), (3, 3)} is a  irreflexive relation.
     
  4. AntiSymmetric Relation:
     A relation R on a set M is antisymmetric iff (m, n) ∈ R and (n, m) ∈ R then a = b.
    Equivalently:
    For any m ∈ M and n ∈ M, if mRn and nRm, then x = y.
    Example:
     M = {1, 2, 3} then R = {(1, 2) (2, 2), (1, 3)} is a  AntiSymmetric relation.
     
  5.  Asymmetric Relation:
    An Asymmetric Relation is a relation R on a set M that indicates that (n, m) does not belong to R for every  (m, n) ∈ R.
    Example:
     M = {1, 2, 3} then R = {(1, 2) (2,3), (1,3)} is a  Asymmetric relation.
     
  6. Transitive Relation:
    Many relations can be linked together in a chain.
    A binary relation R over a set A is considered transitive if mRn and nRp, then mRp are valid for all m, n, p ∈ M.
    A Relation R on set M is said to be transitive iff (m, n) ∈ R and (n, p) ∈ R ⟺ (m, p) ∈ R.

Comparison of All Relations

The following table represents the formulae for finding the smallest relation, the largest relation, and the number of possible relations on a set with n elements. Also, the cartesian product of the respective set contains nelements.

Equivalence Relations

If a relation R on a set M satisfies the following three criteria, it is termed an equivalence relation:

  1. The Relation R should be Reflexive, i.e., mRm ∀ m∈M.
  2. The Relation R should be Symmetric, i.e., mRn ⟹ nRm.
  3. The Relation R should be transitive, i.e., mRn and nRp ⟹ mRp.

Example: Let's assume that E is a relation on the set R real numbers described by mEn, such that m-n is an integer. Show that E is an equivalence relation on R.

Reflexive: Consider that m belongs to R, then m– m = 0, an integer. Therefore mEm.

Symmetric: Consider m and n belong to R and mEn. Then m-n is an integer. Thus, n-m = – ( m – n), n-m is also an integer. Therefore nEm.

Transitive: Consider m and n belong to R, mEn, and nEp. Therefore m-n and n-p are integers. According to the transitive property, ( m – n ) + ( n – p ) = m – p is also an integer. So that mEn.

Thus, E is an equivalence relation on R.

Partial Order Relation

A relation P is said to be Partial Order Relation on a set M if it satisfies all the following properties:

  1. Relation P should be Reflexive, i.e., mPm ∀ m∈M.
  2. Relation P should be  Antisymmetric i.e., mPn and nPm ⟹ m = n.
  3. Relation P should be Transitive, i.e., mPn and nPp ⟹ mPp.

FAQs

  1. What is a digraph?
     A directed graph can also express a binary relation on a finite set ( a digraph for short). A directed graph comprises a collection of vertices and many edges that connect them.
     
  2. What is an Identity Relation?
     An Identity relation on set A should be reflexive, transitive, and symmetric.
     
  3. What is Void or Empty Relation?
     If no items of A are associated with any element of A, a relation R on set A is called an empty relation.
     
  4. When is a binary relation called transitive?
    For all a, b, and c in A, a binary relation X defined on a set A is said to be a transitive relation. If a X b and b RX c, then an X c, or if a is connected to b and b is related to c, then a must also be related to c.

Key Takeaways

This article has discussed Binary relations, Properties of Binary Relations, Equivalence, and Partial Order relations.

You can also read about other engineering mathematics topics like set theory and the transpose of the matrix.

Recommended Readings:

 

Recommended problems -

 

Visit Coding Ninjas Studio, our practice platform, to practice top problems, take mock tests, read interview experiences, and many more technical kinds of stuff.

 

We wish you Good Luck! Keep coding and keep reading Ninja!!

 

Next article
Representation of Relations
Live masterclass