有限模型理論/基礎

查詢

概念

想象一個客戶資料庫軟體產品，不同的公司使用它來管理他們的客戶，也就是說，他們都使用自己的安裝了同一個資料庫產品的軟體，並且當然也擁有他們自己的客戶資料。現在，人們可以對這樣的資料庫進行查詢，例如“在非洲的客戶”，這將返回一個包含所有在非洲的客戶的列表。雖然資料庫的內容不同，但查詢在所有資料庫中都是定義的 - 假設它們擁有客戶、國家和“在”關係的定義。當然，它可能會返回不同的結果。

類似地，人們可以定義在結構上進行查詢，以返回宇宙中的一組元素。這裡，一組符號 S 對應於資料庫產品，即裸資料庫結構，具體的 S-結構對應於資料庫例項，而解釋對應於資料庫條目。例如，$\forall _{x}xRy$ 將檢索 y 的所有可能的值。一般來說，對於具有 n 個自由變數的公式，我們將得到一組 n 元組（可能為空）。如果查詢是一個句子（沒有自由變數），我們將得到“是”或“否”作為結果，具體取決於查詢在結構中是否有模型。在上面的資料庫中，這可以對應於“Kay Ubuntu 是在非洲的客戶”。

定義

令 ${\mathfrak {A}}$ 是一個具有宇宙 A 的 S-結構，m 是一個非負整數，Q 是從 S-結構到 A^m 的子集集合的對映，使得每個 ${\mathfrak {A}}$ 都對映到 A^m 的一個子集。

如果 Q 在同構下是封閉的，則稱 Q 是 S-結構上的 m 元查詢，

其中在同構下封閉（或保留）是指：如果 ${\mathfrak {A}}\cong {\mathfrak {B}}$ 透過同構 $f$，則 $f(Q({\mathfrak {A}}))=Q({\mathfrak {B}})$.

備註

• 0 元 Q 也稱為布林查詢。在這種情況下，Q 對映到 A⁰，即 0 元組或空集。前者結果也稱為 TRUE，後者稱為 FALSE。
• 對於布林查詢 Q，可以定義 S-結構的子集 C 為：${\mathfrak {A}}\in C$ 當且僅當 $Q({\mathfrak {A}})=true$
• 封閉性條件確保只有結構的“形狀”才是查詢，也就是說，宇宙由什麼組成並不重要，只要它們以相同的方式相關。

示例

簡單

取 S = {<}。我們查詢“所有沒有比它更小的元素的元素”。對於 {10, 11, 12} 的宇宙，這將得到結果 {(10)}（一組 1 元組）。查詢“所有有比它更小的元素的元素”將得到 {(11), (12)}。查詢“所有直接後繼的元素”將得到 {(10, 11), (11, 12)}（一組 2 元組）。查詢“存在一個最大的元素”將得到 {()}（0 元元素），而查詢“不存在最大的元素”將得到 {}（false）。

反例？

可定義性

一方面，我們擁有或多或少“複雜”的查詢。只需想象一個簡單的資料庫查詢，用於查詢所有名為“Ubuntu”的客戶，與一個涵蓋許多屬性和關係的查詢進行比較。另一方面，我們擁有不同表達能力的語言，例如 FO 和 MFO（單調一階邏輯）。因此，人們可以問，一種語言的表達能力是否足夠強大，足以表達（定義）一個特定的查詢。

結構類

令 C 為有限結構的類，L 為邏輯。如果存在 L 中的句子 φ，使得 C 是 φ 的所有有限模型的集合，則稱 C 在邏輯 L 中是可定義的。

查詢

令 Q 為查詢，L 為邏輯

如果存在 L 中的公式 φ(x₁,..., x_m)，使得對於所有 ${\mathfrak {A}}$ $Q({\mathfrak {A}})$ 中的所有元素都是 φ 上的賦值，使得 ${\mathfrak {A}}\vDash \varphi$，則稱 Q 在 L 中是可定義的。

備註

• 因此，布林查詢對應於句子。

示例

簡單

在有限圖上，查詢“存在一個元素與所有其他元素相鄰”可以用 FO 表示為 $\exists _{x}\forall _{y}xRy$。語言甚至可以進一步限制，例如，每個公式只允許兩個變數（這大約是邏輯 FO² 的作用）。

應用

資料庫查詢語言 SQL 包含許多擴充套件，以增強其功能。

部分同構

定義

結構之間的部分同構

令 ${\mathfrak {A}}$ 和 ${\mathfrak {B}}$ 是關係 S-結構，p 是一個對映。如果滿足以下所有條件，則稱 p 是從 ${\mathfrak {A}}$ 到 ${\mathfrak {B}}$ 的部分同構：

• dom(p) $\subseteq$ A 且 codom(p) $\subseteq$ B
• p 是單射的
• 對於 S 中的每個常數符號 c 和每個 a：a = c^A 當且僅當 p(a) = c^B
• 對於 S 中的每個 n 元關係符號 R 和 $a_{1}$,..., $a_{n}$: $R^{\mathfrak {A}}$ $a_{1}$... $a_{n}$ 當且僅當 $R^{\mathfrak {B}}$ $p(a_{1})$... $p(a_{n})$

其中 $a_{*}$ $\in$ A, $b_{*}$ $\in$ B.

備註

• 也就是說，在 ${\mathfrak {A}}$ 和 ${\mathfrak {B}}$ 上的區域性同構是透過選擇 dom(p) 和 codom(p) 以及分別“修剪”常數和關係獲得的子結構上的（普通）同構。
• 區域性同態...

示例

• 設 S ={<} 在 A ={1, 2, 3} 和 B ={3, 4, 5, 6} 上以自然的方式定義。那麼，$p_{1}$ 其中 1->3 和 2->4 是一個區域性同構（因為 1 < 2 並且 p(1) < p(2)）以及 $p_{3}$ 其中 2->3 和 3->6 以及 $p_{2}$ 其中 1->6。然而，$p_{4}$ 其中 1->6 和 2->3（因為 1 < 2 但 p(1) < p(2) 不成立）以及 $p_{5}$ 其中 2->5 和 3->5 都不是區域性同構。
• 設 S ={R}，其中 $R^{\mathfrak {A}}=\{(1,2),(2,3),(3,4),(4,1)\}$（一個“正方形”）和 $R^{\mathfrak {B}}=\{(1,2),(1,3),(3,4),(3,5)\}$（一個“二叉樹”）。A ={1,..., 4} 和 B ={1,..., 5}。然後 p: {1, 2, 3} -> {1, 3, 4}，其中 1->1，2->3，3->4，是從 ${\mathfrak {A}}$ 到 ${\mathfrak {B}}$ 的一個區域性同構，因為 {(1, 2), (2, 3)} 變成了 {(1, 3), (3, 4)}。請注意，如果 $R_{\mathfrak {B}}$ 還包含例如 (4, 1)，那麼 p 就不是一個區域性同構。
• 設 S ={<} 在 A ={1, 2, 3, 4, 5, 6} 和 B ={1, 3, 5} 上以自然方式定義。然後 p，其中 2->3 和 4->5，定義了一個區域性同構。請注意，例如 $\exists _{x}(x<4\land 2<x)$ 在 ${\mathfrak {A}}$ 上成立，但 $\exists _{x}(x<p(4)\land p(2)<x)$ 在 ${\mathfrak {B}}$ 上不成立。也就是說，一般來說，含有量詞的語句的有效性不會被保留。因此，為了保留這種有效性，我們需要比區域性同構更強的概念。這正是 Ehrenfeucht 博弈將要為我們提供的。

定義

區域性同構結構

對於 p 的某個域大小（稱為 n），可以將兩個結構稱為區域性同構。這可以在弱意義上進行，即存在一個 n 元區域性同構；或者在強意義上進行，即對於 A 的每個 n-基本子集，都存在一個區域性同構。後者將在後面變得很重要。

量詞秩

定義 : FO 公式的量詞秩

設 φ 為一個 FO 公式。φ 的量詞秩，記為 qr(φ)，定義如下：

• $qr(\varphi )=0$，如果 φ 是原子公式。
• $qr(\varphi _{1}\land \varphi _{2})=qr(\varphi _{1}\lor \varphi _{2})=max(qr(\varphi _{1}),qr(\varphi _{2}))$.
• $qr(\lnot \varphi )=qr(\varphi )$.
• $qr(\exists _{x}\varphi )=qr(\varphi )+1$.

備註

• 我們用 FO[n] 表示所有量詞秩（quantifier rank）不大於 n 的一階公式 φ 的集合，即 $qr(\varphi )\leq n$.
• 請注意，在預解正規化（prenex normal form）中，公式 φ 的量詞秩恰好等於 φ 中出現的量詞數量。

示例

• 句子 $\forall _{x}(\exists _{y}((\lnot x=y)\land xRy))\land (\exists _{y}((\lnot x=z)\land zRx))$ 的量詞秩為 2。
• 預解正規化中的句子 $\forall _{x}\exists _{y}\exists _{y}((\lnot x=y)\land xRy)\land ((\lnot x=z)\land zRx)$ 的量詞秩為 3。請注意，它與上面的句子是等價的。

型別

定義

秩 k m-型別

假設...