Lindstrom theorems for fragments of first-order logic

DOI10.2168/LMCS-5(3:3)2009zbMATH Open1168.03017arXiv0905.3668MaRDI QIDQ3395097FDOQ3395097

Authors: Balder ten Cate, Jouko Väänänen, Johan van Benthem 

Publication date: 20 August 2009

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/0905.3668

Recommendations

• A new modal Lindström theorem
• scientific article; zbMATH DE number 3935021
• Lindström's theorem
• A general Lindström theorem for some normal modal logics
• First-order modal logic: frame definability and a Lindström theorem

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Subsystems of classical logic (including intuitionistic logic) (03B20) Logic in computer science (03B70) Basic properties of first-order languages and structures (03C07) Cylindric and polyadic algebras; relation algebras (03G15) Interpolation, preservation, definability (03C40)

Cited In (23)

• A PSPACE-complete first-order fragment of computability logic
• Feferman-vaught decompositions for prefix classes of first order logic
• Fragments of first-order logic over infinite words
• Title not available (Why is that?)
• Model theoretic methods for fragments of FO and special classes of (finite) structures
• Graph games and logic design
• The many faces of interpolation
• A new modal Lindström theorem
• First-order modal logic: frame definability and a Lindström theorem
• A general Lindström theorem for some normal modal logics
• Lindström's theorem
• Craig interpolation for decidable first-order fragments
• Games and Lindström theorems
• First-Order Linear-time Epistemic Logic with Group Knowledge: An Axiomatisation of the Monodic Fragment
• Chain logic and Shelah's infinitary logic
• Logic between expressivity and complexity
• Title not available (Why is that?)
• Keeping logic in the trivium of computer science: a teaching perspective
• Lindström theorems in graded model theory
• MAXIMALITY OF LOGIC WITHOUT IDENTITY
• Lindström's theorem for positive logics, a topological view
• Finitistic proofs of 0-1 laws for fragments of second-order logic
• Combinations of Theories for Decidable Fragments of First-Order Logic

This page was built for publication: Lindstrom theorems for fragments of first-order logic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3395097)