Some variants of function domination
math.LO
Submitted: 2026-11-01
Updated: 2026-11-01
License: http://creativecommons.org/licenses/by/4.0/
The gist: We investigate whether classical recursion-theoretic notions defined by function domination remain unchanged when success is required only on sets of prescribed asymptotic density.
Terminology
Abstract
We investigate whether classical recursion-theoretic notions defined by function domination remain unchanged when success is required only on sets of prescribed asymptotic density. We establish robustness for many such notions and uncover unexpected connections between familiar degree properties by comparing upper and lower density. In contrast, pdomination, as defined by Chong, Hoi, Stephan and Turetsky, is not robust under density weakenings. We also answer a question of Kjos-Hanssen and Nies by characterizing superhighness as domination with a threshold boundedly limit recursive in the oracle. As an application, we introduce supermaximal sets, a strengthening of maximality whose degrees are exactly the superhigh r.e. degrees.
Related papers
- The consistency strength of the failure of amenable C-sequences
- Classification of bipartite observables III: simplicity, mixtures and quantum error correction
- The Additive Arithmetic of Linear Orders
- Indiscernible Extraction in Theories with Bounded k-splitting
- Measuring the Complexity of Countable Presburger Models
- A non-trivially non-trivial automorphism at an inaccessible cardinal