Making a reflexive and transitive relation into a partial order

167 Views Asked by At

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

1

There are 1 best solutions below

0
On BEST ANSWER

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