Properties of relation: Reflexivity, Symmetricity and more
Properties of relations are important to understand the characteristics or the behaviour of relations. Many set properties are similar for crisp relations and fuzzy relations. We have already discussed the properties of crisp sets and the properties of fuzzy sets. In this article, we will learn about the properties of the relation
Note: The Greek letter Ī (chi) is represented as Ī in the article.
Properties of relation:
Reflexivity:
Relation R is reflexive if every element in the set is associated with itself, i.e. ÎŧR(x, x) = 1, âx â X
Example:
Consider the universe X = {1, 2, 3}. The fuzzy relation R defined over X is,
As we can see that ÎŧR(1, 1) = ÎŧR(2, 2) = ÎŧR(3, 3) = 1.
This relation holds the condition ÎŧR(x, x) = 1 for all x in X. So this is reflexive relation.
Anti-reflexivity:
Relation R is an anti-reflexive if âx â X, (x, x) â R, i.e. ÎŧR(x, x) = 0, âx â X
Example:
Consider the universe X = {1, 2, 3}. The fuzzy relation R defined over X is,
As we can see that ÎŧR(1, 1) = ÎŧR(2, 2) = ÎŧR(3, 3) = 0.
This relation holds the condition ÎŧR(x, x) = 0 for all x in X. So this is anti-reflexive relation.
Symmetricity:
A relation R is called symmetric if element x is related to element y then element y must be related to x, i.e. ÎŧR(x, y) = ÎŧR(y, x), âx, y â X
Example:
Consider the universe X = {1, 2, 3}. The fuzzy relation R defined over X is,
As we can see that the transpose of relation matrix R is the matrix itself. So the given relation is symmetric relation.
Anti-symmetricity:
Relation R is called anti-symmetric if, ÎŧR(x, y) > 0, then ÎŧR(y, x) = 0, x, y â X, x â y
Example:
Consider the universe X = {1, 2, 3}. The fuzzy relation R defined over X is,
As we can observe in above relation matrix, R(1, 3), R(2, 1) and R(3, 2) are non zero, and their corresponding R(y, x), i.e. R(3, 1), R(1, 2) and R(2, 3) are zero and hence the relation is anti-symmetric.
Transitivity:
For crisp Relation:
Crisp Relation R is called transitive if x is related to y and y is related to z then x must be related to z.
That states if, (x, y) â R and (y, z) â R â (x, z) â R
For fuzzy relation:
Let Îģ1= ÎŧR(xi, xj ), Îģ2= ÎŧR(xj, xk) and Îģ = ÎŧR(xi, xk)
For fuzzy relation to be transitive, Îģ âĨ minâĄ(Îģ1, Îģ2 ) for all Îģ
Note: It is clear that ⤠is reflexive, anti-symmetric and transitive, and < is anti-reflexive, anti-symmetric and transitive.
How to test transitivity?
For any given matrix, it is hard to manually test all the pairs for different Îģ values. It takes a tremendous amount of time. Can we do it a better way? Of course, there is a smarter and easier way to test if a given relation is transitive or not.
We can compute R2 by taking the composition of relation R with itself, i.e. R2 = R â R
ÎŧR2(x, z) = max( ÎŧR(x, y), ÎŧR(y, z) ) where y â X
R is transitive if R2 â R, i.e. ÎŧR2(x, y) ⤠ÎŧR(x, y)
Example:
Check if the given relation is transitive or not.
Solution:
As discussed above, to check the transitivity of relation R, we shall compute R2
For the above matrices,
ÎŧR2(1, 1) ⤠ÎŧR(1, 1)
ÎŧR2(1, 2) ⤠ÎŧR(1, 2)
ÎŧR2(1, 3) â¤/ ÎŧR(1, 3) ( â¤/ indicates not less than or equal to)
As ÎŧR2(x, y) is not always less than or equal to ÎŧR(x, y), for all (x, y), hence R is not transitive
Similarity / Equivalence Relation:
If relation RÂ Ė is reflexive, symmetric and transitive then it is called a similarity (equivalence) relation
Anti-Similarity / Partial Order Relation:
If R is a similarity relation then its complement is an anti-similarity (partial order) relation
i.e. ÎŧR‘(x, y)=1 – ÎŧR(x, y)
Anti-similarity relation is anti-reflexive, symmetric and transitive, in the sense of max-min
ÎŧR‘(x, y) âĨ min( max( ÎŧR‘(x, y), ÎŧR‘(y, z)) ) where y â X
Example:
Check if the given relation is anti-similarity relation or not.
ÎŧR‘(x, y) = 1 – ÎŧR(x, y)
As it is anti-reflexive, symmetric and transitive, R is anti-similarity relation
Watch on YouTube: Properties of relation
Weak Similarity / Tolerance Relation:
If relation R is reflexive and symmetric but not transitive then it is called a weak similarity (tolerance) relation
Order Relations:
Relation R is an order relation if it is a transitive relation
Relation R is pre-order relation if it is a reflexive and transitive relation
Relation R is half-order relation if it is reflexive and weak anti-symmetric relation
Tolerance to Equivalence relation conversion:
Tolerance (weak similarity) relation can be converted to equivalence (similarity) by taking the composition of relation with itself
RⲠâ R ° R
Râ˛â˛ â RⲠ° Râ˛
Example – 1:
Check if the given crisp relation is equivalency or not:
Solution:
Here, (xi, xi ) â R, âi, so R is reflexive
R = RT, so R is symmetric
Ī(x1, x2) = 1, Ī(x2, x5) = 1 but Ī(x1, x5) = 0, so R is not transitive
Hence R is Not equivalence but it is Tolerance
Example 2: Ī
Convert the following relation into equivalence if it is not already
Solution:
ÎŧR(xi, xi) = 1, âi, so relation is reflexive
ÎŧR(xi, xj) = ÎŧR(xj, xi) , so relation is symmetric
Îģ1 = ÎŧR(x1, x2) = 0.8
Îģ2 = ÎŧR(x2, x5) = 0.9
Îģ = ÎŧR(x1, x5) = 0.2
For fuzzy relation to be transitive, Îģ âĨ minâĄ(Îģ1, Îģ2)
For given relation matrix Îģ < minâĄ( Îģ1, Îģ2 ), so given relation is tolerance but not equivalence
We can convert tolerance relation into equivalence relation by taking the composition of relation with itself. This process is to be repeated until it becomes equivalence.
Îģ1 = ÎŧR(x1, x2) = 0.8
Îģ2 = ÎŧR(x2, x4) = 0.5
Îģ = ÎŧR(x1, x4) = 0.2
For given relation matrix Îģ < minâĄ( Îģ1, Îģ2 ), so given relation is yet not equivalence
Let us repeat the step again and take composition once again.
Îģ1 = ÎŧR(x1, x3) = 0.4
Îģ2 = ÎŧR(x3, x2) = 0.4
Îģ = ÎŧR(x1, x2) = 0.8
For the given relation matrix Îģ > minâĄ( Îģ1, Îģ2 ), this is true for any pair in the above matrix. So given relation is now equivalence
Thus, this article concludes all the properties of relation.
Test Your Knowledge!
Given the relation matrix,
Answer the following questions:
- Is the relation reflexive? Why?
- Is the relation symmetric? Why?
- Is relation transitive? Why?
- Is relation equivalence? Why?
- Is the relation partial order / anti-similar? Why?
- Is the relation weak similar / tolerance? Why?
Please post your answer / query / feedback in comment section below !