Results for '03D30'

23 found
Order:
  1.  21
    Computable Reducibility of Equivalence Relations and an Effective Jump Operator.John D. Clemens, Samuel Coskey & Gianni Krakoff - forthcoming - Journal of Symbolic Logic:1-22.
    We introduce the computable FS-jump, an analog of the classical Friedman–Stanley jump in the context of equivalence relations on the natural numbers. We prove that the computable FS-jump is proper with respect to computable reducibility. We then study the effect of the computable FS-jump on computably enumerable equivalence relations (ceers).
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  2.  14
    Weihrauch Goes Brouwerian.Vasco Brattka & Guido Gherardi - 2020 - Journal of Symbolic Logic 85 (4):1614-1653.
    We prove that the Weihrauch lattice can be transformed into a Brouwer algebra by the consecutive application of two closure operators in the appropriate order: first completion and then parallelization. The closure operator of completion is a new closure operator that we introduce. It transforms any problem into a total problem on the completion of the respective types, where we allow any value outside of the original domain of the problem. This closure operator is of interest by itself, as it (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  3.  14
    On the Uncountability Of.Dag Normann & Sam Sanders - 2022 - Journal of Symbolic Logic 87 (4):1474-1521.
    Cantor’s first set theory paper (1874) establishes the uncountability of ${\mathbb R}$. We study this most basic mathematical fact formulated in the language of higher-order arithmetic. In particular, we investigate the logical and computational properties of ${\mathsf {NIN}}$ (resp. ${\mathsf {NBI}}$ ), i.e., the third-order statement there is no injection resp. bijection from $[0,1]$ to ${\mathbb N}$. Working in Kohlenbach’s higher-order Reverse Mathematics, we show that ${\mathsf {NIN}}$ and ${\mathsf {NBI}}$ are hard to prove in terms of (conventional) comprehension axioms, (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  4.  22
    On the Structure of Computable Reducibility on Equivalence Relations of Natural Numbers.Uri Andrews, Daniel F. Belin & Luca San Mauro - 2023 - Journal of Symbolic Logic 88 (3):1038-1063.
    We examine the degree structure $\operatorname {\mathrm {\mathbf {ER}}}$ of equivalence relations on $\omega $ under computable reducibility. We examine when pairs of degrees have a least upper bound. In particular, we show that sufficiently incomparable pairs of degrees do not have a least upper bound but that some incomparable degrees do, and we characterize the degrees which have a least upper bound with every finite equivalence relation. We show that the natural classes of finite, light, and dark degrees are (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  5.  11
    The wadge order on the Scott domain is not a well-quasi-order.Jacques Duparc & Louis Vuilleumier - 2020 - Journal of Symbolic Logic 85 (1):300-324.
    We prove that the Wadge order on the Borel subsets of the Scott domain is not a well-quasi-order, and that this feature even occurs among the sets of Borel rank at most 2. For this purpose, a specific class of countable 2-colored posets$\mathbb{P}_{emb} $equipped with the order induced by homomorphisms is embedded into the Wadge order on the$\Delta _2^0 $-degrees of the Scott domain. We then show that$\mathbb{P}_{emb} $admits both infinite strictly decreasing chains and infinite antichains with respect to this (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  6.  10
    Degrees of randomized computability.Rupert Hölzl & Christopher P. Porter - 2022 - Bulletin of Symbolic Logic 28 (1):27-70.
    In this survey we discuss work of Levin and V’yugin on collections of sequences that are non-negligible in the sense that they can be computed by a probabilistic algorithm with positive probability. More precisely, Levin and V’yugin introduced an ordering on collections of sequences that are closed under Turing equivalence. Roughly speaking, given two such collections $\mathcal {A}$ and $\mathcal {B}$, $\mathcal {A}$ is below $\mathcal {B}$ in this ordering if $\mathcal {A}\setminus \mathcal {B}$ is negligible. The degree structure associated (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  7.  12
    On Robust Theorems Due to Bolzano, Weierstrass, Jordan, and Cantor.Dag Normann & Sam Sanders - forthcoming - Journal of Symbolic Logic:1-51.
    Reverse Mathematics (RM hereafter) is a program in the foundations of mathematics where the aim is to identify theminimalaxioms needed to prove a given theorem from ordinary, i.e., non-set theoretic, mathematics. This program has unveiled surprising regularities: the minimal axioms are very oftenequivalentto the theorem over thebase theory, a weak system of ‘computable mathematics’, while most theorems are either provable in this base theory, or equivalent to one of onlyfourlogical systems. The latter plus the base theory are called the ‘Big (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  8.  6
    Regainingly Approximable Numbers and Sets.Peter Hertling, Rupert Hölzl & Philip Janicki - forthcoming - Journal of Symbolic Logic.
    We call an $\alpha \in \mathbb {R}$ regainingly approximable if there exists a computable nondecreasing sequence $(a_n)_n$ of rational numbers converging to $\alpha $ with $\alpha - a_n n}$ for infinitely many n. Similarly, there exist regainingly approximable sets whose initial segment complexity infinitely often reaches the maximum possible for c.e. sets. Finally, there is a uniform algorithm splitting regular real numbers into two regainingly approximable numbers that are still regular.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  9.  46
    Isolation and the high/low hierarchy.Shamil Ishmukhametov & Guohua Wu - 2002 - Archive for Mathematical Logic 41 (3):259-266.
    Say that a d.c.e. degree d is isolated by a c.e. degree b, if bMathematics Subject Classification (2000): 03D25, 03D30, 03D35 RID=""ID="" Key words or phrases: Computably (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  10.  33
    A cohesive set which is not high.Carl Jockusch & Frank Stephan - 1993 - Mathematical Logic Quarterly 39 (1):515-530.
    We study the degrees of unsolvability of sets which are cohesive . We answer a question raised by the first author in 1972 by showing that there is a cohesive set A whose degree a satisfies a' = 0″ and hence is not high. We characterize the jumps of the degrees of r-cohesive sets, and we show that the degrees of r-cohesive sets coincide with those of the cohesive sets. We obtain analogous results for strongly hyperimmune and strongly hyperhyperimmune sets (...)
    Direct download  
     
    Export citation  
     
    Bookmark   27 citations  
  11.  23
    A variant of the Notion of Semicreative set.Heinrich Rolletschek - 1993 - Mathematical Logic Quarterly 39 (1):33-46.
    This paper introduces the notion of cW10-creative set, which strengthens that of semicreative set in a similar way as complete creativity strengthens creativity. Two results are proven, both of which imply that not all semicreative sets are cW10-creative. First, it is shown that semicreative Dedekind cuts cannot be cW10-creative; the existence of semicreative Dedekind cuts was shown by Soare. Secondly, it is shown that if A ⊕ B, the join of A and B, is cW10-creative, then either A or B (...)
    Direct download  
     
    Export citation  
     
    Bookmark  
  12.  52
    The algebraic structure of the isomorphic types of tally, polynomial time computable sets.Yongge Wang - 2002 - Archive for Mathematical Logic 41 (3):215-244.
    We investigate the polynomial time isomorphic type structure of (the class of tally, polynomial time computable sets). We partition P T into six parts: D −, D^ − , C, S, F, F^, and study their p-isomorphic properties separately. The structures of , , and are obvious, where F, F^, and C are the class of tally finite sets, the class of tally co-finite sets, and the class of tally bi-dense sets respectively. The following results for the structures of and (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  13.  43
    On Σ1 1 equivalence relations over the natural numbers.Ekaterina B. Fokina & Sy-David Friedman - 2012 - Mathematical Logic Quarterly 58 (1-2):113-124.
    We study the structure of Σ11 equivalence relations on hyperarithmetical subsets of ω under reducibilities given by hyperarithmetical or computable functions, called h-reducibility and FF-reducibility, respectively. We show that the structure is rich even when one fixes the number of properly equation imagei.e., Σ11 but not equation image equivalence classes. We also show the existence of incomparable Σ11 equivalence relations that are complete as subsets of ω × ω with respect to the corresponding reducibility on sets. We study complete Σ11 (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  14.  29
    Pa Relative to an Enumeration Oracle.G. O. H. Jun Le, Iskander Sh Kalimullin, Joseph S. Miller & Mariya I. Soskova - 2023 - Journal of Symbolic Logic 88 (4):1497-1525.
    Recall that B is PA relative to A if B computes a member of every nonempty $\Pi ^0_1(A)$ class. This two-place relation is invariant under Turing equivalence and so can be thought of as a binary relation on Turing degrees. Miller and Soskova [23] introduced the notion of a $\Pi ^0_1$ class relative to an enumeration oracle A, which they called a $\Pi ^0_1{\left \langle {A}\right \rangle }$ class. We study the induced extension of the relation B is PA relative (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  15.  23
    Maximal Towers and Ultrafilter Bases in Computability Theory.Steffen Lempp, Joseph S. Miller, André Nies & Mariya I. Soskova - 2023 - Journal of Symbolic Logic 88 (3):1170-1190.
    The tower number ${\mathfrak t}$ and the ultrafilter number $\mathfrak {u}$ are cardinal characteristics from set theory. They are based on combinatorial properties of classes of subsets of $\omega $ and the almost inclusion relation $\subseteq ^*$ between such subsets. We consider analogs of these cardinal characteristics in computability theory.We say that a sequence $(G_n)_{n \in {\mathbb N}}$ of computable sets is a tower if $G_0 = {\mathbb N}$, $G_{n+1} \subseteq ^* G_n$, and $G_n\smallsetminus G_{n+1}$ is infinite for each n. (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  16.  12
    On the bounded quasi‐degrees of c.e. sets.Roland Sh Omanadze - 2013 - Mathematical Logic Quarterly 59 (3):238-246.
  17.  6
    Effective Concept Classes of PAC and PACi Incomparable Degrees, Joins and Embedding of Degrees.Dodamgodage Gihanee M. Senadheera - 2023 - Bulletin of Symbolic Logic 29 (2):298-299.
    The Probably Approximately Correct (PAC) learning is a machine learning model introduced by Leslie Valiant in 1984. The PACi reducibility refers to the PAC reducibility independent of size and computation time. This reducibility in PAC learning resembles the reducibility in Turing computability. The ordering of concept classes under PAC reducibility is nonlinear, even when restricted to particular concrete examples.Due to the resemblance to Turing Reducibility, we suspected that there could be incomparable PACi and PAC degrees for the PACi and PAC (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  18.  4
    Investigating the Computable Friedman–Stanley Jump.Uri Andrews & Luca San Mauro - forthcoming - Journal of Symbolic Logic:1-27.
    The Friedman–Stanley jump, extensively studied by descriptive set theorists, is a fundamental tool for gauging the complexity of Borel isomorphism relations. This paper focuses on a natural computable analog of this jump operator for equivalence relations on $\omega $, written ${\dotplus }$, recently introduced by Clemens, Coskey, and Krakoff. We offer a thorough analysis of the computable Friedman–Stanley jump and its connections with the hierarchy of countable equivalence relations under the computable reducibility $\leq _c$. In particular, we show that this (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  19.  16
    Expanding the Reals by Continuous Functions Adds No Computational Power.Uri Andrews, Julia F. Knight, Rutger Kuyper, Joseph S. Miller & Mariya I. Soskova - 2023 - Journal of Symbolic Logic 88 (3):1083-1102.
    We study the relative computational power of structures related to the ordered field of reals, specifically using the notion of generic Muchnik reducibility. We show that any expansion of the reals by a continuous function has no more computing power than the reals, answering a question of Igusa, Knight, and Schweber [7]. On the other hand, we show that there is a certain Borel expansion of the reals that is strictly more powerful than the reals and such that any Borel (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  20.  10
    Initial Segments of the Degrees of Ceers.Uri Andrews & Andrea Sorbi - 2022 - Journal of Symbolic Logic 87 (3):1260-1282.
    It is known that every non-universal self-full degree in the structure of the degrees of computably enumerable equivalence relations (ceers) under computable reducibility has exactly one strong minimal cover. This leaves little room for embedding wide partial orders as initial segments using self-full degrees. We show that considerably more can be done by staying entirely inside the collection of non-self-full degrees. We show that the poset can be embedded as an initial segment of the degrees of ceers with infinitely many (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  21.  12
    The Discontinuity Problem.Vasco Brattka - 2023 - Journal of Symbolic Logic 88 (3):1191-1212.
    Matthias Schröder has asked the question whether there is a weakest discontinuous problem in the topological version of the Weihrauch lattice. Such a problem can be considered as the weakest unsolvable problem. We introduce the discontinuity problem, and we show that it is reducible exactly to the effectively discontinuous problems, defined in a suitable way. However, in which sense this answers Schröder’s question sensitively depends on the axiomatic framework that is chosen, and it is a positive answer if we work (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  22.  6
    Low sets without subsets of higher many-one degree.Patrizio Cintioli - 2011 - Mathematical Logic Quarterly 57 (5):517-523.
    Given a reducibility ⩽r, we say that an infinite set A is r-introimmune if A is not r-reducible to any of its subsets B with |A\B| = ∞. We consider the many-one reducibility ⩽m and we prove the existence of a low1 m-introimmune set in Π01 and the existence of a low1 bi-m-introimmune set.
    Direct download  
     
    Export citation  
     
    Bookmark  
  23.  7
    On Cupping and Ahmad Pairs.Iskander Sh Kalimullin, Steffen Lempp, N. G. Keng Meng & Mars M. Yamaleev - forthcoming - Journal of Symbolic Logic:1-12.
    Working toward showing the decidability of the $\forall \exists $ -theory of the ${\Sigma ^0_2}$ -enumeration degrees, we prove that no so-called Ahmad pair of ${\Sigma ^0_2}$ -enumeration degrees can join to ${\mathbf 0}_e'$.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark