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.
• 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)
Bib entry
@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}
}