Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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 2:09
add comment

1 Answer 1

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.

share|improve this answer
    
@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 3:10
    
You're correct. Missed that pair. –  amWhy Jul 19 '13 at 3:12
    
Thanks Alraxite for your counter example that answers my question. –  Doug Jul 19 '13 at 12:56
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.