Degrees of difficulty of generalized r.e. separating classes

Archive for Mathematical Logic 46 (7-8):629-647 (2008)

Important examples of $\Pi^0_1$ classes of functions $f \in {}^\omega\omega$ are the classes of sets (elements of ω 2) which separate a given pair of disjoint r.e. sets: ${\mathsf S}_2(A_0, A_1) := \{f \in{}^\omega2 : (\forall i < 2)(\forall x \in A_i)f(x) \neq i\}$ . A wider class consists of the classes of functions f ∈ ω k which in a generalized sense separate a k-tuple of r.e. sets (not necessarily pairwise disjoint) for each k ∈ ω: ${\mathsf S}_k(A_0,\ldots,A_k-1) := \{f \in {}^\omega k : (\forall i < k) (\forall x \in A_i) f(x) \neq i\}$ . We study the structure of the Medvedev degrees of such classes and show that the set of degrees realized depends strongly on both k and the extent to which the r.e. sets intersect. Let ${\mathcal S}^m_k$ denote the Medvedev degrees of those ${\mathsf S}_k(A_0,\ldots,A_{k-1})$ such that no m + 1 sets among A 0,...,A k-1 have a nonempty intersection. It is shown that each ${\mathcal S}^m_k$ is an upper semi-lattice but not a lattice. The degree of the set of k-ary diagonally nonrecursive functions $\mathsf{DNR}_k$ is the greatest element of ${\mathcal S}^1_k$ . If 2 ≤ l < k, then 0 M is the only degree in ${\mathcal S}^1_l$ which is below a member of ${\mathcal S}^1_k$ . Each ${\mathcal S}^m_k$ is densely ordered and has the splitting property and the same holds for the lattice ${\mathcal L}^m_k$ it generates. The elements of ${\mathcal S}^m_k$ are exactly the joins of elements of ${\mathcal S}^1_i$ for $\lceil{k \over m}\rceil \leq i \leq k$
Keywords Medvedev reducibility  Degrees  Separating class
Categories (categorize this paper)
DOI 10.1007/s00153-007-0058-y
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 49,128
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Mass Problems and Randomness.Stephen G. Simpson - 2005 - Bulletin of Symbolic Logic 11 (1):1-27.
A Splitting Theorem for the Medvedev and Muchnik Lattices.Stephen Binns - 2003 - Mathematical Logic Quarterly 49 (4):327.
Density of the Medvedev Lattice of Π0 1 Classes.Douglas Cenzer & Peter G. Hinman - 2003 - Archive for Mathematical Logic 42 (6):583-600.
Density of the Medvedev Lattice of Π [Sup0][Sub1].Douglas Cenzer & Peter G. Hinman - 2003 - Archive for Mathematical Logic 42 (6):583-600.

Add more references

Citations of this work BETA

A Survey of Mučnik and Medvedev Degrees.Peter G. Hinman - 2012 - Bulletin of Symbolic Logic 18 (2):161-229.
Shift-Complex Sequences.Mushfeq Khan - 2013 - Bulletin of Symbolic Logic 19 (2):199-215.

Add more citations

Similar books and articles

Density of the Medvedev Lattice of Π0 1 Classes.Douglas Cenzer & Peter G. Hinman - 2003 - Archive for Mathematical Logic 42 (6):583-600.
Embedding FD(Ω) Into {Mathcal{P}_s} Densely.Joshua A. Cole - 2008 - Archive for Mathematical Logic 46 (7-8):649-664.
Goodness in the Enumeration and Singleton Degrees.Charles M. Harris - 2010 - Archive for Mathematical Logic 49 (6):673-691.
Mass Problems and Intuitionism.Stephen G. Simpson - 2008 - Notre Dame Journal of Formal Logic 49 (2):127-136.
The Medvedev Lattice of Computably Closed Sets.Sebastiaan A. Terwijn - 2006 - Archive for Mathematical Logic 45 (2):179-190.
Partitions of Large Rado Graphs.M. Džamonja, J. A. Larson & W. J. Mitchell - 2009 - Archive for Mathematical Logic 48 (6):579-606.
Some Remarks on Category of the Real Line.Kyriakos Keremedis - 1999 - Archive for Mathematical Logic 38 (3):153-162.
Around Splitting and Reaping for Partitions of Ω.Hiroaki Minami - 2010 - Archive for Mathematical Logic 49 (4):501-518.
Degrees of Unsolvability of Continuous Functions.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (2):555 - 584.
Bounded Enumeration Reducibility and its Degree Structure.Daniele Marsibilio & Andrea Sorbi - 2012 - Archive for Mathematical Logic 51 (1-2):163-186.


Added to PP index

Total views
29 ( #330,488 of 2,311,514 )

Recent downloads (6 months)
1 ( #753,566 of 2,311,514 )

How can I increase my downloads?


My notes

Sign in to use this feature