Computational Prospects of Infinity
(20 Jun - 15 Aug 2005)
~ Abstracts ~
Refuting Downey's conjecture
Steffen Lempp University of Wisconsin, Madison, USA
We prove that the degree structures of the d.c.e. and the 3-c.e. Turing degrees are not elementarily equivalent, thus refuting a conjecture of Downey. More specifically, we show that the following statement fails in the former but holds in the latter structure: There are degrees f > e > d > 0 such that any degree u < f is either comparable with both e and d, or incomparable with both.
Seetapun's theorem and related
conjectures on the strength of stable Ramsey's theorem for
pairs
Carl Jockusch, University of Illinois, Urbana-Champaign,
USA
David Seetapun (see Seetapun-Slaman, Notre Dame Journal, 1995) showed that for any computable 2-coloring of [N]^2 and any non-computable sets C_0, C_1, ..., there is an infinite homogeneous set A such that no C_i is Turing reducible to A . This implied that Ramsey's Theorem for pairs (RT^2_2) is strictly weaker than Ramsey's theorem for triples over the base theory RCA_0. We give a new proof of Seetapun's Theorem by first showing the following: For any set X and any noncomputable sets C_0, C_1, ... there is an infinite set A contained in X or its complement such that no C_i is Turing reducible to A . (This latter result can be deduced from Seetapun's Theorem, but we give a simplified direct proof.) A 2-coloring of [N]^2 is called stable if for each natural number a all but finitely many pairs {a,b} have the same color. Let SRT^2_2 be the assertion that every stable 2-coloring of pairs has an infinite homogeneous set. We discuss conjectures related to the open problem of whether SRT^2_2 implies RT^2_2 in RCA_0.
Weak degrees of Pi^0_1 subsets
of 2^omega
Stephen G. Simpson, Pennsylvania State University, USA
Let P,Q subseteq 2^omega be viewed as mass problems, i.e., "decision problems with more than one solution." We say that the mass problem P is weakly reducible to the mass problem Q if, for every solution Y of Q, there exists a solution X of P such that X is Turing reducible to Y. A weak degree is an equivalence class of mass problems under mutual weak reducibility. (Weak degrees are also known as Muchnik degrees.) Let P_w be the set of weak degrees of nonempty Pi^0_1 subsets of 2^omega, partially ordered by weak reducibility. It is easy to see that P_w is a countable distributive lattice. The speaker and others have studied P_w in a series of publications beginning in 1999. Our principal findings are as follows.
1. There is a natural embedding of R_T, the countable semilattice of recursively enumerable Turing degrees, into P_w. This embedding is one-to-one and preserves the partial ordering leq, the semilattice operation v, and the top and bottom elements 0 and 0'. We identify R_T with its image in P_w under this embedding.
2. Like the semilattice R_T, the lattice P_w is structurally rich. In particular, any countable distributive lattice is lattice embeddable in any nontrivial initial segment of P_w. Also, the P_w analog of the Sacks Splitting Theorem holds. These structural results are proved by means of priority arguments. The P_w analog of the Sacks Density Theorem remains as an open problem.
3. Unlike R_T, the lattice P_w contains a large number of specific, natural degrees other than the top and bottom elements. These specific, natural degrees in P_w are related to foundationally interesting topics such as reverse mathematics, algorithmic randomness, subrecursive hierarchies from Gentzen-style proof theory, and computational complexity.
4. All of these specific, natural degrees in P_w are incomparable with all of the recursively enumerable Turing degrees in R_T. The only exceptions are 0 and 0', the top and bottom elements of R_T, which are the same as the top and bottom elements of P_w.
Reverse mathematics and Pi^1_2
comprehension
Stephen G. Simpson, Pennsylvania State University, USA
This is joint work with Carl Mummert. We initiate the reverse mathematics of general topology. We show that a certain metrization theorem is equivalent to Pi^1_2 comprehension. An MF space is defined to be a topological space of the form MF(P) with topology generated by { N_p | p in P }. Here P is a poset, MF(P) is the set of maximal filters on P, and N_p = { F in MF(P) | p in F }. If the poset P is countable, the space MF(P) is said to be \emph{countably based}. The class of countably based MF spaces can be defined and discussed within the subsystem ACA_0 of second order arithmetic. One can prove within ACA_0 that every complete separable metric space is homeomorphic to a countably based MF space which is regular. We show that the converse statement, "every countably based MF space which is regular is homeomorphic to a complete separable metric space," is equivalent to Pi^1_2-CA_0. The equivalence is proved in the weaker system Pi^1_1-CA_0. This is the first example of a theorem of core mathematics which is provable in second order arithmetic and implies Pi^1_2 comprehension.
On the problems of
definability in the enumeration degrees
Iskander Kalimullin, Kazan State University, Russia
The talk will devoted to problems of definabilty of natural classes and predicates in the ordering of enumeration degrees. In particular, it will be studied the problem on definability of the class TOT of total degrees posed by Rogers in 1967. It is already known that if we replace in this problem the class TOT by the class TOT(\ge 0') of all total enumeration degrees above 0' then the obtained problem has a positive solution. I will present new results in favour the following hypothesis for a positive solution of the original problem: an e-degree x is total iff there are no e-degrees u and a such that u<a, u<x+u, and such that each z above u is the infimum of the e-degrees a+z and x+z. It is known that the right-to-left implication of the hypothesis is correct but the reverse is still an open problem
Generalized tabular
reducibilities in infinite levels of the Ershov difference
hierarchy
Marat Arslanov, Kazan State University, Russia
It is known that finite and $\omega$ levels of the Ershov difference hierarchy are connected with bounded truth table and truth table reducibilities accordingly. In my talk I consider a collection of reducibilities which are intermediate between Turing and truth table reducibilities and have similar properties relatively to infinite levels of the Ershov hierarchy which are defined by means of limit constructive ordinals.
Weak axioms of determinacy and
subsystems of second order arithmetic
Kazuyuki Tanaka, Tohoku University, Japan
This is joint work with M. O. MedSalem. After J. Steel proved (in a certain system) that ATR_0 is necessary and sufficient for $\Sigma^0_1$-determinacy, we proved that $\Delta^0_2$-determinacy and $\Sigma^0_2$-determinacy are equivalent to $\Pi^1_1$-TR_0 and $\Sigma^1_1$-MI_0, respectively, where MI stands for monotone inductive definition. In this talk, we first deduce $\Delta^0_3$-determinacy from $\Delta^1_2$-MI_0 plus $\Pi^1_3$-transfinite induction. We then present a new axiom of inductive definitions which is equivalent to $\Delta^0_3$-determinacy.
