Is negation of a $\Delta$-formula a $\Delta$-formula?

249 Views Asked by At

I'm trying to understand the relations between $\Delta$-formulas and $\Sigma$-formulas and $\Pi$-formulas.

As far as I know, if all quantifiers of a formula are bounded, then the formula is $\Delta$-formula; And being a $\Delta$-formula leads to being both $\Sigma$-formula and $\Pi$-formula. Because $\Delta$-formulas are actually the intersection of $\Sigma$-formulas and $\Pi$-formulas.

Now Let's consider following formula:

$\phi :\equiv (x<y) \vee (\forall z<w) x+\bar{17}=\bar{42}$

As there is no unbounded quantifier, then $\phi$ is a $\Delta$-formula (i.e., $\phi$ is both $\Sigma$-formula and $\Pi$-formula). Furthermore,

$\neg \phi :\equiv \neg(x<y) \wedge (\exists z<w) \neg(x+\bar{17}=\bar{42})$

which is a $\Delta$-formula, as well.

Can I generally claim the following argument?:

If $\phi$ is a $\Delta$-formula, then $\neg \phi$ is a $\Delta$-formula, too

1

There are 1 best solutions below

4
On BEST ANSWER

Looks like you can. By hypothesis, $\phi$ is of the form $\forall x (x<\overline{n} \land \varphi(x))$ or $\exists x (x<\overline{n} \rightarrow \varphi(x))$ (up to logical equivalence). Apply negation and play around with the symbols a bit and you'll find $\neg \phi$ can be expressed (up to logical equivalence) in a similar format.