有限模型理论/动机

我们先给出一个简单的 FMT 应用示例，然后给出一些典型的示例。

FMT 无处不在

一些简单的示例，展示了 FMT 所关注的问题是多么基础。

• ...

数据库

FMT 的一个典型应用领域是数据库理论。

• 考虑一个公司数据库，其中包含所有经理以及他们之间的“是上级”关系。在一个合适的层次结构中，数据库不应该包含循环，即经理不能是其上级的上级。查询这个关系对应于检查图是否具有环。如上所述，这在 一阶逻辑 (FO) 中无法实现。
• 假设两位经理想知道他们中是否有一个人比另一个人更有权势。他们需要查询数据库以确定他们的下属数量是否相等，即下属集的基数（例如，直接和间接）是否相等。这在 FO 中无法实现（“FO 无法计数”）。这就是 SQL 通过计数函数扩展的原因。
• 考虑一个机场和它们之间连接航班的数据库 $F$，其中 $F(x,y)$ 表示从机场 $x$ 到机场 $y$ 有直达航班。我们可以编写一个零阶查询，查询从机场 $a$ 到机场 $b$ 的直接可达性，如下所示：

$q_{0}(a,b)=F(a,b)$.

现在，为了查询中转一次的连接，我们编写

$q_{1}(a,b)=\exists _{c}F(a,c)\land F(c,b)$ 并得到 $Q_{1}(a,b)=q_{0}(a,b)\lor q_{1}(a,b)$

对于零次或一次中转的连接。因此，为了将其扩展到可达性（无论经过多少次中转），我们必须编写

$Q=\bigvee _{k\in \mathbb {N} }q_{k}$

它不是 FO 表达式。因此，对于最多到某个 k 的有限可达性，FO 可以很好地工作，但对于图论中出现的可达性，FO 就无法处理。实际上，可以证明可达性无法在 FO 中查询。