Submission date: 4 December 2012.

Abstract:

Ehrenfeucht-Fraïssé games are very useful in studying separation and equivalence results in logic. The standard finite Ehrenfeucht-Fraïssé game characterizes equivalence in first order logic. The standard Ehrenfeucht-Fraïssé game in infinitary logic characterizes equivalence in L_{ω_1ω}. The logic L_{ω_1ω} is the extension of first order logic with countable conjunctions and disjunctions. There was no Ehrenfeucht-Fraïssé game for L_{ω_1ω} in the literature.

In this paper we develop an Ehrenfeucht-Fraïssé Game for L_{ω_1ω}. This game is based on a game for propositional and first order logic introduced by Hella and Väänänen. Unlike the standard Ehrenfeucht-Fraïssé games which are modeled solely after the behavior of quantifiers, this new game also takes into account the behavior of connectives in logic. We prove the adequacy theorem for this game. We also apply the new game to prove complexity results about infinite binary strings.

Mathematics Subject Classification: 03C75

Keywords and phrases:

Full text arXiv 1212.0108: pdf, ps.