In my notes the Arithmetical Hierarchy is defined recursively as follows:
- $\Delta_0$ is the smallest class of ( arithmetical first-order ) formulae which contains all atomic formulae and is closed under logical connectives and bounded quantifiers.
- $\Sigma_1^0$ is the smalles class of formulae which contains $\Delta_0$ and it is closed under disjunction, conjunction, bounded quantifiers and existential (unbounded) quantifiers.
- $\Pi_1^0$ is the smalles class of formulae which contains $\Delta_0$ and it is closed under disjunction, conjunction, bounded quantifiers and universal (unbounded) quantifiers.
- $\Sigma_{n+1}^0$ is the smalles class of formulae which contains $\Pi_n^0$ and it is closed under disjunction, conjunction, bounded quantifiers and existential (unbounded) quantifiers.
- $\Pi_{n+1}^0$ is the smalles class of formulae which contains $\Sigma_n^0$ and it is closed under disjunction, conjunction, bounded quantifiers and universal (unbounded) quantifiers.
Then it is said that these classes are closed under logical equivalence, but no proof is presented.
I've seen other definitions of this Hierarchy whose closure property under logical equivalence stems directly from the definition itself, but in this case I don't see how this should be obvious. How can it be shown from the definition I gave above? Thanks
Best Answer
Your notes are incorrect. For example, $\exists x(x=x)$ is logically equivalent to $0=0$, but the former is not $\Delta_0$ while the latter is $\Delta_0$.
More generally, let $A,B$ be any pair of formulas with $B$ much more syntactically complicated than $A$; then $A$ and $A\wedge (B\vee\neg B)$ are logically equivalent but the latter will show up later in the arithmetical hierarchy than the former.