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

I am having trouble with this exercise.

Let $O: A \leftrightarrow A$ be a partial order relation over $A$ (reflexive, transitive). Prove that $E: A \leftrightarrow A$, defined as $E = O\cap O^{T}$ (where $O^{T}$ is the transpose or inverse of $O$) is an equivalence relation.

The fact is that I'm trying to use the definitions of a reflexive relation and a transitive relation to define $O$ as a set. I've been trying to define $O$ as: $O = \{(a,b)| aOb \wedge(aOb\wedge bOc\rightarrow aOc)\}$ so as to intersect both $O$ and $O^{T}$ (which, by the way, I am not able to define) and get an equivalence relation. I cannot seem to go much further than defining $O$ (I'd bet it is wrongly defined).


share|cite|improve this question
No, you can't define the set $O$ like that. However, you just need to show that $O\cap O^T$ is reflexive, symmetric and transitive. Use simple logic statements and $\in$ relations – Hagen von Eitzen Oct 20 '12 at 19:42
Do you mean that it is sufficient to prove the relation for any $x ∈ O$? – user1290143 Oct 20 '12 at 19:43
You can’t define $O$ because it’s what you’re given, and you have no control over it. You should know the definition of $O^T$: $O^T=\{\langle b,a\rangle\in A\times A:\langle a,b\rangle\in O\}$. It’s the relation obtained from $O$ by ‘turning all the pairs around’. – Brian M. Scott Oct 20 '12 at 20:05
up vote 2 down vote accepted

Hint "Just do it", as they say. By definition, $x E y \equiv x O y \land y O x$, where $O$ is transitive and reflexive. And you have to establish separately each of

  1. $x E x$
  2. $x E y \to y E x$
  3. $x E y \land y E z \to x E z$.

But each of those is immediate given the definition and the condition on $O$ ...

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.