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)

• Combinations of Theories for Decidable Fragments of First-Order Logic
• A PSPACE-complete first-order fragment of computability logic
• Fragments of first-order logic over infinite words
• Feferman-vaught decompositions for prefix classes of first order logic
• scientific article; zbMATH DE number 5872415 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 3935021 (Why is no real title available?)
• Keeping logic in the trivium of computer science: a teaching perspective
• Lindström theorems in graded model theory
• Finitistic proofs of 0-1 laws for fragments of second-order logic
• MAXIMALITY OF LOGIC WITHOUT IDENTITY
• Lindström's theorem for positive logics, a topological view

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)