有限模型論/邏輯與結構

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}$ ...

定義

語法 ...

語義 ...