${\mathsf {CAC\ for\ trees}}$ is the statement asserting that any infinite subtree of $\mathbb {N}^{<\mathbb {N}}$ has an infinite path or an infinite antichain. In this paper, we study the computational strength of this theorem from a reverse mathematical viewpoint. We prove that ${\mathsf {CAC\ for\ trees}}$ is robust, that is, there exist several characterizations, some of which already appear in the literature, namely, the statement $\mathsf {SHER}$ introduced by Dorais et al. [8], and the statement $\mathsf {TAC}+\mathsf {B}\Sigma ^0_2$ (...) where $\mathsf {TAC}$ is the tree antichain theorem introduced by Conidis [6]. We show that ${\mathsf {CAC\ for\ trees}}$ is computationally very weak, in that it admits probabilistic solutions. (shrink)

We present the true stages machinery and illustrate its applications to descriptive set theory. We use this machinery to provide new proofs of the Hausdorff–Kuratowski and Wadge theorems on the structure of $\mathbf {\Delta }^0_\xi $, Louveau and Saint Raymond’s separation theorem, and Louveau’s separation theorem.

There exist two main notions of typicality in computability theory, namely, Cohen genericity and randomness. In this article, we introduce a new notion of genericity, called partition genericity, which is at the intersection of these two notions of typicality, and show that many basis theorems apply to partition genericity. More precisely, we prove that every co-hyperimmune set and every Kurtz random is partition generic, and that every partition generic set admits weak infinite subsets, for various notions of weakness. In particular, (...) we answer a question of Kjos-Hanssen and Liu by showing that every Kurtz random admits an infinite subset which does not compute any set of positive effective Hausdorff dimension. Partition genericity is a partition regular notion, so these results imply many existing pigeonhole basis theorems. (shrink)

A mass problem is a set of functions$\omega \to \omega $. For mass problems${\mathcal {C}}, {\mathcal {D}}$, one says that${\mathcal {C}}$is Muchnik reducible to${\mathcal {D}}$if each function in${\mathcal {C}}$is computed by a function in${\mathcal {D}}$. In this paper we study some highness properties of Turing oracles, which we view as mass problems. We compare them with respect to Muchnik reducibility and its uniform strengthening, Medvedev reducibility.For$p \in [0,1]$let${\mathcal {D}}(p)$be the mass problem of infinite bit sequencesy(i.e.,$\{0,1\}$-valued functions) such that for each (...) computable bit sequencex, the bit sequence$ x {\,\leftrightarrow\,} y$has asymptotic lower density at mostp(where$x {\,\leftrightarrow\,} y$has a$1$in positionniff$x(n) = y(n)$). We show that all members of this family of mass problems parameterized by a realpwith$0 p$for each computable setx. We prove that the Medvedev (and hence Muchnik) complexity of the mass problems${\mathcal {B}}(p)$is the same for all$p \in (0, 1/2)$, by showing that they are Medvedev equivalent to the mass problem of functions bounded by${2^{2}}^{n}$that are almost everywhere different from each computable function.Next, together with Joseph Miller, we obtain a proper hierarchy of the mass problems of type$\text {IOE}$: we show that for any order functiongthere exists a faster growing order function$h $such that$\text {IOE}(h)$is strictly above$\text {IOE}(g)$in the sense of Muchnik reducibility.We study cardinal characteristics in the sense of set theory that are analogous to the highness properties above. For instance,${\mathfrak {d}} (p)$is the least size of a setGof bit sequences such that for each bit sequencexthere is a bit sequenceyinGso that$\underline \rho (x {\,\leftrightarrow\,} y)>p$. We prove within ZFC all the coincidences of cardinal characteristics that are the analogs of the results above. (shrink)

The aim of this paper is to determine the logical and computational strength of instances of the Bolzano-Weierstraß principle and a weak variant of it.We show that BW is instance-wise equivalent to the weak König’s lemma for Σ01-trees . This means that from every bounded sequence of reals one can compute an infinite Σ01-0/1-tree, such that each infinite branch of it yields an accumulation point and vice versa. Especially, this shows that the degrees d ≫ 0′ are exactly those containing (...) an accumulation point for all bounded computable sequences.Let BWweak be the principle stating that every bounded sequence of real numbers contains a Cauchy subsequence . We show that BWweak is instance-wise equivalent to the cohesive principle and—using this—obtain a classification of the computational and logical strength of BWweak. Especially we show that BWweak does not solve the halting problem and does not lead to more than primitive recursive growth. Therefore it is strictly weaker than BW. We also discuss possible uses of BWweak. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim. (shrink)

Theorems of hyperarithmetic analysis occupy an unusual neighborhood in the realms of reverse mathematics and recursion-theoretic complexity. They lie above all the fixed iterations of the Turing jump but below ATR $_{0}$. There is a long history of proof-theoretic principles which are THAs. Until the papers reported on in this communication, there was only one mathematical example. Barnes, Goh, and Shore [1] analyze an array of ubiquity theorems in graph theory descended from Halin’s [9] work on rays in graphs. They (...) seem to be typical applications of ACA $_{0}$ but are actually THAs. These results answer Question 30 of Montalbán’s Open Questions in Reverse Mathematics [19] and supply several other natural principles of different and unusual levels of complexity.This work led in [25] to a new neighborhood of the reverse mathematical zoo: almost theorems of hyperarithmetic analysis. When combined with ACA $_{0}$ they are THAs but on their own are very weak. Denizens both mathematical and logical are provided. Generalizations of several conservativity classes are defined and these ATHAs as well as many other principles are shown to be conservative over RCA $_{0}$ in all these senses and weak in other recursion-theoretic ways as well. These results answer a question raised by Hirschfeldt and reported in [19] by providing a long list of pairs of principles one of which is very weak over RCA $_{0}$ but over ACA $_{0}$ is equivalent to the other which may be strong or very strong going up a standard hierarchy and at the end being stronger than full second-order arithmetic. (shrink)

We analyze three applications of Ramsey’s Theorem for 4-tuples to infinite traceable graphs and finitely generated infinite lattices using the tools of reverse mathematics. The applications in graph theory are shown to be equivalent to Ramsey’s Theorem while the application in lattice theory is shown to be provable in the weaker system RCA0.

We study complexity of the index set of countably categorical theories and Ehrenfeucht theories in finite languages.

Theorems of hyperarithmetic analysis (THAs) occupy an unusual neighborhood in the realms of reverse mathematics and recursion theoretic complexity. They lie above all the fixed (recursive) iterations of the Turing Jump but below ATR $_{0}$ (and so $\Pi _{1}^{1}$ -CA $_{0}$ or the hyperjump). There is a long history of proof theoretic principles which are THAs. Until Barnes, Goh, and Shore [ta] revealed an array of theorems in graph theory living in this neighborhood, there was only one mathematical denizen. In (...) this paper we introduce a new neighborhood of theorems which are almost theorems of hyperarithmetic analysis (ATHAs). When combined with ACA $_{0}$ they are THAs but on their own they are very weak. We generalize several conservativity classes ( $\Pi _{1}^{1}$, r- $\Pi _{2}^{1}$, and Tanaka) and show that all our examples (and many others) are conservative over RCA $_{0}$ in all these senses and weak in other recursion theoretic ways as well. We provide denizens, both mathematical and logical. These results answer a question raised by Hirschfeldt and reported in Montalbán [2011] by providing a long list of pairs of principles one of which is very weak over RCA $_{0}$ but over ACA $_{0}$ is equivalent to the other which may be strong (THA) or very strong going up a standard hierarchy and at the end being stronger than full second order arithmetic. (shrink)

We investigate what it means for a (Hausdorff, second-countable) topological group to be computable. We compare several potential definitions based on classical notions in the literature. We relate these notions with the well-established definitions of effective presentability for discrete and profinite groups, and compare our results with similar results in computable topology.

Partial combinatory algebras (pcas) are algebraic structures that serve as generalized models of computation. In this article, we study embeddings of pcas. In particular, we systematize the embeddings between relativizations of Kleene’s models, of van Oosten’s sequential computation model, and of Scott’s graph model, showing that an embedding between two relativized models exists if and only if there exists a particular reduction between the oracles. We obtain a similar result for the lambda calculus, showing in particular that it cannot be (...) embedded in Kleene’s first model. (shrink)

This article studies the complexity of decomposability of rings from the perspective of computability. Based on the equivalence between the decomposition of rings and that of the identity of rings, we propose four kinds of rings, namely, weakly decomposable rings, decomposable rings, weakly block decomposable rings, and block decomposable rings. Let R be the index set of computable rings. We study the complexity of subclasses of computable rings, showing that the index set of computable weakly decomposable rings is m-complete Σ10 (...) within R and that the index set of computable decomposable (resp., weakly block decomposable, block decomposable) rings is m-complete Σ20 within R. (shrink)

In the vertex pursuit game of cops and robbers on finite graphs, the cop has a winning strategy if and only if the graph admits a dominating order. Such graphs are called constructible in the graph theory literature. This equivalence breaks down for infinite graphs, and variants of the game have been proposed to reestablish partial connections between constructibility and being cop-win. We answer an open question of Lehner about one of these variants by giving examples of weak cop-win graphs (...) which are not constructible. We show that the index set of computable constructible graphs is Π11 hard and the index set of computable constructible locally finite graphs is Π40 hard. Finally, we give an example of a computable constructible graph for which every dominating order computes 0″. (shrink)

The main question of this article is whether there is a family closed under finite differences (i.e., if A belongs to the family and B=∗A, then B also belongs to the family) that can be enumerated by any noncomputable c.e. degree, but which cannot be enumerated computably. This question was formulated by Greenberg et al. (2020) in their recent work in which families that are closed under finite differences, close to the Slaman–Wehner families, are deeply studied.