Partial Order Relations

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. Aⁿ is called an n-ary relation on A. In particular, a subset of A³ 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!