We construct an explicit recursive tree I whose nodes are labelled with recursively enumerable theories extending Peano arithmetic (PA). Each theory is obtained by iterating uniform reflection and adding a Rosser sentence — a true Π₁ sentence independent of the parent theory. The branching degree of the tree is controlled by a primitive recursive function that takes values 2, 3, 4, 5, 6 and is constant (=2) along the leftmost infinite path, guaranteeing that the restricted trees Iₘ (paths never exceeding degree m) are non‑empty for all m ≥ 2. We prove: 1. Π¹₁-completeness. The set I of all infinite paths through I is Π¹₁-complete. This is shown by embedding a universal Π¹₁ binary tree into I; the embedding preserves infinite paths and is effectively continuous. 2. Stratification by branching width. For each m ∈ 2, 3, 4, 5, the set Iₘ of paths that never visit a node of degree > m is Π⁰₁-complete. The hierarchy I₂ ⊊ I₃ ⊊ I₄ ⊊ I₅ ⊊ I is strict and cannot be recursively reduced. 3. Effectivity. All constructions are primitive recursive and formalisable in RCA₀; the Π¹₁-completeness proof requires ACA₀ (to handle the Π¹₁-completeness of WF). The work provides a natural proof‑theoretic realisation of a complete Π¹₁ set, stratified by a simple combinatorial parameter (branching width). It requires no transfinite ordinal notations, no Kleene's O, and only elementary recursion theory and proof theory (Rosser sentences, uniform reflection). Open problems include: whether binary branching suffices for Π¹₁-completeness (conjecture: no) ; the fine structure of absolutely undecidable sentences along all paths; generalisation to ZFC and large cardinals.
Building similarity graph...
Analyzing shared references across papers
Loading...
Daniel Osipenkov
Smolensk State University
Smolensk State University
Building similarity graph...
Analyzing shared references across papers
Loading...
Daniel Osipenkov (Fri,) studied this question.
synapsesocial.com/papers/6992b4139b75e639e9b08eab — DOI: https://doi.org/10.5281/zenodo.18629477