Geometric Obstructions to Dense Sections in Many-One Reductions

Read full text
Authors: Joaquim Reizi Higuchi
Cited by: 0

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