Logical Approaches to Computational Barriers

Partially ordered connectives and ∑

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 |