有限模型论/逻辑与结构

FMT 研究有限结构上的逻辑。这里概述了这些研究对象中最重要的部分。

逻辑

这里定义并在整本书中使用的逻辑始终是关系逻辑，即没有函数符号，并且是有限的，即具有有限的宇宙，恕不另行通知。

FO 的片段

后续限制可以在其他逻辑（如 SO）中类似地找到。

• MFO ...
• ESO 和 USO ...
• FOⁿ ...

二阶逻辑 (SO)

二阶逻辑 通过添加变量和量词来扩展一阶逻辑，这些变量和量词在个体集合上取值。例如，二阶句子 $\forall S\,\forall x\,(x\in S\lor x\not \in S)$ 表示对于每个个体集 *S* 和每个个体 *x*，要么 *x* 在 *S* 中，要么不在。也就是说，规则通过以下内容扩展

• 如果 X 是一个 n 元关系变量，而 t₁ ... t_n 是项，那么 X t₁ ... t_n 是一个公式
• 如果 φ 是一个公式，而 X 是一个关系变量，那么 $\exists _{X}\varphi$ 是一个公式

二阶逻辑的片段

• 片段一元二阶逻辑 (MSO) 仅允许一元关系变量（“集合变量”）。
• 存在片段 (ESO) 是没有普遍二阶量词的二阶逻辑，并且没有二阶量词的否定出现。
• USO ...

无穷逻辑

概念

目的是通过一个无限析取元素在公式集 ψ （无穷逻辑的公式）上扩展 FO

$\bigvee \psi$

因此可以定义以下无穷逻辑

• $L_{\infty \varpi }$ 其中 ψ 是一个任意公式集，例如不可数
• $L_{\varpi \varpi }$ 其中 ψ 是一个可数公式集
• $L_{\infty \varpi }^{n}$ ...

定义

语法 ...

语义 ...