Tameness in least fixed-point logic and mccolm’s conjecture
Research output: Contribution to journal › Journal article › Research › peer-review
Documents
- Tameness in least fixed-point logic and mccolm’s conjecture
Final published version, 352 KB, PDF document
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 language | English |
---|---|
Article number | 2 |
Journal | Logical Methods in Computer Science |
Volume | 17 |
Issue number | 1 |
Pages (from-to) | 2:1-2:16 |
ISSN | 1860-5974 |
DOIs | |
Publication status | Published - 2021 |
Bibliographical note
Publisher Copyright:
© Siddharth Bhaskar and Alex Kruckman.
- Finite model theory, Inductive definability, Least fixed-point logic, Model-theoretic dividing lines
Research areas
ID: 269503322