---
tag: M00S55MA1T
kind: definition
name: Analytical hierarchy
msc: [03D55, 03F35]
defines: M6JGF4TPM6
uses: [DC60FYCSPM, 7CVJCQKY41]
sources:
  - url: https://en.wikipedia.org/wiki/Analytical_hierarchy
---

## Definition

Work in the language of [[second-order arithmetic|DC60FYCSPM]], which has number variables and set variables.
It is interpreted in the standard model, where set variables range over all subsets of $\N$.
A formula is *arithmetical* if it has no quantifiers over sets; it may have free set variables.
The classes of formulas $\Sigma^1_n$ and $\Pi^1_n$ are defined by induction on $n$.

1. $\Sigma^1_0 = \Pi^1_0$ is the class of arithmetical formulas.
2. A formula is $\Sigma^1_{n+1}$ if it has the form $\exists X_1 \cdots \exists X_k \, \psi$ with $\psi$ in $\Pi^1_n$.
3. A formula is $\Pi^1_{n+1}$ if it has the form $\forall X_1 \cdots \forall X_k \, \psi$ with $\psi$ in $\Sigma^1_n$.

A set $A \subseteq \N$ is $\Sigma^1_n$, or $\Pi^1_n$, if a formula of that class defines it in the standard model.
The formula must have one free number variable and no other free variables.
A set is $\Delta^1_n$ if it is both $\Sigma^1_n$ and $\Pi^1_n$, and *analytical* if it is $\Sigma^1_n$ for some $n$.

## Remarks

Example: let $W$ be the set of $e$ such that program $e$ computes the characteristic function of a well-ordering of a subset of $\N$.
"Every nonempty set $X$ in the field of the ordering has a least element" is a universal set quantifier over an arithmetical formula.
So $W$ is $\Pi^1_1$; in fact it is $\Pi^1_1$-complete, so it is not $\Sigma^1_1$.

Non-example: the set of Gödel numbers of second-order sentences true in the standard model is not analytical, by Tarski's undefinability argument.

Every [[arithmetical|7CVJCQKY41]] set is $\Delta^1_1$, and the inclusion is strict.
By a theorem of Kleene, the $\Delta^1_1$ sets are exactly the [[hyperarithmetical sets|NS1HWGTD8E]].