一句话：研究最小不动点逻辑的四种模型论驯顺性，证明其仅依赖一阶极限理论，并在驯顺极限理论下证实 McColm 猜想。
本文在有限结构族上研究最小不动点逻辑（LFP）的四种模型论驯顺性。作者证明，这些性质都只取决于该结构族的一阶（初等）极限理论，并完全刻画了它们之间成立的蕴含关系。与任意结构上的一阶逻辑不同，在该设定下序性质与独立性质等价。McColm 猜想断言 LFP 可定义性坍缩为一阶可定义性当且仅当 proficiency 失效；该猜想一般情形已知为假。本文证明，对于极限理论在模型论意义上驯顺的任意有限结构族，McColm 猜想成立。
We investigate four model-theoretic tameness properties in the context of least fixed-point logic over a family of finite structures. We find that each of these properties depends only on the elementary (i.e., first-order) limit theory, and we completely determine the valid entailments among them. In contrast to the context of first-order logic on arbitrary structures, the order property and independence property are equivalent in this setting. McColm conjectured that least fixed-point definability collapses to first-order definability exactly when proficiency fails. McColm's conjecture is known to be false in general. However, we show that McColm's conjecture is true for any family of finite structures whose limit theory is model-theoretically tame.
@article{paperbot1347,
title = {Tameness in least fixed-point logic and McColm's conjecture},
author = {Siddharth Bhaskar and Alex Kruckman},
journal = {Logical Methods in Computer Science},
volume = {Volume 17, Issue 1},
year = {2021},
doi = {10.23638/lmcs-17(1:2)2021}
}