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.