A New Ehrenfeucht–Fraïssé Game for Dependence Logic
Joni Puljujärvi, Jouko Väänänen · 2026
Read A New Ehrenfeucht–Fraïssé Game for Dependence Logic by Joni Puljujärvi, Jouko Väänänen (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-00812.txt.
Introduction
Puljujärvi and Väänänen design a new game for dependence logic in this 2026 paper. In logic, games can test if two structures count as the same. The Ehrenfeucht-Fraïssé game does this for first-order logic, with moves of single elements. A past game for dependence logic forced moves made of whole teams. Teams can be huge, so each move got unwieldy.
Their new game returns to single-element moves. One fresh trait sets it apart. A player may declare that a move rests only on certain past moves. That claim marks the move as free of the rest. The pair prove the game captures elementary equivalence in dependence logic. Two structures tie in the game if and only if no sentence of the logic splits them. The result gives logicians a leaner tool for a logic built to state how values depend on each other.
Catalog record
| CREATOR | Joni Puljujärvi, Jouko Väänänen |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 54 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.00812
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A New Ehrenfeucht–Fraïssé Game for Dependence Logic Joni Puljujärvi, Jouko Väänänen Abstract We define a new Ehrenfeucht–Fraïssé game for dependence logic. The previously known rendition of such a game was based on moves that are teams. Since teams can be massive, making team moves may be quite complicated. To remedy this, our new Ehrenfeucht–Fraïssé game for dependence logic has only moves that consist of single elements, as in the classical Ehrenfeucht–Fraïssé game of first order logic. A new feature of the game is that a player can declare that their move is made on the basis of certain previous moves only and thereby in a sense independent of other moves. We show that our game characterizes elementary equivalence in dependence logic. 1 Introduction The Ehrenfeucht–Fraïssé game [ 5 ] is a fundamental tool of first order logic. We define the corresponding game for dependence logic [ 15 ] —an extension of first order logic by dependence atoms \mathop{=}(x,y) , with the intuitive meaning “ y is completely determined by x ”—and show that the game characterizes elementary equivalence in this logic. Previously, versions of the Ehrenfeucht–Fraïssé game have been defined for a variety of extensions and fragments of first order logic, in particular infinitary logics ( [ 9 ] , [ 2 ] , [ 3 ] ), second order logic ( [ 13 ] ), logics with generalized quantifiers ( [ 16 ] , [ 12 ] , [ 1 ] , [ 17 ] , [ 10 ] ) and logics with a fixed finite number of variables ( [ 8 ] , [ 14 ] , [ 11 ] ). Moreover, one version of the Ehrenfeucht–Fraïssé game for the very dependence logic that is our subject in this paper was already defined in [ 15 ] . However, that game was “second order” in the sense that moves were sets of assignments, or teams, as they are called. Similarly, there is a “second-order” game for inclusion logic [ 6 ] , as well as one for inquisitive logic [ 7 ] . Our new game is “first order” in the sense that moves are elements as in the original Ehrenfeucht–Fraïssé game of [ 5 ] . We show that our game captures dependence logic in the same way as the original Ehrenfeucht–Fraïssé game captures first order logic. The ordinary Ehrenfeucht–Fraïssé game is a tool for comparing two models. The game is a perfect-information zero-sum game with two players, \mathrm{\mathbf{I}} and \mathrm{\mathbf{II}} . Winning strategies of player \mathrm{\mathbf{II}} are witnesses to levels of similarity (or isomorphism) of the models, manifested by elementary equivalence up to a quantifier rank. Winning strategies of player \mathrm{\mathbf{I}} are witnesses to a difference between the models, manifested by a first-order sentence which is true in one model but not in the other. It is possible to think of the game as a syntax-free approach to comparing the models. We can use the game to express inability to separate the models with a first-order sentence of a certain size. Equivalently, we can use the game to say that one of the models has a first-order property that the other model does not have. In this analysis, the concept of “first order” can be varied by modifying the game. In using the Ehrenfeucht–Fraïssé game approach for the logical analysis of dependence, something we aim to do in this paper, we have two models and we want to analyze whether they have the same dependence-type properties. For example, there may be a definable binary relation which in one model contains a one-one function but in the other model perhaps not. Or there may be two definable unary relations P and Q such that in one model |P|\leq|Q| and in the other model perhaps |P|>|Q| . Or there may be a definable linear order which is a well-order in one model but perhaps not in the other. Or there may be a definable graph relation which is 3-colourable in one model but perhaps not in the other. How does the Ehrenfeucht–Fraïssé game capture such differences? A possible solution is to use a second order Ehrenfeucht–Fraïssé game in which the players play relations rather than elements, or teams as in [ 15 ] . An interesting case is the game for the Henkin (i.e. partially ordered) quantifier, where moves involve choosing a function which is then thrown away [ 12 ] . So positions in that game are first order even if moves are second order. This is relevant from the point of view of dependence logic because sentences of the latter have the same expressive power as sentences which start with a partially ordered quantifier prefix followed by a first order formula. However, in this paper we want to stay on the first-order level and focus on an Ehrenfeucht–Fraïssé game in which the moves are elements of the models, not teams or functions. Admittedly, it is not absolutely clear that there is a real difference, as we impose second order conditions on winning strategies. One important feature of dependence logic that comes to play a role is the lack of negation, except in front of first-order atomic formulas. Therefore, we aim at defining a variant of the Ehrenfeucht–Fraïssé game for \mathfrak{A} and \mathfrak{B} such that if player \mathrm{\mathbf{II}} has a winning strategy, then \mathfrak{A}\models\phi implies \mathfrak{B}\models\phi for all dependence logic sentences \phi . By stating the same also in converse order, i.e. existence of a winning strategy for \mathrm{\mathbf{II}} in the game for \mathfrak{B} and \mathfrak{A} , we obtain a criterion for elementary equivalence in the usual sense. Let us consider, as an example, two graphs \mathfrak{A} and \mathfrak{B} . Let us assume that \mathfrak{A} is 2-colourable but \mathfrak{B} is not. We assume the possibility to refer to two colours in both graphs and the question is whether the vertices can be coloured with these colours in a way that is required by the concept of 2-colouring. 1 1 1 One way to do this is to add a constant symbol for each colour. Another option is to simply play two additional rounds of the game in the beginning and treat the two first moves of each player as the two colours in each graph. Then a colouring of either of the graphs will correspond to a function on the graph that maps each element to one of these two distinguished elements. Thus \mathfrak{A} has the dependence-type property that we can assign one of two colours to each vertex in such a way that neighboring vertices get different colour. How would player \mathrm{\mathbf{I}} take advantage of this colouring f in \mathfrak{A} and the lack of any 2-colouring in \mathfrak{B} ? An obvious idea is the following: (1) \mathrm{\mathbf{I}} picks x_{0} in \mathfrak{B} asking \mathrm{\mathbf{II}} to give its colour. (2) \mathrm{\mathbf{II}} retaliates by picking y_{0} in \mathfrak{A} and asking \mathrm{\mathbf{I}} to give first its colour. (3) \mathrm{\mathbf{I}} gives a colour x_{1} for y_{0} , making the commitment that he chose the colour on the basis of knowing y_{0} only . (4) Now \mathrm{\mathbf{II}} gives some colour y_{1} for x_{0} , making the commitment that she chose the colour on the basis of knowing x_{0} only . (5) \mathrm{\mathbf{I}}