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.

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

Let $R$ be a relation that is transitive. Does complementary of $R$ ($\overline R$) is transitive?($\overline R$is hold transitive)

share|cite|improve this question
You need more hypotheses, because as it stands, the statement is false: $\varnothing$ and $A\times A$ are complementary, transitive relations on $A$. – Brian M. Scott Jan 3 '13 at 15:28
Sorry.I think new question is correct. – geni Jan 3 '13 at 15:39

This isn't true, even for nontrivial relations.

For instance, consider $R \subseteq \{ 1,2,3 \}^2$ given by $$R = \{ (1,2),(1,3),(2,3) \}$$ Then $R$ is transitive, and $$\bar R = \{(1,1), (2,1), (2,2), (3,1), (3,2), (3,3) \}$$ which is also transitive.

Edit: Even with the question edit, the result still doesn't hold. For instance, let $R = \{ (1,3) \}$ on the set $\{1,2,3\}$. Then $(1,2) \in \bar R$ and $(2,3) \in \bar R$ but $(1,3) \not \in \bar R$, so $\bar R$ is not transitive, even though $R$ is transitive.

share|cite|improve this answer
Or more generally $<$ and $\ge$, where $<$ is any linear order on the underlying set. – Brian M. Scott Jan 3 '13 at 15:36
Sorry,I edited body of question. – geni Jan 3 '13 at 15:44
@geni: It still doesn't hold; see my edit. – Clive Newstead Jan 3 '13 at 15:49
(I may have missed something though; I don't know what 'hold transitive' means.) – Clive Newstead Jan 3 '13 at 15:50

Knowing only that a relation is transitive doesn't allow you to conclude anything about the transitivity of its complement.

For example the standard order relation $<$ on the integers is transitive, but its complement $\geq$ is also transitive.

On the other hand, the equality relation $=$ on the integers is transitive, but its complement $\neq$ is not.

share|cite|improve this answer

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.