Papers

Call a linear order type $\varphi$ Hagendorf if it shares two properties with additively indecomposable ordinal numbers without being one itself: $\varphi$ is strictly indecomposable to the right and whenever $\psi < \varphi$, then $\psi$ can be embedded into a proper initial segment of $\varphi$. In the 1970s, J. Hagendorf asked whether such types exist. F. Galvin observed that they must be uncountable, and soon thereafter, J. Larson proved that they cannot be scattered. We provide a simplification of her argument that might give additional insight into the $\sigma$-scattered case. We then show that consistently Hagendorf types exist and that this holds in many models of set theory, for instance under $\mathsf{BA}$ or $\mathsf{MA}_{\aleph_1}$. In fact, their non-existence has large cardinal strength. Furthermore, we construct real Hagendorf types from $\diamondsuit$ and from $\mathsf{PFA}$. This marks the first progress on this interesting problem since its description by Larson four dozen years ago.

{Non-contingency logic $(\KWL)$ replaces the usual necessity operator of modal logic with an operator expressing that a proposition is necessarily true or necessarily false. Besides its intrinsic logical interest, it admits natural interpretations as knowing whether in epistemic logic and as decidability under the arithmetical interpretation of provability logic. Although the semantics of non-contingency logic have been extensively studied, its proof theory remains comparatively underdeveloped. In this paper, we develop a uniform proof-theoretic framework for $\KWL$ over a broad class of frame conditions. Our approach is based on generalized path conditions (GPCs), a grammar-theoretic formalism that uniformly captures many standard modal frame properties. For every finite set $\gpc$ of GPCs, we construct a corresponding labelled sequent calculus. All calculi share a common set of logical rules and differ only by a single structural rule generated from $\gpc$, which captures the underlying frame conditions. We prove that these calculi are sound and complete with respect to their corresponding frame classes, thereby providing a uniform proof theory for a large family of non-contingency logics.}

We prove that, for every irrational $\xi$, any $F_\sigma$ additive subgroup of $\R$ has an $F_\sigma$ $\Q$-vector space extension of the same Hausdorff dimension satisfying $A+\xi A=\R$. Iteration gives simultaneous surjectivity for any prescribed countable family of irrational multipliers. Such a space exists in every prescribed dimension $d\in[0,1)$. We also construct in ZFC a zero-dimensional lightface $\Delta^0_3$ $\Q$-vector subspace $A$ for which $A+\xi A=\R$ holds for every irrational $\xi$, answering both parts of Question~2 of Ye, Yu, and Zhao. This universal group is a difference of two $F_\sigma$ sets, but is neither $F_\sigma$ nor $G_\delta$. Both constructions use direct inductions on finite binary strings and admit effective versions. As applications, we obtain zero-dimensional $F_\sigma$ groups whose Cartesian squares have Hausdorff dimension one, and relate their dilate sums to Marstrand's projection theorem.

Let $\Sigma_{1} = \mathbb{N}^*$ and $\Sigma_{k+1} = \overline{\mathbb{N}^* + \Sigma_{k}}$ be the cumulative depth filtration of $\beta\mathbb{N}$, the analogue for $(\mathbb{N},+)$ of a chain of closed ideals that Protasov and Protasova studied for discrete groups, where strict descent follows from a theorem of Lutsenko and Protasov. For every $k$ we give an explicit set whose closure meets $\Sigma_{k}$ but not $\Sigma_{k+1}$. Fix the doubly exponential sequence $e_{n} = 2^{2^{n}}$, partition it into $k$ subsequences $E_{0}, \dots, E_{k-1}$ by the residue of the index modulo $k$, and set $A_{k} = E_{0} + \cdots + E_{k-1}$. We prove that any sum $q_{0} + \cdots + q_{k-1}$ of free ultrafilters with $E_{t} \in q_{t}$ lies in $\Sigma_{k} \setminus \Sigma_{k+1}$. The engine is a master lemma, proved by induction on $j$: if a sum $F_{1} + \cdots + F_{j}$ of subsequences of $\{e_{n}\}$ with pairwise disjoint index sets belongs to a free ultrafilter $s$, then $s \notin \Sigma_{j+1}$. The proof rests on a single rigidity of the doubly exponential sequence: a fixed difference forces the largest index in any shift-intersection, once it is large, to cancel within its own subsequence, which makes every shift-intersection descend by at least one level. The same witnesses lie in the gaps of the pure filtration.

We give an exposition of some of the ideas leading up to Jacob Tsimerman's groundbreaking work developing the theory of o-minimal definability in arithmetic and algebraic geometry.

We determine the decidability of Karp's NP-complete problems on structures which are first-order definable over the theory of equality, also known as orbit-finite sets with atoms or nominal sets.

We prove a rank-preserving version of Gaifman's Theorem. Compared to earlier rank-preserving locality theorems (in particular, [Grohe, Kreutzer, Siebertz, JACM 2017]), our theorem is much simpler and yields formulas in exactly the same normal form as Gaifman's original theorem. Furthermore, it holds not only for first-order logic, but also for first-order logic with modulo-counting quantifiers and, more generally, for the first-order logic on weighted structures ngFOW+ that is introduced in this article. As an application of our theorem, we give a simplified proof of the algorithmic meta-theorem of [Grohe, Kreutzer, Siebertz, JACM 2017] stating that first-order properties of nowhere dense structures can be decided in almost-linear time. Our locality theorem for the weight logic ngFOW+ can be seen as an essential step toward such a meta-theorem for this logic.

We prove the equivalence of Hindman's finite sums theorem with a natural extension of Ramsey's theorem.

We define a class of classes of complete first-order theories, denoted by $\mathfrak{D}_{n\text{-var}}$, using positive consistency-inconsistency configurations and generalized indiscernibles. It contains the classes of stable, simple, NIP, NTP$_1$, NTP$_2$, NATP, NCTP, NBTP, NWP, NGP, and NPM$^{(k)}$ theories. For any dividing line $D\in\mathfrak{D}_{n\text{-var}}$ and any complete first-order theory $T\notin D$, we can always find a formula $\varphi(x,y)$ witnessing $T\notin D$ with an indexed set of parameters such that the set of its instances required to be consistent has a realization whose algebraic dimension over the whole set of parameters is $|x|$. We call statements of this form $n$-variable theorems, as they may be regarded as weak versions of one-variable theorems. Under the appropriate hypotheses on $T$, we prove that $T\in D$ if and only if the corresponding theory belongs to $D$ for (i) $T^{gt}$, (ii) $T_P$, (iii) $T^{ind}$, (iv) $T^G_K$, (v) ACF$_T$, and (vi) any completion of $T^{\bar\delta,nc}_g$. These are, respectively, the theories of generic trivializations, lovely pair expansions, $H$-structure expansions, vector spaces with a dense-codense generic $K$-subspace, algebraically closed fields with a distinguished subfield, and generic non-commutative derivations of algebraically bounded fields. The $n$-variable theorem is essential in proving (i)–(v). We also prove preservation for a special case of Mordell-Lang theories. We extend the framework to a larger class $\mathfrak{D}^h_{n\text{-var}}\supseteq\mathfrak{D}_{n\text{-var}}$, capturing higher-arity dividing lines such as NOP$_k$, NFOP$_k$, and NIP$_k$ for $1<k<\omega$. The $n$-variable theorem and preservation results (ii), (iii), (iv), and (vi) also hold for this larger class, while (i) holds assuming ${\rm acl=dcl}$.

We prove that if a minimal ordered structure $(M, <, \ldots)$ with infinite chains in an arbitrary language extending the language of strict orders interprets (in some power $M^n$) the linear order $(\omega, <)$, then this fact can be witnessed for $n=1$ via the incomparability relation of an $<$-definable strict order $R$; that $R$ is unique up to “almost equality”, i.e., finite rearrangements of elements of $M$; and that $R$ can be defined from $<$ in a constructive way. We also show that several variants of the question whether a minimal ordered structure interprets an infinite linear order are all equivalent.

The shallow embedding of higher-order modal logic in classical higher-order logic, used in Benzmüller and Scott's Notes on Gödel's and Scott's variants of the ontological argument, reaches beyond the modal object language: its quantifiers range over domains containing the nominals and satisfaction operators of hybrid logic. A proof using one proves a theorem of the embedding, not necessarily of the modal logic. Whether a result is one of the modal logic can be settled by replaying it in an explicit calculus, or, more cheaply and for all results at once, by analysing what the embedding's proofs substitute. Every statement the Notes prove has a proof in the embedding substituting nothing outside the object language, 294 of them explicit. The Notes' own proofs substitute none either; what it flags are terms a prover introduced. A soundness theorem over general models closed under the object language, and a sentence of that language the embedding proves but which fails in one of them, fix what the certificate says. The Notes' three open questions are settled too, without nominals, but by the empty instance of the conjunction axiom, too cheaply to convince. Generalised to Gödel's "any number of summands", the axiom covers the empty conjunction and the singleton. This article restricts it to at least two different conjuncts, a non-degenerate reading of Gödel's footnote, and settles them again without nominals. In effect only the empty conjunction is excluded; the singleton comes back with the other axioms. In one variant the restriction refutes the possible existence of a God-like being; the answers return, with no side condition, once the Notes' non-emptiness clause is confined to Gödel's essence. Every theorem here is verified in Isabelle/HOL and independently in Lean 4, the separating model in its propositional part; the countermodels are Nitpick's, checked by the build.

The problem to establish a lower bound for $\mbox{AC}^0[p]$-Frege refutations of a system of polynomial equations over ${\bf F}_p$ was in K. (2024) reduced to the existence of a pseudo-solution (a notion defined there) for the system. Here we reduce this further, for the system expressing the negation of the PHP, to a property of search trees querying values of linear maps on the vector space of low degree polynomials over ${\bf F}_p$.

We present an abstract framework for conservation and translation theorems between logical calculi. Unlike previous approaches, our setting does not require the underlying consequence relations to satisfy structural properties such as cut, allowing in particular for cut-free calculi. Moreover, we study translations between arbitrary calculi rather than only from a stable extension to the original calculus. Translations are formulated at the level of sequents by pairs of functions acting on antecedents and succedents, and the framework is developed for multi-succedent calculi while subsuming the single-succedent case. This yields a uniform treatment of classical results including negative translations, minimality theorems, Orevkov's conservation classes, and a characterisation of the least logic satisfying Kuroda's double negation theorem.

In this paper we contribute to the study of compactness properties for algebraic structures. We prove two compactness theorems in the context of almost projective modules from $\lambda$-strongly compact and weakly compact, respectively.

Let $R$ be a countable ring. Given an $R$-module $A$, we call a decomposition $A = \bigoplus_{i \in I} N_i$ a Kaplansky decomposition if each $N_i$ is countable. We characterize the uncountable Polish $R$-modules that admit a Kaplansky decomposition: they are exactly the modules of the form $B \oplus M^{\omega}$, where $B$ and $M$ are countable and $M$ is $\Sigma$-algebraically compact. The countable summand $B$ may moreover be taken to be an elementary submodule satisfying a closure condition, which makes $M^{\omega}$ unique up to isomorphism, and hence an invariant of $A$. We use this to characterize the countable rings admitting a free uncountable Polish $R$-module, generalizing results of Shelah and Solecki. This class of rings has a purely ring-theoretic description: it consists exactly of the countable left perfect and right coherent rings, i.e. the rings identified by Chase's theorem on products of projective modules. We observe that these are also exactly the countable $F$-rings, i.e. those countable rings $R$ for which $R^{\omega}$ is free. Finally, we give a ring-theoretic characterization of the countable rings $R$ for which there exists an uncountable projective Polish $R$-module.

We prove that every acylindrical action on uniformly locally finite product of trees induces the hyperfinite orbit equivalence relation on the Roller boundary. As a byproduct, we construct an example of a standard Borel space and two commuting bounded-to-one surjective partial Borel maps that generate a universal countable Borel equivalence relation. This contrasts to Shinko-Weilacher-Yu's theorem on hyperfiniteness of bounded-to-one actions of commutative monoids.

Jananthan and Simpson showed that special $\Pi^0_1$ classes exist in three of the four possible cases determined by whether the Join Property and the Pseudojump Inversion Property hold, leaving open the existence of a special $\Pi^0_1$ class with the Join Property but not the Pseudojump Inversion Property. We construct such a class, thereby answering their question affirmatively and completing the four-way existence pattern. Moreover, the class can be chosen to consist entirely of generalized low reals, with the Join Property holding locally on every nonempty relatively basic open subclass. More generally, every special $\Pi^0_1$ class contained in $\mathrm{GL}_1$ has a special $\Pi^0_1$ extension, still contained in $\mathrm{GL}_1$, on which the Join Property holds locally. We also show that no class contained in $\mathrm{GL}_1$ has the Pseudojump Inversion Property. An independent appendix proves that, for any class with the Join Property, every jump-inversion fibre above $0'$ is countably infinite.

Jananthan and Simpson asked in Conjecture~4.5 whether every pseudo-hyperjump $\operatorname{HJ}_e(X)=X\oplus V_e^X$, with $V_e^X$ uniformly $\Pi^1_1(X)$, admits Turing-degree inversion above Kleene's $\mathcal{O}$. We settle their conjecture in the negative. We construct one index $e_*$ such that $X<_{\mathrm T}\operatorname{HJ}_{e_*}(X)$ for every real $X$, while the range of $\operatorname{HJ}_{e_*}$ omits every Turing degree $\mathbf d$ such that $\deg_{\mathrm T}(\mathcal{O})\leq\mathbf d<\deg_{\mathrm T}(\mathcal{O}^{\mathcal{O}})$. Thus Conjecture~4.5 fails even for an operator which strictly raises the Turing degree of every input. Each of Properties~4.6–4.8 implies Conjecture~4.5; consequently, the accompanying class-characterisation problems collapse: no class of reals, even without a definability assumption, satisfies any one of these properties.

We show that the percolation components on a square grid can be $5$-colored as a factor of iid so that neighboring components get different colors. Above the critical probability, we observe that these regions can be 4-colored. Along the way, we extend the classical correspondence between fiid process and measurable labellings of the Bernoulli shift to this quotient setting, prove a general coloring result about hyperfinite pmp planar graphs, and clarify some foundational issues about how to define planarity for Borel graphs.

We can associate a compactness principle $\mathcal K_{\mathcal{D}}$ to the Constraint Satisfaction Problem (CSP) with constraint library $\mathcal{D}$. These principles were studied by Katáy, Tóth, and Vidnyánszky and by Rorabaugh, Tardif, and Wehlau. We expand their work comparing the strength of $K_{\mathcal{D}}$ for varying structures $\mathcal{D}$. We characterize the structures whose compactness principles are provable from ZF; these turn out to be the width-1 structures. We compare some important compactness principles, namely those of $2\text{SAT}$, $3\text{LIN}2$, and $K_2$, settling a question of Katáy, Tóth, and Vidnyánszky. And, we find an infinite chain and an infinite anti-chain of compactness principles related to directed cycles and finite choice.

We continue the study of selection principles in the uncountable setting initiated in [18] and further developed in [1]. We investigate several problems posed in [1] concerning the Scheepers diagram, the $\kappa$-Hurewicz Conjecture, and related questions on $\kappa$-Menger and $K_\kappa$-spaces. We determine the Scheepers diagram in the uncountable setting up to three unresolved implications and compute the critical cardinalities of several properties occurring in the diagram. For weakly compact $\kappa$, we show that there is a model of ZFC in which the $\kappa$-Hurewicz Conjecture fails; in particular, it cannot hold under GCH at $\kappa$. Moreover, any model in which $\kappa$ is weakly compact and the $\kappa$-Hurewicz Conjecture holds must satisfy $2^{\mathfrak{b}_\kappa} = 2^\kappa$. We also study the existence of $\mathfrak{b}_\kappa$-scale sets which are $K_\kappa$-spaces and derive a necessary tree-theoretic condition for such an example. Under the additional assumption of the Perfect Subtree Property, no $\mathfrak{b}_\kappa$-scale set is a $K_\kappa$-space. Consequently, under this assumption, every $\mathfrak{b}_\kappa$-scale set yields an alternative example of a $\kappa$-Menger space which is not a $K_\kappa$-space.

A class of graphs is monadically dependent if one cannot encode all graphs in coloured graphs from the class using a fixed first-order formula, and monadically stable if one cannot even encode arbitrarily long linear orders. Bonnet et al. (ICALP 2025) characterised monadic dependence by flip-separability: for every vertex weighting, boundedly many flips - complementations of the adjacency relation within a vertex subset - make every ball of radius $r$ carry at most an $\varepsilon$-fraction of the weight, so that every set carrying an $\varepsilon$-fraction has two elements pulled apart. We introduce flip-packability: boundedly many graphs, each obtained from the input by boundedly many flips and all determined by the weighting before any set is presented, such that every set carrying an $\varepsilon$-fraction of the weight has $m$ elements pairwise far apart in one of them. The number of flips producing each graph depends on the radius alone; only the number of graphs depends on $\varepsilon$ and $m$. We prove that a class of graphs is flip-packable if and only if it is monadically stable, and $2$-flip-packable, that is, flip-packable with $m=2$, if and only if it is monadically dependent. The passage from two scattered elements to $m$ is thus exactly what separates the two notions. For monadically stable classes we show that the flipped graphs can be computed from the weighting in cubic time. Varying the three parameters of the definition - the sparsifying operation, the radius, and the number $m$ of elements scattered - produces eight known characterisations of sparse and dense graph classes from the same template. In each case $m$ separates a depth-like notion from its width-like relaxation: treedepth from treewidth, shrubdepth from cliquewidth, and monadic stability from monadic dependence.

Motivated by recent work of Aguilera–Bagaria–Lücke and Aguilera–Bagaria–Goldberg–Lücke (ABGL), we analyze various effects of set-theoretic forcing upon the classes of exacting and ultraexacting cardinals. Using Magidor support products of Prikry forcings, we prove that an I2-embedding yields a transitive, set-sized model of ZFC with a proper class of exacting cardinals. We show that under Woodin's HOD Conjecture, no exacting cardinal can be a limit of exacting cardinals. In contrast, we prove that models of ZF containing large cardinals beyond choice have forcing extensions that are models of ZFC in which a regular cardinal is a stationary limit of ultraexacting cardinals. We also show that, assuming the HOD Conjecture, an analogue of the classical Levy–Solovay theorem holds for exacting and ultraexacting cardinals. Finally, we analyze the large cardinal properties possessed by exacting cardinals in HOD. We prove that if $\lambda$ is exacting and $V_\lambda$ satisfies the HOD Hypothesis, then $\lambda$ has strong large cardinal properties in HOD. Carrying forward forcing constructions from ABGL, we start with a model of ZFC with an I2-embedding and produce a model of ZF in which the successor of an exacting cardinal $\lambda$ is extendible in all models of the form $\mathrm{HOD}_x$ for $x\subseteq \lambda$.

We study filter-Laver forcing on omegaxomega with successor sets containing final quadrants. The observation retaining the minimum coordinate and orientation is a complete projection. Its finite nontrivial hidden-label quotients are Cohen, whereas the full offset quotient has Boolean density equal to the ground-model dominating number dV . For the associated grid-meager ideal I_box, we prove cov(I_box) = add(M) for the usual meager ideal M, and obtain further cardinal bounds. We also analyze threshold games, oracle degrees and the distinction between positive and filter-large certificate sets: recurrent filter-large acceptance admits refinements whose every branch succeeds. As an arithmetic application, we prove Wilfs inequality c \leq 13e for numerical semigroups with thirteen elements below the conductor c, where eis the embedding dimension. A complete arithmetic proof, including a bounded exact computation, is given in the appendix. Its terminating certificate procedures supply a computable quadrant tree and uniform refinements for every forcing condition. Finite support kernels describe persistence of the registered proofs; arithmetic absoluteness explains precisely why forcing organizes these certificates without replacing their arithmetic justification.

We build on the recent development that toposes with enough points can be represented as categories of points equipped with ultraconvergence data (a.k.a. virtual ultracategories), characterizing usual classes of geometric morphisms — surjections, embeddings, hyperconnected maps, and localic maps — in terms of their points. In particular, the characterisation of geometric surjections relies on a notion of "virtual ultraretractions", which generalises usual retractions and filtered colimits, categorifies Johnstone's notion of subclosure for topological spaces, and provides a new characterisation of separating classes of points of a topos.

The goal of this paper is to refine methods in computable analysis and to employ them in the study of solutions of an optimization problem posed by Bellman. This problem asks how to find optimal (shortest) paths which do not fit into given plane figures. We show that each instance of Bellman's problem has an arbitrarily small uniformly computable perturbation for which the minimal length of path is computable, and thus the class of optimal paths is a $\Pi_1^0$ class, and there are uniformly computable paths which escape with arbitrarily small length greater than the minimum possible.

Let $P$ and $Q$ be proper upward monotone unary generalized quantifiers on a fixed domain $D$. We study the validity, over all structures $M$ with domain $D$, of \[ M \models Px\,Qy\,R(x,y) \rightarrow Qy\,Px\,R(x,y), \] called scope dominance. The iteration of two quantifiers lies between their branching product, which is generated by rectangles, and the dual of the branching product of their duals. We give criteria for equality with these bounds, obtain a new proof of the countable characterization of scope dominance, and characterize the case in which the inner quantifier is "at least $\kappa$ many." Under the Generalized Continuum Hypothesis, Goldberg's theorem shows that, for ultrafilters, scope dominance is equivalent to equality between iteration and the branching product, whereas an elementary counterexample on a domain of size $\aleph_2$ shows that this equivalence fails for arbitrary upward monotone quantifiers. For the case where both quantifiers are filters, the question becomes set-theoretic: the existence of a counterexample is equiconsistent with the existence of a measurable cardinal.

In this article, we prove that the theory $T_3$ of groups of exponent $3$ has a model companion. Previous work established the existence of model companions for theories of groups of fixed finite exponent and nilpotency class at most $2$ (Saracino–Wood), and for theories of groups of prime exponent $p$ and nilpotency class at most $c<p$ (Maier). These results do not cover $T_3$, since groups of exponent $3$ may have nilpotency class $3$. Our theorem verifies the $n=3$ case of a conjecture proposed by the third author that, for each integer $n>1$, the theory $T_n$ of groups of exponent $n$ has a model companion if and only if every finitely generated group of exponent $n$ is finite, or equivalently, if and only if the Burnside problem has a positive solution for exponent $n$.

We present two new applications of Simmons' point-free Cantor-Bendixson coderivative operator in intuitionistic logic. First, we use it to give a simplified proof of the recent result of Xu and Ye that the free Heyting algebra on two generators does not occur as the Heyting algebra of subterminal objects in any elementary topos. Then we use it to prove that complete Heyting algebra semantics is not strongly complete for intuitionistic second-order propositional logic: semantic consequence from an arbitrary set of assumptions does not coincide with ordinary syntactic consequence.

Let $\mathcal I$ be an admissible ideal on $\mathbb N$. Zhou, Liu, Liu, and Lin asked whether every regular space with a $\sigma$-hereditarily closure-preserving $\mathcal I$-$sn$-network is $\mathcal I$-$sn$-metrizable. The answer is affirmative for every admissible ideal. The proof rests on a local countability theorem. If $y_n\to_{\mathcal I}x$ and $\{n\mid y_n\ne x\}\in\mathcal I^+$, then every point-discrete family of $\mathcal I$-sequential neighborhoods of $x$ is countable. In a $T_1$ space, this applies in particular to every HCP family. If no $\mathcal I$-convergent sequence to $x$ has $\mathcal I$-positive support away from $x$, then $\{x\}$ is an $\mathcal I$-sequential neighborhood. It follows that every space with a $\sigma$-point-discrete $\mathcal I$-$sn$-network is $\mathcal I$-$snf$-countable. This conclusion, together with the characterization theorems of Ge and of Zhou, Liu, Liu, and Lin, settles Problem 5.2. The countability bound cannot in general be strengthened to finiteness. A countable Rudin–Keisler antichain of free ultrafilters gives an admissible ideal for which local HCP-finiteness fails. Every $P^{-}$ ideal has local HCP-finiteness. Preservation theorems for Fubini products, heterogeneous Fubini sums under cross-row Katětov absorption, and suitable increasing unions extend local HCP-finiteness beyond the $P^{-}$ class. They apply to the finite Fubini powers of $\mathrm{Fin}$, Katětov's first limit-stage ideal $\mathrm{Fin}^{\omega}$ and its finite successors, the tree-derived rank-$\omega$ ideal $\mathcal H_{<\omega}$, and the inductive-limit ideal $\mathrm{Fin}_{\omega}$. Every listed example other than $\mathrm{Fin}$ fails $P^{-}$.