Modal Quantifiers
Natasha Alechina
Abstract:
This thesis contains a study of generalizations of first order quantification. In a sense, the quantifiers studied here stand to ∀ and ∃ as the modal operators 2 and 3 stand to the universal modality.
The idea behind separating this class of quantifiers is based on the following intuition. We understand binding variables as follows: if a ‘universal-type’ quantifier binds a variable x, then this means that for every object in the range of x, the expression in the scope of the quantifier holds. For the ‘existential-type’ quantifier, dually, there is an object in the range of x for which the formula under the quantifier holds. For the ordinary quantifiers, the range of a variable is given in advance: it is the domain of the model. For modal quantifiers, the range of a variable depends on the point where the formula is evaluated; a similar definition of ‘modal’, as depending on the evaluation point, is given in (Blackburn and Seligman 1995). Another property of modal quantifiers, which will be discussed later in this introduction, is that the variables bound by them have internal structure and ‘individuality’ which ordinary first order variables lack. We will see that the variables bound by modal quantifiers resemble more the variables used in programming languages, such as Pascal.
In the introduction I give examples of modal quantifiers: 'ordinary' ∀ and ∃ (no dependence between variables), generalized quantifiers like 'for almost all', 'for uncountable many', quantifiers in logics with limited sets of dispensations, etc. Given so many examples from different fields, the general theory of similar quantifiers seems to improve and use the analogy with modal logic to prove new theorems.
The first chapter following this introduction contains some facts about various logics which arise from the idea that the range of a variable can be restricted by the values of some ‘relevant’ variables. We give a Hilbert-style axiomatization of the logic of structured dependence models which we consider as the most basic system under the assumption that ‘relevant variables’ are precisely the free variables of the formula in the scope of the quantifier.
Also, a Hilbert-style axiomatization for partial assignments and a tableau calculus for the logic of assignments models are given. Further, we show that by a general result of Andréka and Németi (1994) these logics are decidable. We prove some results about the relationships between them.
This chapter owes a lot to discussions with H. Andréka and I. Németi.
Chapter 3 studies model and proof theory of the minimal logic of generalized quantifiers, in particular we prove preservation under bisimulations, decidability and interpolation theorems. It is partly based on (van Benthem and Alechina 1993), ‘Modal Quantification over Structured Domains’, to appear in M. de Rijke, ed., Advances in Intensional Logic, and (Alechina 1995c), ‘On A Decidable Generalized Quantifier Logic Corresponding to a Decidable Fragment of First Order Logic’, to appear in the Journal of Logic, Language and Information.
In Chapter 4 we study the correspondence between quantifier axioms and the properties of R in dependence models and prove a Sahlqvist theorem for correspondence and completeness. It is based on (van Benthem and Alechina 1993), (Alechina and van Lambalgen 1995a): ‘Correspondence and Completeness for Generalized Quantifiers’, Bulletin of the IGPL 3, 167 – 190, and (Alechina and van Lambalgen 1995b): ‘Generalized Quantification as Substructural Logic’, to appear in the Journal of Symbolic Logic.
In Chapter 5 the approach to unary generalized quantifiers presented in Chapters 3 and 4 is extended to the binary case. It also studies connections between binary generalized quantifiers and conditionals and their applications in formalizing defeasible reasoning. This chapter is based on (Alechina 1993): ‘Binary quantifiers and relational semantics’, ILLC Report LP-93-13, and (Alechina 1995a): ‘For All Typical’, in Symbolic and Quantitative Approach to Reasoning and Uncertainty. Proceedings ECSQARU’95.