What classification does this formula have?

27 Views Asked by At

Say I have formulas $P(a,b,c)$, $Q(a,b,c)$, each in $\Sigma^0_1$. The formula that I am interested in is

$\varphi(a,b,c) = $ $\forall a,b,c [\neg P(a,b,c) \vee Q(a,b,c)]$

(You could probably guess that it originally looked like $P \Rightarrow Q$). Because of how quantifiers work I can't really pull out a negative by de Morgan and say we are talking about a $d- \Sigma^0_2$ formula. So how do I deal with this formula? Where is $\varphi$ in the arithmetical hierarchy?

1

There are 1 best solutions below

1
On BEST ANSWER

Basically, multi-ary Boolean combinations inside of quantifiers should be thought of as "picking the worse option." Here we have a $\Sigma_1^0$ (the $Q$) and a $\Pi^0_1$ (the $\neg P$) inside a universal quantifier; the former suggests $\Pi^0_2$ while the latter suggests $\Pi^0_1$. Since the former is worse, this says that the complexity of the whole is $\Pi^0_2$.

To see why this works, note that $$\forall x(\forall y A(x,y)\vee\exists zB(x,z))$$ is equivalent to $$\forall x,y\exists z(A(x,y)\vee B(x,z)).$$