Given a family ${\cal C}$ of infinite subsets of ${\Bbb N}$, we study when there is a Borel function $S:2^{\Bbb N} \to 2^{\Bbb N} $ such that for every infinite $x \in 2^{\Bbb N} $, $S\left( x \right) \in {\Cal C}$ and $S\left( x \right) \subseteq x$. We show that the family of homogeneous sets (with respect to a partition of a front) as given by the Nash-Williams’ theorem admits such a Borel selector. However, we also show that the analogous result for Galvin’s lemma is not true by proving that there is an $F_\sigma $ tall ideal on ${\Bbb N}$ without a Borel selector. The proof is not constructive since it is based on complexity considerations. We construct a ${\bf{\Pi }}_2^1 $ tall ideal on ${\Bbb N}$ without a tall closed subset.

Our aim is to solve a quite old question on the difference between expandability and compact expandability. Toward this, we further investigate the logic of countable cofinality.

A structure is automatic if its domain, functions, and relations are all regular languages. Using the fact that every automatic structure is decidable, in the literature many decision problems have been solved by giving an automatic presentation of a particular structure. Khoussainov and Nerode asked whether there is some way to tell whether a structure has, or does not have, an automatic presentation. We answer this question by showing that the set of Turing machines that represent automata-presentable structures is ${\rm{\Sigma }}_1^1 $-complete. We also use similar methods to show that there is no reasonable characterisation of the structures with a polynomial-time presentation in the sense of Nerode and Remmel.

Given a compact Polish space E and the hyperspace of its compact subsets ${\cal K}\left( E \right)$, we consider Gδσ-ideals of compact subsets of E. Solecki has shown that any σ-ideal in a broad natural class of Gδ ideals can be represented via a compact subset of ${\cal K}\left( E \right)$; in this article we examine the behaviour of Gδ subsets of E with respect to the representing set. Given an ideal I in this class, we construct a representing set that recognises a compact subset of E as being “small” precisely when it is in I, and recognises a Gδ subset of E as being “small” precisely when it is covered by countably many compact sets from I.

We study the behavior of the game operator $$ on Wadge classes of Borel sets. In particular we prove that the classical Moschovakis results still hold in this setting. We also characterize Wadge classes ${\bf{\Gamma }}$ for which the class has the substitution property. An effective variation of these results shows that for all $1 \le \eta < \omega _1^{{\rm{CK}}}$ and $2 \le \xi < \omega _1^{{\rm{CK}}}$, is a Spector class while is not.

This paper consists in the formulation of a novel categorical set theory, MLCat, which is proved to be equiconsistent to New Foundations (NF), and which can be modulated to correspond to intuitionistic (denoted with an “I” on the left) or classical NF, with atoms (denoted with a “U” on the right) or not:

We study genericity and randomness with respect to ITTMs, continuing the work initiated by Carl and Schlicht. To do so, we develop a framework to study randomness in the constructible hierarchy. We then answer several of Carl and Schlicht’s question. We also ask a new question one the equality of two classes of randoms. Although the natural intuition would dictate that the two classes are distinct, we show that things are not as simple as they seem. In particular we show that the categorical analogues of these two classes coincide, in contradiction with the natural intuition. Even though we are not able to answer the question for randomness in this article, we delineate and sharpen its contour and outline.

We prove the following two basis theorems for ${\rm{\Sigma }}_2^1$-sets of reals:

1. (1) Every nonthin ${\rm{\Sigma }}_2^1$-set has a perfect ${\rm{\Delta }}_2^1$-subset if and only if it has a nonthin ${\rm{\Delta }}_2^1$-subset, and this is equivalent to the statement that there is a nonconstructible real.

2. (2) Every uncountable ${\rm{\Sigma }}_2^1$-set has an uncountable ${\rm{\Delta }}_2^1$-subset if and only if either every real is constructible or $\omega _1^L$ is countable.

We also apply the method that proves (2) to show that if there is a nonconstructible real, then there is a perfect ${\rm{\Pi }}_2^1$-set with no nonempty ${\rm{\Pi }}_2^1$-thin subset, strengthening a result of Harrington [4].

We consider a weak version of Schindler’s remarkable cardinals that may fail to be ${{\rm{\Sigma }}_2}$-reflecting. We show that the ${{\rm{\Sigma }}_2}$-reflecting weakly remarkable cardinals are exactly the remarkable cardinals, and that the existence of a non-${{\rm{\Sigma }}_2}$-reflecting weakly remarkable cardinal has higher consistency strength: it is equiconsistent with the existence of an ω-Erdős cardinal. We give an application involving gVP, the generic Vopěnka principle defined by Bagaria, Gitman, and Schindler. Namely, we show that gVP + “Ord is not ${{\rm{\Delta }}_2}$-Mahlo” and ${\text{gVP}}(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle\thicksim}$}}{\Pi } _1 )$ + “there is no proper class of remarkable cardinals” are both equiconsistent with the existence of a proper class of ω-Erdős cardinals, extending results of Bagaria, Gitman, Hamkins, and Schindler.

We introduce a notion of the space of types in positive model theory based on Stone duality for distributive lattices. We show that this space closely mirrors the Stone space of types in the full first-order model theory with negation (Tarskian model theory). We use this to generalise some classical results on countable models from the Tarskian setting to positive model theory.

We show that for any uncountable cardinal λ, the category of sets of cardinality at least λ and monomorphisms between them cannot appear as the category of points of a topos, in particular is not the category of models of a ${L_{\infty ,\omega }}$-theory. More generally we show that for any regular cardinal $\kappa < \lambda$ it is neither the category of κ-points of a κ-topos, in particular, nor the category of models of a ${L_{\infty ,\kappa }}$-theory.

The proof relies on the construction of a categorified version of the Scott topology, which constitute a left adjoint to the functor sending any topos to its category of points and the computation of this left adjoint evaluated on the category of sets of cardinality at least λ and monomorphisms between them. The same techniques also apply to a few other categories. At least to the category of vector spaces of with bounded below dimension and the category of algebraic closed fields of fixed characteristic with bounded below transcendence degree.

We prove that, in order to establish that a theory is NSOP1, it suffices to show that no formula in a single free variable has SOP1.

A formula φ is called n-provable in a formal arithmetical theory S if φ is provable in S together with all true arithmetical ${{\rm{\Pi }}_n}$-sentences taken as additional axioms. While in general the set of all n-provable formulas, for a fixed $n > 0$, is not recursively enumerable, the set of formulas φ whose n-provability is provable in a given r.e. metatheory T is r.e. This set is deductively closed and will be, in general, an extension of S. We prove that these theories can be naturally axiomatized in terms of progressions of iterated local reflection principles. In particular, the set of provably 1-provable sentences of Peano arithmetic $PA$ can be axiomatized by ${\varepsilon _0}$ times iterated local reflection schema over $PA$. Our characterizations yield additional information on the proof-theoretic strength of these theories (w.r.t. various measures of it) and on their axiomatizability. We also study the question of speed-up of proofs and show that in some cases a proof of n-provability of a sentence can be much shorter than its proof from iterated reflection principles.

In this article, we study the commutativity between the pull-back and the push-forward functors on constructible functions in Cluckers–Loeser motivic integration.

In this paper, we study the power and limitations of computing effectively generic sequences using effectively random oracles. Previously, it was known that every 2-random sequence computes a 1-generic sequence (as shown by Kautz) and every 2-random sequence forms a minimal pair in the Turing degrees with every 2-generic sequence (as shown by Nies, Stephan, and Terwijn). We strengthen these results by showing that every Demuth random sequence computes a 1-generic sequence and that every Demuth random sequence forms a minimal pair with every pb-generic sequence (where pb-genericity is an effective notion of genericity that is strictly between 1-genericity and 2-genericity). Moreover, we prove that for every comeager ${\cal G} \subseteq {2^\omega }$, there is some weakly 2-random sequence X that computes some $Y \in {\cal G}$, a result that allows us to provide a fairly complete classification as to how various notions of effective randomness interact in the Turing degrees with various notions of effective genericity.

A new method for blowing up the power of a singular cardinal is presented. It allows to blow up the power of a singular in the core model cardinal of uncountable cofinality. The method makes use of overlapping extenders.

We generalise the α-Ramsey cardinals introduced in Holy and Schlicht (2018) for cardinals α to arbitrary ordinals α, and answer several questions posed in that paper. In particular, we show that α-Ramseys are downwards absolute to the core model K for all α of uncountable cofinality, that strategic ω-Ramsey cardinals are equiconsistent with remarkable cardinals and that strategic α-Ramsey cardinals are equiconsistent with measurable cardinals for all α > ω. We also show that the n-Ramseys satisfy indescribability properties and use them to provide a game-theoretic characterisation of completely ineffable cardinals, as well as establishing further connections between the α-Ramsey cardinals and the Ramsey-like cardinals introduced in Gitman (2011), Feng (1990), and Sharpe and Welch (2011).

Using a technique developed by Coquand and Hofmann [3] we verify that adding the analytical form MP1: $\forall \alpha (\neg \neg \exists {\rm{x}}\alpha ({\rm{x}}) = 0 \to \exists {\rm{x}}\alpha ({\rm{x}}) = 0)$ of Markov’s Principle does not increase the class of ${\rm{\Pi }}_2^0$ formulas provable in Kleene and Vesley’s formal system for intuitionistic analysis, or in subsystems obtained by omitting or restricting various axiom schemas in specified ways.

We study generically stable measures in the local, NIP context. We show that in this setting, a measure is generically stable if and only if it admits a natural finite approximation.