A *partial order* relation $\leq$ on a set $A$ is a binary relation that is reflexive, transitive, and antisymmetric.

A *preorder* relation $\unlhd$ (also sometimes known as a *quasi order* or *pseudo order*) is merely reflexive and transitive. The difference is that a preorder may have nontrivial clusters of equivalent nodes, equivalent via $x\equiv y\iff x\unlhd y\unlhd x$.

**Question.** Is the theory of a partial order bi-interpretable with the theory of a preorder?

It is easy to see that these theories are mutually interpretable, but my question is specifically about bi-interpretation. I had intended to use these theories as an elementary example in the book I am writing in the section on interpretations of models and theories, but I have become confused about whether they are bi-interpretable or not. I strongly suspect that they are not bi-interpretable.

For the theories to be bi-interpretable would mean that in every partial order you can uniformly definably interpret a preorder, and in every preorder you can uniformly definably interpret a partial order, such that if you iterate this from order to preorder to order, the order you get is definably isomorphic with the original order, and similarly with the other iteration. In these interpretations, we allow the interpreted domain to consist of $k$-tuples modulo a definable congruence (like interpreting the complex field $\mathbb{C}$ in $\mathbb{R}$ or like the quotient field construction).

In particular, if the theories were bi-interpretable, then this would provide a bijective correspondence between isomorphism types of partial orders and preorders in such a way that is definable and interpretable, and every order could see for itself how it is copied through the iterated interpretations.

Of course every preorder $Q$ has the natural quotient $Q/\equiv$, which is a partial order interpretable in $Q$. But this construction will not help with a bi-interpretation, since many different preorders have isomorphic quotient orders — you cannot recover the original preorder from the quotient order.

Meanwhile, I do know that every preorder $Q$, as a structure, is bi-interpretable with a certain partial order $P$, an order that codes the original preorder in a tighter manner. Namely, one splits up the clusters of $Q$ into little antichains, each with its own private maximal element above, thereby marking it as such. In the resulting order $P$, we can definably identify which are the original nodes, and in $Q$ we can simulate $P$ and in $P$ we can simulate $Q$ in a structure-bi-interpretation manner.

But this is not a bi-interpretation of the theories, since not every partial order will arise as such a coding order. I wonder if one can somehow fix things up so that every order codes a preorder and conversely? Actually, I think it is not true.

2more comments