0
$\begingroup$

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).

Thanks.

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$ Oct 20, 2012 at 19:42
  • $\begingroup$ Do you mean that it is sufficient to prove the relation for any $x ∈ O$? $\endgroup$
    – rlbstr
    Oct 20, 2012 at 19:43
  • $\begingroup$ 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’. $\endgroup$ Oct 20, 2012 at 20:05

1 Answer 1

2
$\begingroup$

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$ ...

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .