Contributed Session
Here are talks accepted for workshop contributed session. According to the
workshop schedule we also give our propositions for contributed session timetable:
- Amelie Gherbrand, "Increasing the expressive power of the Carnap first
order modal logic C" — Thursday, 2.15 p.m. (14.15);
- Juha Kontinen, "Logical characterization of the counting hierarchy" — Thursday, 2.45 p.m. (14.45)
- Paula Quinion & Konrad Zdanowski, "The intended Model of Arithmetic. An
argument from Tennenbaum's theorem" — Friday, 1.30 p.m. (13.30);
- Brian Semmes, "Jayne-Rogers Notes" — Friday, 2.15 p.m. (14.15);
- Łukasz Wojtyniak, "Equivalence of Restricted Henkin Quantifiers" — Friday, 1.00 p.m. (13.00).
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.