Computational Prospects of Infinity

The following sections are included:

• CONTENTS

• FOREWORD

• PREFACE

We give an example of a subset of the recursively enumerable Turing degrees which generates the recursively enumerable degrees using meet and join but does not generate them using join alone.

This paper is mainly a survey of recent results concerning the possibility of building forcing extensions in which there is a simple definition, over the structure 〈H(ω₂), ∈〉 and without parameters, of a prescribed member of H(ω₂) or of a well-order of H(ω₂). Some of these results are in conjunction with strong forcing axioms like PFA⁺⁺ or MM, some are not. I also observe (Corollary 4.4) that the existence of certain objects of size ℵ₁ follows outright from the existence of large cardinals. This observation is motivated by an (unsuccessful) attempt to extend a PFA⁺⁺ result to one mentioning MM⁺⁺.

We discuss the use of nonstandard methods in the study of Ramsey type problems, and illustrate this with an example concerning the existence of definable solutions in models of for the combinatorial principles of Ramsey's Theorem for pairs and cohesiveness.

We show that the class of c.e. degrees that can be joined to 0' by an array computable c.e. degree properly contains the class of promptly simple degrees.

Two lowness notions in the setting of Schnorr randomness have been studied (lowness for Schnorr randomness and tests, by Terwijn and Zam-bella [19], and by Kjos-Hanssen, Stephan, and Nies [7]; and Schnorr triviality, by Downey, Griffiths and LaForte [3,4] and Franklin [6]). We introduce lowness for computable machines, which by results of Downey and Griffiths [3] is an analog of lowness for K. We show that the reals that are low for computable machines are exactly the computably traceable ones, and so this notion coincides with that of lowness for Schnorr randomness and for Schnorr tests.

Assume GCH. Let κ = ∪_n<ω κ_n, 〈k_n | n < ω〉 increasing, each κ_n is — strong witnessed by — extender E_n. We would like to force 2^κ = κ⁺³ preserving all the cardinals and without adding new bounded subsets to κ. It was done first in [2, Sec.3]. Here we present a different method of doing this. The advantage of the present construction is that the preparation forcing is split completely from the main one. This makes the presentation much simpler and likely to allow a possibility of extensions to arbitrary gaps preserving large cardinals (which was not the case in [2]).

In this paper we study constructive measure and dimension in the class of limit computable sets. We prove that the lower cone of any Turing-incomplete set in has -dimension 0, and in contrast, that although the upper cone of a noncomputable set in always has -measure 0, upper cones in have nonzero -dimension. In particular the -dimension of the Turing degree of (the Halting Problem) is 1. Finally, it is proven that the low sets do not have -measure 0, which means that they do not form a small subset of . This result has consequences for the existence of bi-immune sets.

We study the reverse mathematics and computability-theoretic strength of (stable) Ramsey's Theorem for pairs and the related principles COH and DNR. We show that implies DNR over RCA₀ but COH does not, and answer a question of Mileti by showing that every computable stable 2-coloring of pairs has an incomplete infinite homogeneous set. We also give some extensions of the latter result, and relate it to potential approaches to showing that does not imply .

Using ⋄ and large cardinals we extend results of Magidor—Malitz and Farah—Larson to obtain models correct for the existence of uncountable homogeneous sets for finite-dimensional partitions and universally Baire sets. Furthermore, we show that the constructions in this paper and its predecessor can be modified to produce a family of 2^ω₁-many such models so that no two have a stationary, costationary subset of ω₁ in common. Finally, we extend a result of Steel to show that trees on reals of height ω₁ which are coded by universally Baire sets have either an uncountable path or an absolute impediment preventing one.

We identify precisely which singular ordinals are definable by monadic second order formulae over the ordinals, assuming knowledge of the definable regular cardinals.

The classical examples of naturally occuring definable Turing ideals in are the ideals generated by the cappable, noncuppable, and non-bounding degrees. We will provide a proof for the conjecture put forward by Nies in [18], that there is a cuppable, non-bounding r.e. degree. This implies that the ideals generated by the non-bounding and/or noncuppable degrees are new, and different from the known ones.

Four classes of sets have been introduced independently by various researchers: low for K, low for ML-randomness, basis for ML-randomness and K-trivial. They are all equal. This survey serves as an introduction to these coincidence results, obtained in [25] and [11]. The focus is on providing backdoor access to the proofs.

For any rational number r, we show that there exists a set A (weak truth-table reducible to the halting problem) such that any set B weak truth-table reducible to it has effective Hausdorff dimension at most r, where A itself has dimension at least r. This implies, for any rational r, the existence of a wtt-lower cone of effective dimension r.

We construct a minimal rK-degree, continuum many, in fact. We also show that every minimal sequence, that is, a sequence with minimal rK-degree, must have very low descriptional complexity, that every minimal sequence is rK-reducible to a random sequence and that there is a random sequence with no minimal sequence rK-reducible to it.

Assuming 2^ω = 2^<κ we construct a diamond on for every cardinal λ > κ. We also construct a model in which 2^ω < 2^ω₁ holds and carries a diamond for every λ > ω₂.

Slaman and Woodin have developed and used set-theoretic methods to prove some remarkable theorems about automorphisms of, and definability in, the Turing degrees. Their methods apply to other coarser degree structures as well and, as they point out, give even stronger results for some of them. In particular, their methods can be used to show that the hyperarithmetic degrees are rigid and biinterpretable with second order arithmetic. We give a direct proof using only older coding style arguments to prove these results without any appeal to set-theoretic or metamathematical considerations. Our methods also apply to various coarser reducibilities.

Recall that is the upper semilattice of recursively enumerable Turing degrees. We consider two fundamental, classical, unresolved issues concerning . The first issue is to find a specific, natural, recursively enumerable Turing degree which is > 0 and < 0'. The second issue is to find a “smallness property” of an infinite, co-recursively enumerable set A ⊆ ω which ensures that the Turing degree is > 0 and < 0'. In order to address these issues, we embed into a slightly larger degree structure, , which is much better behaved. Namely, is the lattice of weak degrees of mass problems associated with nonempty subsets of 2^ω. We define a specific, natural embedding of into , and we present some recent and new research results.

In [5], we proved that follows from and that cannot be dropped. Nevertheless, the exact strength of was left undetermined. In this paper, we settle this problem by showing that it is equivalent to a new axiom of transfinite combinations of -inductive definitions in the presence of -transfinite induction.

The following sections are included:

• Introduction

• Preliminaries

• The main theorem

• Further results

• References

No abstract received.