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

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

share|cite|improve this question
What are those boxes out there? Can you please TeX it for us instead of the Unicode? – user21436 Jan 26 '12 at 19:24
@KannappanSampath: $[x]_S$ is a common notation for the equivalence class of $x$ in $S$. – Asaf Karagila Jan 26 '12 at 19:29
@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...... – user21436 Jan 26 '12 at 19:33
up vote 4 down vote accepted

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

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.