## You are here

Homearithmetical hierarchy

## Primary tabs

# arithmetical hierarchy

The *arithmetical hierarchy* is a hierarchy of either (depending on the context) formulas or relations. The relations of a particular level of the hierarchy are exactly the relations defined by the formulas of that level, so the two uses are essentially the same.

The first level consists of formulas with only bounded quantifiers, the corresponding relations are also called the Primitive Recursive relations (this definition is equivalent to the definition from computer science). This level is called any of $\Delta^{0}_{0}$, $\Sigma^{0}_{0}$ and $\Pi^{0}_{0}$, depending on context.

A formula $\phi$ is $\Sigma^{0}_{n}$ if there is some $\Delta^{0}_{0}$ formula $\psi$ such that $\phi$ can be written:

$\phi(\vec{k})=\exists x_{1}\forall x_{2}\cdots{Q}x_{n}\psi(\vec{k},\vec{x})$ |

$\text{ where }Q\text{ is either }\forall\text{ or }\exists\text{, whichever % maintains the pattern of alternating quantifiers}$ |

The $\Sigma^{0}_{1}$ relations are the same as the Recursively Enumerable relations.

Similarly, $\phi$ is a $\Pi^{0}_{n}$ relation if there is some $\Delta^{0}_{0}$ formula $\psi$ such that:

$\phi(\vec{k})=\forall x_{1}\exists x_{2}\cdots Qx_{n}\psi(\vec{k},\vec{x})$ |

$\text{ where }Q\text{ is either }\forall\text{ or }\exists\text{, whichever % maintains the pattern of alternating quantifiers}$ |

A formula is $\Delta^{0}_{n}$ if it is both $\Sigma^{0}_{n}$ and $\Pi^{0}_{n}$. Since each $\Sigma^{0}_{n}$ formula is just the negation of a $\Pi^{0}_{n}$ formula and vice-versa, the $\Sigma^{0}_{n}$ relations are the complements of the $\Pi^{0}_{n}$ relations.

The relations in $\Delta^{0}_{1}=\Sigma^{0}_{1}\cap\Pi^{0}_{1}$ are the Recursive relations.

Higher levels on the hierarchy correspond to broader and broader classes of relations. A formula or relation which is $\Sigma^{0}_{n}$ (or, equivalently, $\Pi^{0}_{n}$) for some integer $n$ is called *arithmetical*.

The superscript $0$ is often omitted when it is not necessary to distinguish from the analytic hierarchy.

## Mathematics Subject Classification

03B10*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## Pi^0_n definition correct?

I think that $Pi^0_n$ definition should require that $xi$ (the inner formula) be a $Delta_0$ formula, and not $Delta^0_1$.

## Re: Pi^0_n definition correct?

I can't seem to find the definition that you are talking about, but the definitions are equivalent. Surely any $\Delta_0$ formula is $\Delta_1$. The other way is basically since a $\Delta_1$ formula $\varphi$ can be written as either $(\exists x)\psi_1$ or $(\forall x)\psi_2$, where both $\psi_1$ and $\psi_2$ are $\Delta_0$. So if you are say, $\Pi_2$, you look like $(\forall x)(\exists y)\varphi$, where $\varphi$ is $\Delta_1$, you also look like $(\forall x)(\exists y)(\exists z)\psi$, where $\psi$ is $\Delta_0$. (I assume you know how to make two existential quantifiers into one.)

I hope this makes sense.

-Flynn

## Re: Pi^0_n definition correct?

$\Delta_0$ and $\Delta_1$ however, are NOT the same! (though both are absolute for models of set theory)

## Re: Pi^0_n definition correct?

Yes, you are right.

But, if the definitions are equivalent, how come $Delta_0$ not equal to $Delta_1$?

(the definitions are in "Arithmetical Hierarchy").

## Re: Pi^0_n definition correct?

The definition currently on page "arithmetical hierarchy" is, indeed, incorrect. Or circular.

The line

A formula $\phi$ is $\Sigma^0_n$ if there is some $\Delta^0_1$ formula ...

should read

A formula $\phi$ is $\Sigma^0_n$ if there is some $\Delta^0_0$ formula ...

and similarly for the definition of $\Pi^0_n$ .

AS IT IS: $\Delta^0_1$ is definied in terms of $\Sigma^0_1$ which is defined in terms of $\Delta^0_1$ ...

## Delta 0

Rautenberg p239 says Delta-0 is pr but that pr need not be Delta-0–he gives hyperexponentiation as example

## Delta 0-cont.

However, Rautenberg on p 265 mentions variant Delta-0 ’s and one variant is (the above) prim. rec.. He also says that higher index things are ”fairly stable” under minor changes in Delta-0.