136k views
4 votes
how can the directed graph of a relation R on a finite set A be used to determine whether a relation is asymmetric

User Ole Tange
by
7.4k points

1 Answer

2 votes

A directed graph can be used to determine whether a relation R on a finite set A is asymmetric or not by checking whether there is any pair of elements (a, b) in R such that both (a, b) and (b, a) are present in R.

If such a pair exists, then the relation is not asymmetric because it violates the condition for asymmetry, which states that for any (a, b) in R, (b, a) cannot be in R.

In the directed graph, this means that there is a directed edge from a to b and also a directed edge from b to a. This would result in a cycle in the directed graph, which is not allowed in an asymmetric relation.

If there are no such pairs in R, then the relation is asymmetric, and the directed graph will not contain any cycles. Therefore, the directed graph can be a helpful tool to quickly determine if a relation is asymmetric or not, especially for larger sets A.

User Erik Elmgren
by
8.5k points