We explore the complexity of Sacks’ Splitting Theorem in terms of the mind change functions associated with the members of the splits. We prove that, for any c.e. set A, there are low computably enumerable sets $A_0\sqcup A_1=A$ splitting A with $A_0$ and $A_1$ both totally $\omega ^2$-c.a. in terms of the Downey–Greenberg hierarchy, and this result cannot be improved to totally $\omega $-c.a. as shown in [9]. We also show that if cone avoidance is added then there is no level below $\varepsilon _0$ which can be used to characterize the complexity of $A_1$ and $A_2$.

We consider of constructing normal ultrafilters in extensions are here Easton support iterations of Prikry-type forcing notions. New ways presented. It turns out that, in contrast with other supports, seemingly unrelated measures or extenders can be involved here.

We study model theory of actions of finite groups on substructures of a stable structure. We give an abstract description of existentially closed actions as above in terms of invariants and PAC structures. We show that if the corresponding PAC property is first order, then the theory of such actions has a model companion. Then, we analyze some particular theories of interest (mostly various theories of fields of positive characteristic) and show that in all the cases considered the PAC property is first order.

We establish an equiconsistency between (1) weak indestructibility for all $\kappa +2$-degrees of strength for cardinals $\kappa $ in the presence of a proper class of strong cardinals, and (2) a proper class of cardinals that are strong reflecting strongs. We in fact get weak indestructibility for degrees of strength far beyond $\kappa +2$, well beyond the next inaccessible limit of measurables (of the ground model). One direction is proven using forcing and the other using core model techniques from inner model theory. Additionally, connections between weak indestructibility and the reflection properties associated with Woodin cardinals are discussed. This work is a part of my upcoming thesis [7].

A field K in a ring language $\mathcal {L}$ is finitely undecidable if $\mbox {Cons}(T)$ is undecidable for every nonempty finite $T \subseteq {\mathtt{Th}}(K; \mathcal {L})$. We extend a construction of Ziegler and (among other results) use a first-order classification of Anscombe and Jahnke to prove every NIP henselian nontrivially valued field is finitely undecidable. We conclude (assuming the NIP Fields Conjecture) that every NIP field is finitely undecidable. This work is drawn from the author’s PhD thesis [48, Chapter 3].

The notion of countable well order admits an alternative definition in terms of embeddings between initial segments. We use the framework of reverse mathematics to investigate the logical strength of this definition and its connection with Fraïssé’s conjecture, which has been proved by Laver. We also fill a small gap in Shore’s proof that Fraïssé’s conjecture implies arithmetic transfinite recursion over $\mathbf {RCA}_0$, by giving a new proof of $\Sigma ^0_2$-induction.

Given a sound first-order p-time theory T capable of formalizing syntax of first-order logic we define a p-time function $g_T$ that stretches all inputs by one bit and we use its properties to show that T must be incomplete. We leave it as an open problem whether for some T the range of $g_T$ intersects all infinite ${\mbox {NP}}$ sets (i.e., whether it is a proof complexity generator hard for all proof systems).

A propositional version of the construction shows that at least one of the following three statements is true:

1. 1. There is no p-optimal propositional proof system (this is equivalent to the non-existence of a time-optimal propositional proof search algorithm).

2. 2. $E \not \subseteq P/poly$.

3. 3. There exists function h that stretches all inputs by one bit, is computable in sub-exponential time, and its range $Rng(h)$ intersects all infinite ${\text {NP}}$ sets.

A first-order structure $\mathfrak {A}$ is called monadically stable iff every expansion of $\mathfrak {A}$ by unary predicates is stable. In this paper we give a classification of the class $\mathcal {M}$ of $\omega $-categorical monadically stable structure in terms of their automorphism groups. We prove in turn that $\mathcal {M}$ is the smallest class of structures which contains the one-element pure set, is closed under isomorphisms, and is closed under taking finite disjoint unions, infinite copies, and finite index first-order reducts. Using our classification we show that every structure in $\mathcal {M}$ is first-order interdefinable with a finitely bounded homogeneous structure. We also prove that every structure in $\mathcal {M}$ has finitely many reducts up to interdefinability, thereby confirming Thomas’ conjecture for the class $\mathcal {M}$.

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.

We discuss the role of weakly normal formulas in the theory of thorn forking, as part of a commentary on the paper [5]. We also give a counterexample to Corollary 4.2 from that paper, and in the process discuss “theories with selectors.”

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 continue investigating variants of the splitting and reaping numbers introduced in [4]. In particular, answering a question raised there, we prove the consistency of and of . Moreover, we discuss their natural generalisations $\mathfrak {s}_{\rho }$ and $\mathfrak {r}_{\rho }$ for $\rho \in (0,1)$, and show that $\mathfrak {r}_{\rho }$ does not depend on $\rho $.

Assume $G\prec H$ are groups and ${\cal A}\subseteq {\cal P}(G),\ {\cal B}\subseteq {\cal P}(H)$ are algebras of sets closed under left group translation. Under some additional assumptions we find algebraic connections between the Ellis [semi]groups of the G-flow $S({\cal A})$ and the H-flow $S({\cal B})$. We apply these results in the model theoretic context. Namely, assume G is a group definable in a model M and $M\prec ^* N$. Using weak heirs and weak coheirs we point out some algebraic connections between the Ellis semigroups $S_{ext,G}(M)$ and $S_{ext,G}(N)$. Assuming every minimal left ideal in $S_{ext,G}(N)$ is a group we prove that the Ellis groups of $S_{ext,G}(M)$ are isomorphic to closed subgroups of the Ellis groups of $S_{ext,G}(N)$.

We present sound and complete sequent calculi for the modal mu-calculus with converse modalities, aka two-way modal mu-calculus. Notably, we introduce a cyclic proof system wherein proofs can be represented as finite trees with back-edges, i.e., finite graphs. The sequent calculi incorporate ordinal annotations and structural rules for managing them. Soundness is proved with relative ease as is the case for the modal mu-calculus with explicit ordinals. The main ingredients in the proof of completeness are isolating a class of non-wellfounded proofs with sequents of bounded size, called slim proofs, and a counter-model construction that shows slimness suffices to capture all validities. Slim proofs are further transformed into cyclic proofs by means of re-assigning ordinal annotations.

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.

Orthogonality in model theory captures the idea of absence of non-trivial interactions between definable sets. We introduce a somewhat opposite notion of cohesiveness, capturing the idea of interaction among all parts of a given definable set. A cohesive set is indecomposable, in the sense that if it is internal to the product of two orthogonal sets, then it is internal to one of the two. We prove that a definable group in an o-minimal structure is a product of cohesive orthogonal subsets. If the group has dimension one, or it is definably simple, then it is itself cohesive. As an application, we show that an abelian group definable in the disjoint union of finitely many o-minimal structures is a quotient, by a discrete normal subgroup, of a direct product of locally definable groups in the single structures.

It is proved that for every positive integer n, the number of non-Tukey-equivalent directed sets of cardinality $\leq \aleph _n$ is at least $c_{n+2}$, the $(n+2)$-Catalan number. Moreover, the class $\mathcal D_{\aleph _n}$ of directed sets of cardinality $\leq \aleph _n$ contains an isomorphic copy of the poset of Dyck $(n+2)$-paths. Furthermore, we give a complete description whether two successive elements in the copy contain another directed set in between or not.

We study the possible structures which can be carried by sets which have no countable subset, but which fail to be ‘surjectively Dedekind finite’, in two possible senses, that there is surjection to $\omega $, or alternatively, that there is a surjection to a proper superset.

We introduce self-divisible ultrafilters, which we prove to be precisely those $w$ such that the weak congruence relation $\equiv _w$ introduced by Šobot is an equivalence relation on $\beta {\mathbb Z}$. We provide several examples and additional characterisations; notably we show that $w$ is self-divisible if and only if $\equiv _w$ coincides with the strong congruence relation $\mathrel {\equiv ^{\mathrm {s}}_{w}}$, if and only if the quotient $(\beta {\mathbb Z},\oplus )/\mathord {\mathrel {\equiv ^{\mathrm {s}}_{w}}}$ is a profinite group. We also construct an ultrafilter $w$ such that $\equiv _w$ fails to be symmetric, and describe the interaction between the aforementioned quotient and the profinite completion $\hat {{\mathbb Z}}$ of the integers.

We introduce and analyze a new axiomatic theory $\mathsf {CD}$ of truth. The primitive truth predicate can be applied to sentences containing the truth predicate. The theory is thoroughly classical in the sense that $\mathsf {CD}$ is not only formulated in classical logic, but that the axiomatized notion of truth itself is classical: The truth predicate commutes with all quantifiers and connectives, and thus the theory proves that there are no truth value gaps or gluts. To avoid inconsistency, the instances of the T-schema are restricted to determinate sentences. Determinateness is introduced as a further primitive predicate and axiomatized. The semantics and proof theory of $\mathsf {CD}$ are analyzed.