2
$\begingroup$

Consider first-order logic without equality with a single binary relation $R$. Now, the class $C$ of strict linear orders can't be axiomatized in first-order logic without equality. However, it does have a corresponding equality-free theory $Th(C)$. I conjecture that that theory is the same as the equality-free theory of the class $C'$ of strict partial orders. Is it true?

$\endgroup$

2 Answers 2

5
$\begingroup$

Noah's answer is perfectly adequate, but let me add that while you cannot define equality in this setting, you can define something very close. Let $x \sim y$ be an abbreviation for the formula $\forall z ((x < z \leftrightarrow y < z) \wedge (z < x \leftrightarrow z < y))$. This defines an equivalence relation on each strict partial order. Its equivalence classes can be ordered in the obvious way, and one can show by induction over the complexity of formulas that the original strict partial order and its quotient have the same first-order theory without equality. The relation defined on the quotient by the formula $x \sim y$ is the equality relation.

One can infer from this that the equality-free elementary theory of strict linear orders is axiomatized relative to the equality-free elementary theory of strict partial orders by the equality-free sentence $\forall x \forall y ((x < y) \vee (x \sim y) \vee (y < x))$.

$\endgroup$
5
$\begingroup$

No: writing "$<$" instead of "$R$" for simplicity, consider for example $$(*)\quad \exists x,y, u,v[u<x\wedge \neg u<y\wedge \neg v<x\wedge v<y].$$ This is an equality-free sentence satisfied in some strict partial orders (e.g. the order on $\{a,b,c,d\}$ with $a<b, c<d$, and no other comparabilities) but in no strict linear orders (one consequence of linearity is $\forall x,y,u[u<x\wedge \neg u<y\rightarrow y<x]$, which prevents $(*)$ from holding).

$\endgroup$

You must log in to answer this question.

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