$2$-variable segment of FO over ordered, finite structures

2011-04-20T12:51:10Z

Let $FO$ be first-order logic and $FO^k$ be $k$-variable segment of $FO$, i.e. $FO^k$ has only $k$ variables.

To my understanding, for every sentence $\varphi\in FO$ there exists a sentence $\psi\in FO^2$ such that for all finite structures $\mathfrak{A}$ with linear order it is the case that $\mathfrak{A}\vDash\varphi$ iff $\mathfrak{A}\vDash\psi$.

Is this true? Are there any assumptions about the vocabulary?

Answer by Michaël for $2$-variable segment of FO over ordered, finite structures

2011-04-20T21:33:14Z

It is not the case. As an example, the following paper:

Kouck´y, M., Lautemann, C., Poloczek, S., Th´erien, D.: Circuit lower bounds via Ehrenfeucht-Fraiss´e games, 2006.

shows that, over words, FO[+, $\times$] with 2 variables is equivalent to AC$^0$ with linear size circuits --- while FO[+, $\times$] is equivalent to the whole class AC$^0$.

Those two classes are known to differ (S. Chaudhuri and J. Radhakrishnan: Deterministic restrictions in circuit complexity, 1996).

$2$-variable segment of FO over ordered, finite structures - MathOverflow

$2$-variable segment of FO over ordered, finite structures

Answer by Michaël for $2$-variable segment of FO over ordered, finite structures