We survey the theory of Mucnik and Medvedev degrees of subsets of $^{\omega}{\omega}$with particular attention to the degrees of $\Pi_{1}^{0}$ subsets of $^{\omega}2$. Sections 1-6 present the major definitions and results in a uniform notation. Sections 7-6 present proofs, some more complete than others, of the major results of the subject together with much of the required background material.

The partial ordering of Medvedev reducibility restricted to the family of Π0 1 classes is shown to be dense. For two disjoint computably enumerable sets, the class of separating sets is an important example of a Π0 1 class, which we call a ``c.e. separating class''. We show that there are no non-trivial meets for c.e. separating classes, but that the density theorem holds in the sublattice generated by the c.e. separating classes.

Abstract.The partial ordering of Medvedev reducibility restricted to the family of Π01 classes is shown to be dense. For two disjoint computably enumerable sets, the class of separating sets is an important example of a Π01 class, which we call a ``c.e. separating class''. We show that there are no non-trivial meets for c.e. separating classes, but that the density theorem holds in the sublattice generated by the c.e. separating classes.

Thirty-two years ago W. V. Quine proposed a definition of 'logical truth' that has been widely repeated and reprinted. Quine himself seems to have recognized that this definition is wrong in detail; in section 1 we eliminate this fault. What has perhaps been less widely observed is that, in abandoning the model-theoretic account of logical truth in favor of a "substitutional" account, Quine's definition swells the ranks of the logical truths and makes the classification of a sentence as a logical (...) truth dependent both on the interpretation of its extralogical words and on the extralogical vocabulary available in the language. (shrink)

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$. (shrink)

A result of Soare and Stob asserts that for any non-recursive r.e. setC, there exists a r.e.[C] setA such thatA⊕C is not of r.e. degree. A setY is called [of]m-REA (m-REA[C] [degree] iff it is [Turing equivalent to] the result of applyingm-many iterated ‘hops’ to the empty set (toC), where a hop is any function of the formX→X ⊕W e X . The cited result is the special casem=0,n=1 of our Theorem. Form=0,1, and any (m+1)-REA setC, ifC is not ofm-REA (...) degree, then for alln there exists an-r.e.[C] setA such thatA ⊕C is not of (m+n)-REA degree. We conjecture that this holds also form≥2. (shrink)

Provability, Computability and Reflection.

Gert H. Müller The growth of the number of publications in almost all scientific areas,· as in the area of (mathematical) logic, is taken as a sign of our scientifically minded culture, but it also has a terrifying aspect. In addition, given the rapidly growing sophistica tion, specialization and hence subdivision of logic, researchers, students and teachers may have a hard time getting an overview ofthe existing literature, partic ularly if they do not have an extensive library available in their (...) neighbourhood: they simply do not even know what to ask for! More specifically, if someone vaguely knows that something vaguely connected with his interests exists some where in the literature, he may not be able to find it even by searching through the publications scattered in the review journals. Answering this challenge was and is the central motivation for compiling this Bibliography. The Bibliography comprises (presently) the following six volumes (listed with the corresponding Editors): I. Classical Logic W. Rautenberg II. Non-c1assical Logics W. Rautenberg IH. Model Theory H. -D. Ebbinghaus IV. Recursion Theory P. G. Hinman V. Set Theory A. R. Blass VI. ProofTheory; Constructive Mathematics J. E. Kister; D. van Dalen & A. S. Troelstra. (shrink)

The partial order structure of degrees of unsolvability represented by continuous type-2 functionals is a proper extension of the partial order structure of type-1 degrees.