Fork me on GitHub
Math for the people, by the people.

User login

arithmetical hierarchy

sigma n, sigma-n, pi n, pi-n, delta n, delta-n, recursive, recursively enumerable, delta-0, delta 0, delta-1, delta 1, arithmetical
arithmetic hierarchy, arithmetic, arithmetical, arithmetic formula, arithmetical formulas
Type of Math Object: 
Major Section: 

Mathematics Subject Classification

03B10 no label found


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

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.


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

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").

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$ ...

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

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.

Subscribe to Comments for "arithmetical hierarchy"