Here, we present a category ${\mathbf {pEff}}$ which can be considered a predicative variant of Hyland's Effective Topos ${{\mathbf {Eff} }}$ for the following reasons. First, its construction is carried in Feferman’s predicative theory of non-iterative fixpoints ${{\widehat {ID_1}}}$ . Second, ${\mathbf {pEff}}$ is a list-arithmetic locally cartesian closed pretopos with a full subcategory ${{\mathbf {pEff}_{set}}}$ of small objects having the same categorical structure which is preserved by the embedding in ${\mathbf {pEff}}$ ; furthermore subobjects in ${{\mathbf {pEff}_{set}}}$ are classified by a non-small object in ${\mathbf {pEff}}$ . Third ${\mathbf {pEff}}$ happens to coincide with the exact completion of the lex category defined as a predicative rendering in ${{\widehat {ID_1}}}$ of the subcategory of ${{\mathbf {Eff} }}$ of recursive functions and it validates the Formal Church’s thesis. Hence pEff turns out to be itself a predicative rendering of a full subcategory of ${{\mathbf {Eff} }}$ .

We define a weak iterability notion that is sufficient for a number of arguments concerning $\Sigma _{1}$ -definability at uncountable regular cardinals. In particular we give its exact consistency strength first in terms of the second uniform indiscernible for bounded subsets of $\kappa $ : $u_2(\kappa )$ , and secondly to give the consistency strength of a property of Lücke’s.

TheoremThe following are equiconsistent:

1. (i) There exists $\kappa $ which is stably measurable;

2. (ii) for some cardinal $\kappa $ , $u_2(\kappa )=\sigma (\kappa )$ ;

3. (iii) The $\boldsymbol {\Sigma }_{1}$ -club property holds at a cardinal $\kappa $ .

Here $\sigma (\kappa )$ is the height of the smallest $M \prec _{\Sigma _{1}} H ( \kappa ^{+} )$ containing $\kappa +1$ and all of $H ( \kappa )$ . Let $\Phi (\kappa )$ be the assertion:

TheoremAssume $\kappa $ is stably measurable. Then $\Phi (\kappa )$ .

And a form of converse:

TheoremSuppose there is no sharp for an inner model with a strong cardinal. Then in the core model K we have: $\mbox {``}\exists \kappa \Phi (\kappa ) \mbox {''}$ is (set)-generically absolute ${\,\longleftrightarrow \,}$ There are arbitrarily large stably measurable cardinals.

When $u_2(\kappa ) < \sigma (\kappa )$ we give some results on inner model reflection.

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 sequences y (i.e., $\{0,1\}$ -valued functions) such that for each computable bit sequence x, the bit sequence $ x {\,\leftrightarrow\,} y$ has asymptotic lower density at most p (where $x {\,\leftrightarrow\,} y$ has a $1$ in position n iff $x(n) = y(n)$ ). We show that all members of this family of mass problems parameterized by a real p with $0 < p <1/2 $ have the same complexity in the sense of Muchnik reducibility. We prove this by showing Muchnik equivalence of the problems ${\mathcal {D}}(p)$ with the mass problem $\text {IOE}({2^{2}}^{n})$ ; here for an order function h, the mass problem $\text {IOE}(h)$ consists of the functions f that agree infinitely often with each computable function bounded by h. This result also yields a new version of the proof to of the affirmative answer to the “Gamma question” due to the first author: $\Gamma (A)< 1/2$ implies $\Gamma (A)=0$ for each Turing oracle A.

As a dual of the problem ${\mathcal {D}}(p)$ , define ${\mathcal {B}}(p)$ , for $0 \le p < 1/2$ , to be the set of bit sequences y such that $\underline \rho (x {\,\leftrightarrow\,} y)> p$ for each computable set x. 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 function g there 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 set G of bit sequences such that for each bit sequence x there is a bit sequence y in G so 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.

We prove a variety of theorems about stationary set reflection and concepts related to internal approachability. We prove that an implication of Fuchino–Usuba relating stationary reflection to a version of Strong Chang’s Conjecture cannot be reversed; strengthen and simplify some results of Krueger about forcing axioms and approachability; and prove that some other related results of Krueger are sharp. We also adapt some ideas of Woodin to simplify and unify many arguments in the literature involving preservation of forcing axioms.

In this paper we study the relativized Lascar Galois group of a strong type. The group is a quasi-compact connected topological group, and if in addition the underlying theory T is G-compact, then the group is compact. We apply compact group theory to obtain model theoretic results in this note. For example, we use the divisibility of the Lascar group of a strong type to show that, in a simple theory, such types have a certain model theoretic property that we call divisible amalgamation. The main result of this paper is that if c is a finite tuple algebraic over a tuple a, the Lascar group of $\operatorname {stp}(ac)$ is abelian, and the underlying theory is G-compact, then the Lascar groups of $\operatorname {stp}(ac)$ and of $\operatorname {stp}(a)$ are isomorphic. To show this, we prove a purely compact group-theoretic result that any compact connected abelian group is isomorphic to its quotient by every finite subgroup. Several (counter)examples arising in connection with the theoretical development of this note are presented as well. For example, we show that, in the main result above, neither the assumption that the Lascar group of $\operatorname {stp}(ac)$ is abelian, nor the assumption of c being finite can be removed.

Recent work in computability theory has focused on various notions of asymptotic computability, which capture the idea of a set being “almost computable.” One potentially upsetting result is that all four notions of asymptotic computability admit “almost computable” sets in every Turing degree via coding tricks, contradicting the notion that “almost computable” sets should be computationally close to the computable sets. In response, Astor introduced the notion of intrinsic density: a set has defined intrinsic density if its image under any computable permutation has the same asymptotic density. Furthermore, introduced various notions of intrinsic computation in which the standard coding tricks cannot be used to embed intrinsically computable sets in every Turing degree. Our goal is to study the sets which are intrinsically small, i.e. those that have intrinsic density zero. We begin by studying which computable functions preserve intrinsic smallness. We also show that intrinsic smallness and hyperimmunity are computationally independent notions of smallness, i.e. any hyperimmune degree contains a Turing-equivalent hyperimmune set which is “as large as possible” and therefore not intrinsically small. Our discussion concludes by relativizing the notion of intrinsic smallness and discussing intrinsic computability as it relates to our study of intrinsic smallness.

We give an example of two ordered structures $\mathcal {M},\mathcal {N}$ in the same language $\mathcal {L}$ with the same universe, the same order and admitting the same one-variable definable subsets such that $\mathcal {M}$ is a model of the common theory of o-minimal $\mathcal {L}$ -structures and $\mathcal {N}$ admits a definable, closed, bounded, and discrete subset and a definable injective self-mapping of that subset which is not surjective. This answers negatively two question by Schoutens; the first being whether there is an axiomatization of the common theory of o-minimal structures in a given language by conditions on one-variable definable sets alone. The second being whether definable completeness and type completeness imply the pigeonhole principle. It also partially answers a question by Fornasiero asking whether definable completeness of an expansion of a real closed field implies the pigeonhole principle.

We present an alternative proof that from large cardinals, we can force the tree property at $\kappa ^+$ and $\kappa ^{++}$ simultaneously for a singular strong limit cardinal $\kappa $ . The advantage of our method is that the proof of the tree property at the double successor is simpler than in the existing literature. This new approach also works to establish the result for $\kappa =\aleph _{\omega ^2}$ .

In contrast to the robust mutual interpretability phenomenon in set theory, Ali Enayat proved that bi-interpretation is absent: distinct theories extending ZF are never bi-interpretable and models of ZF are bi-interpretable only when they are isomorphic. Nevertheless, for natural weaker set theories, we prove, including Zermelo–Fraenkel set theory $\mathrm {ZFC}^{-}$ without power set and Zermelo set theory Z, there are nontrivial instances of bi-interpretation. Specifically, there are well-founded models of $\mathrm {ZFC}^{-}$ that are bi-interpretable, but not isomorphic—even $\langle H_{\omega _1},\in \rangle $ and $ \langle H_{\omega _2},\in \rangle $ can be bi-interpretable—and there are distinct bi-interpretable theories extending $\mathrm {ZFC}^{-}$ . Similarly, using a construction of Mathias, we prove that every model of ZF is bi-interpretable with a model of Zermelo set theory in which the replacement axiom fails.

A sequent calculus with the subformula property has long been recognised as a highly favourable starting point for the proof theoretic investigation of a logic. However, most logics of interest cannot be presented using a sequent calculus with the subformula property. In response, many formalisms more intricate than the sequent calculus have been formulated. In this work we identify an alternative: retain the sequent calculus but generalise the subformula property to permit specific axiom substitutions and their subformulas. Our investigation leads to a classification of generalised subformula properties and is applied to infinitely many substructural, intermediate, and modal logics (specifically: those with a cut-free hypersequent calculus). We also develop a complementary perspective on the generalised subformula properties in terms of logical embeddings. This yields new complexity upper bounds for contractive-mingle substructural logics and situates isolated results on the so-called simple substitution property within a general theory.

We study the generic theory of algebraically closed fields of fixed positive characteristic with a predicate for an additive subgroup, called $\mathrm {ACFG}$ . This theory was introduced in [16] as a new example of $\mathrm {NSOP}_{1}$ nonsimple theory. In this paper we describe more features of $\mathrm {ACFG}$ , such as imaginaries. We also study various independence relations in $\mathrm {ACFG}$ , such as Kim-independence or forking independence, and describe interactions between them.

We introduce and study a natural class of fields in which certain first-order definable sets are existentially definable, and characterise this class by a number of equivalent conditions. We show that global fields belong to this class, and in particular obtain a number of new existential (or diophantine) predicates over global fields.

In previous work, the author has shown that $\Pi ^1_1$ -induction along $\mathbb N$ is equivalent to a suitable formalization of the statement that every normal function on the ordinals has a fixed point. More precisely, this was proved for a representation of normal functions in terms of Girard’s dilators, which are particularly uniform transformations of well orders. The present paper works on the next type level and considers uniform transformations of dilators, which are called 2-ptykes. We show that $\Pi ^1_2$ -induction along $\mathbb N$ is equivalent to the existence of fixed points for all 2-ptykes that satisfy a certain normality condition. Beyond this specific result, the paper paves the way for the analysis of further $\Pi ^1_4$ -statements in terms of well ordering principles.

We continue the research of the relation $\hspace {1mm}\widetilde {\mid }\hspace {1mm}$ on the set $\beta \mathbb {N}$ of ultrafilters on $\mathbb {N}$ , defined as an extension of the divisibility relation. It is a quasiorder, so we see it as an order on the set of $=_{\sim }$ -equivalence classes, where $\mathcal {F}=_{\sim }\mathcal {G}$ means that $\mathcal {F}$ and $\mathcal {G}$ are mutually $\hspace {1mm}\widetilde {\mid }$ -divisible. Here we introduce a new tool: a relation of congruence modulo an ultrafilter. We first recall the congruence of ultrafilters modulo an integer and show that $=_{\sim }$ -equivalent ultrafilters do not necessarily have the same residue modulo $m\in \mathbb {N}$ . Then we generalize this relation to congruence modulo an ultrafilter in a natural way. After that, using iterated nonstandard extensions, we introduce a stronger relation, which has nicer properties with respect to addition and multiplication of ultrafilters. Finally, we introduce a strengthening of $\hspace {1mm}\widetilde {\mid }\hspace {1mm}$ and show that it also behaves well with respect to the congruence relation.

We study closure properties of measurable ultrapowers with respect to Hamkin’s notion of freshness and show that the extent of these properties highly depends on the combinatorial properties of the underlying model of set theory. In one direction, a result of Sakai shows that, by collapsing a strongly compact cardinal to become the double successor of a measurable cardinal, it is possible to obtain a model of set theory in which such ultrapowers possess the strongest possible closure properties. In the other direction, we use various square principles to show that measurable ultrapowers of canonical inner models only possess the minimal amount of closure properties. In addition, the techniques developed in the proofs of these results also allow us to derive statements about the consistency strength of the existence of measurable ultrapowers with non-minimal closure properties.

We prove that the two-variable fragment of first-order logic has the weak Beth definability property. This makes the two-variable fragment a natural logic separating the weak and the strong Beth properties since it does not have the strong Beth definability property.

A complete list of one dimensional groups definable in the p-adic numbers is given, up to a finite index subgroup and a quotient by a finite subgroup.

In this work we investigate the Weihrauch degree of the problem Decreasing Sequence ( $\mathsf {DS}$ ) of finding an infinite descending sequence through a given ill-founded linear order, which is shared by the problem Bad Sequence ( $\mathsf {BS}$ ) of finding a bad sequence through a given non-well quasi-order. We show that $\mathsf {DS}$ , despite being hard to solve (it has computable inputs with no hyperarithmetic solution), is rather weak in terms of uniform computational strength. To make the latter precise, we introduce the notion of the deterministic part of a Weihrauch degree. We then generalize $\mathsf {DS}$ and $\mathsf {BS}$ by considering $\boldsymbol {\Gamma }$ -presented orders, where $\boldsymbol {\Gamma }$ is a Borel pointclass or $\boldsymbol {\Delta }^1_1$ , $\boldsymbol {\Sigma }^1_1$ , $\boldsymbol {\Pi }^1_1$ . We study the obtained $\mathsf {DS}$ -hierarchy and $\mathsf {BS}$ -hierarchy of problems in comparison with the (effective) Baire hierarchy and show that they do not collapse at any finite level.

We investigate the Tukey order in the class of $F_{\sigma }$ ideals of subsets of $\omega $ . We show that no nontrivial $F_{\sigma }$ ideal is Tukey below a $G_{\delta }$ ideal of compact sets. We introduce the notions of flat ideals and gradually flat ideals. We prove a dichotomy theorem for flat ideals isolating gradual flatness as the side of the dichotomy that is structurally good. We give diverse characterizations of gradual flatness among flat ideals using Tukey reductions and games. For example, we show that gradually flat ideals are precisely those flat ideals that are Tukey below the ideal of density zero sets.