In Munkres $\S$3, there are a few boring exercises that involves proving a relation is a total order. To name a few (I changed the strict orders to non-strict ones),

  • Q6: Define a relation on the plane by setting $(x_0,y_0) \leq (x_1,y_1)$ if $(y_0-x_0^2 < y_1-x_1^2$ $)$ or $($ $y_0-x_0^2 = y_1-x_1^2$ and $x_0 \leq x_1)$.

  • Q8: Define a relation on $\Bbb{R}$ by setting $xCy$ if $(x^2<y^2)$ or $(x^2 = y^2$ and $x\leq y)$.

  • Q9: Check that the dictionary order on two totally ordered set $(A, \leq_A)$ and $(B, \leq_B)$ is a total order. The dictionary order is defined as follows: if $a_1, a_2 \in A$ and $b_1, b_2 \in B$, then $(a_1,b_1) \leq (a_2, b_2) \iff (a_1 <_A a_2)$ or $(a_1 = a_2$ and $b_1 \leq_B b_2)$.

I found these problems can be generalized as follows:

Let $P,R \subseteq A \times A$. Suppose $P$ is a equivalence relation on $A$. Then we say $R \in T(P)$ if the following are satisfied:

  • $R$ is a transitive relation containing $P$.

  • (Comparability) For all $x, y \in A$, $xRy$ or $yRx$.

  • (Some generalization of antisymmetry?) If $xRy$ and $yRx$, then $xPy$.

Proposition 1: Let $P, Q$ be equivalence relations on $A$ such that $x Py$ and $x Q y \implies x =y$. Suppose $P', Q'$ be relations on $A$ such that $P' \in T(P)$ and $Q' \in T(Q)$. Then let $$x R y \iff \neg (y P' x) \text{ or } (x P y \text{ and } x Q' y) $$ Then $R$ is a total order defined on $A$.

I have already proven proposition 1 is true. Let's apply proposition 1 to Q6:

Let $(x_0,y_0)P(x_1,y_1) \iff y_0-x_0^2 = y_1-x_1^2$ and $(x_0,y_0)Q(x_1,y_1) \iff x_0 = x_1$. Clearly $P,Q$ are equivalence relations on $\Bbb{R}^2$ and we have $(x_0,y_0)P(x_1,y_1) \wedge (x_0,y_0)Q(x_1,y_1) \implies (x_0,y_0)=(x_1,y_1)$.

Let $(x_0,y_0)P'(x_1,y_1) \iff y_0-x_0^2 \leq y_1-x_1^2$. Clearly $P'$ is transitive. $P \subseteq P'$ since $y_0-x_0^2 = y_1-x_1^2 \implies y_0-x_0^2 \leq y_1-x_1^2$. For all $(x_0,y_0), (x_1,y_1) \in \Bbb{R}^2$, we also have $y_0-x_0^2 \leq y_1-x_1^2$ or $y_1-x_1^2 \leq y_0-x_0^2$. Finally, $y_0-x_0^2 \leq y_1-x_1^2$ and $y_1-x_1^2 \leq y_0-x_0^2$ implies $y_0-x_0^2= y_1-x_1^2$. So that $P' \in T(P)$.

Similarly, we let $(x_0,y_0)Q'(x_1,y_1) \iff x_0 \leq x_1$. We see that $Q'\in T(Q)$. So that the relation in Q6 is a total order by proposition 1.

So my questions are:

(1) Do we have a special name for the method of defining total order as described by proposition 1?

(2) Is there anymore important or interesting examples where we define total order in this way?

(3) Given an equivalence relation $P$, Do we have a special name for $T(P)$?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.