Is the theory of a partial order bi-interpretable with the theory of a pre-order?

Question

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.

For clarity, one theory $S$ is interpretable in another theory $T$, if for some $n$ (the dimension) we can in $T$ define a class of $n$-tuples and an equivalence relation on them, and provide $T$-formulas to be used for the interpretations of the relations, functions, and constants of $S$, such that $T$ proves every resulting translation of an assertion in $S$, using the equivalence relation as the interpretation of $=$. A classic example is the interpretation of the rational field in the integer ring, using pairs (with second coordinate not zero) under the same-ratio equivalence relation.

Two theories are mutually interpretable, if each is interpreted in the other. Two theories are bi-interpretable, in contrast, a significantly stronger notion, if they are mutually interpretable in such a manner that each theory can also define a copy of its own universe in the interpreted copy of a copy. In terms of models, each model is interpreted in the other, and when doing it twice, each model is copied to the copy of itself within the copy of the other model. The critical requirement is that the resulting isomorphisms are definable in the parent model.

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.

Answer 1

They are not one dimensional bi-interpretable. The pre-order on $\{a,b,c,d\}$ given by $a\equiv b$ and $c\equiv d$ (and $a, b$ not related to $c, d$) is homogeneous in the sense that for any individuals $x, y$, there is an automorphism permuting $x$ and $y$. If those theories were one-dimensional bi-interpretable, there would be a partial order with the same domain (for the domain is finite) and the same automorphism group. But there is no such partial ordering on $\{a,b,c,d\}$ because the only homogeneous partial ordering on this set is the identity relation, whose automorphism group is not the automorphism group of the original pre-order.

EDIT

More information can be extracted from the above example. Let $P$ denote the theory of partial orderings and $Q$ denote the theory of preorders. Let $I$ be an interpretation of $P$ in $Q$ and $J$ be an interpretation of $Q$ in $P$.  Fix a preorder $M$, and let $N$ and $\bar M$ be the partial order defined by $I$ and the preorder defined by $J$, respectively. The automorphism group $G(M)$ of $M$ acts on the domain of $N$, so that this domain must be a set of orbits. Similarly, the automorphism group $G(N)$ of $N$ acts on the domain of $\bar M$.

We can show that if $I$ is one-dimensional, then $(I,J)$ is not a bi-interpretation, no matter what is the dimension of $J$, and also that if $I$ is two-dimensional and $J$ one-dimensional then $(I,J)$ is not a bi-interpretation.

Let $M$ be our preorder on $\{a,b,c,d\}$. 

First, suppose that $I$ is one-dimensional. Then, every automorphism of the original preorder must be an automorphism of the defined partial order. Therefore, the defined partial order must be the identity relation, and we cannot definably recover the original preorder from the identity relation, no matter what is the dimension of $J$. Indeed, the defined structure on tuples must be preserved by every automorphism of the partial order.

Now assume that $I$ is two-dimensional and $J$ is one-dimensional. The ordered pairs of the original preorder may be separated in three orbits of the action of $G(M)$, according to the natural equivalence relation in the preorder:

$A=\{(x,y) : x= y \}$

$B=\{(x,y) : x\equiv y\ ,x\neq y \}$

$C=\{(x,y) : x\not\equiv y\}$

Sets $A$ and $B$ contain four elements each, and $C$ contains eight elements.  The domain of $N$ is a set of $G(M)$-orbits of ordered pairs of  $\{a,b,c,d\}$. Within a given orbit, there can be no comparison between different ordered pairs in $N$, for any two pairs within the same orbit can be permuted by the action of an automorphism of $G(M)$. So, for any two pairs within the same orbit (of the action of $G(M)$) there is an automorphism in $G(N)$ that permutes exactly these pairs and fixes the rest of the orbit (for there is no comparison to be preserved by $G(N)$ within an orbit). The action of $G(M)$ is not like that.

If the domain of the preorder $\bar M$ defined by the composition of $J$ and $I$ over the original preorder contains a  pair $p\in C$, then this domain must contain all of $C$, because it is an orbit of the action of the original automorphism group on those tuples, and similarly for $A$ and $B$. However, the original preorder does not contain eight elements.

So, the domain of $\bar M$ is either $A$ or $B$. But if $\bar M$ were isomorphic to $M$, then $G(N)$ would contain an automorphism of $A$ and an automorphism of $B$ that could not be automorphisms of $\bar M$. Indeed, in both cases, the automorphism of $N$ that permutes exactly two nonequivalent (according to $\bar M$) pairs could not be an automorphism of $\bar M$.

Answer 2

There are no equality-preserving bi-interpretations. Take the pre-order in my previous answer, $a\equiv b$ and $c\equiv d$, and no further relations. Let $I$ be an $m$-dimensional interpretation of the theory of partial orders in the theory of pre-orders and $J$ be an $n$-dimensional interpretation in the other direction. Suppose that both $I$ and $J$ are equality-preserving in the sense that the equality relation on $m$-tuples defined by $I$ is the canonical one, and similarly for $J$.

When interpretation $I$ is applied to our pre-order, it defines a partial order of $m$-tuples extracted from $\{a, b, c, d\}$. Let $\overline{\alpha}$ be one of the $m$-tuples in the domain of the defined partial order. Suppose, without loss of generality, that the first term in $\overline{\alpha}$ is $a$.

There are automorphisms $f_1$, $f_2$, $g$ and $h$ of our original pre-order, all of them of order $2$, permuting $a$ and $b$, $a$ and $c$, and $a$ and $d$. $f_1$ and $f_2$ both permute $a$ and $b$, but $f_1$ fixes $c$ and $d$, while $f_2$ permutes them also. These induce automorphisms $\overline{f_1}$, $\overline{f_2}$, $\overline{g}$ and $\overline{h}$ on the $m$-tuples of the defined partial order, so that there must be at least other three $m$-tuples $\overline{\beta_1}=\overline{f_1}(\overline{\alpha})$, $\overline{\beta_2}=\overline{f_2}(\overline{\alpha})$, $\overline{\gamma}=\overline{g}(\overline{\alpha})$ and $\overline{\delta}=\overline{h}(\overline{\alpha})$ in the domain of the defined partial order. Notice that $\overline{\beta_1}$ and $\overline{\beta_2}$ may be equal.

Therefore, $\overline{\alpha}$, $\overline{\beta_1}$, $\beta_2$, $\overline{\gamma}$ and $\overline{\delta}$ must be incomparable, because for each pair of these tuples there is an automorphism of the defined partial order which maps the first element of the pair to the second element. For example, $\overline{g}\circ\overline{h}^{-1}$ maps $\overline{\delta}$ to $\overline{\gamma}$. We conclude that the defined partial order restricted to $\overline{\alpha}$, $\overline{\beta_1}$, $\overline{\beta_2}$, $\overline{\gamma}$ and $\overline{\delta}$ must be trivial, hence any permutation of those $m$-tuples gives an automorphism of this partial order.

Now, when interpretation $J$ is applied to the defined partial order (defined by the application of $I$ to our pre-order), it defines a pre-order of $n$-tuples of $m$-tuples. Let $\overline{a}$ be one of the $n$-tuples in the domain of the defined pre-order. Let $\overline{\alpha}$, which is an $m$-tuple, be the first term in $\overline{a}$.

Therefore,

1. $\overline{a}=(\overline{\alpha},...)$,
2. $\overline{b_1}=(\overline{f_1}(\overline{\alpha}),...)=(\overline{\beta_1},...)$,
3. $\overline{b_2}=(\overline{f_2}(\overline{\alpha}),...)=(\overline{\beta_2},...)$,
4. $\overline{c}=(\overline{g}(\overline{\alpha}),...)=(\overline{\gamma},...)$ and
5. $\overline{d}=(\overline{h}(\overline{\alpha}),...)=(\overline{\delta},...)$

must all be in the domain of the defined pre-order, for its domain must be preserved by the automorphisms. If this pre-order is supposed to be isomorphic to our original pre-order with four elements, then $\beta_1$ must be equal to $\beta_2$. This implies that the $m$-tuple $\overline{\alpha}$ must contain only equivalent terms. That is, if $a$ is a term of $\overline{\alpha}$, then this $m$-tuple cannot contain $c$ or $d$. More generally, the orbit of $\overline{\alpha}$ in the defined partial order must contain only $\overline{\beta}=\overline{\beta_1}=\overline{\beta_2}$, $\overline{\gamma}$ and $\overline{\delta}$.

Now, we have

1. $\overline{a}=(\overline{\alpha},...)$,
2. $\overline{b}=(\overline{\beta},...)$,
3. $\overline{c}=(\overline{\gamma},...)$,
4. $\overline{d}=(\overline{\delta},...)$

in our defined pre-order. Suppose that one among $\overline{\beta}$, $\overline{\gamma}$ and $\overline{\delta}$ is a term in $\overline{a}$, say, $\overline{a}=(\overline{\alpha},\overline{\beta},...)$. But then, we would also have more than four $n$-tuples in this case. In fact, since the defined partial ordering of $\overline{\alpha}$, $\overline{\beta}$, $\overline{\gamma}$ and $\overline{\delta}$ is trivial and any permutation of this four $m$-tuples is an automorphism, we have that $\overline{a}$ could be mapped to

1. $(\overline{\beta},\overline{\alpha},...)$ by the transposition of $\overline{\alpha}$ and $\overline{\beta}$;
2. $(\overline{\gamma},\overline{\beta},...)$ by the transposition of $\overline{\alpha}$ and $\overline{\gamma}$;
3. $(\overline{\delta},\overline{\beta},...)$ by the transposition of $\overline{\alpha}$ and $\overline{\delta}$;
4. $(\overline{\alpha},\overline{\gamma},...)$ by the transposition of $\overline{\beta}$ and $\overline{\gamma}$.

Since the domain of the defined pre-order must be preserved by these permutations, the four $n$-tuples above must be in the domain, together with $\overline{a}$, a contradiction.

Therefore, there are no elements in $\overline{a}$ which are in the orbit of $\overline{\alpha}$ and are distinct from $\overline{\alpha}$, and similarly for $\overline{b}$ and $\overline{\beta}$, $\overline{c}$ and $\overline{\gamma}$, $\overline{d}$ and $\overline{\delta}$. Since any permutation of $\overline{\alpha}$, $\overline{\beta}$, $\overline{\gamma}$ and $\overline{\delta}$ fixing all other elements is an automorphism of the defined partial order, then we have that each transposition between $\overline{\alpha}$ and any one among $\overline{\beta}$, $\overline{\gamma}$ and $\overline{\delta}$ induces a similar transposition between $\overline{a}$ and the corresponding $n$-tuple among $\overline{b}$, $\overline{c}$ and $\overline{d}$, which must be an automorphism of the defined pre-order. In fact, the transposition between $\overline{\alpha}$ and $\overline{\beta}$ exchanges $\overline{a}$ and $\overline{b}$, and fixes $\overline{c}$ and $\overline{d}$, by the above. Hence this pre-order must be trivial and cannot be isomorphic to the original pre-order on $a$, $b$, $c$ and $d$.