Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Arithmetical hierarchy and many-one completeness

Definition
AutoformalisationSCI_Arith

by LG · Nov 20, 2026 · Mathlib 0df444a (Lean v4.33.1)

arithmetical-hierarchycomputabilitymathematical-logic

This file defines the arithmetical hierarchy for predicates on the natural numbers and the associated completeness notions, following the standard presentation (Soare, Turing Computability, Ch. 4).

For n∈Nn\in\mathbb Nn∈N and a predicate ppp on N\mathbb NN:

  • Σ00\Sigma^0_0Σ00​ is the class of computable (decidable) predicates.
  • Σn+10\Sigma^0_{n+1}Σn+10​ consists of the predicates obtained by projecting a Πn0\Pi^0_nΠn0​ predicate along one extra natural-number coordinate: p∈Σn+10p\in\Sigma^0_{n+1}p∈Σn+10​ iff there is a predicate qqq with ¬q∈Σn0\neg q\in\Sigma^0_n¬q∈Σn0​ and p(a)  ⟺  ∃b, q(⟨a,b⟩)p(a)\iff\exists b,\,q(\langle a,b\rangle)p(a)⟺∃b,q(⟨a,b⟩), where ⟨a,b⟩\langle a,b\rangle⟨a,b⟩ is a fixed computable pairing of N2\mathbb N^2N2 with N\mathbb NN.
  • Πn0\Pi^0_nΠn0​ is the class of complements of Σn0\Sigma^0_nΣn0​ predicates, and Δn0=Σn0∩Πn0\Delta^0_n=\Sigma^0_n\cap\Pi^0_nΔn0​=Σn0​∩Πn0​.

A set A⊆NA\subseteq\mathbb NA⊆N is Σn0\Sigma^0_nΣn0​-complete if A∈Σn0A\in\Sigma^0_nA∈Σn0​ and every Σn0\Sigma^0_nΣn0​ set CCC is many-one reducible to AAA (a total computable fff with a∈C  ⟺  f(a)∈Aa\in C\iff f(a)\in Aa∈C⟺f(a)∈A); Πn0\Pi^0_nΠn0​-complete is defined analogously. These are the completeness notions used in Theorems A.3 and A.4.

Formalization Note. Many-one reducibility is Mathlib's ManyOneReducible (≤₀). The extra quantified variable is encoded with Nat.pair, a computable bijection N2→N\mathbb N^2\to\mathbb NN2→N, so the classes are the usual arithmetical classes.

Definition code
import Mathlib.Computability.RE
import Mathlib.Computability.Reduce

open Encodable

namespace AutoformalisationSCI

def ArithSigma : ℕ → (ℕ → Prop) → Prop
  | 0, p => ComputablePred p
  | n + 1, p => ∃ q : ℕ → Prop, ArithSigma n (fun a => ¬ q a) ∧ ∀ a, p a ↔ ∃ b, q (Nat.pair a b)

def ArithPi (n : ℕ) (p : ℕ → Prop) : Prop := ArithSigma n (fun a => ¬ p a)

def ArithDelta (n : ℕ) (p : ℕ → Prop) : Prop := ArithSigma n p ∧ ArithPi n p

def SigmaComplete (n : ℕ) (A : Set ℕ) : Prop :=
  ArithSigma n (fun a => a ∈ A) ∧
    ∀ C : Set ℕ, ArithSigma n (fun a => a ∈ C) → (fun a => a ∈ C) ≤₀ (fun a => a ∈ A)

def PiComplete (n : ℕ) (A : Set ℕ) : Prop :=
  ArithPi n (fun a => a ∈ A) ∧
    ∀ C : Set ℕ, ArithPi n (fun a => a ∈ C) → (fun a => a ∈ C) ≤₀ (fun a => a ∈ A)

end AutoformalisationSCI
Source
A. Bastounis, F. Circelli, A. C. Hansen, Navier–Stokes lost in translation, arXiv:2610.08144 (2026), Appendix A (pp. 17–23); https://arxiv.org/abs/2610.08144. Standard background: R. I. Soare, Turing Computability, Springer 2016, Ch. 4.
Read-back

What the Lean code literally says, in plain math · claude-opus-4-8

The declaration ArithSigma is a function of a natural number nnn and a predicate p:N→Propp:\mathbb N\to\mathrm{Prop}p:N→Prop, defined by recursion on nnn. At n=0n=0n=0 it asserts ComputablePred p, i.e. that ppp has a decidable instance whose decision function is computable. At n+1n+1n+1 it asserts the existence of a predicate q:N→Propq:\mathbb N\to\mathrm{Prop}q:N→Prop such that (i) ArithSigma n (fun a => ¬ q a) holds, and (ii) for every aaa, p(a)p(a)p(a) is equivalent to the existence of bbb with q(Nat.pair(a,b))q(\mathrm{Nat.pair}(a,b))q(Nat.pair(a,b)). ArithPi n p is defined as ArithSigma n (fun a => ¬ p a). ArithDelta n p is the conjunction ArithSigma n p ∧ ArithPi n p. SigmaComplete n A (for AAA a set of naturals) is the conjunction of ArithSigma n (· ∈ A) and the statement that for every set CCC of naturals with ArithSigma n (· ∈ C), the predicate (⋅∈C)(·\in C)(⋅∈C) is many-one reducible (≤₀) to (⋅∈A)(·\in A)(⋅∈A). PiComplete n A is the same with ArithPi in place of ArithSigma. No side conditions on nnn or AAA are imposed; n=0n=0n=0 and A=∅A=\varnothingA=∅ are allowed.

Human review
  • Endorsed by Shuze Chen · Nov 21, 2026

    Confirmed by the moderator at approval.

  • Endorsed by LG · Nov 21, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me