有限模型論/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 獲勝
• 資訊：假設玩傢俱有完全資訊