有限模型論/預備知識

一階邏輯 (FO)

維基百科在 一階邏輯 中有相關資訊

我們在這裡只對 FO 做一個非常粗略的總結。可以在 FO 中找到介紹。

語法

語法只是關於符號序列。FO 的字母表包括

變數 $x_{0},x_{1},x_{2},...$
邏輯連線詞： $\neg$ , $\land$
量詞： $\exists$
等式： $\equiv$
括號：), (
n 元關係符號，對於沒有或多個 n>0，例如 R(., .)
常數符號（沒有或多個）

括號的處理方式是“通常”的，在此不再做進一步的正式描述。

對於給定的符號集 S，變數和常數符號被稱為 S-項。

S-表示式透過以下規則的多次應用得到

$t_{1}\equiv t_{2}$ 是一個表示式
$Rt_{1}...t_{n}$ 是一個表示式，對於 n 元關係符號 R
$\neg \varphi ,\varphi _{1}\land \varphi _{2}$ 是表示式
$\exists _{x}\varphi$ 是一個表示式

其中 $t_{.}$ 是一個項， $\varphi _{.}$ 是一個表示式。

因此，可以定義 OR、IMPLICATION、EQUIVALENCE 等的附加連線詞，以及 FOR ALL 量詞。

語義

語義透過三個步驟為語言新增意義

首先，它定義了邏輯符號（連線詞和量詞）的含義（這在 FO 中始終成立），
其次，它將關係符號和常數符號對映到給定實體集上的實際關係和常數（這通常由主題定義，例如分析或統計），以及
第三，它將自由變數（未繫結到量詞）對映到實體（通常由問題定義，例如求解方程）。

首先，我們假設邏輯符號 $\neg ,\land ,...,\exists$ 具有通常的含義。

其次，S-結構是 (A, a) 的一對，

一個非空集 A，即宇宙，和
從 S 到 a 的對映，使得
- 每個 n 元關係符號都被對映到 A 上的 n 元關係，並且
- 每個常數符號都被對映到 A 的一個元素

一個解釋是，一對 $({\mathfrak {A}},\beta )$ ，其中 ${\mathfrak {A}}$ = (A, a) 是一個 S 結構，並且 $\beta$ 是一個將所有自由變數對映到 A 中的一個元素的對映。

如果一個解釋是對一組 S 表示式 $\Phi$ （ ${\mathfrak {I}}\vDash \Phi$ ）的 **模型**，當且僅當以下所有條件成立：

${\mathfrak {I}}(t_{1})={\mathfrak {I}}(t_{1})$ ，對於 ${\mathfrak {I}}\vDash t_{1}\equiv t_{2}$
$R^{n}{\mathfrak {I}}(t_{1}),...,{\mathfrak {I}}(t_{n})$ ，對於 ${\mathfrak {I}}\vDash Rt_{1}...t_{n}$
不 ${\mathfrak {I}}\vDash \varphi$ ，對於 ${\mathfrak {I}}\vDash \neg \varphi$
${\mathfrak {I}}\vDash \varphi _{0})$ 並且 ${\mathfrak {I}}\vDash \varphi _{1})$ ，對於 ${\mathfrak {I}}\vDash \varphi _{0}\land \varphi _{1}$
存在一個 $a\in A$ 使得 ${\mathfrak {I}}\vDash \varphi (a)$ ，對於 ${\mathfrak {I}}\vDash \exists _{x}\varphi (x)$

遊戲

維基百科在 博弈論 中有相關資訊

一個遊戲由以下內容描述：

它的玩家（>1）
它的規則，即誰在何時玩以及允許做什麼
它的可能結果和收益。

更正式地說，它是一個元組 (P, T, m, u)，其中

P（玩家）是一個集合，其中 |P| = n > 1
T 是一個在節點集上的圖，形成一個分類法，即 T 是一棵具有指定根節點的樹。葉子被稱為終結節點 T，所有其他節點都是決策節點 D。這描述了可能的移動序列。
m 是從 D 到 P 的對映，它表示在哪個點誰應該移動。
u 是一組對映 u_i（每個玩家 i 一個），從 T 到有序集合 U，它給出每個玩家在每個終結節點的收益。

我們在這裡以及在下面假設每個玩家都擁有完美資訊（因此以上定義是不完整的），即所有玩家到目前為止的所有移動，我們不考慮隨機移動。關於規則和玩家的常識是預設假設的。以上稱為博弈的擴充套件形式表示。其他形式，如規範形式表示，對這個做了簡化假設（例如，關於資訊）並使用策略的概念而不是單一移動。

注意不同的移動會導致相同的“位置”，即一個位置可以在一個博弈樹中被表示多次。並且，相同的收益對於不同的玩家可以有不同的意義。

結構上的同構

同態

同構

來回方法

由於以下原因，計算一個集合可能會變得很混亂

以非自然順序計算事物
多次計算元素

...

方法

固定基礎集的列舉（無重複）

{\begin{matrix}A&=&\{\,a_{1},a_{2},a_{3},\dots \,\},\\\\B&=&\{\,b_{1},b_{2},b_{3},\dots \,\}.\end{matrix}}

現在我們構造一個 A 和 B 之間的一一對應關係，它是嚴格遞增的。最初 A 中的成員沒有與 B 中的任何成員配對。

(1) 令 i 為最小的索引，使得 a_i 還沒有與 B 中的任何成員配對。令 j 為最小的索引，使得 b_j 還沒有與 A 中的任何成員配對並且 a_i 可以與 b_j 配對，符合配對必須嚴格遞增的要求。將 a_i 與 b_j 配對。

(2) 令 j 為最小的索引，使得 b_j 還沒有與 A 中的任何成員配對。令 i 為最小的索引，使得 a_i 還沒有與 B 中的任何成員配對並且 b_j 可以與 a_i 配對，符合配對必須嚴格遞增的要求。將 b_j 與 a_i 配對。

(3) 返回步驟(1)。

仍然需要檢查步驟(1)和(2)中要求的選擇是否可以根據要求實際進行。以步驟(1)為例

如果 A 中已經有與 B 中的 b_p 和 b_q 分別對應的 a_p 和 a_q，使得 $a_{p}<a_{i}<a_{q}$ 並且 $b_{p}<b_{q}$ ，我們使用密度在 b_p 和 b_q 之間選擇 b_j。否則，我們使用 B 既沒有最大值也沒有最小值的事實來選擇合適的較大或較小元素。在步驟(2)中做出的選擇是雙重可能的。最後，構造在可數的許多步驟之後結束，因為 A 和 B是可數無窮的。注意我們必須使用所有先決條件。

如果我們只迭代步驟(1)，而不是來回迭代，那麼生成的配對將無法雙射。