[FOM] branching quantifiers

[Marcin Mostowski]

This is in reply for the question on Henkin prefixes by Thomas Forster.

>I have two questions about them. 
>(i) Does anybody know any useful facts relating expressive power of quantifiers 
>with branching quantifiers to the *width* of the quantifier prefix? 

A survey of the topic of Branched quantifiers has been published in 1995
in the book "QUANTIFIERS", vol. 1, Synthese library, Kluwer Pub. Co.,
written by Michal Krynicki and me. Actually we know slightly more.
The paper by Konrad Zdanowski and me is "in printing" in Archive for
Mathematical Logic (you can ask Konrad for the best version available
<konrad.zdanowski at wp.pl>). Some other fresh results are in 
the survey "Henkin quantifiers in finite models" by Konrad Zdanowski 
and me (still on the preparation stage).

>(ii) Logic with branching quantifiers is equivalent in expressive to a logic 
>allowing single higher-order existential quantifiers. As far as i can see, 
>this exploits the presence of `=' in an essential way. Am i right? 
>Does anyone know anything about the expressive power of 
>the branching-quantifier logic *without* equality?

As a matther of fact you cannot get the full expressive power of
the second order logic in this way the discussion in the suvey by
Michal Krynicki and me is still actual.
A propos of the role of "=" Konrad has observed that the logic
of Henkin quantifiers without equality in monadic vocabularies 
is decidable. It follows from the fact that it has the finite model
property. More precisely if a formula has a model then it has 
a finte model, and the size of the model is bounded by the number
of predicates in use and the quantifier depth of the formula.
On the other hand (see the survey and the paper with Konrad),
The same logic with equality has decidable tautology problem for
the simplest quantifier prefixes only.

Additionally, I would advertise the paper 
by Dominika Wojtyniak and me on the computational
complexity of semantics for some statements
with an essentially weaker version of Henkin
quantifiers which seem to express some natural 
language sentences (it follows the proble of
Hintikka 1973, and some observations of
Blass-Gurevitch, APAL 1986). The paper is in
printin in APAL (currently available online
throu science direct). 
Roughly speaking it says that the problem of
truth value of sentences like 
"Some relative of each vllager and some relative 
of each townsman hates each other."
is NP-complete. The paper discuss possible 
consequences of the observation for natural
language semantics and cognitive sciences.

Marcin Mostowski



_____________________

Marcin Mostowski
Department of Logic
Institute of Philosophy
Warsaw University