Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
Partially ordered connectives and ∑11 on finite models

Author(s): Merlijn Sevenster and Tero Tulenheimo
Slot: Array, 14:50-15:10, col. 4


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