# 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. - 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} }