Sh:525

• Gurevich, Y., Immerman, N., & Shelah, S. (1994). McColm’s conjecture [positive elementary inductions]. In Proceedings Ninth Annual IEEE Symposium on Logic in Computer Science, IEEE Computer Society Press, pp. 10–19. arXiv: math/9411235 DOI: 10.1109/LICS.1994.316091
• 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.
• Version 1994-11-12_10 (10p) published version (10p)

@incollection{Sh:525,
 author = {Gurevich, Yuri and Immerman, Neil and Shelah, Saharon},
 title = {{McColm's conjecture [positive elementary inductions]}},
 booktitle = {{Proceedings Ninth Annual IEEE Symposium on Logic in Computer Science}},
 month = {July},
 year = {1994},
 pages = {10-19},
 publisher = {IEEE Computer Society Press},
 doi = {10.1109/LICS.1994.316091},
 note = {\href{https://arxiv.org/abs/math/9411235}{arXiv: math/9411235}},
 arxiv_number = {math/9411235},
 keyword = {formal logic;positive elementary inductions;finite structures;first-order formula;first-order logic;least fixed point operator;model-theoretic constructions;Vocabulary;Logic;Computer science;Mathematics;Building materials}
}