Showing that every satisfiable sentence with at most two variables has a finite model - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T14:25:32Z http://mathoverflow.net/feeds/question/79859 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/79859/showing-that-every-satisfiable-sentence-with-at-most-two-variables-has-a-finite-m Showing that every satisfiable sentence with at most two variables has a finite model anonymous 2011-11-02T19:16:46Z 2011-11-02T21:20:51Z <p>I have tried to prove, in first order logic, that every satisfiable sentence (without function symbols) with at most two variables has a finite model. My attempts were unsuccessful.</p> <p>This is an exercise from the (wider) model theory book written by Hodges (Encyclopedia of Mathematics and its Applications, Volume 42 - Model Theory, page 111). It follows an exercise about Immerman's pebble game, probably as an application.</p> <p>It's easy to see that proving the following will suffice: (*) given a structure A, prove that for every number n, there is a finite structure B such that player II has a winning strategy in immerman's pebble game of length n with 2 pebbles (between A and B).</p> <p>thanks for the help!</p>