# [FOM] Two Questions About Second-order Branching Quantifiers

Tero Tulenheimo tero.tulenheimo at helsinki.fi
Sat Jan 27 06:21:24 EST 2007

Semantics of *first-order* branching quantifiers is typically given in terms of
*second-order* logic, in terms of Skolem functions. E.g., the formula

(Ax)(Ey)
B(x,y,z,v,w)
(Az)(Ev)

is by definition satisfied in a model M under assignment g iff the second-order
formula

EfEf'AxAz B(x,fx,z,f'z)

is. Analogously, one would expect the semantics of *second-order* branching
quantifiers to be in terms of *third-order* logic.

Now, applying such semantics to the formula

> (1)
>     (EF)
> 	       B_xy(Fx,Gy,z) ,
>     (AG)

this formula is seen to be satisfied in a model M under assignment g iff
there is a zero-place function F' whose image is a subset of M (whence F' simply
is a subset of M) such that for all subsets G' of M, the formula

B_xy(Fx,Gy,z)

is satisfied in M by g, when F is interpreted as F' and G as G'. But this simply
means that the formula is satisfied in precisely the same structures as the
plain second-order formula

(EF)(AG) B_xy(Fx,Gy,z).

Hence (1) is clearly \Sigma^1_2.

When it comes to \Delta^1_1, isn't it trivially the case that every
\Delta^1_1 formula can be written in the form (1) -- if any finite number of
existential quantifiers is allowed on the upper row? For any formula of the form

(EX_1)...(EX_n) \phi,

with \phi first-order, is already in such form, with nothing written on the
lower row. (Or otherwise the lower row may be filled with a vacuous quantifier
(AG), with the variable G appearing nowhere in the formula.)

Best regards,
Tero Tulenheimo

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
Tero Tulenheimo, DPhil
Post-Doctoral Research Fellow of the Academy of Finland
URL (official): http://www.helsinki.fi/filosofia/filo/henk/tulenheimo.htm
URL (personal): http://www.geocities.com/tero_tulenheimo
E-mail: tero.tulenheimo at helsinki.fi
Department of Philosophy
University of Helsinki
P.O. Box 9
FIN-00014 University of Helsinki
Finland
Tel: 358.9.19129248 / Mobile: 358.(0)40.5738182
Fax: 358.9.19129229