[FOM] branching quantifiers

[Marcin Mostowski]

Dear Thomas Forster,

I am not sure of your definition of the prefixes. However the following
facts are known:
1. Each formula without negative occurences of Henkin quantifiers (in the
scope of an odd number of negations) is equivalent to a simple formula (Q
\phi, where Q is a Henkin prefix and \phi is quantifier free). Look at the
survey by Michal and me.
2. Positive formulae and \Sigma_1^1 are equivalent. Enderton-Walkoe.
3. Each positive formula is equivalent to a formula of the form
  \forall (first order variables) \exists (first order variables)
  \forall (first order variables) \exists (first order variables)
This is from Walkoe.
So as I well understood your observation, it roughly follows from these
facts. However, I am not sure the estimation of the size of resulted
prefixes.
By the way all the facts mentioned depend essentially on AC. Of course it
depends on the definition of the semantics (the discussion of these
problems you can find in the survey).

>From the observation that the Henkin logic witout equality in monadic case
has the finite model property, it follows that it has not greater
expressive power as the first order logic with equality. However it is not
obvious that exactly the same.

I am not sure whether I have catch exactly your questions. Nevertheless I
can try to be more precise if you have any other questions.

Best Regards

Marcin Mostowski


_____________________

Marcin Mostowski
Department of Logic
Institute of Philosophy
Warsaw University