2
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Can you cite any of the texts you have problems with? $\endgroup$
    – Rob Arthan
    Feb 8, 2021 at 23:54
  • 2
    $\begingroup$ Usually, "interpretable" means "definable on a quotient of a definable set by a definable equivalence relation" or, equivalently, "definable in $M^{eq}$". But it's possible the texts you're reading are using one or both of these terms in a non-standard way. I agree with Rob Arthan that you should cite some examples. $\endgroup$ Feb 9, 2021 at 4:11
  • $\begingroup$ Thanks a lot for your replies. I think what Alex said is correct. The motivation of this question comes from NIP theories. We know that unstable NIP theories are SOP, and so they admit a definable partial order with infinite chains. There is an open question about whether all unstable NIP theories interpret an infinite linear order. At first I though this was the same as admitting a definable infinite linear order, but then I watched a talk by Pierre Simon where he said that this infinite linear order cannot be definable, hence my confusion. $\endgroup$ Feb 9, 2021 at 9:01
  • $\begingroup$ See the introduction of this: arxiv.org/pdf/1807.07949.pdf $\endgroup$ Feb 9, 2021 at 9:03

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks a lot Alex! This was very helpful. $\endgroup$ Feb 10, 2021 at 9:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .