Interpolation and Definability in Guarded Fragments

ISSN： 0039-3215

Source： Studia Logica, Vol.70, Iss.3, 2002-04, pp. : 373-409

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

The guarded fragment (GF) was introduced by Andréka, van Benthem and Németi as a fragment of first order logic which combines a great expressive power with nice, modal behavior. It consists of relational first order formulas whose quantifiers are relativized by atoms in a certain way. Slightly generalizing the admissible relativizations yields the packed fragment (PF). In this paper we investigate interpolation and definability in these fragments. We first show that the interpolation property of first order logic fails in restriction to GF and PF. However, each of these fragments turns out to have an alternative interpolation property that closely resembles the interpolation property usually studied in modal logic. These results are strong enough to entail the Beth definability property for GF and PF. Even better, every guarded or packed finite variable fragment has the Beth property. For interpolation, we characterize exactly which finite variable fragments of GF and PF enjoy this property.