McColm conjecture
From MaRDI portal
Publication:6503569
arXivmath/9411235MaRDI QIDQ6503569FDOQ6503569
Authors: Yuri Gurevich, Neil Immerman, S. Shelah 
Abstract: Gregory McColm conjectured that positive elementary inductions are bounded in a class K of finite structures if every (FO + LFP) formula is equivalent to a first-order formula in K. Here (FO + LFP) is the extension of first-order logic with the least fixed point operator. We disprove the conjecture. Our main results are two model-theoretic constructions, one deterministic and the other randomized, each of which refutes McColm's conjecture.
This page was built for publication: McColm conjecture
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6503569)
