arithmetical hierarchy is a proper hierarchy

By definition, we have ${\mathrm{\Delta }}_n={\mathrm{\Pi }}_n\cap {\mathrm{\Sigma }}_n$. In addition, ${\mathrm{\Sigma }}_n\cup {\mathrm{\Pi }}_n\subseteq {\mathrm{\Delta }}_{n+1}$.

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

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

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

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

Title	arithmetical hierarchy is a proper hierarchy
Canonical name	ArithmeticalHierarchyIsAProperHierarchy
Date of creation	2013-03-22 12:55:14
Last modified on	2013-03-22 12:55:14
Owner	Henry (455)
Last modified by	Henry (455)
Numerical id	6
Author	Henry (455)
Entry type	Result
Classification	msc 03B10