Assuming AD, we show that all of the ordinals below $\delta _5^1$ represented by descriptions (c.f. [2], but also defined below) are cardinals. Using this analysis we also get a simple representation for the cardinal structure below $\delta _5^1$. As an application, we compute the cofinalitites of all cardinals below $\delta _5^1$.

We introduce the notion of finitary computable reducibility on equivalence relations on the domain ω. This is a weakening of the usual notion of computable reducibility, and we show it to be distinct in several ways. In particular, whereas no equivalence relation can be ${\rm{\Pi }}_{n + 2}^0$ -complete under computable reducibility, we show that, for every n, there does exist a natural equivalence relation which is ${\rm{\Pi }}_{n + 2}^0$ -complete under finitary reducibility. We also show that our hierarchy of finitary reducibilities does not collapse, and illustrate how it sharpens certain known results. Along the way, we present several new results which use computable reducibility to establish the complexity of various naturally defined equivalence relations in the arithmetical hierarchy.

Let ($\rm L$;C) be the (up to isomorphism unique) countable homogeneous structure carrying a binary branching C-relation. We study the reducts of ($\rm L$;C), i.e., the structures with domain $\rm L$ that are first-order definable in ($\rm L$;C). We show that up to existential interdefinability, there are finitely many such reducts. This implies that there are finitely many reducts up to first-order interdefinability, thus confirming a conjecture of Simon Thomas for the special case of ($\rm L$;C). We also study the endomorphism monoids of such reducts and show that they fall into four categories.

If X and Y are orthogonal hyperdefinable sets such that X is simple, then any group G interpretable in X ∪ Y has a normal hyperdefinable X-internal subgroup N such that G/N is Y-internal; N is unique up to commensurability. In order to make sense of this statement, local simplicity theory for hyperdefinable sets is developed. Moreover, a version of Schlichting’s Theorem for hyperdefinable families of commensurable subgroups is shown.

We separate many of the basic fragments of classical logic which are used in reverse constructive mathematics. A group of related Kripke and topological models is used to show that various fragments of the Weak Law of the Excluded Middle, the Limited Principle of Omniscience, and Markov’s Principle, including Weak Markov’s Principle, do not imply each other.

In this paper, we consider Foreman’s maximality principle, which says that any nontrivial forcing notion either adds a new real or collapses some cardinals. We prove the consistency of some of its consequences. We observe that it is consistent that every c.c.c. forcing adds a real and that for every uncountable regular cardinal κ, every κ-closed forcing of size 2<κ collapses some cardinal.

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 RCA0 for ${\rm{\Pi }}_1^1$ -sentences.

Let $ \le _c $ be computable the reducibility on computably enumerable equivalence relations (or ceers). We show that for every ceer R with infinitely many equivalence classes, the index sets $\left\{ {i:R_i \le _c R} \right\}$ (with R nonuniversal), $\left\{ {i:R_i \ge _c R} \right\}$, and $\left\{ {i:R_i \equiv _c R} \right\}$ are ${\rm{\Sigma }}_3^0$ complete, whereas in case R has only finitely many equivalence classes, we have that $\left\{ {i:R_i \le _c R} \right\}$ is ${\rm{\Pi }}_2^0$ complete, and $\left\{ {i:R \ge _c R} \right\}$ (with R having at least two distinct equivalence classes) is ${\rm{\Sigma }}_2^0$ complete. Next, solving an open problem from [1], we prove that the index set of the effectively inseparable ceers is ${\rm{\Pi }}_4^0$ complete. Finally, we prove that the 1-reducibility preordering on c.e. sets is a ${\rm{\Sigma }}_3^0$ complete preordering relation, a fact that is used to show that the preordering relation $ \le _c $ on ceers is a ${\rm{\Sigma }}_3^0$ complete preordering relation.

Assume V ≠ L. Then L is not E-Recursively Enumerable in any member of L via a forcing argument inspired by Friedberg [1]. This approach leads to an extension of Levy-Shoenfield absoluteness.

This paper is a contribution to the growing investigation of strong reducibilities between ${\rm{\Pi }}_2^1$ statements of second-order arithmetic, viewed as an extension of the traditional analysis of reverse mathematics. We answer several questions of Hirschfeldt and Jockusch [13] about Weihrauch (uniform) and strong computable reductions between various combinatorial principles related to Ramsey’s theorem for pairs. Among other results, we establish that the principle $SRT_2^2$ is not Weihrauch or strongly computably reducible to $D_{ < \infty }^2$, and that COH is not Weihrauch reducible to $SRT_{ < \infty }^2$, or strongly computably reducible to $SRT_2^2$. The last result also extends a prior result of Dzhafarov [9]. We introduce a number of new techniques for controlling the combinatorial and computability-theoretic properties of the problems and solutions we construct in our arguments.

We analyze the modified extender based forcing from Assaf Sharon’s PhD thesis. We show there is a bad scale in the extension and therefore weak square fails. We also present two metatheorems which give a rough characterization of when a diagonal Prikry-type forcing forces the failure of weak square.

We give an example of a pure group that does not have the independence property, whose Fitting subgroup is neither nilpotent nor definable and whose soluble radical is neither soluble nor definable. This answers a question asked by E. Jaligot in May 2013.

We classify irreducible actions of connected groups of finite Morley rank on abelian groups of Morley rank 3.

No natural principle is currently known to be strictly between the arithmetic comprehension axiom (ACA0) and Ramsey’s theorem for pairs ( $RT_2^2$ ) in reverse mathematics. The tree theorem for pairs ( $TT_2^2$ ) is however a good candidate. The tree theorem states that for every finite coloring over tuples of comparable nodes in the full binary tree, there is a monochromatic subtree isomorphic to the full tree. The principle $TT_2^2$ is known to lie between ACA0 and $RT_2^2$ over RCA0, but its exact strength remains open. In this paper, we prove that $RT_2^2$ together with weak König’s lemma (WKL0) does not imply $TT_2^2$ , thereby answering a question of Montálban. This separation is a case in point of the method of Lerman, Solomon and Towsner for designing a computability-theoretic property which discriminates between two statements in reverse mathematics. We therefore put the emphasis on the different steps leading to this separation in order to serve as a tutorial for separating principles in reverse mathematics.

The forcing theorem is the most fundamental result about set forcing, stating that the forcing relation for any set forcing is definable and that the truth lemma holds, that is everything that holds in a generic extension is forced by a condition in the relevant generic filter. We show that both the definability (and, in fact, even the amenability) of the forcing relation and the truth lemma can fail for class forcing.

In addition to these negative results, we show that the forcing theorem is equivalent to the existence of a (certain kind of) Boolean completion, and we introduce a weak combinatorial property (approachability by projections) that implies the forcing theorem to hold. Finally, we show that unlike for set forcing, Boolean completions need not be unique for class forcing.

We introduce the definability strength of combinatorial principles. In terms of definability strength, a combinatorial principle is strong if solving a corresponding combinatorial problem could help in simplifying the definition of a definable set. We prove that some consequences of Ramsey’s Theorem for colorings of pairs could help in simplifying the definitions of some ${\rm{\Delta }}_2^0$ sets, while some others could not. We also investigate some consequences of Ramsey’s Theorem for colorings of longer tuples. These results of definability strength have some interesting consequences in reverse mathematics, including strengthening of known theorems in a more uniform way and also new theorems.

M. Beiglböck, V. Bergelson, and A. Fish proved that if G is a countable amenable group and A and B are subsets of G with positive Banach density, then the product set AB is piecewise syndetic. This means that there is a finite subset E of G such that EAB is thick, that is, EAB contains translates of any finite subset of G. When G = ℤ, this was first proven by R. Jin. We prove a quantitative version of the aforementioned result by providing a lower bound on the density (with respect to a Følner sequence) of the set of witnesses to the thickness of EAB. When G = ℤd , this result was first proven by the current set of authors using completely different techniques.