Alladi Ramakrishnan Hall

Hereditariness in the finite and prefix classes of first order logic

Abhishek Sankaran

Dept. of Computer Science, University of Cambridge

The Los-Tarski theorem is a result from classical model theory that states that over arbitrary (finite or infinite) structures, a first order (FO) sentence is hereditary if, and only if, it is equivalent to a universal sentence. This theorem however fails in the finite. Tait (1959) and independently Gurevich and Shelah (1984) showed that there is an FO sentence that is hereditary over the class of all finite structures but that is not equivalent over this class, to any universal sentence.
In a recent paper [2], a strengthening of the above failure was shown: for every k, there is an FO sentence that is hereditary over all finite structures but that is not equivalent over this class to any Σ02 sentence that contains k existential quantifiers. We generalize this result by showing that for every n, there is an FO sentence φn that is hereditary over all finite structures but that is not equivalent over this class to any Σ0n sentence. In short, (FO-)hereditariness over all finite structures is not capturable by any prefix class of FO. We show further that ¬φn is expressible in Datalog(̸=, ¬), thus answering in the negative a question open since 1994, posed by Weinstein and Rosen [1], that asks whether FO ∩ Datalog(̸=, ¬) is contained (semantically) inside some prefix class of FO. At the heart of our proof is the construction of structures that exhibit self-similarity.
The talk will be in two parts. In Part I, we illustrate the ideas behind our result by taking a relook at Tait’s counterexample referred to above, and showing that not only is it not equivalent to any universal sentence, but in fact, it is not equivalent to any Σ03 sentence as well. The methods used to show this extend the ideas from [2] in a significant way that would allow us to prove our generalization. In Part II of the talk, we present our generalized construction and the arguments involved therein. Each talk will be for 40 mins with an intervening break of 10 mins.

[1] Eric Rosen and Scott Weinstein. Preservation theorems in finite model theory. In Inter- national Workshop on Logic and Computational Complexity, pages 480–502. Springer, 1994.

[2]Abhisekh Sankaran. Revisiting the generalized L􏰣os-Tarski theorem.In Logic and Its Applications - 8th Indian Conference, ICLA 2019, Delhi, India, March 1-5, 2019, Proceedings, pages 76–88, 2019.