Andrzej Mostowski (1913-1975)

Andrzej Mostowski was born 100 years ago today. While Mostowski worked in many areas of logic, including early fundamental work on model theory, for our readers he's best known for co-discovering the arithmetic hierarchy, sometimes called the Kleene-Mostowski hierarchy.

The arithmetic hierarchy has a few different equivalent definitions but let's use one based on computability. We define inductively there hierarchies, Σ_i⁰, Π_i⁰ and Δ_i⁰. Σ₀⁰=Π₀⁰=Δ₀⁰ are the computable sets and

1. Δ_i+1⁰ are the sets computable with a Σ_i⁰ oracle.
2. Σ_i+1⁰ are the sets computably enumerable with a Σ_i⁰ oracle.
3. Π_i⁰ = co-Σ_i⁰.

In particular, Δ₁⁰ are the computable sets and Σ₁⁰ are the computably enumerable sets. The halting problem is Σ₁⁰-complete under computable reductions, the set of Turing machines that accepting infinite sets are Π₂⁰-complete.

We completely know the structure of the arithmetic hierarchy, for i > 0, Σ_i⁰ ≠ Π_i⁰ and for i ≥ 0, Δ_i⁰ = Σ_i+1⁰ ∩ Π_i+1⁰.

The arithmetic hierarchy inspired the polynomial-time hierarchy in complexity theory. Unlike the arithmetic hierarchy, separations in the polynomial-time hierarchy remain open and any separation implies P ≠ NP. While we have relativized worlds which do quite a few different separations and collapses in the polynomial-time hierarchy the following remains open: Does there exist a relativized world where the polynomial-time hierarchy looks like the arithmetic hierarchy, i.e., for i > 0, Σ_i^p ≠ Π_i^p and for i ≥ 0, Δ_i^p = Σ_i+1^p ∩ Π_i+1^p?