19
$\begingroup$

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.

$\endgroup$
9
  • 2
    $\begingroup$ Is the category of preordered sets equivalent to the category of partially ordered sets (where the morphisms are the maps $f$ with $x\leq y\Rightarrow f(x)\leq f(y)$)? $\endgroup$ Jul 30, 2022 at 1:10
  • 2
    $\begingroup$ I'm not sure, but the answer could be relevant. $\endgroup$ Jul 30, 2022 at 1:12
  • $\begingroup$ Does a bi-interpretation between theories provide adjoint functors for the associated categories of models of those theories? $\endgroup$ Jul 30, 2022 at 1:32
  • 8
    $\begingroup$ @JosephVanName: They are not equivalent. In both categories, the singleton * is a final object, and for any object $X$ the underlying set can be recovered as $\mathrm{Hom}(*,X)$. So any equivalence should respect cardinalities. But, up to isomorphism, there are three (resp. only two) preordered (resp. ordered) sets with two elements. $\endgroup$ Jul 30, 2022 at 6:39
  • $\begingroup$ Ah, this won't help, then, because interpretations don't have to respect cardinalities, because of the k-tuples. $\endgroup$ Jul 30, 2022 at 11:19

1 Answer 1

18
$\begingroup$

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$.

$\endgroup$
10
  • 1
    $\begingroup$ Thanks for this answer, which shows that any interpretation must use tuples. One can also see this by observing, alternatively, that there are strictly more preorders than orders of a given finite size (at least 2), which means we cannot definably pair them. (By the way, are you any relation of my coauthor Alfredo Freire?) $\endgroup$ Jul 30, 2022 at 11:44
  • 2
    $\begingroup$ @JoelDavidHamkins Thanks, no, I am not member of Alfredo's family, but we are good friends and I was his co-advisor here in Brazil. I suspect that the "automorphism group argument" may be adapted to show the failure of higher dimensional bi-interpretability. $\endgroup$ Jul 30, 2022 at 12:04
  • 3
    $\begingroup$ That would be great! (And I think I may have asked you before about Alfredo, sorry about that, if so.) $\endgroup$ Jul 30, 2022 at 12:58
  • $\begingroup$ @JoelDavidHamkins There is nothing to be sorry about, and I really appreciate your work. My idea is as follows. Suppose that we have a definable partial ordering on the ordered pairs of individuals of the above preorder. In order to recover the original preorder, this partial order cannot be the identity relation. There are two kinds of ordered pairs: eight whose terms are equivalent in the preorder, and eight whose terms are not equivalent. Any nontrivial relation in the partial order must use different types of pairs (because of the automorphisms of the the preoder). To be continued. $\endgroup$ Aug 1, 2022 at 16:18
  • 1
    $\begingroup$ Yes, my comment applies to the first case, not the second (I got the directions mixed up). $\endgroup$ Aug 3, 2022 at 16:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.