A Maximal Order is a Total Order

Question

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

O$1$. $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 sometiomes 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$.
• Define $S:=\left\{R\subseteq X\times X : \text{R is a order on X}\right\}$

$(M,\leq)$ is maximal order in $S$ that for any $M\in S$ if $M\subseteq R$ then $M=R$.

Question: Maximal orders are total order.

My proof of the question. Define $S:=\left\{R\subseteq X\times X : \text{R is a order on X}\right\}$. Let $(M,\leq)$ be maximal order in $S$. We will show $(M,\leq)$ is also a total order. Assume not, that is there is an element of $M$ such that it is not comparable, so define

$$M'=M\cup\left\{(a,b)\right\}$$

We need to show $M'$ is a partially ordered, so we need to check:

$i)$ $(x,x)\not\in M'$ for any $x\in M'$.

Proof of i). Since $(x,x)\not\in \left\{(a,b)\right\}$ and $(x,x)\not\in M$ because $M$ is a partially order, hence $(x,x)\not\in M'$ for any $x\in M'$.

$ii)$ if $(x,y)\in M'$ and $(y,x)\in M'$ for all $x,y\in M'$, then $x=y$.

Proof of ii). Assume $(x,y)\in M'$ and $(y,x)\in M'$. If $(x,y)\in\left\{(a,b)\right\}$, then $(x,y)=(a,b)$, so $(y,x)\in M$, hence $x=y$. If $(x,y),(y,x)\in M$, then we would have a contradiction because our assumption $M$ is not a total order. Then, wlog $(x,y)\in\left\{(a,b)\right\}$.

$iii)$. If $(x,y)\in M'$ and $(y,z)\in M'$, then $(x,z)\in M'$.

Proof of iii). Assume $(x,y)\in M'$ and $(y,z)\in M'$. Wlog, $(x,y)\in\left\{(a,b)\right\}$, then $(x,y)=(a,b)$, so $(y,z)\in M'$, hence $(y,z)\in M'$, so if $(x,y),(y,z)\in M$, then $M'$ is not transitive because $(a,b)\in M'$ but $(b,a)\not\in M'$.

So, I couldn't coninue, can you help me?

Answer 1

If $R$ is a maximal (by inclusion in $X \times X$) partial order (I'll write $xRy$ interchangeably with $(x,y) \in R$, as is usual), then this is linear: suppose not, then there are $a,b \in M$ such that $(a,b) \notin R$ and $(b,a) \notin R$.

Then define $R' = R \cup \{(x,y) \in X \times X: xRa \land bRy \}$, which adds more pairs (probably) than just adding $(a,b)$ as you did.

We do add something, as $(a,b) \in R'$ by definition (the second case holds). So if we show it's a partial order still, it will contradict the maximality and we're done. Note that we already build in our reliance on transitivity : we want to add $(a,b)$ that doesn't kill it for some $x,y$ elsewhere.. In fact, if $xRa$ and $bRy$ already both held, we have to add $(x,y)$ to the relation when we add $(a,b)$..

$xRx$ for all $x$ so certainly $xR'x$ for all $x$ too.

If $xR'y$ and $yR'x$ there are some cases to consider:

• $xRy$ and $yRx$ hold, and then $x=y$.
• $xRy,yRa \text{ and } bRx$ hold (so the second $R'$ is from the added set). But then transitivity gives $xRa$ and $bRy$ and then also $bRa$, which contradicts the assumption that $(b,a) \notin R$. So this case cannot occur.
• $xRa, bRy$ (from the first) and $yRx$ (second was "old"). We get $bRx$ and hence $bRa$ again, contradiction. So another impossible case.
• Both are new: $xRa, bRy$ and $yRa$ and $bRx$ hold. But $bRx$ and $xRa$ implies $bRa$ contradiction.

Conclusion: the only way we can have both $xR'y$ and $yR'x$ is when these relations aren't new and then we're home free as we then know $x=y$.

Transitivity:

Suppose $xR'y$ and $yR'z$. Again 4 cases (I'll skip the trivial case there are no new relations):

• $xRy$ and $yRa$ and $bRz$. The first two give $xRa$ and so with the last one $xR'z$ holds, as required.

• $xRa$ and $bRy$ and $yRa$ and $bRz$. So the first and last directly get us $xR'z$.

• $xRa$ and $bRy$ and $yRz$. So $bRz$ from the last two and so $xR'z$ as required.

This concludes the proof that $R'$ is a partial order.