Are partial orders definable in first order logic without equality?

Question

Consider a first order language without equality, and just one relation symbol P. Is there a set of axioms(which could be either a finite or infinite set) in that language, such that all those axioms will be true iff P is a reflexive partial order? Certainly, antireflexive (also known as strict) partial orders are definable. I was wondering if reflexive partial orders are definable as well.

Answer 1

In the first-order language without equality, and just one (binary) relation symbol $P$, all models of the sentence $\forall x\forall y Pxy$ satisfy exactly the same sentences, but only the one-element models of that sentence are (reflexive) partial orders. Therefore, the class of (reflexive) partial orders is not definable in that language.

Answer 2

In first-order logic without equality, one can add a new, non-logical symbol "$=$" to the language, add axioms to ensure that the interpretation of $=$ is an equivalence relation, and add an axiom scheme $$ x = y \to (\phi(x) \leftrightarrow \phi(y)) $$ for all formulas $\phi$ in the newly extended language. The result is that, in any model $M$ of the extended language, we can mod out by $=$ to obtain a model that satisfies the same sentences and in which $=$ is interpreted by the true equality relation (these are called "normal models"). Thus every model of the extended theory looks like a model of first-order logic with equality that has been "blown up" by replacing individual elements with equivalence classes of indistinguishable elements.

So, the result is that although partial orders are not axiomatizable in first-order logic without equality, something very similar is: kinda-partial orders in which the $=$ relation is actually just some equivalence relation, and in which the order relation respects this equivalence relation and otherwise acts just like a partial order. These can be viewed as partial orders on setoids -- for example, if we define real numbers as equivalence classes of Cauchy sequences of rationals, then the usual order relation on $\mathbb{R}$ induces a kinda-partial order on the Cauchy sequences themselves.

The same phenomenon holds for arbitrary theories, not just partial orders. In first-order logic without equality we can always add an $=$ symbol that has the same substitutivity property as true equality, but the interpretation of $=$ may be an arbitrary equivalence relation. But we are rarely interested in the equivalence relation. So it is common to limit ourselves to normal models - which is the same as just working in first-order logic with equality.