Date and Time: Tuesday, 12th April 2022, 8.30pm
The Downward Lowenheim-Skolem Property in the Finite
Abhisek Sankaran
Cambridge University, UK.
12-04-22

---

Abstract

The Downward Lowenheim-Skolem (DLS) theorem is a cornerstone result of classical model theory that states that any infinite structure contains a countable substructure that is equivalent with respect to all properties expressible in first order logic. We present a finitary analogue of the mentioned DLS property, that we denote FDLS, and show that FDLS affords many desirable features, algorithmic and structural, for any class on which it holds. We show that a number of classes of structures of interest in computer science satisfy FDLS, and that the latter remains stable under various well-known operations on structures. We go further to present a "pseudo-finitary" analogue of the DLS property, denoted PFDLS, that generalizes FDLS by considering infinite structures as well. We show that natural extensions with infinite structures of the mentioned FDLS classes, satisfy PFDLS, and hence that these extensions indeed continue to enjoy the aforementioned algorithmic and structural features. We conclude with directions for future work.