# arithmetical hierarchy is a proper hierarchy

By definition, we have $\Delta_{n}=\Pi_{n}\cap\Sigma_{n}$. In addition, $\Sigma_{n}\cup\Pi_{n}\subseteq\Delta_{n+1}$.

This is proved by vacuous quantification. If $R$ is equivalent to $\phi(\vec{n})$ then $R$ is equivalent to $\forall x\phi(\vec{n})$ and $\exists x\phi(\vec{n})$, where $x$ is some variable that does not occur free in $\phi$.

More significant is the proof that all containments are proper. First, let $n\geq 1$ and $U$ be universal for $2$-ary $\Sigma_{n}$ relations. Then $D(x)\leftrightarrow U(x,x)$ is obviously $\Sigma_{n}$. But suppose $D\in\Delta_{n}$. Then $D\in Pi_{n}$, so $\neg D\in\Sigma_{n}$. Since $U$ is universal, ther is some $e$ such that $\neg D(x)\leftrightarrow U(e,x)$, and therefore $\neg D(e)\leftrightarrow U(e,e)\leftrightarrow\neg U(e,e)$. This is clearly a contradiction, so $D\in\Sigma_{n}\setminus\Delta_{n}$ and $\neg D\in\Pi_{n}\setminus\Delta_{n}$.

In addition the recursive join of $D$ and $\neg D$, defined by

 $D\oplus\neg D(x)\leftrightarrow(\exists y

Clearly both $D$ and $\neg D$ can be recovered from $D\oplus\neg D$, so it is contained in neither $\Sigma_{n}$ nor $\Pi_{n}$. However the definition above has only unbounded quantifiers except for those in $D$ and $\neg D$, so $D\oplus\neg D(x)\in\Delta_{n+1}\setminus\Sigma_{n}\cup\Pi_{n}$

Title arithmetical hierarchy is a proper hierarchy ArithmeticalHierarchyIsAProperHierarchy 2013-03-22 12:55:14 2013-03-22 12:55:14 Henry (455) Henry (455) 6 Henry (455) Result msc 03B10