Definition talk:Arithmetical Hierarchy

When I have my next stint of contributing, (hopefully after my first year progression exams) I will fill this in with Soare's book "Turing Computability: Theory and Applications". I think these are both excellent sources. As to what's written on this page already, I would want to stress we are talking about a hierarchy of formulas that has an associated hierarchy of subsets of $\N$: we would call a set $A \subseteq \N$ say $\Sigma_n$ if there existed a $\Sigma_n$ formula $\phi$ in the language of arithmetic such that $A = \set {n \in \N : \map \phi n}$, and call a set arithmetical if any formula in the language of arithmetic defines it (basically a collection that you can understand purely in arithmetic without a set theory). I would want to call a quantifier-free formula in the language of arithmetic a $\Delta_0$ formula in a new page. Caliburn (talk) 16:02, 22 May 2024 (UTC)

Looking forward to your return. Best of British with the exams. --prime mover (talk) 17:24, 22 May 2024 (UTC)