Premium
An Ehrenfeucht‐Fraïssé game for L ω 1 ω
Author(s) -
Väänänen Jouko,
Wang Tong
Publication year - 2013
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.201200104
Subject(s) - mathematics , discrete mathematics , binary number , mathematical economics , arithmetic
In this paper we develop an Ehrenfeucht‐Fraïssé game for L ω 1 ω . 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.