Lindstrom theorems for fragments of first-order logic

DOI10.2168/LMCS-5(3:3)2009MaRDI QIDQ3395097zbMATH OpenFDO

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)

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

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)

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.

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

Cited in

(23)

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

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)