A few basic questions about the arithmetical hierarchy, mostly about terminology.

Question

I was reading about the arithmetical hierarchy, and I have a few questions, mostly notational. For completeness, here's the definition given over at Wikipedia.

The classifications $\Sigma_n$ and $\Pi_n$ are defined inductively for every natural number $n$ using the following rules:

1. If $\phi$ is logically equivalent to a formula of the form $\exists n_1 \exists n_2\cdots \exists n_k \psi$, where $\psi$ is $\Pi_n$, then $\phi$ is assigned the classification $\Sigma_{n+1}$.

2. If $\phi$ is logically equivalent to a formula of the form $\forall n_1 \forall n_2\cdots \forall n_k \psi$, where $\psi$ is $\Sigma_n$, then $\phi$ is assigned the classification $\Pi_{n+1}$.

A few questions, mostly about notation.

Firstly, given a formula $\phi$ such that $\phi \in \bigcup_{n=0}^\infty \Sigma_n^0 \cup \Pi_n^0,$ is there a traditional name for the least $n$ such that $\phi \in \Sigma_n^0 \cup \Pi_n^0$?

Secondly, suppose we replace the phrase 'logically equivalent' with 'equal to.' Lets also write the sigma's and pi's in lowercase to compensate. Is there traditional notation / terminology associated with this definition? The definition is:

The classifications $\sigma_n$ and $\pi_n$ are defined inductively for every natural number $n$ using the following rules:

1. If $\phi$ is equal to to a formula of the form $\exists n_1 \exists n_2\cdots \exists n_k \psi$, where $\psi$ is $\pi_n$, then $\phi$ is assigned the classification $\sigma_{n+1}$.

2. If $\phi$ is equal to to a formula of the form $\forall n_1 \forall n_2\cdots \forall n_k \psi$, where $\psi$ is $\sigma_n$, then $\phi$ is assigned the classification $\pi_{n+1}$.

Thirdly, suppose we define that for a formula $\phi$ we have that $e(\phi)$ is the set of all logically equivalent formulae. Lets furthermore define that for a set of formulae $\Phi$ we have that $$e(\Phi) = \bigcup_{\phi \in \Phi} e(\phi).$$

Under these definitions, does it hold that $\Sigma_n = e(\sigma_n)$ and $\Pi_n = e(\pi_n)$?

Thank you for your time & energy.

Answer 1

• No, there is no traditional name for $\Sigma^0_n \cup \Pi^0_n$.

• There is no traditional name for the least $n$ such that a formula is in $\Sigma^0_n \cup \Pi^0_n$.

• The answer to the final question is yes; you can prove this by induction on $n$. The only reason for the "logically equivalent to" in the definition is so that every formula gets a classification. Some authors do use "equal to", so not every formula is classified; that does not cause any problems in practice.