0
$\begingroup$

This is a natural follow-up to my question, here:In first-order logic without equality, is the theory of partial orders the same as preorders?. My current question is, consider first-order logic without equality with a single binary relation $R$. Is the equality-free theory of reflexive linear orders the same as the equality-free theory of linear preorders? By the way, I define a linear preorder to be a preorder such that for all $x$ and $y$ in the preorder, either $x \leq y$ or $y \leq x$. Also, if the answer is no, what is an explicit axiomatization of the equality-free theory of reflexive linear orders?

$\endgroup$

1 Answer 1

3
$\begingroup$

The answer to this question is yes, and we can use exactly the same trick I've used to answer a couple of your earlier questions (1, 2, 3).

Specifically, given a linear preorder $L$, let $L'$ be the quotient of $L$ by the relation $x\sim y\iff x\le y\wedge y\le x$. Then $L'$ is clearly a linear order. Meanwhile, the quotient map $L\rightarrow L'$ preserves and reflects the linear order $\le$, so we get $L\equiv_{\mathsf{FOL_{w/o=}}}L'$. This shows that the $\mathsf{FOL_{w/o=}}$-theory of linear preorders contains the $\mathsf{FOL_{w/o=}}$-theory of linear orders; since the converse inclusion is trivial, we're done.

I strongly recommend that you carefully read the general result in the third-linked answer above (relink); I think mastering it will help you answer questions of this type yourself much more quickly. In general, always look for "quasi-isomorphism" relations when trying to show equivalence of $\mathsf{FOL_{w/o=}}$-theories.

$\endgroup$

You must log in to answer this question.

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