A set $X$ together with a binary relation $\leq$ such that for all $x,y,z\in X$,

$O1$. $x\leq x$

$O2$. $x\leq y$ and $y\leq x$ then $x=y$

$O3$. $x\leq y$ and $y\leq z$ then $x\leq z$

is called an ordered or sometimes a partially ordered.

An ordered $(X,\leq)$ is called a total order if for all $x,y\in X$, either $x\leq y$ or $y\leq x$.

Question: Show that total orders are maximal orders

My question: is there a typo in the question? What is a maximal order? How can I prove the question, can you help? Thanks...

  • $\begingroup$ Maximal in the sense that there is no partial ordering of $X$ which extends a total order, except the total order itself. $\endgroup$
    – Asaf Karagila
    Feb 21 '19 at 8:29
  • $\begingroup$ @AsafKaragila thanks, how should I prove the question, may you give me a hint? $\endgroup$
    – user295645
    Feb 21 '19 at 8:30

General remarks. An order relation $\leq$ on a set $X$ is a subset of $X \times X$ (i.e. an element of the powerset $\mathcal{P}(X \times X)$) satisfying axioms $O_1, O_2, O_3$. Since the set $\mathcal{P}(X \times X)$ is in turn ordered by inclusion $\subseteq$, the question on comparing two orders on $X$ makes sense. In particular, an order $\leq$ on $X$ is maximal if, for every order $\leq'$ on $X$, $\leq \,\subseteq \, \leq'$ implies $\leq \,=\, \leq'$ (roughly, $\leq$ is maximal if there is no other order in $X$ putting "more order'' than $\leq$). Note that:

  1. $\leq \,\subseteq \, \leq'$ means that for all $x, y \in X$, if $x \leq y$ then $x \leq' y$ (roughly, if $x$ is less than $y$ according to the order $\leq$, then they are so according to the order $\leq'$);

  2. $\leq \,=\, \leq'$ means that for all $x, y \in X$, $x \leq y$ if and only if $x \leq' y$, i.e. the orders $\leq$ and $\leq'$ coincide.

Answer to your question. Concretely, suppose that $\leq$ is a total order on $X$. We show that $\leq$ is maximal, i.e. that for every order $\leq'$ on $X$, if $\leq \,\subseteq \, \leq'$ then $\leq \,=\, \leq'$. So, let $\leq'$ be an order on $X$ such that $\leq \,\subseteq\, \leq'$. We have to prove that $\leq \,=\,\leq'$, i.e. (see Point 2 above) that for all $x, y \in X$, $x \leq y$ if and only if $x \leq' y$. Let $x, y \in X$.

  • Since $\leq \,\subseteq\, \leq'$, we already know (see Point 1 above) that if $x \leq y$ then $x \leq' y$.

  • Suppose now that $x \leq' y$. There are two cases: either $y \leq x$ or $y \not\leq x$.

    1. If $y \leq x$ then $y \leq' x$ because $\leq \,\subseteq\, \leq'$. From $x \leq' y$ and $y \leq' x$ it follows (by axiom $O_2$) that $x = y$; in particular, $x \leq y$.
    2. If $y \not \leq x$ then $x \leq y$, since $\leq$ is a total order (i.e. either $x \leq y$ or $y \leq x$).

    We have just proved that, in all cases, if $x \leq' y$ then $x \leq y$.

This complete the proof that for all $x, y \in X$, $x \leq y$ if and only if $x \leq' y$. Therefore, $\leq \,=\, \leq'$.


Your Answer

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