[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