Lindstrom theorems for fragments of first-order logic

Details Lindstrom theorems for fragments of first-order logic Lindstrom theorems for fragments of first-order logic

2009-05-22

arxiv.org/abs/0905.3668v2

LMCS 5 (3:3) 2009

Computer Science

Logic in Computer Science

Appears in Logical Methods in Computer Science (LMCS)

Scientific paper

10.2168/LMCS-5(3:3)2009

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.

Affiliated with

Also associated with

No associations

Rating

Lindstrom theorems for fragments of first-order logic does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Lindstrom theorems for fragments of first-order logic, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lindstrom theorems for fragments of first-order logic will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-325514