Abstract We investigate the class of bipartite Borel graphs organized by the order of Borel homomorphism. We show that this class is unbounded by finding a jump operator for Borel graphs analogous to a jump operator of Louveau for Borel equivalence relations. The proof relies on a nonseparation result for iterated Fréchet ideals and filters due to Debs and Saint Raymond. We give a new proof of this fact using effective descriptive set theory. We also investigate an analogue of the Friedman-Stanley jump for Borel graphs. This analogue does not yield a jump operator for bipartite Borel graphs. However, we use it to answer a question of Kechris and Marks by showing that there is a Borel graph with no Borel homomorphism to a locally countable Borel graph, but each of whose connected components has a countable Borel coloring.

Abstract This paper uses the framework of reverse mathematics to investigate the strength of two recurrence theorems of topological dynamics. It establishes that one of these theorems, the existence of an almost periodic point, lies strictly between WKL and ACA (working over RCA0). This is the first example of a theorem with this property. It also shows the existence of an almost periodic point is conservative over RCA0for ${\rm{\Pi }}_1^1$ -sentences.

Abstract An infinite binary sequence A is absolutely undecidable if it is impossible to compute A on a set of positions of positive upper density. Absolute undecidability is a weakening of bi-immunity. Downey, Jockusch and Schupp [2] asked whether, unlike the case for bi-immunity, there is an absolutely undecidable set in every non-zero Turing degree. We provide a positive answer to this question by applying techniques from coding theory. We show how to use Walsh–Hadamard codes to build a truth-table functional which maps any sequence A to a sequence B, such that given any restriction of B to a set of positive upper density, one can recover A. This implies that if A is non-computable, then B is absolutely undecidable. Using a forcing construction, we show that this result cannot be strengthened in any significant fashion.

Abstract This paper investigates indifferent sets for comeager classes in Cantor space focusing of the class of all 1-generic sets and the class of all weakly 1-generic sets. Jockusch and Posner showed that there exist 1-generic sets that have indifferent sets [10]. Figueira, Miller and Nies have studied indifferent sets for randomness and other notions [7]. We show that any comeager class in Cantor space contains a comeager class with a universal indifferent set. A forcing construction is used to show that any 1-generic set, or weakly 1-generic set, has an indifferent set. Such an indifferent set can by computed by any set in which bounds the (weakly) 1-generic. We show by approximation arguments that some, but not all, 1-generic sets can compute an indifferent set for themselves. We show that all weakly 1-generic sets can compute an indifferent set for themselves. Additional results on indifferent sets, including one of Miller, and two of Fitzgerald, are presented.

In this paper we seek to analyze the relationship between two different ways of understanding the intrinsic algorithmic randomness of strings and real numbers. In the setting of discrete spaces, a cornerstone of the theory of prefix-free Kolmogorov complexity is the coding theorem. This theorem states that the negative logarithm of the probability that a string is the output of a universal prefix-free machine coincides, within some additive constant, with the length of its shortest description. It has been suggested that this ties two fundamental principles together: Bayes' theorem and Occam's razor. Certainly, the result lends support to the belief that prefix-free complexity is a natural measure of the algorithmic randomness of strings.