PS-File
PDF-File
Bibtex Entry
Department of Artificial Intelligence, Faculty of Sciences, Vrije Universiteit Amsterdam, De Boelelaan 1081a, 1081 HV Amsterdam, The Netherlands
marx@cs.vu.nl
http://www.cs.vu.nl/~marx
Out of the joint work of Johan van Benthem and the Hungarian group round Hajnal Andréka, István Németi and Ildikó Sain and their PhD students, two approaches for taming a logic evolved. With taming a logic we mean changing the logic in such a way that it becomes decidable. For first order logic, they took a semantic route using relativisation of models, and a syntactic route focusing on guarded fragments. The purpose of this paper is to show that these two routes are really two sides of the same coin. We do this by showing that a certain guarded fragment (called here the packed fragment) of first order logic forms precisely the set of first order sentences which are invariant for relativisation with a tolerance relation. Besides this technical contribution we provide an intuitive explanation of relativisation in terms of information transmission.