𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An Ehrenfeucht-Fraïssé class game

✍ Scribed by Wafik Boulos Lotfallah

Publisher
John Wiley and Sons
Year
2004
Tongue
English
Weight
159 KB
Volume
50
Category
Article
ISSN
0044-3050

No coin nor oath required. For personal study only.

✦ Synopsis

This paper introduces a new Ehrenfeucht-Fraïssé type game that is played on two classes of models rather than just two models. This game extends and generalizes the known Ajtai-Fagin game to the case when there are several alternating (coloring) moves played in different models. The game allows Duplicator to delay her choices of the models till (practically) the very end of the game, making it easier for her to win. This adds on the toolkit of winning strategies for Duplicator in Ehrenfeucht-Fraïssé type games and opens up new methods for tackling some open problems in descriptive complexity theory. As an application of the class game, it is shown that, if m is a power of a prime, then first order logic augmented with function quantifiers F 1 n of arity 1 and height n < m can not express that the size of the model is divisible by m. This, together with some new expressibility results for Henkin quantifiers H 1 n gives some new separation results on the class of finite models among various F 1 n on one hand and between F 1 n and H 1 n on the other. Since function quantifiers involve a bounded type of second order existential quantifiers, the class game (in a sense) solves an open problem raised by Fagin, which asks for some inexpressibility result using a winning strategy by Duplicator in a game that involves more than one coloring round.

📜 SIMILAR VOLUMES

Trees and Ehrenfeucht–Fraı̈ssé games
Trees and Ehrenfeucht–Fraı̈ssé games
✍ Stevo Todorčević; Jouko Väänänen 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 221 KB

Trees are natural generalizations of ordinals and this is especially apparent when one tries to ÿnd an uncountable analogue of the concept of the Scott-rank of a countable structure. The purpose of this paper is to introduce new methods in the study of an ordering between trees whose analogue is the

Almost free groups and long Ehrenfeucht–
Almost free groups and long Ehrenfeucht–Fraı̈ssé games
✍ Pauli Väisänen 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 357 KB

An Abelian group G is strongly -free i G is L ∞; -equivalent to a free Abelian group i the isomorphism player has a winning strategy in an Ehrenfeucht-Fra ssà e game of length ! between G and a free Abelian group. We study possible longer Ehrenfeucht-Fra ssà e games between a nonfree group and a fre

Continuous Fraïssé Conjecture
Continuous Fraïssé Conjecture
✍ Arnold Beckmann; Martin Goldstern; Norbert Preining 📂 Article 📅 2008 🏛 Springer Netherlands 🌐 English ⚖ 472 KB
ON NON-DETERMINED EHRENFEUCHT-FRAÏSSÉ GA
ON NON-DETERMINED EHRENFEUCHT-FRAÏSSÉ GAMES AND UNSTABLE THEORIES
✍ Tapani Hyttinen; T. Hyttinen 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 511 KB

## Abstract In this paper we prove under some set theoretical assumptions that if __T__ is a countable unstable theory then there is a pair of models of __T__ such that Ehrenfeucht‐Fraïssé games between these models of large variety of lengths are non‐determined.