1

Let A={1,2,3,4,5,6,7,8} and relation R={(1,2),(1,3),(1,4),(2,5),(2,6),(4,6),(4,7),(3,7),(3,5),(5,8),(6,8),(7,8),(5,8)}. How to prove or disprove that transitive closure T of relation R is antisymmetric? I have hard time doing this, and this is how far i am.

  1. i have drawn a graph: GRAPH
  2. I can conclude, as we can see relation R is antisymmetric...

and this is were i am stuck.

Edvards Zakovskis
  • 135

1 Answers1

1

All arrows in your graph are going upwards. (This is possible because there are no cycles)

If you add arrows to make the transitive closure of $R$, then still all arrows will be going upwards. This is because new arrows are made by combining multiple arrows in a row into a new arrow. If individual arrows go upwards, then their combination must also go upwards.

Antisymmetric means that for each directed edge in a graph, no edge exists that goes the other way. If an edge existed that would go the other way, then such an edge would be going downwards. But since you only have upwards arrows, such edges do not exist and your relation $T$ is antisymmetric.

Paul
  • 2,795