Degrees of difficulty of generalized r.e. separating classes

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


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$



    Upload a copy of this work     Papers currently archived: 89,654

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

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

32 (#426,313)

6 months
2 (#648,997)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

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

References found in this work

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 Π01 classes.Douglas Cenzer & Peter G. Hinman - 2003 - Archive for Mathematical Logic 42 (6):583-600.

Add more references