有限模型理论/基础

查询

概念

想象一个客户数据库软件产品，不同的公司使用它来管理他们的客户，也就是说，他们都使用自己的安装了同一个数据库产品的软件，并且当然也拥有他们自己的客户数据。现在，人们可以对这样的数据库进行查询，例如“在非洲的客户”，这将返回一个包含所有在非洲的客户的列表。虽然数据库的内容不同，但查询在所有数据库中都是定义的 - 假设它们拥有客户、国家和“在”关系的定义。当然，它可能会返回不同的结果。

类似地，人们可以定义在结构上进行查询，以返回宇宙中的一组元素。这里，一组符号 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-类型

假设...