Warsaw University Institute of Philosophy

Contributed Session

Here are talks accepted for workshop contributed session. According to the workshop schedule we also give our propositions for contributed session timetable:

Juha Kontinen, "Logical characterization of the counting hierarchy"

Abstract: The counting hierarchy CH is the analogue of the polynomial hierarchy PH, the building block being probabilistic polynomial time PP instead of NP. We show that the extension of first-order logic by second-order majority quantifiers of all arities describes exactly the problems in the counting hierarchy. This result is based on definability results which show that using the k-ary majority quantifier and first-order logic, the relativized k-ary majority quantifier (for k>1) and the k-ary second-order existential quantifier are uniformly expressible. We also consider extending the characterization to general proportional quantifiers Q_r saying "more than an r-fraction of relations". We show that the result can be generalized if r is of the form s/2^m, where s,m are positive integers, but for any other 0 < r < 1 the corresponding logic satisfies the 0-1 law.

Brian Semmes, "Jayne-Rogers Notes"

Abstract: We review the Eraser and Backtrack Games and use them to give a proof of the Jayne-Rogers theorem on the Baire Space.

Łukasz Wojtyniak, "Equivalence of Restricted Henkin Quantifiers"

Abstract: Blass and Gurevich consider Henkin quantifiers to obtain results concerning computational complexity problems. For this purpose, they define restricted Henkin quantifiers with Boolean existential variables. Sandu considers Henkin quantifiers in terms of their expressive power. For this purpose, he defines Henkin quantifiers with partially ordered connectives. It is so-called “logical folklore” that these restricted Henkin quantifiers are equivalent. I show a proof of this fact.