Geometric Obstructions to Dense Sections in Many-One Reductions
Abstract
We introduce a notion of dense decidable sections for many-one reductions and show that, once the induced range remains thick, such reductions cannot target simple sets. The argument is driven by a short "pushback" lemma transferring thickness from the induced range to a computable subset of the source set under an almost-containment hypothesis. We further classify geometric mechanisms that produce sections and effective inversion bounds, using schedule-level decodability for truth-table and weak truth-table computations. Finally, we show how to weaken the thickness hypothesis (lower density) to upper density or block density, at the cost of strengthening the corresponding immunity requirement on the source set.
Fields of Study & Subjects
Computability
Logic
AI Algorithms
semigroups and automata theory
Advanced Topology and Set Theory
Publication details
- Journal / source
- Zenodo (CERN European Organization for Nuclear Research)
- Publication date
- 10 January 2026
- Language
- EN
- Document type
- Preprint