---
title: "On notation for ordinal numbers"
authors:
  - "Stephen C. Kleene"
year: 1938
venue: "Journal of Symbolic Logic"
arxiv: null
doi: "10.2307/2267778"
source: "https://doi.org/10.2307/2267778"
topics:
  - ordinals
  - kleene
  - recursion
  - o-notation
seed_rank: 527
seed_batch: "foundations-greats-2026-08-13"
reviewed: "2026-08-13"
pool: "maths-foundations"
relevance_score: 8
lineage: foundations-of-computing
cites:
  - title: "Systems of Logic Based on Ordinals"
    url: "https://doi.org/10.1112/plms/s2-45.1.161"
    year: 1939
    arxiv: null
    doi: "10.1112/plms/s2-45.1.161"
  - 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: "Introduction to Metamathematics"
    url: "https://openlibrary.org/works/OL5959470W/Introduction_to_metamathematics"
    year: 1952
    arxiv: null
    doi: null
see:
  - "518-systems-of-logic-based-on-ordinals"
  - "528-recursive-predicates-and-quantifiers"
  - "529-introduction-to-metamathematics"
---

# On notation for ordinal numbers

## One-sentence takeaway

Kleene's system \(\mathcal{O}\) is a recursive notation system for constructive ordinals—the language in which Turing's ordinal logics and the hyperarithmetic hierarchy are later written.

## Why it matters here

Proof-theoretic ordinals, "how far can we climb past incompleteness," and any later talk of recursive well-founded trees in Anoptic verification all inherit this notation. Turing's 1939 thesis indexes theories by notations in \(\mathcal{O}\).

## Key ideas

- Natural numbers are used as *notations* for ordinals: successor and limit constructors are themselves recursive operations on codes.
- Not every notation denotes, and the same ordinal may have many notations; \(\mathcal{O}\) is a \(\Pi^1_1\)-complete set of well-founded codes.
- Constructive / recursive ordinals are exactly those with a notation in \(\mathcal{O}\).
- Basis for the hyperarithmetic hierarchy and for later proof-theoretic ordinal analysis.

## Caveats

## Links

- DOI: [10.2307/2267778](https://doi.org/10.2307/2267778)
- JSTOR: https://www.jstor.org/stable/2267778