The Arithmetical Hierarchy and Post's Theorem: Examples and Counterexamples

Validity of a proposed finite history is primitive recursive, so the displayed formula has one leading unbounded existential quantifier over a bounded matrix.

Hence it is a ${\mathrm{\Sigma }}_1^0$ presentation. The witness is precisely the finite accepting computation used by the recognizer of $K$.

The numbering and decoder are effective, so bounded simulation makes $(e,s)\mapsto h(e,s)$ computable.

If ${\mathrm{\Phi }}_e^{\mathrm{\varnothing }}(e)$ never halts every value is $0$; if it halts at stage $r$, every value from $r$ onward is $1$. Thus ${\lim }_{s}h(e,s)={\chi }_{0^{\mathrm{\prime }}}(e)$, without supplying a computable stage at which this happens.

The set $E$ of even natural numbers has the decidable predicate $x=2q$ for some $q$, and its complement has the decidable predicate $x=2q+1$ for some $q$.

Therefore $E$ is ${\mathrm{\Delta }}_1^0$ and is in both ${\mathrm{\Sigma }}_n^0$ and ${\mathrm{\Pi }}_n^0$ after padding for every $n\ge 1$. It witnesses overlap, not equality of the two classes.