Let $R$ be a total order. Is $R^{-1}$ a total order?

83 Views Asked by At

Let us assume that $R$ is a total order on a set $A$. Is its inverse, $R^{-1}$, also a total order on the set $A$?

Clearly $R$ is also a partial order and thus $R^{-1}$ is a partial order, so all that remains to prove (from the set of total order axioms) is that all the elements of $A$ are related to each other by $R^{-1}$, i.e.

\begin{align} \forall x \in A \forall y \in A (xR^{-1}y \lor yR^{-1}x). \end{align}

I attempt to prove this by contradiction. Let $R$ be a total order on $A$ and $R^{-1}$ not a total order. This is equivalent to stating that

\begin{align} [\forall x \in A \forall y \in A (xRy \lor yRx)] \land \lnot[\forall x \in A \forall y \in A (xR^{-1}y \lor yR^{-1}x)]. \end{align} The right term of the conjunction is equivalent to $\exists x \in A \exists y \in A ((x,y) \notin R^{-1} \land (y,x) \notin R^{-1})$. By using existential instantiation on this statement, I claim that $x_o$ and $y_o$ are such examples such that \begin{align} (x_o,y_o) \notin R^{-1} \land (y_o,x_o) \notin R^{-1}. \end{align} By using the rule of simplification, the definition of the inverse relation and the finally, the rule of conjunction, on the previous statement, I arrive at \begin{align} (y_o,x_o)\notin R \land (x_o,y_o) \notin R. \end{align}

However, when I universally instantiate $\forall x \in A \forall y \in A (xRy \lor yRx)$ (one of the initial assumptions) for $x_o$ and $y_o$, I get \begin{align} x_oRy_o \lor y_oRx_o \end{align} Which contradicts the previous statement, i.e. $(y_o,x_o)\notin R \land (x_o,y_o) \notin R$. Thus $R^{-1}$ needs to be a total ordering on $A$.

I can't shake the feeling that I made a mistake...Is all of this correct?

Thank you for your time!