Papers

The sets-as-trees interpretation of set theory in a dependent type theory with an impredicative universe of propositions validates Zermelo set theory, and it validates Replacement if the type theory has a choice or description operator, which turns a functional relation into a function. It has been natural to expect that without such an operator the strength of the type theory drops well below that of $\mathrm{ZF}$. We show that it does not. In the type theory of Lean with two predicative universes, from excluded middle as the only assumption and with no axiom (no choice, no propositional extensionality, no quotients), we prove the consistency of $\mathrm{ZF}$, stated outright for a first-order proof system. The proof is formalized. The mechanism is the large elimination of the accessibility predicate over a type as large as the type of sets: a recursion on accessibility whose recursive calls are guarded by propositions, and whose later calls are indexed by the value of an earlier call, computes as a term any ordinal that is specified by a proposition through a well-founded tree of a certain shape. We give a rule that produces such a tree for every ordinal, unless some $V_\rho$ is already a model of $\mathrm{ZF}$; the rule does not choose a cofinal map into a limit ordinal but takes all definable ones at once. In the first case the sets-as-trees satisfy Replacement for arbitrary propositional relations. Either way $\mathrm{ZF}$ has a model. Finally, the double negation of excluded middle suffices, and what remains of it is exactly that membership is not not well-founded in the stable reading of sets; this in turn implies the double negation of Markov's principle.

Gödelian incompleteness yields arithmetical sentences $A$ such that $PA+A$ and $PA+\neg A$ are both consistent. Are such extensions equally legitimate? I propose graded epistemic arithmetical non-pluralism: justification for choosing between them varies with the set-theoretic strength of $A$. I defend $PA+Con(PA)$ and show Koellner's non-pluralism for first-order arithmetic is inadequate given Friedman's concrete incompleteness. Resolving the selection problem for such sentences turns on justifying large cardinals. Defending graded non-pluralism thus engages Gödel's programme and the justification of very large cardinals.

Let $B$ be the bluebird combinator with reduction rule $Bxyz \to_{w} x\left(yz\right)$, let $M$ be the mockingbird combinator with reduction rule $Mx \to_{w} xx$, and let $I$ be the identity bird combinator with reduction rule $Ix \to_{w} x$. A fixed-point combinator, called a sage bird by Smullyan, is a closed term $Y$ such that, for a fresh variable $x$, $Yx$ is equivalent to $x\left(Yx\right)$ under these reduction rules. For a fixed variable $x$, we construct an invariant $\mathrm{Tr}_{x}\left(u\right)$ of a $BMI$-term $u$ with respect to $\to_{w}$. This invariant traces the occurrences of $x$ in the leftmost-innermost reduction sequence of $u$. We then prove that $\mathrm{Tr}_{x}\left(Yx\right) \neq \mathrm{Tr}_{x}\left(x^{r}\left( Yx \right)\right)$ for every $x$-free $BMI$-term $Y$ and every $r\geq 1$. Consequently, there exists no fixed-point combinator in $BMI$-combinatory logic. This provides a negative answer to the problem posed by Smullyan in 1985.

Filter bubbles can be understood as configurations characterized by within-group proximity and separation from outsiders. Personalized feeds may form or preserve such configurations. We develop hybrid-style logics for reasoning about filter bubbles. The static logic characterizes bubble-shaped configurations, while its dynamic extension captures their formation and persistence under personalized feeds. We provide sound and strongly complete axiomatizations for the static and dynamic logics and prove their decidability.

We give a proof, that does not rely on analytic determinacy, of the existence of an idealistic analytic equivalence relation with Borel classes that is not classwise Borel isomorphic to an orbit equivalence relation. This result answers a question of Becker, and Calderoni and Motto Ros. Our proof proceeds through an analysis of Borel complexity of certain sets of countable rooted trees defined via the notion of the Lusin derivative.

Let $G$ be a Borel digraph with maximum out-degree $d \in \mathbb{N}$. We show that $G$ admits a random Borel $(2d+1)$-coloring for which every edge is almost surely not monochromatic. This gives a simpler proof of a recent result of Pelayo-Gómez: such a graph $G$ admits a measurable proper $(2d+1)$-coloring with respect to any Borel probability measure on $V(G)$. Our proof is an adaptation of Pelayo-Gómez's proof to the randomized Borel setting.

We study Scott products and sobriety of countable meet-continuous domains, meaning meet-continuous dcpos without any additional continuity or least-element assumption. Using the complete-lattice test-family theorem of Xu and Ji, we prove finite-product equality for those domains that are $L$-dcpos, and for the weaker class whose principal ideals have suprema of all nonempty subsets. For an arbitrary family of nonempty countable meet-continuous $L$-dcpos, we prove that the Scott topology on the order product equals the product of the factor Scott topologies if and only if only finitely many factors lack a least element. We also establish sobriety under bounded completeness and under additional common-upper-bound conditions. Assuming square-product equality, sobriety is characterized by Scott closedness of common-upper-bound sections associated with irreducible Scott-closed sets, with an equivalent sequential formulation in the countable case. Two extraction lemmas extend to meet-semilattice dcpos. The finite-product and sobriety questions for general countable meet-continuous domains remain unresolved here.

We demonstrate that forking in monadically NIP theories satisfies a very strong form of triviality over arbitrary sets, generalizing Baldwin-Shelah in monadically stable theories and analogous to Shelah's result for finite satisfiability over models in monadically NIP theories. This implies in particular that strict non-forking independence is particularly well behaved, and that the forking relation induces a canonical semilinear partial order on singletons. We also give an example of an $\omega$-categorical monadically NIP theory so that no finite set is an extension base.

For a suitable class of structures $\mathcal{K}$, let ${\rm Sh}(\mathcal{K}_\lambda^{\rm op},J_{\rm at})$ denote the atomic sheaf topos over the opposite of the category $\mathcal{K}_\lambda$ of structures in $\mathcal{K}$ of cardinality at most $\lambda$, with embeddings as morphisms. In this article, we analyze the relationship between model-theoretic properties of $\mathcal{K}$ and logical properties of ${\rm Sh}(\mathcal{K}_\lambda^{\rm op},J_{\rm at})$. For an infinite cardinal $\lambda$, we show that $\mathcal{K}$ is Galois $\lambda$-stable if and only if the atomic sheaf topos ${\rm Sh}(\mathcal{K}_\lambda^{\rm op},J_{\rm at})$ satisfies the axiom of choice for $\lambda^+$-indexed families. We further show that every structure in $\mathcal{K}_\lambda$ extends to a maximal structure if and only if ${\rm Sh}(\mathcal{K}_\lambda^{\rm op},J_{\rm at})$ satisfies the internal axiom of choice. If $\mathcal{K}_{\rm fin}$ is a class of finite structures, the cardinalities of the structures in each connected component of $\mathcal{K}_{\rm fin}$ have a finite upper bound if and only if ${\rm Sh}(\mathcal{K}^{\rm op}_{\rm fin},J_{\rm at})$ satisfies the internal axiom of (countable) choice. Furthermore, via the topological Galois representation, we establish a correspondence between the criteria for the axiom of choice for atomic sheaf toposes and those for permutation models in set theory.

Given a noncomputable, computably enumerable set $D$, we construct a computable structure $G$ such that any two computable copies of $G$ are computably isomorphic while there are two $D$-computable copies of $G$ that are not $D$-computably isomorphic. In other words, $G$ is computably categorical, but not computably categorical relative to $D$. Conversely, we construct a computable structure that is not computably categorical, but is computably categorical relative to $D$. These results differ from those in the literature regarding computable categoricity and its relativiziations because the degree $D$ is given instead of constructed. Our work negatively answers a question of Downey, Harrison-Trainor and Melnikov in the computably enumerable case.

Christensen and Pedersen proved that every properly infinite $\mathrm{AW}^*$-algebra is monotone sequentially complete, and Saitô and Wright developed a transfinite form of their dilation argument. We revisit the transfinite construction using normality of $\mathrm{AW}^*$-algebras. Normality simplifies the limit stages by turning suprema into compressions of joins, so the construction only needs a supply of fresh orthogonal projections large enough to contain the supports of the summands at successor stages. We use this simplified proof to show that a $*$-homomorphism between $\mathrm{AW}^*$-algebras that preserves only the joins needed to encode such a sum preserves the sum itself. We also use it to deduce order-continuity facts about $\kappa$-join-preserving $*$-homomorphisms. We also show that a finite $\mathrm{AW}^*$-algebra has suprema for all bounded positive families whose supports have bounded total center-valued dimension.

We revisit the analysis of Bayesian convergence to the truth under finite additivity in a recent paper by Nielsen (J. Philos. Logic, 2021, doi:10.1007/s10992-020-09569-2) Its principal theorem proves that the posteriors of a probability function converge to the truth almost uniformly if and only if the function has two properties: an approximation property, and so-called countable additivity on conditional hitting times. We show that the two properties are necessary but not sufficient, so that the theorem is false, and we locate the error in its published proof. We construct a merely finitely additive probability function that has both properties and whose posteriors converge to the truth almost surely but not almost uniformly. Three of the paper's four remaining theorems, and its corollary, lose their published proofs as well, two with the failed implication and two to a separate defect that we also identify. Two of the four results we reprove and one we leave undecided; the last is the corollary, which our counterexample does not refute, and which we establish for a family including the counterexample and leave open in general. We also show that almost-sure convergence of posteriors to the truth for every event does not characterize countable additivity. We close with what a repaired characterization of almost-uniform convergence would have to add.

We develop a complex-analytic approach to the model theory of the (real) unrestricted exponential. As a consequence we derive sharp forms of many of the foundational results for the structure ${\mathbb R}^\text{RE}_{\exp}$ (and more general structures). In particular we establish sharp o-minimality, a sharp form of Wilkie's theorem of the complement, a sharp form of Wilkie's conjecture and a sharp form of piecewise definability by terms. Our approach is based on a complexification of the LE-preparation theorem of Lion–Rolin. We also develop a parallel complex theory for ${\mathbb R}_\text{an,exp}$, proving for example that the rational points of height $H$ on a nowhere-dense definable set can be interpolated by an algebraic hypersurface of degree $\text{poly}(\log H)$. This generalizes a theorem of Cluckers–Pila–Wilkie who proved the same statement for ${\mathbb R}_\text{an}^\text{pow}$.

In this paper we propose a reconstruction of the theory of multiple generality in Stoic Logic using the Natural Term Logic (NTL) developped by the author in \cite{ntl}. Contrary to a frequent misconception, it can be shown conclusively, based on the available evidence, that Stoic logic was far more than a mere propositional logic (we further argue that even identifying the Stoic conditional with any type of propositional connective is misleading). Its more general and complex logical theory - and notable the treatment of multiple generality - was rather patterned after the logico-syntactic mechanisms of natural language (subject to a regimentation which recalls Polish notation) rather than the variable-based quantifier logic of the modern Fregean tradition. NTL is likewise is a variable-free formal framework which captures the core syntactic and logic mechanisms of natural language (and notably a large array of features involving intensionality and anaphoric constructions). Bobzien and Shogry \cite{bobzienshogry} have presented abundant evidence and arguments for the case that quantified conditionals and multiple generality were treated by the Stoics through a disambiguifying regimentation of syntax using indefinite pronouns and anaphoric constructions involving such pronouns. There are however some patent difficulties involving how exactly the equivalent of universal quantification was treated. In this paper we explore some possible building blocks for a formal reconstruction of the Stoic logic of multiple generality based on a variant of NTL. We focus on formalizing the more general form of Stoic modus ponens involving quantified conditions which was clearly attested by ancient authors. We also sketch, as a preliminary study for formalizing the grammatical theory deployed in Stoic logic, how NTL can be used to formalize adjectival and adverbial constructions.

We give a short proof that $\kappa$-cocompact objects in a presentable category are subterminal. As our main result, we extend this to the setting of presentable $\infty$-categories. A consequence is that an $\infty$-category $\mathcal{C}$ such that both $\mathcal{C}$ and $\mathcal{C}^\mathsf{op}$ are presentable is a small complete lattice, extending a classical theorem of Gabriel-Ulmer. Along the way, we prove a nilpotence result for phantom maps in general pointed presentable $\infty$-categories. Additionally, we show that a strengthening of our main result is equivalent to the existence of a proper class of measurable cardinals.

The Solvability Complexity Index (SCI) provides an extensional limit-height formalism for recovering a target map $\Xi$ from finite samples of an evaluation interface $\Lambda$ by finite-height towers of pointwise limits. At first sight this sounds like a typical Type-2 question, so it seems natural to ask how deep and rich the connection of SCI approximation questions and Type-2 computability questions is. This note aims to explain this connection further with explicit examples mostly from the literature.

We prove a generalization of the version, due to A. Gabrielov, of the Łojasiewicz inequality for not necessarily restricted semi-Pfaffian sets. Unlike the most variants of the Łojasiewicz inequality, it describes the rate of growth of a Pfaffian function on a semi-Pfaffian set $X$ not only in a neighbourhood of its zero set in the domain of $X$ but also in a neighbourhood of zeroes on the boundary of the domain. Gabrielov's version is essentially one-dimensional, we generalize it to a multidimensional case.

We prove that, in Zermelo–Fraenkel set theory with the axiom of Foundation removed, the statement that every vector space has a basis implies the Axiom of Choice ($\mathsf{AC}$), concluding that the classical equivalence between $\mathsf{AC}$ and the existence of bases does not require regularity. This result extends to set theory with atoms.

A variety $\mathcal{V}$ is called a Schreier variety if every subalgebra of a $\mathcal{V}$-free algebra is a $\mathcal{V}$-free algebra. We use ideas from Tame Congruence Theory to classify locally finite Schreier varieties. One version of the classification theorem states that a locally finite variety $\mathcal{V}$ is a Schreier variety if and only if (i) every finite algebra in $\mathcal{V}$ is a $\langle 0,1\rangle$-minimal algebra and (ii) if $\mathcal{V}$ has a constant $1$-ary term operation, then $\mathcal{V}$ also has a constant $0$-ary term operation.

We prove that every countable meet-continuous lattice is Scott sober. For any family of such lattices, the Scott topology on the product equals the product of the factor Scott topologies, and the product Scott space is sober. These results answer affirmatively Questions 7.1 and 7.2 of Xu (arXiv:2609.18032v1), extending the countable-frame results beyond finite distributivity. A diagonal argument on meet coordinates extracts directed punctured intervals from nonprincipal ideals. Join translates of these intervals form a countable family detecting Scott openness and yield Scott open rectangles by successive finite choices. We also show that the cardinal spectrum of Scott non-sober meet-continuous lattices is upward closed and, under the Continuum Hypothesis, consists of all uncountable cardinals.

We consider the Kolchin-generic complete $1$-type of the inviscid Burgers equation $Dx=x\partial x$ in a differentially closed field of characteristic zero with two commuting derivations. We prove that this type has Lascar rank $1$ and Morley rank $\omega$.

For various reasons, higher-order objects are often studied in mathematical logic via second-order `codes' or `representations'. An important example hailing from real analysis and topology is provided by open sets, which are represented by unions $\cup_{n\in \mathbb{N}}I_{n}$ where each $I_{n}$ is a basic open interval. Now, Montalbán has recently highlighted the importance of robustness of logical systems in Reverse Mathematics (abbreviated RM). It is then a natural RM-question whether basic properties of open sets are robust under slight modifications of the coding of open sets. Here, we study the representation where $I_{n}$ as above is either an open interval or the union of two such intervals but we cannot decide which one. Under this slight variation of the usual coding, basic properties of open and closed sets readily imply the relatively strong system ATR$_{0}$ from RM. Moreover, we obtain equivalences for the former properties and the enumeration principle. The latter states that countable sets can be enumerated and boasts many equivalences from Fourier analysis. Along the way, we investigate the RM-properties of the closure, interior, and boundary of sets of reals, a study interesting in its own right.

We prove that the Scott topology commutes with arbitrary products of countably presented frames and that every such product has a sober Scott space. In particular, this holds for arbitrary products of countable complete Heyting algebras. For a family of consonant spaces, Scott-product compatibility of their open-set lattices is equivalent to consonance of their topological sum. Countable generation does not suffice: a countably generated spatial frame can have a non-sober Scott space and fail the product identity for its square. We also show that the cardinal spectra of Scott non-sober frames and spatial frames are upward closed and, under the Continuum Hypothesis, consist of all uncountable cardinals. Finally, every Artinian $T_0$ web space is a $B$-space; if it is also a $d$-space, it carries the Scott topology of an algebraic dcpo. Consequently, every Artinian meet-continuous dcpo is algebraic. This yields a dichotomy theorem: a dcpo with a non-sober Scott space must fail meet continuity or Artinianity.

We prove that there is a 1-generic set which computes a uniformly almost everywhere dominating function. The proof has two ingredients: a Baire space version of the Chong-Downey Sigma01-density criterion and the forcing of Cholak-Greenberg-Miller.

A set B is AEWG if almost every set computes a weakly 1-B-generic. Extending two results of Hirschfeldt, Jockusch and Schupp, we prove that there is an AEWG superhigh r.e. set and every low2 r.e. set is AEWG.

This paper gives results which relate the definable Galois theory of [28] to the definable Galois cohomology of [18] in the setting of a totally transcendental first order theory. Firstly, we show that under some common assumptions the definable Galois cohomology of the extrinsic definable Galois group associated to fixed internality data classifies the number of definable Galois extensions inside a copy of the prime model. This generalizes a well-known result for Picard-Vessiot differential Galois theory shown originally via tannakian methods [3]. We then collate some triviality results for differential Galois cohomology [21] and recent results on iterated Picard-Vessiot extensions [10] [15] to give colimit formulas for differential Galois cohomology. Precisely, for an ordinary differential field $K$ of characteristic $0$ and a linear differential algebraic group $G$ over $K$, the differential Galois cohomology $\text{H}^1_{\delta}(K,G)$, is given by a colimit over the family of normal closures of iterated Picard-Vessiot extensions of $K$ of finite type. We then propose a new notion of boundedness for a differential field. We finally show that the minimal closure of a set of parameters $A$, the intersection of all elementary embeddings of a copy of the prime model over $A$ into itself, contains all of the definable Galois cohomological information for definable groups over $A$ satisfying also some strong but common conditions. Lastly, we give some colimit formulas for definable Galois cohomology and propose a model-theoretic definition of a bounded set of parameters.

We prove that every bounded-to-one action of a finitely generated commutative monoid has finite asymptotic dimension, without a freeness assumption. If the group completion has torsion-free rank $r$, we give an explicit upper bound $(3^{r+1}-3)/2$. This answers a question of Shinko, Weilacher and Yu, and extends a theorem of theirs.

We introduce d-minimal and b-minimal extensions, two weakenings of minimality based respectively on eventual domination and infinitely often domination. We prove that the generic extensions obtained by the full Mathias forcing and by Mathias forcing relative to Ramsey ultrafilters are d-minimal, whereas Hechler extensions are b-minimal. We also construct a d-minimal extension that is weakly $\omega^\omega$-bounding but neither minimal nor $\omega^\omega$-bounding, and realize every constellation of these properties compatible with their natural implications.

If ZFC is consistent, then so is ZF+DC+BPI+there is no Vitali set.

An algebra with binary operations $+,\cdot,\uparrow$ and constant $1$ is called an HSI algebra if it satisfies the basic commutative semiring laws for $+,\cdot,1$ on~$\mathbb{N}$ as well as the familiar index laws for exponentiation $\uparrow$. These basic axioms, known as the “High School Identities” are known to be incomplete, and an algebra satisfying $\HSI$ but failing an equation valid on ${\bf N}:=\langle \mathbb{N};+,\cdot,\uparrow,1\rangle$ is called a Gurevič algebra. It is currently unknown if there is an algorithm to recognise finite Gurevič algebras, and the best current result is that there exists a 12-element Gurevič algebra, and that none of the five 2-element HSI algebras are Gurevič algebras. We explain how the work of Alex Wilkie can be used to provide an algorithm for deciding validity of the equational laws of $\langle \mathbb{N};+,\cdot,\uparrow,1\rangle$, and use this to show that multiplicatively-idempotent HSI algebras satisfy all valid laws of $\langle \mathbb{N};+,\cdot,\uparrow,1\rangle$. As consequences of this result, we show that all 44 HSI algebras on 3 elements lie in the variety of $\langle \mathbb{N};+,\cdot,\uparrow,1\rangle$ (that is, are not Gurevič algebras), as well as 597 of the 657 models on 4 elements and 11158 of the 13577 models on 5 elements. A further consequence is that every Brouwerian lattice lies in the variety of $\langle \mathbb{N};+,\cdot,\uparrow,1\rangle$ (up to a simple term equivalence), showing that the variety of $\langle \mathbb{N};+,\cdot,\uparrow,1\rangle$ has continuum many subvarieties. The constant-free signature is also explored, and it is shown that in this case all $2$-element models of the constant-free High School Laws satisfy all valid constant-free laws in $\langle \mathbb{N};+,\cdot,\uparrow\rangle$.