Reflexive Relation on Set

0 0 5 minutes read

A relation is a subset of the cartesian product of a set with another set. A relation contains ordered pairs of elements of the set it is defined on. To learn more about relations refer to the article on “Relation and their types“.

What is a Reflexive Relation?

A relation R on a set A is called reflexive relation if

(a, a) ∈ R ∀ a ∈ A, i.e. aRa for all a ∈ A,
where R is a subset of (A x A), i.e. the cartesian product of set A with itself.

This means if element “a” is present in set A, then a relation “a” to “a” (aRa) should be present in relation R. If any such aRa is not present in R then R is not a reflexive relation.

A reflexive relation is denoted as:

I_A = {(a, a): a ∈ A}

Example:

Consider set A = {a, b} and R = {(a, a), (b, b)}.
Here R is a reflexive relation as for both a and b, aRa and bRb are present in the set.

Properties of a Reflexive Relation

Empty relation on a non-empty relation set is never reflexive.
Relation defined on an empty set is always reflexive.
Universal relation defined on any set is always reflexive.

How to verify a Reflexive Relation?

The process of identifying/verifying if any given relation is reflexive:

Check for the existence of every aRa tuple in the relation for all a present in the set.
If every tuple exists, only then the relation is reflexive. Otherwise, not reflexive.

Follow the below illustration for a better understanding:

Illustration:

Consider set A = {a, b} and a relation R = {{a, a}, {a, b}}.

For the element a in A:
=> The pair {a, a} is present in R.
=> Hence aRa is satisfied.

For the element b in A:
=> The pair {b, b} is not present int R.
=> Hence bRb is not satisfied.

As the condition for ‘b’ is not satisfied, the relation is not reflexive.

Below is a code implementation of the approach.

C++

// C++ code to check if a set is reflexive
 
#include <bits/stdc++.h>
using namespace std;
 
class Relation {
public:
    bool checkReflexive(set<int> A, set<pair<int, int> > R)
    {
        // Property 1
        if (A.size() > 0 && R.size() == 0) {
            return false;
        }
        // Property 2
        else if (A.size() == 0) {
            return true;
        }
 
        for (auto i = A.begin(); i != A.end(); i++) {
 
            // Making a tuple of same element
            auto temp = make_pair(*i, *i);
 
            if (R.find(temp) == R.end()) {
 
                // If aRa tuple not exists in relation R
                return false;
            }
        }
 
        // All aRa tuples exists in relation R
        return true;
    }
};
 
// Driver code
int main()
{
    // Creating a set A
    set<int> A{ 1, 2, 3, 4 };
 
    // Creating relation R
    set<pair<int, int> > R;
 
    // Inserting tuples in relation R
    R.insert(make_pair(1, 1));
    R.insert(make_pair(1, 2));
    R.insert(make_pair(2, 2));
    R.insert(make_pair(2, 3));
    R.insert(make_pair(3, 2));
    R.insert(make_pair(3, 3));
 
    Relation obj;
 
    // R in not reflexive as (4, 4) tuple is not present
    if (obj.checkReflexive(A, R)) {
        cout << "Reflexive Relation" << endl;
    }
    else {
        cout << "Not a Reflexive Relation" << endl;
    }
 
    return 0;
}

Java

// Java code implementation for the above approach
import java.io.*;
import java.util.*;
 
class pair {
  int first, second;
  pair(int first, int second)
  {
    this.first = first;
    this.second = second;
  }
}
 
class GFG {
 
  static class Relation {
    boolean checkReflexive(Set<Integer> A, Set<pair> R)
    {
      // Property 1
      if (A.size() > 0 && R.size() == 0) {
        return false;
      }
 
      // Property 2
      else if (A.size() == 0) {
        return true;
      }
 
      for (var i : A) {
        if (!R.contains(new pair(i, i))) {
          // If aRa tuple not exists in relation R
          return false;
        }
      }
      // All aRa tuples exists in relation R
      return true;
    }
  }
 
  public static void main(String[] args)
  {
    // Creating a set A
    Set<Integer> A = new HashSet<>();
    A.add(1);
    A.add(2);
    A.add(3);
    A.add(4);
 
    // Creating relation R
    Set<pair> R = new HashSet<>();
 
    // Inserting tuples in relation R
    R.add(new pair(1, 1));
    R.add(new pair(1, 2));
    R.add(new pair(2, 2));
    R.add(new pair(2, 3));
    R.add(new pair(3, 2));
    R.add(new pair(3, 3));
 
    Relation obj = new Relation();
 
    // R in not reflexive as (4, 4) tuple is not present
    if (obj.checkReflexive(A, R)) {
      System.out.println("Reflexive Relation");
    }
    else {
      System.out.println("Not a Reflexive Relation");
    }
  }
}
 
// This code is contributed by lokeshmvs21.

Python3

class Relation:
    def checkReflexive(self, A, R):
        # Property 1
        if len(A) > 0 and len(R) == 0:
            return False
        # Property 2
        elif len(A) == 0:
            return True
 
        for i in A:
            if (i, i) not in R:
 
                # If aRa tuple not exists in relation R
                return False
 
        # All aRa tuples exists in relation R
        return True
 
 
# Driver code
if __name__ == '__main__':
 
    # Creating a set A
    A = {1, 2, 3, 4}
 
    # Creating relation R
    R = {(1, 1), (1, 2), (2, 2), (2, 3), (3, 2), (3, 3)}
 
    obj = Relation()
 
    # R in not reflexive as (4, 4) tuple is not present
    if obj.checkReflexive(A, R):
        print("Reflexive Relation")
    else:
        print("Not a Reflexive Relation")

C#

// C# code implementation for the above approach
 
using System;
using System.Collections.Generic;
 
class pair {
  public int first, second;
  public pair(int first, int second)
  {
    this.first = first;
    this.second = second;
  }
}
 
public class GFG {
 
  class Relation {
    public bool checkReflexive(HashSet<int> A,
                               HashSet<pair> R)
    {
      // Property 1
      if (A.Count > 0 && R.Count == 0) {
        return false;
      }
 
      // Property 2
      else if (A.Count == 0) {
        return true;
      }
 
      foreach(var i in A)
      {
        if (!R.Contains(new pair(i, i))) 
        {
           
          // If aRa tuple not exists in relation R
          return false;
        }
      }
       
      // All aRa tuples exists in relation R
      return true;
    }
  }
 
  static public void Main()
  {
 
    // Creating a set A
    HashSet<int> A = new HashSet<int>();
    A.Add(1);
    A.Add(2);
    A.Add(3);
    A.Add(4);
 
    // Creating relation R
    HashSet<pair> R = new HashSet<pair>();
 
    // Inserting tuples in relation R
    R.Add(new pair(1, 1));
    R.Add(new pair(1, 2));
    R.Add(new pair(2, 2));
    R.Add(new pair(2, 3));
    R.Add(new pair(3, 2));
    R.Add(new pair(3, 3));
 
    Relation obj = new Relation();
 
    // R in not reflexive as (4, 4) tuple is not present
    if (obj.checkReflexive(A, R)) {
      Console.WriteLine("Reflexive Relation");
    }
    else {
      Console.WriteLine("Not a Reflexive Relation");
    }
  }
}
 
// This code is contributed by lokesh

Javascript

// JS code to check if a set is reflexive
 
function checkReflexive(A, R)
{
    let cnt = 0;
    // Property 1
    if (A.size > 0 && R.size == 0) {
        return false;
    }
    // Property 2
    else if (A.size == 0) {
        return true;
    }
 
    A.forEach(i => {
         
        // Making a tuple of same element
        let temp = [i, i];
 
        if (!R.has(temp)) {
 
            // If aRa tuple not exists in relation R
            cnt++;
        }
 
    });
 
 
    // All aRa tuples exists in relation R
    if(cnt==0)
        return true;
    else
        return false;
}
 
 
// Driver code
// Creating a set A
let A = new Set([ 1, 2, 3, 4 ]);
 
// Creating relation R
let R = new Set();
 
// Inserting tuples in relation R
R.add([1,1]);
R.add([1,2]);
R.add([2,2]);
R.add([2,3]);
R.add([3,2]);
R.add([3,3]);
R.add([3,3]);
 
// R in not reflexive as (4, 4) tuple is not present
if (checkReflexive(A, R)) {
    console.log("Reflexive Relation");
}
else {
    console.log("Not a Reflexive Relation");
}
 
// This code is contributed by akashish__

Output

Not a Reflexive Relation

Time Complexity: O(N * log M) where N is the size of the set and M is the number of pairs in the relation
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!