Richard A. Shore

Halin in 1965 proved that if a graph has n many pairwise disjoint rays for each n then it has infinitely many pairwise disjoint rays. We analyze the complexity of this and other similar results in terms of computable and proof theoretic complexity. The statement of Halin’s theorem and the construction proving it seem very much like standard versions of compactness arguments such as König’s Lemma. Those results, while not computable, are relatively simple. They only use arithmetic procedures or, equivalently, finitely many iterations of the Turing jump. We show that several Halin-type theorems are much more complicated. They are among the theorems of hyperarithmetic analysis. Such theorems imply the ability to iterate the Turing jump along any computable well ordering. Several important logical principles in this class have been extensively studied beginning with work of Kreisel, H. Friedman, Steel and others in the 1960s and 1970s. Until now, only one purely mathematical example was known. Our work provides many more and so answers Question 30 of Montalbán’s Open Questions in Reverse Mathematics in 2011. Some of these theorems including ones in Halin in 1965 are also shown to have unusual proof theoretic strength as well.

We extend the usual language of second order arithmetic to one in which we can discuss an ultrafilter over of the sets of a given model. The semantics are based on fixing a subclass of the sets in a structure for the basic language that corresponds to the intended ultrafilter. In this language we state axioms that express the notion that the subclass is an ultrafilter and additional ones that say it is idempotent or Ramsey. The axioms for idempotent ultrafilters prove, for example, Hindman's theorem and its generalizations such as the Galvin-Glazer theorem and iterated versions of these theorems (IHT and IGG). We prove that adding these axioms to IHT produce conservative extensions of ACA(0)+IHT, ACA(0)(+), ATR(0), pi(1)(2)-CAO, and pi(1)(2)-CAo for all sentences of second order arithmetic and for full Z(2) for the class of sentences pi(1)(4). We also generalize and strengthen a metamathematical result of Wang (1984) to show, for example, that any pi(1)(2) theorem for all X there exists Y Theta(X, Y) provable in ACA(0) or ACA(0)(+) there are e,k is an element of N such that ACA(0) or ACA(0)(+) proves that root x(Theta(x,Phi(e) (J((k)) (X))) where Phi(e) is the eth Turing reduction and J((k)) is the kth iterate of the Turing or Arithmetic jump, respectively. (A similar result is derived for pi(1)(3) theorems of pi(1)(1)-CA(0) and the hyperjump.).

If X₀and X₁are both generic, the theories of the degrees below X₀and X₁are the same. The same is true if both are random. We show that then-genericity orn-randomness of X do not suffice to guarantee that the degrees below X have these common theories. We also show that these two theories (for generics and randoms) are different. These results answer questions of Jockusch as well as Barmpalias, Day and Lewis.

Classical computable model theory is most naturally concerned with countable domains. There are, however, several methods – some old, some new – that have extended its basic concepts to uncountable structures. Unlike in the classical case, however, no single dominant approach has emerged, and different methods reveal different aspects of the computable content of uncountable mathematics. This book contains introductions to eight major approaches to computable uncountable mathematics: descriptive set theory; infinite time Turing machines; Blum-Shub-Smale computability; Sigma-definability; computability theory on admissible ordinals; E-recursion theory; local computability; and uncountable reverse mathematics. This book provides an authoritative and multifaceted introduction to this exciting new area of research that is still in its early stages. It is ideal as both an introductory text for graduate and advanced undergraduate students and a source of interesting new approaches for researchers in computability theory and related areas.