Ehrenfeucht Fraisse Games Extended to Higher Order Logic
Ehrenfeucht-Fraisse games are a technique in mathematical logic used to compare two structures and determine whether they are elementarily equivalent. The games were originally defined for first-order logic, where quantification is restricted to variables ranging over the elements of the structure. However, the games can be extended to higher-order logic, which allows quantification over relations and functions as well as elements.
In the higher-order version of Ehrenfeucht-Fraisse games, there are two players, called Spoiler and Duplicator. The game is played on two structures, A and B, and proceeds as follows:
- Spoiler selects an element a from A or a relation or function R of any arity and provides it to Duplicator.
- Duplicator selects an element b from B or a relation or function S of the same arity as R and provides it to Spoiler.
- The players switch roles, and Spoiler selects an element b from B or a relation or function S of any arity and provides it to Duplicator.
- Duplicator selects an element a from A or a relation or function R of the same arity as S and provides it to Spoiler.
The game continues for a finite number of rounds, and at the end of the game, the structures are compared based on the information exchanged during the game. The structures are said to be elementarily equivalent if Duplicator has a winning strategy, meaning that they can match the elements and relations of A to those of B in a way that preserves the truth of all first-order and higher-order formulas.
In the higher-order version of the game, the formulas used to determine the winner can include quantifiers over relations and functions as well as elements, allowing for more complex comparisons between the structures. The extension of the game to higher-order logic makes it a powerful tool for comparing and analyzing complex mathematical structures.