Return to Answer

To prove that this is a metric, consider the following theorem.

Theorem. If the second player can survive for $n$ steps in the $(\Gamma_1,\Gamma_2)$ game, and for $m$ steps in the $(\Gamma_2,\Gamma_3)$ game, then he can survive for $\min(n,m)$ steps in the $(\Gamma_1,\Gamma_3)$ game.

Proof. The idea is simply to combine the strategies for the two games. Fix strategies for the second player in the $(\Gamma_1,\Gamma_2)$ and $(\Gamma_2,\Gamma_3)$ games. In the main $(\Gamma_1,\Gamma_3)$ game, now, let the second player answer any move of the opponent on either side by first copying the move into $\Gamma_2$, and then copying the response of that move into $\Gamma_1$ or $\Gamma_3$, accordingly. In this way, every play of the $(\Gamma_1,\Gamma_3)$ game can be seen as the composition of the strategies for $(\Gamma_1,\Gamma_2)$ and $(\Gamma_2,\Gamma_3)$ games. Since the resulting finite subgraphs $A_1$ and $A_2$ will be isomorphic for $n$ steps and $A_2$,$A_3$ isomorphic for $m$ steps, we will thereby maintain $A_1$ isomorphic to $A_3$ for $\min(n,m)$ steps, as desired. $\Box$

It now follows that the distance from $\Gamma_1$ to $\Gamma_3$ is no larger than the larger of the distances from $\Gamma_1$ to $\Gamma_2$ or from $\Gamma_2$ to $\Gamma_3$, respectively and so we will obey the triangle inequality.

Your games are closely related to Ehrenfeucht–Fraïssé games, but not exactly the same, since in the Ehrenfeucht–Fraïssé games, one keeps track of the moves, and these must be the isomorphism, but the way you described the game, it seems that you allow one to change the isomorphism as play proceeds.

The argument I gave above is the analogue of Lemma 3.2.1(c) in Hodges Model Theory. He shows that Ehrenfeucht–Fraïssé games determine an equivalence relation for length-$\gamma$ play, and this is obtained precisely by copying moves into a supplemental game as I described.

To prove that this is a metric, consider the following theorem.

Theorem. If the second player can survive for $n$ steps in the $(\Gamma_1,\Gamma_2)$ game, and for $m$ steps in the $(\Gamma_2,\Gamma_3)$ game, then he can survive for $\min(n,m)$ steps in the $(\Gamma_1,\Gamma_3)$ game.

Proof. The idea is simply to combine the strategies for the two games. Fix strategies for the second player in the $(\Gamma_1,\Gamma_2)$ and $(\Gamma_2,\Gamma_3)$ games. In the main $(\Gamma_1,\Gamma_3)$ game, now, let the second player answer any move of the opponent on either side by first copying the move into $\Gamma_2$, and then copying the response of that move into $\Gamma_1$ or $\Gamma_3$, accordingly. In this way, every play of the $(\Gamma_1,\Gamma_3)$ game can be seen as the composition of the strategies for $(\Gamma_1,\Gamma_2)$ and $(\Gamma_2,\Gamma_3)$ games. Since the resulting finite subgraphs $A_1$ and $A_2$ will be isomorphic for $n$ steps and $A_2$,$A_3$ isomorphic for $m$ steps, we will thereby maintain $A_1$ isomorphic to $A_3$ for $\min(n,m)$ steps, as desired. $\Box$

It now follows that the distance from $\Gamma_1$ to $\Gamma_3$ is no larger than the larger of the distances from $\Gamma_1$ to $\Gamma_2$ or from $\Gamma_2$ to $\Gamma_3$, respectively and so we will obey the triangle inequality.

Your games are closely related to Ehrenfeucht–Fraïssé games, but not exactly the same, since in the Ehrenfeucht–Fraïssé games, one keeps track of the moves, and these must be the isomorphism, but the way you described the game, it seems that you allow one to change the isomorphism as play proceeds.

But actually, I think you should probably use the Ehrenfeucht–Fraïssé style games, where the isomorphism must be that arising from the play, instead of what you wrote. For example, your claim that $D(\Gamma_1,\Gamma_2)=0$ if and only if $\Gamma_1\cong\Gamma_2$ is not correct in general, unless you use the Ehrenfeucht–Fraïssé style winning conditions. To see this, observe that any two infinite linear orders (coded as graphs) will have distance 0 according to your rules, since any two linear orders of length $n$ are isomorphic, but they need not be Ehrenfeucht–Fraïssé equivalent.

The argument I gave above is the analogue of Lemma 3.2.1(c) in Hodges Model Theory. He shows that Ehrenfeucht–Fraïssé games determine an equivalence relation for length-$\gamma$ play, and this is obtained precisely by copying moves into a supplemental game as I described.

To prove that this is a metric, consider the following theorem.

Theorem. If the second player can survive for $n$ steps in the $(\Gamma_1,\Gamma_2)$ game, and for $m$ steps in the $(\Gamma_2,\Gamma_3)$ game, then he can survive for $\min(n,m)$ steps in the $(\Gamma_1,\Gamma_3)$ game.

Proof. The idea is simply to combine the strategies for the two games. Fix strategies for the second player in the $(\Gamma_1,\Gamma_2)$ and $(\Gamma_2,\Gamma_3)$ games. In the main $(\Gamma_1,\Gamma_3)$ game, now, let the second player answer any move of the opponent on either side by first copying the move into $\Gamma_2$, and then copying the response of that move into $\Gamma_1$ or $\Gamma_3$, accordingly. In this way, every play of the $(\Gamma_1,\Gamma_3)$ game can be seen as the composition of the strategies for $(\Gamma_1,\Gamma_2)$ and $(\Gamma_2,\Gamma_3)$ games. Since the resulting finite subgraphs $A_1$ and $A_2$ will be isomorphic for $n$ steps and $A_2$,$A_3$ isomorphic for $m$ steps, we will thereby maintain $A_1$ isomorphic to $A_3$ for $\min(n,m)$ steps, as desired. $\Box$

It now follows that the distance from $\Gamma_1$ to $\Gamma_3$ is no larger than the shortest distance from $\Gamma_1$ to $\Gamma_2$ or $\Gamma_2$ to $\Gamma_3$, and so we will obey the triangle inequality.

Your games are closely related to Ehrenfeucht–Fraïssé games, but not exactly the same, since in the Ehrenfeucht–Fraïssé games, one keeps track of the moves, and these must be the isomorphism, but the way you described the game, it seems that you allow one to change the isomorphism as play proceeds.

The argument I gave above is the analogue of Lemma 3.2.1(c) in Hodges Model Theory. He shows that Ehrenfeucht–Fraïssé games determine an equivalence relation for length-$\gamma$ play, and this is obtained precisely by copying moves into a supplemental game as I described.

To prove that this is a metric, consider the following theorem.

Theorem. If the second player can survive for $n$ steps in the $(\Gamma_1,\Gamma_2)$ game, and for $m$ steps in the $(\Gamma_2,\Gamma_3)$ game, then he can survive for $\min(n,m)$ steps in the $(\Gamma_1,\Gamma_3)$ game.

Proof. The idea is simply to combine the strategies for the two games. Fix strategies for the second player in the $(\Gamma_1,\Gamma_2)$ and $(\Gamma_2,\Gamma_3)$ games. In the main $(\Gamma_1,\Gamma_3)$ game, now, let the second player answer any move of the opponent on either side by first copying the move into $\Gamma_2$, and then copying the response of that move into $\Gamma_1$ or $\Gamma_3$, accordingly. In this way, every play of the $(\Gamma_1,\Gamma_3)$ game can be seen as the composition of the strategies for $(\Gamma_1,\Gamma_2)$ and $(\Gamma_2,\Gamma_3)$ games. Since the resulting finite subgraphs $A_1$ and $A_2$ will be isomorphic for $n$ steps and $A_2$,$A_3$ isomorphic for $m$ steps, we will thereby maintain $A_1$ isomorphic to $A_3$ for $\min(n,m)$ steps, as desired. $\Box$

It now follows that the distance from $\Gamma_1$ to $\Gamma_3$ is no larger than the larger of the distances from $\Gamma_1$ to $\Gamma_2$ or from $\Gamma_2$ to $\Gamma_3$, respectively and so we will obey the triangle inequality.

Your games are closely related to Ehrenfeucht–Fraïssé games, but not exactly the same, since in the Ehrenfeucht–Fraïssé games, one keeps track of the moves, and these must be the isomorphism, but the way you described the game, it seems that you allow one to change the isomorphism as play proceeds.

The argument I gave above is the analogue of Lemma 3.2.1(c) in Hodges Model Theory. He shows that Ehrenfeucht–Fraïssé games determine an equivalence relation for length-$\gamma$ play, and this is obtained precisely by copying moves into a supplemental game as I described.

To prove that this is a metric, consider the following theorem.

Theorem. If the second player can survive for $n$ steps in the game with $\Gamma_1$, $\Gamma_2$, and for $m$ steps with $\Gamma_2$,$\Gamma_3$, then he can survive for $\min(n,m)$ steps with $\Gamma_1$, $\Gamma_3$.

Proof. The idea is simply to combine the strategies for the two games. Fix strategies for the second player in the $(\Gamma_1,\Gamma_2)$ and $(\Gamma_2,\Gamma_3$ games. In the main $(\Gamma_1,\Gamma_3)$ game, now, let the second player answer any move of the opponent on either side by first copying the move into $\Gamma_2$, and then copying the response of that move into $\Gamma_1$ or $\Gamma_3$, accordingly. In this way, every play of the $(\Gamma_1,\Gamma_3)$ game can be seen as the composition of the strategies for $(\Gamma_1,\Gamma_2)$ and $(\Gamma_2,\Gamma_3)$ games. Since the resulting finite subgraphs $A_1$ and $A_2$ will be isomorphic for $n$ steps and $A_2$,$A_3$ isomorphic for $m$ steps, we will thereby maintain $A_1$ isomorphic to $A_3$ for $\min(n,m)$ steps, as desired. $\Box$

It now follows that the distance from $\Gamma_1$ to $\Gamma_3$ is no larger than the shortest distance from $\Gamma_1$ to $\Gamma_2$ or $\Gamma_2$ to $\Gamma_3$, and so we will obey the triangle inequality.

Your games are closely related to Ehrenfeucht–Fraïssé games, but not exactly the same, since in the Ehrenfeucht–Fraïssé games, one keeps track of the moves, and these must be the isomorphism, but the way you described the game, it seems that you allow one to change the isomorphism as play proceeds.

The argument I gave above is the analogue of Lemma 3.2.1(c) in Hodges Model Theory. He shows that Ehrenfeucht–Fraïssé games determine an equivalence relation for length-$\gamma$ play, and this is obtained precisely by copying moves into a supplemental game as I described.

To prove that this is a metric, consider the following theorem.

Theorem. If the second player can survive for $n$ steps in the $(\Gamma_1,\Gamma_2)$ game, and for $m$ steps in the $(\Gamma_2,\Gamma_3)$ game, then he can survive for $\min(n,m)$ steps in the $(\Gamma_1,\Gamma_3)$ game.

Proof. The idea is simply to combine the strategies for the two games. Fix strategies for the second player in the $(\Gamma_1,\Gamma_2)$ and $(\Gamma_2,\Gamma_3)$ games. In the main $(\Gamma_1,\Gamma_3)$ game, now, let the second player answer any move of the opponent on either side by first copying the move into $\Gamma_2$, and then copying the response of that move into $\Gamma_1$ or $\Gamma_3$, accordingly. In this way, every play of the $(\Gamma_1,\Gamma_3)$ game can be seen as the composition of the strategies for $(\Gamma_1,\Gamma_2)$ and $(\Gamma_2,\Gamma_3)$ games. Since the resulting finite subgraphs $A_1$ and $A_2$ will be isomorphic for $n$ steps and $A_2$,$A_3$ isomorphic for $m$ steps, we will thereby maintain $A_1$ isomorphic to $A_3$ for $\min(n,m)$ steps, as desired. $\Box$

It now follows that the distance from $\Gamma_1$ to $\Gamma_3$ is no larger than the shortest distance from $\Gamma_1$ to $\Gamma_2$ or $\Gamma_2$ to $\Gamma_3$, and so we will obey the triangle inequality.

Your games are closely related to Ehrenfeucht–Fraïssé games, but not exactly the same, since in the Ehrenfeucht–Fraïssé games, one keeps track of the moves, and these must be the isomorphism, but the way you described the game, it seems that you allow one to change the isomorphism as play proceeds.

The argument I gave above is the analogue of Lemma 3.2.1(c) in Hodges Model Theory. He shows that Ehrenfeucht–Fraïssé games determine an equivalence relation for length-$\gamma$ play, and this is obtained precisely by copying moves into a supplemental game as I described.