有限模型论

有限模型论 (FMT) 是模型论 (MT) 的一个子领域。MT 是数理逻辑的一个分支，它处理形式语言 (语法) 及其解释 (语义) 之间的关系。FMT 是将 MT 限制在有限结构上，例如有限图或字符串。由于许多 MT 的中心定理在限制到有限结构时不成立，因此 FMT 在方法和应用领域方面与 MT 大不相同。FMT 已成为计算机科学中的一种“非常有效的”工具，例如在数据库理论、模型检验或用于获得对计算复杂性的新视角中。

这里介绍了 FMT 的三个主要领域：语言的表达能力、描述性复杂性和随机结构。但首先，在 一阶语言的层面上介绍了对所有领域都至关重要的结果。

基础知识

为什么? (动机)

它是什么? (定义和背景)

为什么它很特殊? (... 与 '普通' 模型论相比)

它是关于什么的? (研究的典型逻辑和结构)

需要什么? (预备知识)

从哪里开始? (基本概念)

针对 FO 的 Ehrenfeucht-Fraisse 游戏

问题 (属性的可表达性)

想法 I (Fraisse 定理)

想法 II (Ehrenfeucht 游戏)

工具 (Ehrenfeucht-Fraisse 方法)

一些实用程序 (局部性)

一些解决方案 (针对某些结构)

复杂性？

语言的表达能力

典型问题：给定一个有限图，是否可以用一阶语言表达无环性的属性？

随机结构

这个 数学 模块是 残根。你可以通过 帮助 维基教科书 扩展它。