Exercises
[06G] Let \(R⊆ X× X\) be a relation; taken \(x,y∈ X\) we will write \(xRy\) instead of \((x,y)∈ R\). Suppose \(R\) is reflexive i.e. \(xRx\) for every \(x\), and that it is transitive that is for every \(x,y,z∈ X\) you have \(xRy∧ yRz⇒ xRz\).
\(R\) is not necessarily an order relation, because we have not assumed that it is antisymmetric: however, we can "build" an order relation "identifying with each other" the elements of \(X\) on which \(R\) is not antisymmetric. Let’s see the construction in detail.
Let now \(∼\) the relation given by
\[ x∼ y \iff xRy ∧ yRx \]show that it is an equivalence relation.
Consider the quotient \(Y=X/∼\), we want to show how \(R\) passes to the quotient and produces a relation \(T\) on \(Y\). Show that if \(x,y,\tilde x,\tilde y∈ X\) and we have \(x∼ \tilde x,y∼ \tilde y\) then \(xRy\iff \tilde xR\tilde y\). So let’s define \(T\) as the set of all pairs of classes of equivalence whose products are contained in \(R\) i.e. \(T=\{ (z,w)∈ Y^ 2 : z× w ⊆ R\} \); this can also be written as
\[ zTw \iff (∀ x∈ z,∀ y∈ w , xRy) \]we abbreviate this definition as \([x]T[y] \iff xRy\) (which is a good definition because the right member does not depend on the choice of representatives in the classes).
Finally, show that \(T\) is an order relation on \(Y\).
Solution 1