|
|
|
Viewing Version
4
of
'arithmetical hierarchy'
|
[ view 'arithmetical hierarchy'
|
back to history
]
| Title of object: |
arithmetical hierarchy |
| Canonical Name: |
ArithmeticalHierarchy |
| Type: |
Definition |
| Created on: |
2002-08-06 23:06:30.241199-04 |
| Modified on: |
2002-08-17 22:26:40.032044-04 |
| Classification: |
msc:03B10 |
| Defines: |
sigma n, sigma-n, pi n, pi-n, delta n, deta-n, recursive, recursively enumerable, delta-0, delta 0, delta-1, delta 1, arithmetical |
| Synonyms: |
arithmetical hierarchy=arithmetic hierarchy |
Preamble:
% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands here
%\PMlinkescapeword{theory} |
Content:
The \emph{arithmetical hierarchy} is a hierarchy of relations defined by first order formulas. The first level consists of the recursive relations (this definition is equivalent to the definition from computer science), and is also called $\Delta_0$, $\Delta_1$, $\Sigma_0$ and $\Pi_0$.
An relation $R$ is recursive if there is some formula $\phi$ with only bounded quantifiers such that:
$$R\vec{k}\leftrightarrow \phi(\vec k)$$
$R$ is a $\Sigma_n$ relation if there is some formula $\phi$ with only bounded quantifiers such that:
$$R\vec{k}\leftrightarrow \exists x_1\forall x_2\cdots {Q} x_n\phi(\vec k,\vec x)$$
$$\text{ where }Q\text{ is either }\forall\text{ or }\exists\text{, whichever maintains the pattern of alternating quantifiers}
The $\Sigma_1$ relations are the same as the recursively enumerable relations.
Similarly, $R$ is a $\Pi_n$ relation if there is some formula $\phi$ with only bounded quantifiers such that:
$$R\vec{k}\leftrightarrow \forall x_1\exists x_2\cdots Q x_n\phi(\vec k,\vec x)$$
$$\text{ where }Q\text{ is either }\forall\text{ or }\exists\text{, whichever maintains the pattern of alternating quantifiers}
A relation is $\Delta_n$ if it is both $\Sigma_n$ and $\Pi_n$. Since each $\Sigma_n$ relation is just the negation of a $\Pi_n$ and vice-versa, $R$ is $\Delta_n$ if both $R$ and its complement are $\Sigma_n$.
Higher levels on the hierarchy correspond to broader and broader classes of relations. A relation which is $\Sigma_n$ (or, equivalently, $\Pi_n$) for some integer $n$ is called \emph{arithmetical}.
The members of the arithmetical hierarchy are sometimes denoted with a superscript $0$ (i.e. $\Sigma_0^1$) to distinguish them from analytic hierarchy. |
|
|
|
|
|
