McColm’s Conjecture
- Yuri Gurevich ,
- Neil Immerman ,
- Saharon Shelah
Symposium on Logic in Computer Science, IEEE Computer Society Press |
Gregory McColm conjectured that, over any class K of finite structures, all positive elementary inductions are bounded if every FOL + LFP formula is equivalent to a first-order formula over K. Here FOL + LFP is the extension of first-order logic with the least fixed point operator. Our main results are two model-theoretic constructions — one deterministic and one probabilistic — each of which refutes McColm’s conjecture.