van Benthem, Johan and Cate, Balder ten and Vaananen, Jouko - Lindstrom theorems for fragments of first-order logic

lmcs:895 - Logical Methods in Computer Science, August 3, 2009, Volume 5, Issue 3
Lindstrom theorems for fragments of first-order logic

Authors: van Benthem, Johan and Cate, Balder ten and Vaananen, Jouko

Lindstr\"om theorems characterize logics in terms of model-theoretic conditions such as Compactness and the L\"owenheim-Skolem property. Most existing characterizations of this kind concern extensions of first-order logic. But on the other hand, many logics relevant to computer science are fragments or extensions of fragments of first-order logic, e.g., k-variable logics and various modal logics. Finding Lindstr\"om theorems for these languages can be challenging, as most known techniques rely on coding arguments that seem to require the full expressive power of first-order logic. In this paper, we provide Lindstr\"om theorems for several fragments of first-order logic, including the k-variable fragments for k>2, Tarski's relation algebra, graded modal logic, and the binary guarded fragment. We use two different proof techniques. One is a modification of the original Lindstr\"om proof. The other involves the modal concepts of bisimulation, tree unraveling, and finite depth. Our results also imply semantic preservation theorems.


Source : oai:arXiv.org:0905.3668
DOI : 10.2168/LMCS-5(3:3)2009
Volume: Volume 5, Issue 3
Published on: August 3, 2009
Submitted on: February 16, 2008
Keywords: Computer Science - Logic in Computer Science,F.4.1,F.4.3


Share

Consultation statistics

This page has been seen 49 times.
This article's PDF has been downloaded 53 times.