On winning Ehrenfeucht games and monadic NP (Q1919539): Difference between revisions

For a given property of structures, in model theory, and in particular in finite model theory, its inexpressibility in first-order logic (or fragments of second-order logic) is often proved by means of Ehrenfeucht-Fraïssé games. The main theorem of the present paper states sufficient conditions that ensure that a winning strategy (in these games) for small parts of structures can be extended to a global strategy; one of these conditions says that the substructures induced on the points far distant from the distinguished small subsets are isomorphic. Among others the theorem is applied to show that the connectivity of ordered graphs is not expressible in monadic \(\Sigma^1_1\).