Tameness in least fixed-point logic and mccolm’s conjecture

Research output: Contribution to journalJournal articleResearchpeer-review

Documents

  • Siddharth Bhaskar
  • Alex Kruckman

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.

Original languageEnglish
Article number2
JournalLogical Methods in Computer Science
Volume17
Issue number1
Pages (from-to)2:1-2:16
ISSN1860-5974
DOIs
Publication statusPublished - 2021

Bibliographical note

Publisher Copyright:
© Siddharth Bhaskar and Alex Kruckman.

    Research areas

  • Finite model theory, Inductive definability, Least fixed-point logic, Model-theoretic dividing lines

ID: 269503322