---
title: "Hierarchies of number-theoretic predicates"
authors:
  - "Stephen C. Kleene"
year: 1955
venue: "Bulletin of the American Mathematical Society"
arxiv: null
doi: "10.1090/S0002-9904-1955-09909-1"
source: "https://doi.org/10.1090/S0002-9904-1955-09909-1"
topics:
  - arithmetical-hierarchy
  - kleene
  - hyperarithmetic
seed_rank: 531
seed_batch: "foundations-greats-2026-08-13"
reviewed: "2026-08-13"
pool: "maths-foundations"
relevance_score: 8
lineage: foundations-of-computing
cites:
  - title: "Recursive predicates and quantifiers"
    url: "https://doi.org/10.1090/S0002-9947-1943-0007371-8"
    year: 1943
    arxiv: null
    doi: "10.1090/S0002-9947-1943-0007371-8"
  - title: "On notation for ordinal numbers"
    url: "https://doi.org/10.2307/2267778"
    year: 1938
    arxiv: null
    doi: "10.2307/2267778"
  - title: "Recursively enumerable sets of positive integers and their decision problems"
    url: "https://doi.org/10.1090/S0002-9904-1944-08111-1"
    year: 1944
    arxiv: null
    doi: "10.1090/S0002-9904-1944-08111-1"
see:
  - "528-recursive-predicates-and-quantifiers"
  - "527-on-notation-for-ordinal-numbers"
  - "534-recursively-enumerable-sets-of-positive-integers-and-their-d"
---

# Hierarchies of number-theoretic predicates

## One-sentence takeaway

Kleene extends the 1943 arithmetical hierarchy through the hyperarithmetic levels, indexing definability strength by notations in \(\mathcal{O}\).

## Why it matters here

Companion to the 1943 paper and to Turing's ordinal logics: once Anoptic cares about "this property is not merely r.e. but sits at a recursive ordinal of quantification," this is the roadmap. It is also the definability ladder later descriptive-set-theory cards inherit.

## Key ideas

- Surveys the arithmetical hierarchy and proves hierarchy theorems (each level properly contains the one below).
- Climbs past \(\Delta^1_1\) into the hyperarithmetic hierarchy, using recursive ordinals as indices.
- Ties predicate complexity to constructive ordinals rather than to runtime.
- Written as a BAMS address: part survey, part new theorems.

## Caveats

## Links

- DOI: [10.1090/S0002-9904-1955-09909-1](https://doi.org/10.1090/S0002-9904-1955-09909-1)
- URL: https://doi.org/10.1090/S0002-9904-1955-09909-1