Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Partial Order Relations
3.
Partial Order Set or POSET
4.
n-Ary Relations
5.
Total Order Relation
6.
Equivalence Class
7.
FAQs
8.
Conclusion
Last Updated: Mar 27, 2024
Easy

Partial Order Relations

Author Teesha Goyal
0 upvote
Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

Relations are the relationships between two or more sets of information. A relation is a mapping from one set to another. A mapping function is sometimes used to define the relationship between two or more sets. To learn more about relations go to Relations | Learn & Practice from Coding Ninjas Studio.

Partial Order Relations

A relation R  on a set A is said to be partial order relation if for all the values of a such that a∈A, the relation satisfies the following conditions:

  1. Relation R is reflexive, i.e. aRa for all a∈A.
  2. Relation R is antisymmetric, i.e., aRb and bRa imply a=b.
  3. Relation R is transitive, i.e., aRb and bRc imply aRc.
     

Example: Show whether the relation R such that (x, y) ∈ R, if, x ≥ y defined on the set of positive integers is a partial order relation 

Solution: Consider a set A = {2,3,4,5}. Now according to the given condition for relation R, we have 

Relation R ={(2,2), (3,3), (3,2), (4,4), (4,3), (4,2), (5,5), (5,4), (5,3), (5,2)}

For this relation to be partial order, we must check for it to be reflexive, antisymmetric, and transitive.

  1. Reflexive: Now, since the condition is x ≥ y, then (x,x) will always be there for all values of x∈ A. Hence the relation is reflexive.
     
  2. Antisymmetric: For a relation (x,y) ∈ R, we have to have aRb and bRa imply that a=b, so here x ≥ y and y ≥ x can happen only when x = y. Therefore, the relation is antisymmetric.
     
  3. Transitive: Now, aRb means a ≥ b and bRc means b ≥ c; this means that a ≥ c therefore, aRc also belongs to R. Therefore, R is transitive.
     

Since R is reflexive, antisymmetric, and transitive, R is the partial order relation.

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

Partial Order Set or POSET

A set A together with a partial order relation R on A written in the form (A, R) is said to be a partial order set or a POSET.

Example: Show that the inclusion relation R given by x ⊆ y is a partial ordering on the power set of a set A. 

Solution: The relation R given by x ⊆ y on set A has to satisfy three conditions to be a POSET or partial order set.

  1. Reflexive: The relation R is reflexive because each set is a subset of itself, i.e., x ⊆ x holds good for all x ∈ A.
     
  2. Antisymmetric: The relation R is antisymmetric because aRb and bRa, i.e., a ⊆ b and b ⊆ a, imply that a = b; otherwise, they cannot be the subset of each other.
     
  3. Transitive: If we are given a ⊆ b and b ⊆ c, then a ⊆ c. hence for all aRb and bRc, we have aRc. 
     

Since R is reflexive, antisymmetric, and transitive, R is the partial order relation, and (A, R) is a partial order set or POSET.

n-Ary Relations

An n-ary relation means a set of ordered n-tuples. For any set A, a subset of the product set. An is called an n-ary relation on A. In particular, a subset of A3 is called a ternary relation on A.

Total Order Relation

Consider the relation R on set S. For all a, b ∈ S; we have either (a, b) ∈ R or (b, a) ∈ R or a = b, then the relation R is called a total order relation on set S.

Example: Show that the relation R where (x,y) ∈ R such that x < y defined on N, the set of all positive integers is neither a partially ordered relation nor an equivalence relation but is a total order relation.

Solution: For a relation R to be equivalence, it must be reflexive, symmetric, and transitive, and for a relation R to be a partially ordered relation, it must be reflexive, antisymmetric, and transitive. 

Given relation R such that (x,y) ∈ R and x < y is not reflexive as for any number x, it is not possible that x < x. Therefore, R is not reflexive

Since R is not reflexive, it can neither be a partially ordered relation nor an equivalence relation.

For a relation R to be total ordered relation on N, for all a, b ∈ N, we must have (a, b) ∈ R or (b, a) ∈ R or a = b. Therefore R is a total ordered relation.

Equivalence Class

Consider an equivalent relation R on set A. A relation R is said to be equivalent if it is reflexive, symmetric, and transitive. Now for all a such that a ∈ A, we find the equivalent class. The equivalent class of an element a is the set of all the elements to which a is related. It is denoted by [a]. Learn more about Equivalence relations by clicking on Equivalence of Relations - Coding Ninjas Coding Ninjas Studio.

Example:  Given an equivalence relation R on set A = {1,2,3,4} defined by 

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

Find the equivalent class of all the elements of set A.

Solution: The equivalent classes for all the elements of the set A are as follows:

[1] = {1}

[2] = {2,4}

[3] = {3}

[4] = {2,4}

FAQs

  1. What are the three conditions for a relation R to be an equivalence relation?
    For a relation R on set A to be an equivalence relation, it must be reflexive, symmetric, and transitive.
     
  2. What are the three conditions for a relation R to be a partial order relation? 
    For a relation R on a set A to be a partial order relation, it must be reflexive, antisymmetric, and transitive.
     
  3. What is the total order relation?
    Consider the relation R on set S. For all a, b ∈ S; we have either (a, b) ∈ R or (b, a) ∈ R or a = b, then the relation R is called a total order relation on set S.
     
  4. How do we denote the equivalent class?
    The equivalent class is denoted by square brackets i.e., for an equivalence relation R on set A, the equivalent class is denoted by [a] for all a ∈ A.
     
  5. What is the difference between a partial order relation and an equivalence relation?
    Both the partial order relation and equivalence relation are reflexive and transitive, but the equivalence relation, in addition, is symmetric, and the partial order relation is antisymmetric.

Conclusion

This article discussed partial order relations, partial ordered sets or POSETS, total order relations, and equivalent classes. Learn more about Relations with us. Hope you would have gained a better understanding of these topics now!
Check out this problem - First Missing Positive 

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? 

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Happy Coding!

Live masterclass