The singleton degrees of the Σ 2 0 \Sigma^{0}_{2} sets are not dense

Thomas F. Kent, Keng Meng Ng, Andrea Sorbi · 2024

Read The singleton degrees of the Σ 2 0 \Sigma^{0}_{2} sets are not dense by Thomas F. Kent, Keng Meng Ng, Andrea Sorbi (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-18991.txt.

Introduction

Thomas Kent, Keng Meng Ng, and Andrea Sorbi published this logic paper in 2024. It answers an open question raised by Cooper about a way of ranking mathematical sets by how hard they are to single out. These rankings, called singleton degrees, apply to sets at a certain level of definability. A natural hope was that the ranking has no gaps: between any two ranks, a third should always fit.

The authors show the hope fails. They construct two sets whose degrees sit directly adjacent, one forming a minimal cover of the other with nothing in between. Both sets can even be built inside the same enumeration degree, a related ranking. The result settles the density question for several connected degree systems at once. All of them are now known to have gaps.

Catalog record

CREATORThomas F. Kent, Keng Meng Ng, Andrea Sorbi
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE72 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-18991

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The singleton degrees of the Σ 2 0 \Sigma^{0}_{2} sets are not dense Thanks: The first author was partially supported by Marie Curie Incoming International Fellowship of the European Community FP6 Program under contract number MIFI-CT-2006-021702. Thanks: The second author was partially supported by the Ministry of Education, Singapore, under its Academic Research Fund Tier 2 (MOE-T2EP20222-0018). Thanks: The third author is a member of INDAM-GNSAGA Thomas F. Kent, Keng Meng Ng, Andrea Sorbi Abstract . Answering an open question raised by Cooper, we show that there exist Δ 2 0 \Delta^{0}_{2} sets D D and E E such that the singleton degree of E E is a minimal cover of the singleton degree of D D . This shows that the Σ 2 0 \Sigma^{0}_{2} singleton degrees, and the Δ 2 0 \Delta^{0}_{2} singleton degrees, are not dense (and consequently the Π 2 0 \Pi^{0}_{2} Q Q -degrees, and the Δ 2 0 \Delta^{0}_{2} Q Q -degrees, are not dense). Moreover D D and E E can be built to lie in the same enumeration degree. 2010 Mathematics Subject Classification 03D25, 03D30 1. Introduction The importance of enumeration reducibility and its degree structure has considerably grown in recent years, in the wake of several striking results, such as the first order definability of the Turing degrees inside the enumeration degrees [ 4 ] . Enumeration reducibility is a formalization of the notion of relative enumerability between sets of natural numbers, the informal idea being that a set A is enumerable relatively to a set B if there exists an algorithm which enumerates A given any enumeration of B . Formally, given sets A,B\subseteq\omega (where \omega denotes the set of natural numbers) we say that A is enumeration reducible (or, simply, e -reducible ) to B (in symbol: A\leq_{e}B ) if there exists a computably enumerable (c.e.) set \Phi such that A=\{{x:(\exists u)[\langle x,u\rangle\in\Phi\,\&\,D_{u}\subseteq B]}\}, where D_{u} is the finite set with canonical index u . (In the following, we will often identify finite sets with their canonical indices, thus writing for instance \langle x,F\rangle\in\Phi meaning that F is finite and \langle x,u\rangle\in\Phi where F=D_{u} .) We also write in this case A=\Phi(B) , thus viewing any c.e. set as an operator (called an e -operator ) from sets to sets. The structure of the e -degrees is the set of equivalence classes of the equivalence relation \equiv_{e} on sets, in which A\equiv_{e}B if and only if A\leq_{e}B and B\leq_{e}A . The e -degree of a set A will be denoted by \boldsymbol{a}=\deg_{e}(A) . An important restricted version of e -reducibility is the so-called singleton enumeration reducibility , or simply s -reducibility , which only uses e -operators \Phi subject to the restriction \langle x,F\rangle\in\Phi\Rightarrow[\textrm{$F=\emptyset$ or $F$ is a singleton}]. Any e -operator satisfying this restriction is called an s -operator. We say that a set A is s -reducible to a set B (denoted by A\leq_{s}B ) if there is an s -operator \Phi such that A=\Phi(B) . The equivalence relation originated by \leq_{s} is denoted by \equiv_{s} (where A\equiv_{s}B if A\leq_{s}B and B\leq_{s}A ), and its equivalence classes are called s -degrees : the s -degree of a set A will be denoted by \boldsymbol{a}=\deg_{s}(A) . In general, for r\in\{s,e\} we use the same symbol \leq_{r} to denote both the reducibility (i.e. the pre-ordering relation on sets) and the partial ordering relation induced by the reducibility on the r -degrees. Although s -reducibility is strictly included in e -reducibility, in most concrete examples where e -reducibility shows up in mathematics or logic, it takes the form of s -reducibility. This is probably due to the fact that \leq_{e} nicely embeds into \leq_{s} by A\leq_{e}B if and only if A^{*}\leq_{s}B^{*} , where, given a set X , we denote by X^{*} the set of all finite subsets of X , identified by their canonical indices. Interest in s -reducibility (often through its isomorphic presentation as Q -reducibility, of which we recall later the precise definition), relies also in its many applications to other sections of computability theory, to logic, and general mathematics. For instance it plays a key role in Marchenkov’s solution of Post’s Problem using Post’s methods ( [ 15 ] ); and has applications to word problems (see for instance, [ 2 , 9 ] ) and to abstract computational complexity (see for instance, [ 3 ] , [ 12 ] ). For a survey on Q -reducibility and its applications see [ 17 ] . Throughout the rest of the paper we assume to have fixed some effective listing \{{\Phi_{e}:e\in\omega}\} of the s -operators. Without loss of generality, we assume to work with uniformly computable approximations \{{\Phi_{e,s}:e,s\in\omega}\} to the s -operators such that for every e and s , \Phi_{e,0}=\emptyset , \Phi_{e,s+1}\smallsetminus\Phi_{e,s} contains at most one element, and if \langle x,F\rangle\in\Phi_{e,s} then x,\max(F)<s (where we understand \max(\emptyset)=-1 ). By [ 16 , Proposition 5] we may also assume that if \{{X_{s}}\}_{s\in\omega} is any computable sequence of finite sets then we can combine this sequence with \{{\Phi_{e,s}:s\in\omega}\} , to get a computable sequence \{{\Phi_{e}(X)[s]}\}_{s\in\omega} of finite sets, such that if \{{X_{s}}\}_{s\in\omega} is a \Sigma^{0}_{2} -approximation to a set X (i.e., X=\{{x:(\exists t)(\forall s\geq t)[x\in X_{s}]}\} )), then \{{\Phi_{e}(X)[s]}\}_{s\in\omega} is a \Sigma^{0}_{2} -approximation to the set \Phi_{e}(X) . 2. A minimal cover in the \Sigma^{0}_{2} s -degrees One of the most celebrated theorems on e -degrees is Gutteridge’s theorem [ 13 ] , stating that there is no minimal e -degree. Gutteridge’s proof works for the s -degrees as well. Thus (where we let \boldsymbol{0}_{s} denote the least s -degree, consisting of all c.e. sets) Theorem 2.1 . [ 13 ] For every s -degree \boldsymbol{a}>_{s}\boldsymbol{0}_{s} , there exists an s -degree \boldsymbol{b} such that \boldsymbol{0}_{s}<_{s}\boldsymbol{b}<_{s}\boldsymbol{a} . Proof. See [ 13 ] . See also [ 5 ] . ∎ On the other hand, another celebrated theorem concerning the e -degrees (the Cooper Density Theorem [ 6 ] ) reads that the e -degrees below the first jump \boldsymbol{0}^{\prime}_{e} are dense. (We recall that \boldsymbol{0}^{\prime}_{e}=\deg_{e}(\overline{K}) , where \overline{K} is the complement of the halting set, and the e -degrees below \boldsymbol{0}^{\prime}_{e} partition exactly the \Sigma^{0}_{2} sets.) Cooper’s Density Theorem was later improved by Lachlan and Shore [ 14 ] to show that density is shared by the e -degrees of any class of sets possessing what Lachlan and Shore call “good” approximations, see [ 14 ] : the \Sigma^{0}_{2} sets form such a class. Motivated by his theorem showing density of the \Sigma^{0}_{2} e -degrees, Cooper (see [ 7 , Question §5(e)(11)] , and [ 8 , Question 26] ) asked whether the \Sigma^{0}_{2} s -degrees are dense as well. Our Theorem 2.2 below answers that question, by showing in fact that there are \Delta^{0}_{2} s -degrees \boldsymbol{d}<_{s}\boldsymbol{e} such that the s -degree interval (\boldsymbol{d},\boldsymbol{e}) is empty, i.e. \boldsymbol{e} is a minimal cover of \boldsymbol{d} in the s -degrees. We recall that Downey, La Forte and Nies [ 10 ] showed that the c.e. Q -degrees are dense. A set A is Q -reducible to a set B (in symbols: A\leq_{Q}B ) if there exists a computable function f such that (\forall x)[x\in A\Leftrightarrow W_{f(x)}\subseteq B], where we

Read the complete text