Definable vs Interpretable Order

Question

This is probably a trivial question but I'll ask it nonetheless.

What is the difference between an order being definable, and an order being interpretable? All texts I've read make a distinction between the two, but they are advanced enough to not provide definitions.

I know that a linear/partial order $<$ on $M^n$ is definable if there exists $\phi(\bar x,\bar y)$ such that $M \models \phi(\bar a,\bar b)$ if and only if $\bar a< \bar b$. What would it mean for such an order to be interpretable?

Answer 1

Briefly, "interpretable" means "definable on a quotient of a definable set by a definable equivalence relation" or, equivalently, "definable in $M^{eq}$". In the case of orders, an interpretable partial order is the same thing as a definable pre-order.

Recall the following four axioms for a binary relation $\leq$ on $X$:

1. (Reflexivity) For all $x\in X$, $x\leq x$.
2. (Transitivity) For all $x,y,z\in X$, if $x\leq y$ and $y\leq z$, then $x\leq z$.
3. (Anti-symmetry) For all $x,y\in X$, if $x\leq y$ and $y\leq x$, then $x = y$.
4. (Linearity) For all $x,y\in X$, $x\leq y$ or $y\leq x$.

The following types of order are defined by combinations of these axioms:

• Pre-order: 1 and 2
• Partial order: 1, 2, and 3
• Linear pre-order: 1, 2, and 4
• Linear order: 1, 2, 3, and 4

For any pre-order $\leq$ on $X$, there is an equivalence relation $\sim$ defined by $x\sim y$ if and only if $x\leq y$ and $y\leq x$. Then the relation $\preceq$ defined by $[x]_\sim \preceq [y]_\sim$ if and only if $x\leq y$ is a well-defined partial order on $X/{\sim}$. If $\leq$ is a linear pre-order, then $\preceq$ is a linear order.

Now if the pre-order $\leq$ is definable (on the definable set $X$), then $\sim$ is a definable equivalence relation on $X$, and the induced partial order $\preceq$ on $X/{\sim}$ is interpretable.

Conversely, if $\preceq$ is an intepretable partial order (on the quotient $X/E$ of a definable set $X$ by a definable equivalence relation $E$), then we can "pull back" $\preceq$ to a definable binary relation on $X$ by $x\leq y$ if and only if $[x]_E \preceq [y]_E$. And this relation $\leq$ is a definable pre-order on $X$.

---

Regarding the paper by Pierre Simon that you link to: The statement that SOP is equivalent to "admits a definable partial order with infinite chains" is not quite right. Either "partial order" should be changed to "preorder", or "definable" should be changed to "interpretable".

So the correct statement is that an NIP unstable theory always has an interpretable partial order with infinite chains, and the goal of the paper is to improve this to an interpretable infinite linear order. The main result gives something weaker than interpretable: namely definable on a quotient by a $\bigvee$-definable (but not definable) equivalence relation. In the $\aleph_0$-categorical case, we do actually get an interpretable infinite linear order. But the quotient is essential: We can pull back this interpretable linear order to a definable linear preorder, but not a definable linear order.