Definition:Arithmetical Hierarchy

This article needs to be linked to other articles. In particular: category You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{MissingLinks}} from the code.

This article, or a section of it, needs explaining. In particular: something really needs to be in place in the text which reiterates the name "arithmetical hierarchy" in order to state unambiguously what it actually is You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Explain}} from the code.

This article needs to be tidied. In particular: might also be worth defining it in numbered sections. Please fix formatting and $\LaTeX$ errors and inconsistencies. It may also need to be brought up to our standard house style. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Tidy}} from the code.

Definition

For every $i \in \N$, $\Sigma_i$ and $\Pi_i$ are sets of well-formed formulae in the language of arithmetic.

They are defined recursively as follows:

Let $\phi$ be logically equivalent to a well-formed formula in the language of arithmetic containing no quantifiers.

Then $\phi \in \Sigma_0$ and $\phi \in \Pi_0$

Let $\phi$ be logically equivalent to $Q_1 Q_2 \dotsm Q_k \psi$ where:

$\psi \in \Pi_n$

$Q_j$ is either $\exists x$ or $\forall x < y$, for some variable $x$ and term $y$

Then $\phi \in \Sigma_{n \mathop + 1}$.

Let $\phi$ be logically equivalent to $Q_1 Q_2 \dotsm Q_k \psi$ where:

$\psi \in \Sigma_n$

$Q_j$ is either $\forall x$ or $\exists x < y$, for some variable $x$ and term $y$

Then $\phi \in \Pi_{n \mathop + 1}$.

Sources

There are no source works cited for this page. In particular: I need this definition for a proof, but don't have a reliable source for it. I also don't have access to a large collection of published resources to go looking for one. Source citations are highly desirable, and mandatory for all definition pages. Definition pages whose content is wholly or partly unsourced are in danger of having such content deleted. To discuss this page in more detail, feel free to use the talk page.