Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|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

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|cite|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

Your Answer


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.