Complementary of a preorder relation

Question

We have $R = (A, A, G )$ a preorder relation (reflexive and transitive) which is defined on set $A$ and $ ρ_R = R \cap R^{-1} $ an equivalence relation through $R$. Therefore the relation $\overline{R}$ defined on the quotient set $A/ ρ_R $ through

$[a]_{ρ_R} \, \overline{R} \, [b]_{ρ_R} \iff a\,R\,b$

is well defined and represents a partial order relation on $A/ ρ_R $.
I don't understand why is that, since $ \overline{R} $ can't be reflexive or transitive.

Answer 1

First let me make clear that the formula in the question serves as the definition of $\overline R$. In particular, other than you thought, this overline notation does not denote a complement.

As an example, consider the relation "$xRy \iff$ person $x$ is at most as tall as person $y$" with the following people:

• $a=\text{Adam}$, $170~\rm cm$
• $b=\text{Barbara}$, $180~\rm cm$
• $c=\text{Charles}$, $180~\rm cm$
• $d=\text{Doris}$, $190~\rm cm$

We obviously have $aRa,aRb,aRc,aRd,bRb,bRc,bRd,cRb,cRc,cRd,dRd$.

Now $\rho_r = R \cap R^{-1}$ is the equivalence relation "$x$ is exactly as tall as $y$", with the three equivalence classes

• $[a]_{\rho_R} = \{a\}$
• $[b]_{\rho_R} = [c]_{\rho_R} = \{b,c\}$
• $[d]_{\rho_R} = \{d\}$

Now using the definition of $\overline R$, we get

• $[a]_{\rho_R} \overline R [a]_{\rho_R}$ because $aRa$.
• $[a]_{\rho_R} \overline R [b]_{\rho_R}$ because $aRb$.
• $[a]_{\rho_R} \overline R [d]_{\rho_R}$ because $aRd$.
• $[b]_{\rho_R} \overline R [b]_{\rho_R}$ because $bRb$.
• $[b]_{\rho_R} \overline R [d]_{\rho_R}$ because $bRd$.
• $[d]_{\rho_R} \overline R [d]_{\rho_R}$ because $dRd$.

This is obviously a partial order (indeed, in this case even a total order) of the three equivalence classes.

In the general case, you can see that $\overline R$ is indeed a partial order as follows:

• $\overline R$ is actually well defined (this has to be checked!): If $[a]_{\rho_R} = [b]_{\rho_R}$ and $[c]_{\rho_R} = [d]_{\rho_R}$ then we have to show that $[a]_{\rho_R} \overline R [c]_{\rho_R}$ iff $[b]_{\rho_R} \overline R [d]_{\rho_R}$.

  If $[a]_{\rho_R} = [b]_{\rho_R}$ then we have both $aRb$ and $bRa$, and from $[c]_{\rho_R} = [d]_{\rho_R}$ we get $cRd$ and $dRc$.

  Now by definition of $\overline R$, $[a]_{\rho_R} \overline R [c]_{\rho_R}$ iff $aRc$. Now thanks to transitivity of $R$, we get from $bRa$ and $aRc$ that $bRc$, and then with $cRd$ that $bRd$. The direction $bRd \implies aRc$ works analogously. But by definition of $\overline R$, $bRd \iff [b]_{\rho_R} \overline R [d]_{\rho_R}$.

• Reflexivity: Due to reflexivity of $a$, we have $aRa$, and thus by definition of $\overline R$ we get $[a]_{\rho_R}\overline R [a]_{\rho_R}$.

• Transitivity: If $[a]_{\rho_R} \overline R [b]_{\rho_R}$ and $[b]_{\rho_R} \overline R [c]_{\rho_R}$, then we have by the definition of $\overline R$ that $aRb$ and $bRc$, and thus by transitivity of $R$ we have $aRc$ which by definition of $\overline R$ means $[a]_{\rho_R} \overline R [c]_{\rho_R}$.

• Antisymmetry: If $[a]_{\rho_R} \overline R [b]_{\rho_R}$ and $[b]_{\rho_R} \overline R [a]_{\rho_R}$, then by definition of $\overline R$ we have $aRb$ and $bRa$, but that means that $a$ and $b$ are equivalent according to $\rho_R$, thus $[a]_{\rho_R} = [b]_{\rho_R}$.