first order definability with $<$ vs $Succ, 0$.

77 Views Asked by At

In first order logic formulae with just the predicate $<$ could describe more structures than first order formulaes with $Succ$ (successor predicate) and a constant $0$ such that $\forall x (\neg Succ(x,0)) \equiv true$. And because $Succ$ and $0$ could be defined by $<$ the structures describable by $Succ, 0$ are properly contained in those describable by just $<$.

Has anyone a simple proof that the inclusion is proper? For example a language which could be just defined with $<$ but not with $Succ, 0$?

1

There are 1 best solutions below

0
On BEST ANSWER

The language $c^*ac^*bc^*$ is *FO*$[<]$-definable but is not *FO*$[Succ, Pred, \min, \max]$-definable. More details in the paper The expressive power of existential first order sentences of Büchi's sequential calculus.