Locality : A useful notion for proving inexpressibility in Finite Model Theory

Show full item record


Title: Locality : A useful notion for proving inexpressibility in Finite Model Theory
Author: Mahmood, Yasir
Contributor: University of Helsinki, Faculty of Science, Department of Mathematics and Statistics
Publisher: Helsingin yliopisto
Date: 2018
Language: eng
URI: http://urn.fi/URN:NBN:fi-fe201804208627
Thesis level: master's thesis
Discipline: Mathematics
Abstract: This thesis discusses the notion of locality used in finite model theory to obtain results about the expressive power of first order logic. It turns out that the most commonly used Ehrenfeucht-Fraïssé games are also applicable over finite structures. However, we analyze with an example the need for simpler tools for finite structures due to the complex combinatorial arguments required while using EF-games. We argue that locality is such a tool, although the gap between games and locality is quite narrow as the latter is in fact based on the former. Intuitively speaking: locality of FO implies that in order to check the satisfiability of a FO formula over a finite structure, it is enough to look at a small portion of the universe (which will be called the neighborhood of a point). We discuss two commonly known notions of locality given by William Hanf and Haim Gaifman. We provide the original results of the authors and then their modified versions suitable for finite structures. We then show that first order logic over any relational vocabulary has both of these locality properties. In order to grasp the idea of locality we also include examples wherever required. Towards the end of the thesis we also discuss deficiencies and limitations of the two types of locality and possible solutions to overcome them. In the last section we also discuss locality of order-invariant first order formulas.

Files in this item

Total number of downloads: Loading...

Files Size Format View
Mathematics_Yasir_Mahmood.pdf 421.3Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record