There is a Turing functional $\Phi $ taking $A^\prime $ to a theory $T_A$ whose complexity is exactly that of the jump of A, and which has the property that $A \leq _T B$ if and only if $T_A \trianglelefteq T_B$ in Keisler’s order. In fact, by more elaborate means and related theories, we may keep the complexity at the level of A without using the jump.

We refine results of Gannon [6, Theorem 4.7] and Simon [22, Lemma 2.8] on convergence of Morley sequences. We then introduce the notion of eventual$NIP$, as a property of a model, and prove a variant of [15, Corollary 2.2]. Finally, we give new characterizations of generically stable types (for countable theories) and reinforce the main result of Pillay [17] on the model-theoretic meaning of Grothendieck’s double limit theorem.

The Halpern–Läuchli theorem, a combinatorial result about trees, admits an elegant proof due to Harrington using ideas from forcing. In an attempt to distill the combinatorial essence of this proof, we isolate various partition principles about products of perfect Polish spaces. These principles yield straightforward proofs of the Halpern–Läuchli theorem, and the same forcing from Harrington’s proof can force their consistency. We also show that these principles are not ZFC theorems by showing that they put lower bounds on the size of the continuum.

1. (1) We show that it is possible to add $\kappa ^+$-Cohen subsets to $\kappa $ with a Prikry forcing over $\kappa $. This answers a question from [9].

2. (2) A strengthening of non-Galvin property is introduced. It is shown to be consistent using a single measurable cardinal which improves a previous result by S. Garti, S. Shelah, and the first author [5].

3. (3) A situation with Extender-based Prikry forcings is examined. This relates to a question of H. Woodin.

We can measure the complexity of a logical formula by counting the number of alternations between existential and universal quantifiers. Suppose that an elementary first-order formula $\varphi $ (in $\mathcal {L}_{\omega ,\omega }$) is equivalent to a formula of the infinitary language $\mathcal {L}_{\infty ,\omega }$ with n alternations of quantifiers. We prove that $\varphi $ is equivalent to a finitary formula with n alternations of quantifiers. Thus using infinitary logic does not allow us to express a finitary formula in a simpler way.

We investigate a recently devised polyhedral semantics for intermediate logics, in which formulas are interpreted in n-dimensional polyhedra. An intermediate logic is polyhedrally complete if it is complete with respect to some class of polyhedra. The first main result of this paper is a necessary and sufficient condition for the polyhedral completeness of a logic. This condition, which we call the Nerve Criterion, is expressed in terms of Alexandrov’s notion of the nerve of a poset. It affords a purely combinatorial characterisation of polyhedrally complete logics. Using the Nerve Criterion we show, easily, that there are continuum many intermediate logics that are not polyhedrally complete but which have the finite model property. We also provide, at considerable combinatorial labour, a countably infinite class of logics axiomatised by the Jankov–Fine formulas of ‘starlike trees’ all of which are polyhedrally complete. The polyhedral completeness theorem for these ‘starlike logics’ is the second main result of this paper.

We consider several variants of Keisler’s isomorphism theorem. We separate these variants by showing implications between them and cardinal invariants hypotheses. We characterize saturation hypotheses that are stronger than Keisler’s theorem with respect to models of size $\aleph _1$ and $\aleph _0$ by $\mathrm {CH}$ and $\operatorname {cov}(\mathsf {meager}) = \mathfrak {c} \land 2^{<\mathfrak {c}} = \mathfrak {c}$ respectively. We prove that Keisler’s theorem for models of size $\aleph _1$ and $\aleph _0$ implies $\mathfrak {b} = \aleph _1$ and $\operatorname {cov}(\mathsf {null}) \le \mathfrak {d}$ respectively. As a consequence, Keisler’s theorem for models of size $\aleph _0$ fails in the random model. We also show that for Keisler’s theorem for models of size $\aleph _1$ to hold it is not necessary that $\operatorname {cov}(\mathsf {meager})$ equals $\mathfrak {c}$.

Working toward showing the decidability of the $\forall \exists $-theory of the ${\Sigma ^0_2}$-enumeration degrees, we prove that no so-called Ahmad pair of ${\Sigma ^0_2}$-enumeration degrees can join to ${\mathbf 0}_e'$.

We study the position of the computable setting in the “common theory of locality” developed in [4, 5] for local problems on $\Delta $-regular trees, $\Delta \in \omega $. We show that such a problem admits a computable solution on every highly computable $\Delta $-regular forest if and only if it admits a Baire measurable solution on every Borel $\Delta $-regular forest. We also show that if such a problem admits a computable solution on every computable maximum degree $\Delta $ forest then it admits a continuous solution on every maximum degree $\Delta $ Borel graph with appropriate topological hypotheses, though the converse does not hold.

The Friedman–Stanley jump, extensively studied by descriptive set theorists, is a fundamental tool for gauging the complexity of Borel isomorphism relations. This paper focuses on a natural computable analog of this jump operator for equivalence relations on $\omega $, written ${\dotplus }$, recently introduced by Clemens, Coskey, and Krakoff. We offer a thorough analysis of the computable Friedman–Stanley jump and its connections with the hierarchy of countable equivalence relations under the computable reducibility $\leq _c$. In particular, we show that this jump gives benchmark equivalence relations going up the hyperarithmetic hierarchy and we unveil the complicated highness hierarchy that arises from ${\dotplus }$.

Assuming the existence of a monster model, tameness, and continuity of nonsplitting in an abstract elementary class (AEC), we extend known superstability results: let $\mu>\operatorname {LS}(\mathbf {K})$ be a regular stability cardinal and let $\chi $ be the local character of $\mu $-nonsplitting. The following holds:

1. 1. When $\mu $-nonforking is restricted to $(\mu ,\geq \chi )$-limit models ordered by universal extensions, it enjoys invariance, monotonicity, uniqueness, existence, extension, and continuity. It also has local character $\chi $. This generalizes Vasey’s result [37, Corollary 13.16] which assumed $\mu $-superstability to obtain same properties but with local character $\aleph _0$.

2. 2. There is $\lambda \in [\mu ,h(\mu ))$ such that if $\mathbf {K}$ is stable in every cardinal between $\mu $ and $\lambda $, then $\mathbf {K}$ has $\mu $-symmetry while $\mu $-nonforking in (1) has symmetry. In this case:

   1. (a) $\mathbf {K}$ has the uniqueness of $(\mu ,\geq \chi )$-limit models: if $M_1,M_2$ are both $(\mu ,\geq \chi )$-limit over some $M_0\in K_{\mu }$, then $M_1\cong _{M_0}M_2$;

   2. (b) any increasing chain of $\mu ^+$-saturated models of length $\geq \chi $ has a $\mu ^+$-saturated union. These generalize [31] and remove the symmetry assumption in [10, 38] .

Under $(<\mu )$-tameness, the conclusions of (1), (2)(a)(b) are equivalent to $\mathbf {K}$ having the $\chi $-local character of $\mu $-nonsplitting.

Grossberg and Vasey [18, 38] gave eventual superstability criteria for tame AECs with a monster model. We remove the high cardinal threshold and reduce the cardinal jump between equivalent superstability criteria. We also add two new superstability criteria to the list: a weaker version of solvability and the boundedness of the U-rank.

We study for each computably bounded $\Pi ^0_1$ class P the set of degrees of c.e. paths in P. We show, amongst other results, that for every c.e. degree a there is a perfect $\Pi ^0_1$ class where all c.e. members have degree a. We also show that every $\Pi ^0_1$ set of c.e. indices is realized in some perfect $\Pi ^0_1$ class, and classify the sets of c.e. degrees which can be realized in some $\Pi ^0_1$ class as exactly those with a computable representation.