How can one show that for phi in FO (First Order) there is a psi in
FO^3 (FO formulae that use at most 3 distinct variables) such that phi
and psi define the same class of linear orders?

---

Request for Question Clarification by mathtalk-ga on 03 Mar 2005 07:19 PST

Hi, mathguy123-ga:

This sounds like an interesting question, but I'm a bit thrown by the
"Subject".  A "finite model" would be one thing, but probably you are
asking about models with  a finite number of axioms.

It seems you may be asking this:  Let T be the first order theory of
linear (total) orders with no constants and only "<" and "=" as
predicates (with the usual axioms for equality).  Show that for any
(closed?) formula phi there exists a formula psi with at most 3
distinct variables such that:

  T + {phi} is model-equivalent to T + {psi}

regards, mathtalk-ga