Is it possible to define maximum elements in strict partial orders without using equality?

Question

This is similar to a question I asked a few months ago. It is possible to define maximum elements in reflexive partial orders $\leq$, without using equality: $(\forall x)x \leq c$. I wonder if it is possible to do so in strict partial orders. To make my question precise, suppose we are given a strict partial order $<$, and a constant $c$. Is it possible to define a first-order formula that does not mention equality, that holds precisely when $c$ is the maximum element? My intuition tells me it is not.

Answer 1

As a quick point of clarification: I'll write "the greatest" instead of "the maximal" since maximality usually refers to the weaker notion of having nothing strictly greater. That notion is of course trivially $\mathsf{FOL_{w/o=}}(<)$-definable.

---

Your intuition is correct (but see below). We can prove this using a technique which has been used to answer other questions of yours, including the one linked to in the OP: namely, that in $\mathsf{FOL_{w/o=}}$ surjections which preserve and reflect atomic formulas preserve arbitrary-complexity formulas.$^*$

• This is also true of $\mathsf{FOL}$ of course, but in full $\mathsf{FOL}$ we have the atomic formula "$x=y$" reflection of which forces injectivity. So in $\mathsf{FOL}$ this reduces to the statement that isomorphisms are elementary embeddings; it's only when we drop equality that we get to consider more interesting maps than bijections.

Specifically, let $D_1,D_2$ be the $1$- and $2$-element discrete strict partial orders respectively, and let $f$ be the unique map $D_2\rightarrow D_1$. In the sense of $\mathsf{FOL_{w/o=}}(<)$, the map $f$ is a surjection which preserves and reflects all atomic formulas, so for every $\overline{a}\in D_2$ and every $\mathsf{FOL_{w/o=}}(<)$-formula $\varphi$ we have $$D_2\models\varphi(\overline{a})\quad\iff\quad D_1\models\varphi(f(\overline{a})).$$ Since $D_1$ has a greatest element but $D_2$ doesn't, this means that the property of being a greatest element cannot be expressed by a $\mathsf{FOL_{w/o=}}(<)$-formula.

---

OK, what if we restrict attention to strict partial orders which do have a greatest element; can we now find that greatest element in $\mathsf{FOL_{w/o=}}$?

It turns out the answer is yes. Consider the formula $$\gamma(x)\equiv\forall y,z(y<z\rightarrow y<x).$$ It's easy to see that if $D$ is a strict partial order with a greatest element $a$ then $\gamma^D=\{a\}$.

However, note that this $\gamma$ behaves weirdly in strict partial orders without greatest elements. For example, let $L_{1,2}$ be the partial order with three elements $a,b,c$ such that $b<c$ and no other comparison holds. Then $\gamma^{L_{1,2}}=\{c\}$ even though $c$ is not the greatest element of $L_{1,2}$. Basically, in an arbitrary strict partial order $\gamma$ merely pins down the set of elements which are strictly above all non-maximal elements!

So the more nuanced answer is:

There is an $\mathsf{FOL_{w/o=}}(<)$-formula which identifies the greatest element of a strict partial order when such an element exists; however, there is no $\mathsf{FOL_{w/o=}}(<)$-sentence which holds in exactly the strict partial orders which have a greatest element, and so consequently the aforementioned formula must behave weirdly on some strict partial orders without a greatest element.

---

$^*$Actually, the "right" statement of this fact is a bit different.

Suppose $\mathcal{A},\mathcal{B}$ are structures in the same language with domains $A,B$, and $\mathbb{F}\subseteq A\times B$ is such that:

• $\mathbb{F}$ is total: for all $a\in A$ there is some $b\in B$ such that $a\mathbb{F}b$.

• $\mathbb{F}$ is surjective: for all $b\in B$ there is some $a\in A$ such that $a\mathbb{F}b$.

• $\mathbb{F}$ preserves and reflects atomic formulas: for every atomic formula $\varphi(x_1,...,x_n)$ and every $a_1,...,a_n\in A$ and $b_1,...,b_n\in B$ with $a_i\mathbb{F}b_i$ for all $1\le i\le n$, we have $$\mathcal{A}\models\varphi(a_1,...,a_n)\quad\iff\quad\mathcal{B}\models\varphi(b_1,...,b_n).$$

Then $\mathbb{F}$ preserves and reflects all $\mathsf{FOL_{w/o=}}$-formulas: if $\psi(x_1,...,x_n)$ is an arbitrary $\mathsf{FOL_{w/o=}}$-formula, $a_1,...,a_n\in A$, and $b_1,...,b_n\in B$ with $a_i\mathbb{F}b_i$ for all $1\le i\le n$, we have $$\mathcal{A}\models\psi(a_1,...,a_n)\quad\iff\quad\mathcal{B}\models\psi(b_1,...,b_n).$$ In particular, if such an $\mathbb{F}$ exists then $\mathcal{A}\equiv_\mathsf{w/o=}\mathcal{B}$.

Note that this version of the statement is symmetric and compositional, and arguably such relations give the right notion of "equality-free isomorphism"; that said, it's a bit harder to think about at first.