Can strict partial orders be axiomatized using just one elementary sentence?

49 Views Asked by At

This is a follow-up to my previous question, here: Can equivalence relations be axiomatized using just one elementary sentence?. Referring back to that question, I define an elementary sentence to be an atomic formula, a negated atomic formula, or finite disjunctions of the previous two. Now, strict partial orders can be axiomatized using the two elementary sentences $\neg xRx$ and $\neg xRy \vee \neg yRz \vee xRz$, which are, respectively, Anti-reflexivity and Transitivity. I am wondering if we can axiomatize strict partial orders using just one elementary sentence. If we can't, what is the proof we can't?

1

There are 1 best solutions below

0
On BEST ANSWER

Minor quibble: when you define "elementary sentence," stricty speaking you are conflating a formula with its universal closure. This is a fairly common abuse of terminology, so I'm just going to follow it in the rest of this answer, but it's worth being aware of.

The same basic idea as in my answer to another question of yours gives a negative answer here. Suppose $\varphi$ is an elementary sentence true only in strict partial orders. Then none of the disjuncts of $\varphi$ can be un-negated instaces of $R$, since otherwise $\varphi$ would be true in any structure where $R$ is interpreted as the total relation (= holding of all pairs). However, this means that if $(X;R)\models\varphi$ and $S\subseteq R$ then $(X;S)\models\varphi$ as well, since in passing from $R$ to $S$ we only ever make more disjuncts of $\varphi$ true for any particular variable assignment. But now consider e.g. $X=\{a,b,c\}$, $R=\{(a,b),(b,c),(a,c)\}$, and $S=\{(a,b),(b,c)\}$. Since $(X;S)$ is not transitive, it is not a strict partial order, and so we must have $(X;S)\not\models\varphi$ and hence $(X;R)\not\models\varphi$.

So any elementary sentence true in only the strict partial orders must be false in at least some (indeed, quite a lot of) structures which are not strict partial orders.