A MINIMAL PAIR IN THE GENERIC DEGREES

Denis R. Hirschfeldt

Type: Article

Publication Date: 2019-11-12

Citations: 4

DOI: https://doi.org/10.1017/jsl.2019.77

Abstract

Abstract We show that there is a minimal pair in the nonuniform generic degrees, and hence also in the uniform generic degrees. This fact contrasts with Igusa’s result that there are no minimal pairs for relative generic computability and answers a basic structural question mentioned in several papers in the area.

Locations

Journal of Symbolic Logic - View
arXiv (Cornell University) - View - PDF
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Relative Recursive Enumerability of Generic Degrees : Dedicated to Victor De Sabata	1988	Masahiro Kumabe
+ PDF Chat	Nonexistence of minimal pairs for generic computability	2013	Gregory Igusa
+	Degrees of Generic Sets	1980	Carl G. Jockusch
+	Equivalence of generics	2022	Iian B. Smythe
+	Density-1-bounding and quasiminimality in the generic degrees	2015	Peter Cholak Gregory Igusa
+	On the existence of a strong minimal pair	2016	George Barmpalias Mingzhong Cai Steffen Lempp Theodore A. Slaman
+ PDF Chat	DENSITY-1-BOUNDING AND QUASIMINIMALITY IN THE GENERIC DEGREES	2017	Peter Cholak Gregory Igusa
+	Nonexistence of Minimal Pairs for Generic Computability	2012	Gregory Igusa
+	Dynamic notions of genericity and array noncomputability	1998	Benjamin Schaeffer
+	A WEAKLY 2-GENERIC WHICH BOUNDS A MINIMAL DEGREE	2019	Rodney G. Downey Satyadev Nandakumar
+	Quasiminimal pairs for c.e. degrees of generic and coarse reducibilities	2020	Alexander Rybalov
+	Strong Minimal Pairs in the Enumeration Degrees	2024	Josiah Jacobsen-Grocott
+	Minimal Degrees	1983	Manuel Lerman
+	Lowness for isomorphism and degrees of genericity	2017	Johanna N. Y. Franklin Dan Turetsky
+	A Generic m-Reducibility	2018	Alexander Rybalov
+ PDF Chat	Joining up to the generalized high degrees	2010	Philip Ellison Andrew E. M. Lewis
+	On the existence of a strong minimal pair	2016	George Barmpalias Mingzhong Cai Steffen Lempp Theodore A. Slaman
+ PDF Chat	On the existence of a strong minimal pair	2015	George Barmpalias Mingzhong Cai Steffen Lempp Theodore A. Slaman
+	Generic G-Structures	1975	Larry Clifford Lipskie
+	Incomparability in local structures of s-degrees and Q-degrees	2020	Irakli Chitaia Keng Meng Ng Andrea Sorbi Yue Yang

Works That Cite This (2)

Action	Title	Year	Authors
+	Computing sets from all infinite subsets	2021	Noam Greenberg Matthew Harrison‐Trainor Ludovic Patey Dan Turetsky
+	Computing sets from all infinite subsets	2020	Noam Greenberg Matthew Harrison‐Trainor Ludovic Patey Dan Turetsky

Works Cited by This (9)

Action	Title	Year	Authors
+ PDF Chat	THE GENERIC DEGREES OF DENSITY-1 SETS, AND A CHARACTERIZATION OF THE HYPERARITHMETIC REALS	2015	Gregory Igusa
+	Generic-case complexity, decision problems in group theory, and random walks	2003	Ilya Kapovich Alexei Myasnikov Paul E. Schupp Vladimir Shpilrain
+	Approximations to the halting problem	1974	Nancy Lynch
+ PDF Chat	Asymptotic Density and the Theory of Computability: A Partial Survey	2016	Carl G. Jockusch Paul E. Schupp
+ PDF Chat	ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS	2013	Rodney G. Downey Carl G. Jockusch Paul E. Schupp
+ PDF Chat	Dense computability, upper cones, and minimal pairs	2019	Eric P. Astor Denis R. Hirschfeldt Carl G. Jockusch
+ PDF Chat	Notions of robust information coding	2017	Damir D. Dzhafarov Gregory Igusa
+ PDF Chat	Generic computability, Turing degrees, and asymptotic density	2012	Carl G. Jockusch Paul E. Schupp
+ PDF Chat	COARSE REDUCIBILITY AND ALGORITHMIC RANDOMNESS	2016	Denis R. Hirschfeldt Carl G. Jockusch Rutger Kuyper Paul E. Schupp