Computability in Europe 2006
Logical Approaches to Computational Barriers
Logical Approaches to Computational Barriers
Print this page
Regular Talk:
Partially ordered connectives and ∑11 on finite models
| Author(s): | Merlijn Sevenster and Tero Tulenheimo |
| Slot: | Sat, 14:50-15:10, Faraday E (col. 4) |
Abstract
In this paper we take up the study of Henkin quantifiers with boolean variables (Blass & Gurevich, 1986) also known as partially ordered connectives (Sandu & Vaananen, 1992). We consider first-order formulae prefixed by partially ordered connectives, denoted D, on finite structures. We characterize D as a fragment of second-order existential logic (\Sigma_1^1) whose formulae do not allow for existential variables being argument of predicate variables. We show that this fragments harbors a strict hierarchy induced by the arity of predicate variables and that it is not closed under complementation, by means of a game-theoretical argument. Admitting for at most one existential variable to appear as the argument of a predicate variable already yields a logic coinciding with full second-order existential logic, thus we show.
| websites: Arnold Beckmann | 2006-04-19
|