+++
title = "Arithmetic Hierarchy"
author = "Yann Herklotz"
tags = []
categories = []
backlinks = ["4b1"]
forwardlinks = []
zettelid = "4b2"
+++

This is a hierarchy constructed in the following way, where $k$ is the
type. $k=0$ is the type of $\mathbb{N}$, whereas $k=1$ gives the type of
$\mathbb{N}\rightarrow \mathbb{N}$:

-   the formula is $\Sigma^k_{n+1}$ if the outermost quantifier is
    $\exists^k$, and there are $n$ alternations between blocks of
    $\exists^k$ and $\forall^k$ at the front of the formula.

-   the formula is $\Pi^k_{n+1}$ if the outermost quantifier is
    $\forall^k$, and there are $n$ alternations between blocks of
    $\exists^k$ and $\forall^k$ at the front of the formula.