Anti-Symmetric Relation on a Set

A relation is a subset of the cartesian product of a set with one other set. A relation comprises ordered pairs of components of the set it’s outlined on. To be taught extra about relations discuss with the article on “Relation and their sorts“.

What’s an Anti-Symmetric Relation?

A relation R on a set A known as anti-symmetric relation if 

∀ a, b ∈ A, if (a, b) ∈ R then (b, a) ∉ R or a = b,
the place R is a subset of (A x A), i.e. the cartesian product of set A with itself.

This implies if an ordered pair of components “a” to “b” (aRb) is current in relation R then an ordered pair of components “b” to “a” (bRa) shouldn’t be current in relation R except a = b.

If any such bRa is current for any aRb in R then R isn’t an anti-symmetric relation.

Instance:

Think about set A = {a, b}

R = {(a, b), (b, a)} isn’t anti-symmetric relation as for (a, b) tuple (b, a) tuple is current however
R = {(a, a), (a, b)} is an anti-symmetric relation.

Properties of Anti-Symmetric Relation

1. Empty relation on any set is all the time anti-symmetric.
2. Common relation over set could or will not be anti-symmetric.
3. If the relation is reflexive/irreflexive then it needn’t be anti-symmetric.
4. A relation could also be anti-symmetric and symmetric on the identical time.

Find out how to confirm an Anti-Symmetric Relation?

To confirm anti-symmetric relation:

• Manually test for the existence of each bRa tuple for each aRb tuple (if a ≠ b) within the relation.
• If any of the tuples exist then the relation isn’t anti-symmetric. In any other case, it’s anti-symmetric.

Observe the under illustration for a greater understanding

Think about set A = { 1, 2, 3, 4 } and a relation R = { (1, 2), (1, 3), (2, 3), (3, 4), (4, 4) }

For (1, 2) in R:
    => The reversed pair (2, 1) isn’t current.
    => This satisfies the situation.

For (1, 3) in R:
    => The reversed pair (3, 1) isn’t current.
    => This satisfies the situation.

For (2, 3) in R:
    => The reversed pair (3, 2) isn’t current.
    => This satisfies the situation.

For (3, 4) in R:
    => The reversed pair (4, 3) isn’t current.
    => This satisfies the situation.

For (4, 4) in R:
    => The reversed pair (4, 4) is current however see right here each the weather of the tuple are identical.
    => So this additionally satisfies the situation.

So R is an anti-symmetric relation.

Under is the code implementation of the concept:

Anti-Symmetric Relation

Time Complexity: O(N * log N) the place N is the variety of components within the reation
Auxiliary House: O(1)