From Local to Global Relativization of the Łoś–Tarski Theorem

Speaker(s)

Aliaume Lopez

Affiliation

University of Warsaw

Date

Oct. 18, 2023, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

We consider first order sentences over a finite relational signature σ. Classical preservation theorems, dating back to the 1950s, state the correspondence between syntactic fragments of FO[σ], and semantic ones. The archetypal example of such preservation theorem is the Łoś–Tarski Theorem, that states the correspondence between the syntactic fragment of existential sentences, and the semantic fragment of sentences preserved under extensions. As its proof heavily relies on the compactness of first order logic, it is a priori unclear whether Łoś–Tarski Theorem relativizes to classes of finite structures. Tait has proven in 1959 that the theorem does not relativize to the class Fin[σ] of all finite structures, but it was proven by Atserias, Dawar, and Grohe that the Łoś–Tarski Theorem relativizes to hereditary classes of finite structures that have bounded degree, and are closed under disjoint unions. In this talk, we provide a full characterization of classes of hereditary classes finite structures that are closed under disjoint unions for which the Łoś–Tarski Theorem relativizes. This result follows form the study of the existential-local fragment of first order logic, that corresponds to a positive variant of the Gaifman normal form, and is itself subject to a preservation theorem. This talk is based on the following publication at LICS'22 https://dx.doi.org/10.1145/3531130.3532498.

---