Binary Relations

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

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

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 n² elements.

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:

• Has-A Relationship in Java

 

Recommended problems -

• Binary Array Sorting
• Vertical Order Traversal of a Binary Tree
• Leaf Nodes in Binary Tree

 

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!!