2
$\begingroup$

$R$ is a reflexive and transitive binary relation with field $A$.

Prove that equivalence relation $S$ in $A$ exists and partial ordering $T$ in $A/S$, such that for arbitrary $x$ and $y$ from $A$ the following is true:

$\langle x,y\rangle\in R \iff \langle [x]_S, [y]_S\rangle \in T$

  • 0
    @Asaf I meant that there were boxes (like rectangles) without anything in them. I do know that the notation $[x]_S$ stands for equivalence class of......2012-01-26

1 Answers 1

4

What is missing from $R$ to be a partial order? Of course anti-symmetry, what does that mean? That perhaps there are two distinct $x,y\in A$ such that $x R y$ and $y R x$.

Let $S$ be the equivalence relation defined as: $xSy\iff xRy\land yRx$. It is simple to verify this is indeed an equivalence relation (a job I leave to you).

Now consider the relation $T$ defined as in your question, $\langle [x]_s,[y]_s\rangle\in T\iff \langle x,y\rangle\in R$. It is also not hard to show that it is a partial ordering of $A/S$.