有限模型论/FO EFG

逻辑与游戏

游戏与逻辑量词之间的联系...

简单游戏

1. S 首先从一侧或两侧选择所有 n，然后 D 选择所有
2. 与 1. 中的一样，对于每个 i = 1 ... n，其中第 i 次选择必须包含第 i-1 次选择。

定义

埃伦费斯特-弗拉伊斯游戏 (EFG)

令 ${\mathfrak {A}}$ 和 ${\mathfrak {B}}$ 是有限关系结构，具有相同的关系列符号集，n 是一个固定的自然数。

一个游戏被称为埃伦费斯特-弗拉伊斯游戏，当且仅当它以以下方式构成

• 2 个玩家：破坏者 S 和复制者 D
• 游戏树
  • 根：一对空序列
  • 分支
    • S 的移动：S 选择 A 或 B 中尚未选择的任何一个元素（在第一次移动中，后者不相关）
    • D 的移动：D 选择剩余集合中尚未选择的任何一个元素，即如果 S 从 A 中选择，D 必须从 B 中选择，如果 S 从 B 中选择，D 必须从 A 中选择。
  • 终止器：当且仅当 α 和 β 的大小为 n 时，游戏结束。
• 回合：移动交替进行，S 首先移动。
• 收益：当且仅当最终位置通过为所有 i 映射 α 和 β 的第 i 个元素来定义一个局部同构时，D 获胜。否则 S 获胜
• 信息：假设玩家具有完全信息