Early View

Grothendieck toposes, and by extension, logical theories, can be represented by topological structures. Butz & Moerdijk showed that every topos with enough points can be represented as the topos of sheaves on an open topological groupoid. This paper tackles a follow-up question: we characterise, in model-theoretic terms, which open topological groupoids can represent the classifying topos of a theory. Intuitively, this characterises which groupoids of models contain enough information to reconstruct the theory. Our treatment subsumes many of the previous approaches found in the literature, such as that of Awodey, Butz, Forssell & Moerdijk.

We consider compactness properties for strong logics in terms of strong Henkin models and give characterisations of supercompact cardinals, $\mathrm{C}^{(n)}$-extendible cardinals, and Vopěnka's Principle by these properties. Moreover, we give a characterisation of superstrong cardinals in terms of compactness properties using the previously considered weak Henkin models.

In previous work we defined and studied a notion of typicality, originated with B. Russell, for properties and objects in the context of general infinite first-order structures. In this paper we consider this notion in the context of finite structures. In particular we define the typicality degree of a property $\varphi(x)$ over finite $L$-structures, for a language $L$, as the limit of the probability of $\varphi(x)$ to be typical in an arbitrary $L$-structure $\mathcal{M}$ of cardinality $n$, when $n$ goes to infinity. This poses the question whether the 0-1 law holds for typicality degrees for certain kinds of languages. One of the results of the paper is that, in contrast to the classical well-known fact that the 0-1 law holds for the sentences of every relational language, the 0-1 law fails for degrees of properties of relational languages containing unary predicates. On the other hand it is shown that the 0-1 law holds for degrees of some basic properties of graphs, and this gives rise to the conjecture that the 0-1 law holds for relational languages without unary predicates. Another theme is the neutrality degree of a property $\varphi(x)$ (i.e., the fraction of $L$-structures in which neither $\varphi$ nor $\lnot\varphi$ is typical), and in particular the regular properties (i.e., those with limit neutrality degree $0$). All properties we dealt with, either of a relational or a functional language, are shown to be regular, but the question whether every such property is regular is open.

The ultimate goal of this note is to establish results pointing to our concluding conjecture that instances of tallness are equiconsistent with certain failures of $\mathsf{GCH}$ at a measurable cardinal. Towards that end, we begin by showing that any tall cardinal can have its tallness made indestructible under Sacks forcing, and that the construction used can be iterated so as to produce a model containing a (possibly proper) class of tall cardinals in which each member of the class has its tallness indestructible under Sacks forcing. We then make precise Hamkins' proof sketch given in Corollary 3.14 of "Tall cardinals" (2009) that the theories $\mathsf{ZFC} + {}$"There is a tall cardinal" and $\mathsf{ZFC} + {}$"There is a strong cardinal" are equiconsistent. We finish by proving two theorems concerning equiconsistency, instances of tallness, and failures of $\mathsf{GCH}$ that provide the basis for our concluding conjecture.

We give an elementary proof that theory $T^1_2(R)$ augmented by the weak pigeonhole principle for all $\Delta^{\mathrm{b}}_1(R)$-definable relations does not prove the bijective pigeonhole principle for $R$. This can be derived from known more general results but our proof yields a model of $T^1_2(R)$ in which $\mathsf{ontoPHP}^{n+1}_n(R)$ fails for some nonstandard element $n$ while $\mathsf{PHP}^{m+1}_m$ holds for all $\Delta^{\mathrm{b}}_1(R)$-definable relations and all $m \leq n^{1-\varepsilon}$, where $\varepsilon > 0$ is a fixed standard rational parameter. This can be seen as a step towards solving an open question posed by Ajtai (1990).

We introduce the notion of dependence, as a property of a Keisler measure, and generalize some results of Hrushovski, Pillay & Simon (2013) in NIP theories (theories satisfying the negation of the independence property) to arbitrary theories. Among other things, we show that this notion is very natural and fundamental for several reasons:

1. all measures in NIP theories are dependent,
2. all types and all frequency interpretation measures (fims) in any theory are dependent, and
3. as a crucial result in measure theory, the Glivenko–Cantelli class of functions (formulas) is characterized by dependent measures.

Let $G$ be a proper subgroup of $\mathbb Q$ and $S_G$ be the set of primes $p$ for which $G$ is $p$-divisible. We show that the model-theoretic Grothendieck ring of the ordered abelian group $(G;+,<)$ is a quotient of $(\mathbb Z/q\mathbb Z)[T]/(T+T^2)$, where $q$ is the largest odd integer that divides $p-1$ for all $p \notin S_G$. This implies that the Grothendieck ring of $(G;+,<)$ is trivial in various salient cases, for example when $S_G$ is finite, or when $S_G$ does not contain the set of all primes of the form $2^n +1$, $n\in \mathbb N$.

We show that weak fragments of $\mathsf{ZF}$ and $\mathsf{NF}$ decide stratified subincreasing sentences.

For an infinite class of finite graphs of unbounded size, we define a limit object, to be called a wide limit, relative to some computationally restricted class of functions. The limit object is a first-order Boolean-valued structure. The first-order properties of the wide limit then reflect how a computationally restricted viewer sees a generic member of the class. The construction uses arithmetic forcing with random variables (Krajíček, 2011). We give sufficient conditions for universal and existential sentences to be valid in the limit, provide several examples, and prove that such a limit object can then be expanded to a model of weak arithmetic. To illustrate the concept, we give an example in which the wide limit relates to total $\mathsf{NP}$ search problems. In particular, we take the wide limit of all maps from $\{0,\dots,k-1\}$ to $\{0,\dots,\lfloor k/2\rfloor-1\}$ to obtain a model of $\forall \mathrm{PV}_1(f)$ where the problem $\mathrm{RetractionWeakPigeon}$ is total, but $\mathrm{WeakPigeon}$, the complete problem for $\mathsf{PWPP}$, is not. Thus, we obtain a new proof of this unprovability and show it implies that $\mathrm{WeakPigeon}$ is not many-one reducible to $\mathrm{RetractionWeakPigeon}$ in the oracle setting.

We call an infinite structure $\mathcal{M}$ sunflowerable if whenever $\mathcal{M}'$ is isomorphic to $\mathcal{M}$ with underlying set $\mathcal{M}'$, consisting of finite sets of bounded size, there is an $M_0 \subseteq M'$ such that $M_0$ is a sunflower and $\mathcal{M}'{\restriction_{M_0}}$ is isomorphic to $\mathcal{M}$. We give sufficient conditions on $\mathcal{M}$ to show that $\mathcal{M}$ is sunflowerable. These conditions allow us to show that several well-known structures are sunflowerable and give a complete characterization of the countable linear orderings that are sunflowerable. We show that a sunflowerable structure must be indivisible. This allows us to show that any Fraïssé limit that has the 3-disjoint amalgamation property and a single unary type must be indivisible. In addition to studying sunflowerability of infinite structures we also consider an analogous property of an age, which we call the sunflower property. We show that any sunflowerable structure must have an age with the sunflower property. We also give concrete bounds in the case that the age has the hereditary property, the 3-disjoint amalgamation property and is indivisible.

We axiomatize the first-order theories of exponential integer parts of real-closed exponential fields in a language with $2^x$, in a language with a predicate for powers of $2$, and in the basic language of ordered rings. In particular, the last theory extends $\mathsf{IOpen}$ by sentences expressing the existence of winning strategies in a certain game on integers; we show that it is a proper extension of $\mathsf{IOpen}$, and give upper and lower bounds on the required number of rounds needed to win the game.

Adapting a result of Bazhenov, Kalimullin & Yamaleev (2020), we show that if a Turing degree $\mathbf{d}$ is the degree of categoricity of a computable structure $\mathcal{M}$ and is not the strong degree of categoricity of any computable structure, then $\mathcal{M}$ has a pair of computable copies whose isomorphism spectrum is not finitely generated. Motivated by this result, we introduce a class of computable structures, called computably composite structures, with the property that the isomorphisms between arbitrary computable copies of these structures are exactly the unions of isomorphisms between the computable copies of their components. We use this to show that any computable union of isomorphism spectra is also an isomorphism spectrum. In particular, this gives examples of isomorphism spectra that are not finitely generated.

We show that in the iterated Sacks model over the constructible universe the Mansfield–Solovay theorem holds for $\Sigma^1_3$ sets. In particular, every $\mathbf{\Sigma}^1_3$ set is Marczewski measurable and the optimal complexity for a Bernstein set is $\Delta^1_4$. Based on a result by Kanovei, we also briefly show how to separate the Mansfield–Solovay theorem at non-trivial levels of the projective hierarchy.