Can reflexive partial orders be defined from strict partial orders without using equality?

Question

Consider a reflexive partial order $\leq$. We can define its strict counterpart without using equality, like so: $x \leq y$ $\land$ $\neg y \leq x$. But from a strict partial order $<$, can we define its reflexive counterpart without using any equality formulas in the definition?

Answer 1

No, we cannot do this. (Below I'll write "$\mathcal{L}_{\mathsf{w/o=}}$" for the equality-free version of a logic $\mathcal{L}$.)

The key is that when we drop equality from our logical apparatus we get a notion of "near-isomorphism" which preserves all expressible structure: these are the maps which preserve and reflect all atomic formulas, and are surjective, but are possibly not injective.

To see where these come from, observe that when equality is built into our logical apparatus these are just the isomorphisms in the usual sense. Specifically, considering the atomic formula "$x=y$" we see that reflection of atomic formulas implies injectivity, and that gets us the usual notion of isomorphism. When equality is no longer part of our language, we have the possibility of non-injective maps of the above type. While these are absolutely not isomorphisms, they do suffice to demonstrate that the two structures in question are $\mathsf{FOL_{w/o=}}$-equivalent; this is a good exercise, and was previously used to answer another question of yours.

• In fact, such maps establish far more than $\mathsf{FOL_{w/o=}}$-equivalence. For example, they give full $\mathcal{L}_{\infty,\infty\,\mathsf{w/o=}}$-equivalence. On the other hand they do not yield $\mathsf{SOL_{w/o=}}$-equivalence, since $\mathsf{SOL_{w/o=}}$ is just $\mathsf{SOL}$.

With this in mind it's easy to see that there are strict partial orders in which equality is not $\mathsf{FOL_{w/o=}}$-definable: consider the surjection from the discrete two-element strict partial order to the discrete one-element strict partial order.

---

On the other hand, the above is not the whole story. Certainly some strict partial orders let us define equality with an $\mathsf{FOL_{w/o=}}$ formula. For example, if the order is linear then $x=y$ iff $\neg x<y\wedge\neg y<x$. More generally (and Asaf Karagila mentions this above), equality is $\mathsf{FOL_{w/o=}}$-definable in every strict partial order which is weakly extensional (I don't actually know what the technical term is) in the sense that each element is determined by how it interacts with $<$: $$\{z: z<x\}=\{z: z<y\}\mbox{ and }\{z: x<z\}=\{z: y<z\}\quad\implies\quad x=y.$$

So as a natural follow-up question we can ask:

For which strict partial orders $\mathfrak{A}=(A;<)$ can we define $=$ with an $\mathsf{FOL_{w/o=}}$-formula?

And it turns out that these are exactly the weakly extensional ones in the sense above.

Suppose $\mathfrak{A}$ is not weakly extensional. Let $a,b\in\mathfrak{A}$ be distinct with $\{z: z<a\}=\{z: z<b\}$ and $\{z: a<z\}=\{z: b<z\}$. Now consider the induced suborder $\mathfrak{A}'=(A\setminus \{a\}; <\upharpoonright A\setminus\{a\})$ and the map $f: \mathfrak{A}\rightarrow\mathfrak{A}'$ which is the identity off $\{b\}$ and sends $b$ to $a$. It's easy to check that this $f$ preserves and reflects all atomic $\mathsf{FOL_{w/o=}}$-formulas in our language, but it doesn't reflect equality.

Answer 2

Beyond FOL: Try the intersection of all reflexive total orders that contain your given partial order.