More on Oracles and Quantifiers 


Yachin Pnueli 
Institut für Informatik
Freie Universität Berlin
email: pnueli@inf.fu-berlin.de
(joint work with Janos A. Makowski)
Report B 94-17
September 1994 

Get the report here or by anonymous ftp: 
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-94-17.ps.gz
More on Oracles and Quantifiers We continue the investigation of \cite{ar:MP94} into the relationship between classes of oracle using Turing machines and logics enhanced by Lindstr\"om quantifiers. Let $\cL$ be a logic (FOL or SOL) and let $\cL[K]$ be the enhancement of that logic with a Lindstr\"om quantifier for the set of structures $K$. We show that if for some sets of structures $A,B,C$ we have $\cL[A,C] \subset \cL[B,C]$ then also $\cL[A] \subset \cL[B]$. This has the complexity theoretic implication that, using the appropriate oracle computation model, finding an oracle $K$ such that $\bL^K \subset \bP^K$ constitutes a proof that $\bL \subset \bP$. Considering the case where $\cL$ is Second Order Logic or fragments of it we use the results of Meyer and Stockmeyer about the polynomial hierarchy to show that if $\Sigma_i (\Pi_i)$ is a fragment of $SOL$ capturing level $\PS{i}$ $(\PP{i})$ in the polynomial hierarchy, then the enhanced fragment $\Sigma_i[K] (\Pi_i[K])$ (for arbitrary $K$) captures $\PSK{n}{K}$ $(({\Pi^p}_n)^K)$ - that level relativized to an oracle for the set $K$. As a corollary the logic $SOL[K]$ captures the polynomial hierarchy relativized to oracle $K$ and has a prenex normal form where all second order quantifiers appear outer most.