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.
翻译:我们调查了四种模型理论塔米特性,这些模型理论在最小固定点逻辑背景下对一个有有限结构的大家庭进行了研究。我们发现,这些特性中的每一种都只依赖于基本(即一阶)限制理论,我们完全确定其中的必然因素。与关于任意结构的第一阶逻辑的背景相反,在这一背景下,顺序财产和独立财产是等同的。麦考姆推断,在熟练性失效时,最起码固定点的可定义性会倒塌到第一级可定义性。麦考姆的推测一般是假的。然而,我们表明,McColom的推测对于任何有限结构的大家庭来说都是真实的,其极限理论是模型理论。