On Definable Sets of Positive Integers
Reference: Mostowski, Andrzej (1946). “On definable sets of positive integers.” Fundamenta Mathematicae 34, 81–112. Open scan: fundmath.impan.pl/art/fm34-1-7 / matwbn.icm.edu.pl.
Summary
Mostowski’s 1946 paper develops, independently of and in parallel with Kleene 1943, a systematic theory of the definable sets of positive integers organised by quantifier alternation. Starting from arithmetic predicates — built from recursive (decidable) atomic relations by Boolean operations and quantification over integers — Mostowski identifies a hierarchy (the Kleene–Mostowski hierarchy, i.e. the modern arithmetical hierarchy) in which each additional quantifier alternation yields a strictly larger class. He proves the analogues of Kleene’s normal form, enumeration, and hierarchy theorems and shows that certain natural sets (truth-predicates, complete r.e. sets, their complements, etc.) are complete at specific levels.
A distinctive feature of the paper is its analogy with the projective hierarchy in descriptive set theory. Mostowski draws explicit parallels between (a) the Borel / projective classification of subsets of ℝ by continuous preimage and function-quantifier alternation, and (b) the arithmetical / analytical classification of subsets of ℕ by effective (recursive) reducibility and number- or function-quantifier alternation. The paper thus anticipates the analytical hierarchy — Σ¹_n / Π¹_n classes defined by quantification over functions — which becomes fully developed by Kleene, Addison, and others in the 1950s, and it positions the arithmetical hierarchy as the “effective” shadow of the classical projective hierarchy. This analogy is now one of the organising principles of effective descriptive set theory.
The paper is the canonical European counterpart to Kleene 1943; together they establish the Kleene–Mostowski theorem (the hierarchy is strict at every level) and the language in which all subsequent work on definability over ℕ is conducted.
Key Ideas
- Definability hierarchy for sets of positive integers, indexed by number-quantifier alternation over a decidable matrix — the arithmetical hierarchy.
- Kleene–Mostowski theorem: strict inclusions at every level.
- Analogy with the projective hierarchy of descriptive set theory: arithmetical ↔ projective, effective ↔ topological; anticipation of the analytical hierarchy.
- Complete sets at each level exhibited concretely.
- Developed in parallel with and independently of Kleene 1943 — a rare case of co-discovery in recursion theory.
Connections
- Recursive Function
- Computability
- First-Order Logic
- General Recursive Functions of Natural Numbers
- Recursive Predicates and Quantifiers
- On Notation for Ordinal Numbers
- Recursively Enumerable Sets of Positive Integers and Their Decision Problems
- Classes of Recursively Enumerable Sets and Their Decision Problems
- Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I
Conceptual Contribution
- Claim: The arithmetically definable subsets of
ℕform a strict hierarchy under quantifier alternation, and this hierarchy is the effective analogue of the projective hierarchy in classical descriptive set theory. - Mechanism: Starting from decidable atomic predicates, define Σ_n and Π_n by alternating blocks of number-quantifiers; prove normal form and enumeration theorems; exhibit complete sets at each level; identify the structural parallel with Luzin’s projective classes.
- Concepts introduced/used: arithmetical (Kleene–Mostowski) hierarchy, definable set, analogy with projective hierarchy, Recursive Function, First-Order Logic
- Stance: foundational technical paper (recursion theory / descriptive set theory)
- Relates to: Co-discovered with Kleene 1943; its projective-analogy line becomes the spine of effective descriptive set theory; provides the definability framework within which Rice 1953 locates index sets and Post 1944 locates creative sets.
Tags
#recursion-theory #definability #arithmetical-hierarchy #foundational #mostowski #descriptive-set-theory