2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Any (FOL) formula is $\Sigma_n$ and $\Pi_n$ (and even $\sigma_n,\pi_n$ in your terminology) for sufficiently large $n$, so $\phi \in \bigcup_{n=0}^\infty \Sigma_n^0 \cup \Pi_n^0$ is kind of vacuous. First one is related to quantifier alternation depth, but not exactly. Second one I doubt has a designated symbol, though similar constructions are sometimes implied when performing structural induction on formulas. Third one is clearly true right by the definition of $\Sigma_n,\Pi_n$. $\endgroup$ – tomasz Jul 24 '13 at 2:48
1
$\begingroup$
  • 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.