[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
More information about the FOM
mailing list