$2$-variable segment of FO over ordered, finite structures - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T09:40:37Z http://mathoverflow.net/feeds/question/62404 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/62404/2-variable-segment-of-fo-over-ordered-finite-structures $2$-variable segment of FO over ordered, finite structures Frank 2011-04-20T12:51:10Z 2011-04-20T22:01:49Z <p>Let $FO$ be first-order logic and $FO^k$ be $k$-variable segment of $FO$, i.e. $FO^k$ has only $k$ variables.</p> <p>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$.</p> <p>Is this true? Are there any assumptions about the vocabulary? </p> http://mathoverflow.net/questions/62404/2-variable-segment-of-fo-over-ordered-finite-structures/62461#62461 Answer by Michaël for $2$-variable segment of FO over ordered, finite structures Michaël 2011-04-20T21:33:14Z 2011-04-20T22:01:49Z <p>It is not the case. As an example, the following paper:</p> <p>Kouck´y, M., Lautemann, C., Poloczek, S., Th´erien, D.: Circuit lower bounds via Ehrenfeucht-Fraiss´e games, 2006.</p> <p>shows that, over words, FO[+, $\times$] with 2 variables is equivalent to AC$^0$ with <i>linear size</i> circuits --- while FO[+, $\times$] is equivalent to the whole class AC$^0$.</p> <p>Those two classes are known to differ (S. Chaudhuri and J. Radhakrishnan: Deterministic restrictions in circuit complexity, 1996).</p>