# 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 |