Transitive closure of a reflexive antisymmetric relation

Question

Prove that the transitive closure $S$ of a reflexive antisymmetric relation $R$ is a partial order.

Yes, this is obvious. We know the transitive closure must be transitive and reflexive as given, but the hard part is proving that it is antisymmetric. Can you help? — Doug, Jul 19 '13 at 02:09

Alraxite · Answer 1 · 2013-07-19T03:12:33.347

6

The conjecture is false.

Let $A = \{1,2,3\}$ and let $R = \{(1,1),(2,2),(3,3),(1,2),(2,3),(3,1)\}$ which is reflexive and antisymmetric.

Its transitive closure, S = $\{(1,1),(2,2),(3,3),(1,2),(2,3),(3,1),(1,3),(2,1), (3,2)\}$, however is not antisymmetric since $(2,1)\in S$ and $(1,2)\in S$ but $1\neq 2$ and thus can't be a partial order.

edited Jul 19 '13 at 03:12

answered Jul 19 '13 at 02:22

Alraxite

5,647

@amWhy $R$ is not transitive since $(1,2) \in R$ and $(2,3)\in R$ but $(1,3)\not\in R$. – Alraxite Jul 19 '13 at 03:10
You're correct. Missed that pair. – amWhy Jul 19 '13 at 03:12
Thanks Alraxite for your counter example that answers my question. – Doug Jul 19 '13 at 12:56

Transitive closure of a reflexive antisymmetric relation

1 Answers1

Linked