Degrees of difficulty of generalized r.e. separating classes期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

Degrees of difficulty of generalized r.e. separating classes

Authors:	Douglas Cenzer Peter G Hinman

Institution:	(1) Department of Mathematics, University of Florida, 358 Little Hall, PO Box 118105, Gainesville, FL 32611-8105, USA;(2) Department of Mathematics, University of Michigan, Ann Arbor, MI, USA

Abstract:	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 ₀,...,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$ . Supported by National Science Foundation grants DMS 0554841, 0532644 and 0652732.

Keywords:	Medvedev reducibility Degrees Separating class
本文献已被 SpringerLink 等数据库收录！

设为首页 | 免责声明 | 关于勤云 | 加入收藏