Papers

We introduce a novel extension of reflection calculus, $\mathsf{RC_{BI}}$, to analyze a family of extensions of $\mathsf{ACA}_0$ generated by uniform $\omega$-model and syntactic reflection principles, together with several other related operators. The union of these theories coincides with the theory of Bar Induction ($\mathsf{BI}$). We prove that $\mathsf{RC_{BI}}$ is arithmetically sound, and that it is sound and complete with respect to a natural class of Kripke models. Leveraging these modal semantics, we demonstrate that the class of theories denoted by $\nabla$-free closed formulas is a pre-wellordering with respect to $\Pi^1_1$-soundness and consistency strength. This allows us to establish an ordinal analysis for $\mathsf{BI}$ and its fragments, analogous to Beklemishev's analysis of $\mathsf{PA}$. The structural properties of $\mathsf{RC_{BI}}$ naturally give rise to a novel ordinal notation system for the Bachmann-Howard ordinal which differs substantially from existing representations.

We construct countable, stable, $\omega$-categorical structures with at most two binary relations whose CSPs exhibit three complexity regimes: NP-complete, decidable but not in NP, and undecidable. The templates arise from a controlled Hrushovski construction of stable $\omega$-categorical graphs $M_\alpha$ for suitable irrational parameters $\alpha>1$. Some of these graphs have NP-complete CSPs. Expanding the graphs $M_\alpha$ by the non-edge relation turns age membership into a restriction of the CSP. For every time-constructible bound $t$, there is such an expansion whose CSP is decidable but not in DTIME$(t)$. For an explicit parameter $\alpha$, the restriction to complete instances belongs to $\mathrm{coNP}$ and the full CSP belongs to $\Sigma_2^{\mathrm P}$. Separating the ages of the $M_\alpha$ using graphs with large girth and prescribed density yields $2^{\aleph_0}$ distinct CSPs of these expansions, all but countably many of which are undecidable.

Let $k_0$ be a field of characteristic $0$, and let $C/k_0$ be a smooth geometrically integral curve of positive genus with $C(k_0)=\varnothing$. We prove that the regular inverse Galois problem is solvable over every field existentially closed in the class of $k_0$-fields avoiding $C$, including the curve-excluding fields of Johnson and the author. To this end, we show that for every finite group $G$, there is a parameter variety over $\mathbb Q$ whose function field admits a regular realization of $G$ without adding points to $C$. Finally, we establish $\mathrm{RIGP}$ over the variety-excluding fields of Szachniewicz and the author, when the excluded variety is a locally closed subvariety of an abelian variety.

We examine the metamathematical significance of the Levy scheme $\Lambda$, which asserts, for each natural number $n$, the existence of an $n$-Mahlo cardinal $\kappa$ such that $V_\kappa\prec_{\Sigma_n}V$. Several initially unrelated constructions single out $\mathsf{ZFC}+\Lambda$: comparisons with the model theory of arithmetic and finite set theory; class theories in which the class of ordinals has the tree property; set theories with a proper class of indiscernibles; and interpretations of ordinary set theory in Cantorian parts of models of the extension $\mathsf{NFUA}$ of Quine–Jensen set theory $\mathsf{NFU}$. Taken together, these results provide a precise sense in which $\mathsf{ZFC}+\Lambda$ is an inevitable extension of $\mathsf{ZFC}$ if one attempts to generalize certain metamathematical results about the universe of all finite sets to the entire universe of sets.

Assuming $\mathrm{AD}^+ + V = L(P(\mathbb{R}))$, we show that the Ultrapower Axiom holds in $\mathrm{HOD}_s$ for every $\omega$-sequence of ordinals $s$. We use this result to analyze the structure of Nairian models, showing that they contain many measurable cardinals. As an application, we establish the consistency of the existence of infinitely many consecutive measurable cardinals with ZF, starting with a Woodin limit of Woodin cardinals. This solves a question of Henle, Mathias, and Woodin. From the same large cardinal hypothesis, adapting a forcing technique of Adkisson and Ben-Neria, we produce a model of ZF in which every uncountable cardinal is singular. Gitik's original construction requires a proper class of strongly compact cardinals.

We continue the study of beautiful pairs of henselian valued fields, initiated in joint work of the second author with Cubides Kovacsics and Ye. As our main result, we show that separably closed non-trivially valued fields of arbitrary imperfection degree admit beautiful pairs which are elementary pairs satisfying certain natural axioms. They satisfy beauty transfer, i.e., saturated models of their theory are again beautiful. The same holds for beautiful pairs associated to natural subclasses of all definable types, most notably for all definable types orthogonal to the value group and for all bounded definable types. This yields strict pro-definability of the space of the definable types from any of these classes, in the theory SCVF of separably closed non-trivially valued fields. We also show a separable analog of a classical result of Keisler's, namely that the first order theory of an infinite separable extension $L/K$ of fields - considered in the pairs language and where the large field $L$ is separably closed, is determined by the theory of the small field $K$ together with the imperfection degree of $L$ over $K$.

We prove that every chain-continuous dcpo is continuous and that its way-below relation is the relational square of its chain-below relation, answering a question of Erné. A subalgebra lattice obtained from a locally finite Jónsson algebra shows that the chain-below relation itself need not interpolate. For approximation by Scott-closed sets, we give a finite-upper-bound characterization on lower-set lattices and characterize interpolation by an extension property for directed lower sets. This yields a countably based, completely distributive algebraic lattice on which chain and directed approximation coincide, whereas Scott-closed approximation fails to interpolate, answering questions of Erné and of Ho and Zhao.

We characterize several properties of higher-arity function classes, specifically finite $\VC_k$-dimension, slicewise finite $\VC$-dimension, and finite slicewise Littlestone dimension, in terms of generalizations of Rademacher complexity. These characterizations sets up simple new proofs of several results on finite $\VC_k$-dimension and slicewise finite $\VC$-dimension. These include the preservation of finite $\VC_k$-dimension under taking expectations and uniform law of large numbers statements for both properties. All of these results apply naturally to real-valued function classes as well as boolean-valued classes. We also prove a new adversarial uniform law of large numbers for classes with finite slicewise Littlestone dimension.

Finite convexly ordered binary branching $C$-relations have been viewed as a notable exception to the broad applicability of the partite construction in structural Ramsey theory. The absence of a proof of their Ramsey property by the partite construction was noted by Bodirsky in his 2015 survey and pointed out again by Hubička and Konečný in their 2026 survey. We overcome this limitation by giving proofs based on the partite construction of the known Ramsey properties of the class $\mathcal{CT}$ of finite convexly ordered treeable meet semilattices and of the classes of finite convexly ordered $C$-relations with arbitrary branching and with binary branching. Our proofs do not rely on Milliken's tree theorem. The key is to expand $\mathcal{CT}$ by level predicates and a predecessor function so that the locally finite subclass method applies. We then transfer the resulting Ramsey witnesses to the corresponding reduct classes and to the classes of convexly ordered $C$-relations.

We study definability in fixed-point logic with counting (FPC) for a class of constraint satisfaction problems (CSPs) that simultaneously generalises finite-domain CSPs and temporal CSPs. The templates for the CSPs are first-order expansions of the structure $([k] \times {\mathbb Q};<_1,\dots,<_k,\sim)$ where $<_i \, := \{((i,x),(i,x')) \mid x<x'\}$ and $\sim \, := \{((i,x),(i,x')) \mid i \in [k], x,x' \in {\mathbb Q}\}$, i.e., $k$ copies of $({\mathbb Q};<)$. Such a CSP is definable in FPC precisely when the template pp-constructs neither the ternary temporal relation $X$, which holds on three elements if the minimum is attained exactly twice, nor a nontrivial finite affine structure. Equivalently, the template has global polymorphisms that witness the tractability of the temporal CSPs on the copies, and that provide 3-4 weak near-unanimity operations on the set of copies of ${\mathbb Q}$. In this case, we prove that the CSP is even expressible in the less expressive logic FP$^*$, which is the restriction of FPC without counting terms (i.e., the extension of first-order logic by a fixed point operator and an ordered auxiliary number sort). Our algorithm samples finitely many values in each copy and then performs nested constraint-singleton consistency tests (which is a uniform polynomial-time algorithm for finite-domain CSPs). The correctness proof uses finite-domain CSP theory to combine consistency certificates by a single polymorphism term, fixing each variable to one copy without destroying the certificates needed for the temporal algorithm. We then use a known normal form for algebraic products to control the remaining interactions between different copies.

We investigate the relationships between fragments of SRP and diagonal reflection principles. It turns out that the subcomplete fragment of SRP, augmented with CH, implies that the nonstationary ideal on $\omega_1$ is not saturated, but that Larson's diagonal reflection principle $OSR_{\omega_2}$ holds. In contrast, it was known that the full principle SRP implies the saturation of the nonstationary ideal on $\omega_1$, but it does not imply $OSR_{\omega_2}$. We find several instances of this phenomenon: pairing (variations of) the subcomplete fragment of SRP with stronger failures of the nonstationary ideal on $\omega_1$ to be saturated allows us to conclude more instances of diagonal reflection principles, while boosting (the corresponding variations of) the full principle SRP with strong forms of the saturation of the nonstationary ideal allows us to produce models where these principles still hold, yet weaker versions of diagonal reflection fail.

Törnquist (arXiv:1310.3250) proved that if there exists a $\boldsymbol{\Sigma}^1_2$ maximal almost disjoint (MAD) family, then there exists a $\boldsymbol{\Pi}^1_1$ MAD family. Since then, several other "complexity reduction" proofs have been found for other combinatorial objects, such as maximal independent families or ultrafilters. All of these proofs have relied on $\boldsymbol{\Pi}^1_1$-uniformization, so they did not easily lift to higher projective levels. In this paper, we introduce a principle weaker than Uniformization which we call "Functional Projection", and show that this principle is sufficient for most complexity reduction proofs. On the other hand, we prove that in $L[U]$, the canonical inner model for a measurable cardinal, Functional Projection holds for $\boldsymbol{\Pi}^1_2$ relations. As an immediate corollary, we obtain that in $L[U]$ there are $\boldsymbol{\Pi}^1_2$ witnesses for many combinatorial families.

We examine various applications of logic to $\mathrm{AW}^*$-algebras, particularly the monotone completeness conjecture. We develop a model theory for $\mathrm{AW}^*$-algebras equipped with a faithful normalized quasitrace. Using this language, we provide a separable coding which allows us to reduce the finite case of the monotone completeness conjecture to monotone sequential completeness of $\mathrm{II}_1$ $\mathrm{AW}^*$-factors. Combining an explicit recursive axiomatization with the completeness theorem for continuous logic, we show that this case of the conjecture, and Kaplansky's problem whether every $\mathrm{AW}^*$-factor of type $\mathrm{II}_1$ is a von Neumann algebra, are each equivalent in ZFC to a $\Pi^0_2$ sentence of arithmetic, so that their answers are the same in every $\omega$-model of ZFC. We also consider real $\mathrm{AW}^*$-algebras. Here the Baer-$*$-ring notion of an abelian projection must be distinguished from commutativity; following the real-operator-algebra terminology we call the former semi-abelian. Handelman's matrix theorem implies that a real $\mathrm{AW}^*$-algebra with no nonzero central semi-abelian projection has $\mathrm{AW}^*$ complexification. We answer a number of other open problems in real $\mathrm{AW}^*$-algebras.

A class of models which brings to the fore the inner logic of the calculus of probability instead of assigning probabilities to sentences is introduced and investigated.

In this paper we develop several aspects of the algebraic theory of Girard algebras, regarded as the equivalent algebraic semantics of multiplicative additive Linear Logic $\mathsf{MALL}$. The main structural results concern the bottom of the subvariety lattice of the variety of Girard algebras: varieties generated by simple Girard algebras generated by the constants correspond exactly to the atoms of the lattice. Moreover the lattice itself is atomic, i.e. every nontrivial subvariety contains an atom. These atoms can be represented uniformly by the maximal filters of the free algebra generated by the constants. Moreover every congruence of this free algebra is realized by a subvariety, and the resulting atom-support topology records the behavior of arbitrary joins: the atoms below a join of atoms are precisely the points in the closure of the corresponding subset of the spectrum. The concrete constructions show that the bottom of the lattice is already quite rich. Besides determining the integral and degenerate boundary cases and exhibiting finite modular and nonmodular atoms and chains of covers, we constructed infinite families of atoms whose topology reflects genuinely infinitary behavior; thus finite and infinite joins behave essentially differently at the bottom of the subvariety lattice. On the logical side, these results yield $2^{\aleph_0}$ Post-complete extensions of $\mathsf{MALL}$.

We show that every proper variety of distributive $\ell$-pregroups is periodic; as a result, the subvariety lattice of the variety of distributive $\ell$-pregroups decomposes into a disjoint union of bounded intervals each consisting of all properly $n$-periodic varieties, for different $n \in \mathbb{Z}^+$. On the way, we study non-periodic (one-generated) subalgebras of $\mathbf{F}(\mathbb{Z})$ and show that they either contain a non-periodic idempotent or they contain idempotents of arbitrary big periodicity. The same results holds for non-periodic one-generated subalgebras of $\mathbf{F}(\mathbf{J} \overrightarrow{\times} \mathbb{Z})$, where $\mathbf{J}$ is a chain, generated by a composite element and the resulting idempotents can be taken to be local in the associated wreath product.

Assuming that $\mathcal{P}(\omega)$ is tightly $\sigma$-filtered, we prove that $C(\omega^*)$ fails the ball fixed point property. This axiom holds under the continuum hypothesis and in the $\aleph_2$-Cohen model. The proof shows that the Stone space of the countable–cocountable algebra $\operatorname{Cc}(\omega_1)$ is a continuous retract of $\omega^*$ and uses the equivalence between tight $\sigma$-filteredness of $\operatorname{Cc}(\omega_1)$ and of $\mathcal{P}(\omega)$. We also prove that the quotient of a tightly $\sigma$-filtered Boolean algebra $B$ with the countable separation property by an $\aleph_1$-generated $P$-ideal is a Boolean retract of $B$.

Recently, two exponentiations of ultrafilters have been introduced in [7]. We rephrase them in nonstandard terms, and use the nonstandard formulations to characterize some of their properties. We also study their relations with divisibility by introducing factor-picking functions and highly exponential ultrafilters.

Fix a finite alphabet $\Sigma$ having at least two letters, and natural numbers $n,k\geq 1$. We denote by $D_n(\mathbf{\Pi}^0_k)$ the class of differences of $n$ subsets of the Cantor space $\Sigma^\omega$ in $\mathbf{\Pi}^0_k$, and by $\checked{D}_n(\mathbf{\Pi}^0_k)$ the class of complements of sets in $D_n(\mathbf{\Pi}^0_k)$. We prove, for any natural numbers $n,k\geq 1$, the existence of a finite alphabet $\Sigma$ having at least two letters and a finitary language $U_{n,k}$ over $\Sigma$ accepted by a one-counter automaton such that the $\omega$-power $$U_{n,k}^\infty:=\{ w_0w_1\cdots\in\Sigma^\omega\mid\forall i\in\omega ~~w_i\in U_{n,k}\}$$ is $D_{2n-1}(\mathbf{\Pi}^0_k)$-complete. We also prove a conditional result for the dual classes $\checked{D}\_{2n}(\mathbf{\Pi}^0\_k)$: under the assumption that there exists a finitary language $V_{n,3}$ accepted by a one-counter automaton, such that its $\omega$-power $V_{n,3}^\infty$ is $\checked{D}_{2n}(\mathbf{\Pi}^0_3)$-complete, there would also exist, for any integer $k>3$, a finitary language $V_{n,k}$ accepted by a one-counter automaton, such that its $\omega$-power $V_{n,k}^\infty$ is $\checked{D}_{2n}(\mathbf{\Pi}^0_k)$-complete. Finally we add another conditionnal result about Wadge degrees of rational $\mathbf{\Delta}^0_2$ omega powers, which completes the recent results of [FGL26].

A first-order theory $T$ has the finite model property if every first-order sentence that is implied by $T$ has a finite model. We give a characterization of when a complete $\omega$-categorical theory $T$ has the finite model property. The characterization makes it possible to transfer stability theoretic results in [29] to certain classes of finite structures. This approach also gives information concerning properties that a sequence of finite “base structures” of ever larger size must have in order for its random expansions to a larger vocabulary to have a chance to satisfy a convergence law for first-order logic.

We show that if an automorphism $\pi$ of the truth-table degrees is induced by a Baire measurable function $F\colon 2^{\omega}\to 2^{\omega}$, or merely induced on some comeager set by a continuous function, then $\pi$ is the identity. The same results hold for the weak truth-table degrees. The argument is an adaptation to truth-table reducibility of OpenAI's recent proof that the Turing degrees are rigid.

The periodic tiling conjecture asserts that if a bounded set $\Omega\subset \mathbb R^d$ of finite measure tiles $\mathbb R^d$ by translations, then it admits at least one fully periodic tiling. This conjecture was proved to hold in $\mathbb R$ by Lagarias and Wang, and was recently disproved by Greenfeld and Tao in sufficiently high dimensions. Its discrete analogue in $\mathbb Z^2$ was proved by Bhattacharya, whereas the conjecture in $\mathbb R^2$ remains open. In this paper, we analyze the structure of tilings by axis-parallel polygonal sets: bounded open sets in $\mathbb R^2$ whose boundary is a finite union of line segments parallel to the axes. We prove that every such tiling that is topologically minimal is weakly periodic. Moreover, we show that if an axis-parallel polygonal set $\Omega$ tiles $\mathbb{R}^2$ then it admits a quasi-periodic tiling (i.e., a finite union of translated lattices). The proofs combine geometric decompositions of tilings with rational approximation and discrete tiling theory. As a consequence, we obtain that the translational tiling problem for axis-parallel polygonal sets with real algebraic vertex coordinates is decidable.

We present a faithful translation from Aloni's logic BSL into a classical modal logic over semilattices combining ideas from earlier modal translations of truthmaker semantics with algebraic representation theory. We show how our method can also be made to work for other current hyperintensional logics. Finally, we place our results in a broader setting of translating hyperintensional logics into classical modal ones, and discuss applications and new challenges that arise for both areas of philosophical logic connected in this way.

We construct a sentence of $L_{\omega_1,\omega}$ having exactly $\aleph_1$ many countable models up to isomorphism, but no perfect set of non-isomorphic models. This disproves Vaught's conjecture for infinitary logic. The construction follows a framework devised by Robin Knight, and the proof has been formally verified in Lean.

We present a typed proof-term calculus for intuitionistic intensional first-order logic with Hilbert's epsilon-operator and prove its soundness and completeness with respect to hyperdoctrinal models with thin bicartesian closed setoid categories (BiCCCs) as fibres and formula-indexed witness selections. The calculus provides an explicit internal language for these epsilon-hyperdoctrines: for each fixed typed signature, its syntactic term model is initial for syntax-indexed, interpretation-preserving model morphisms, with uniqueness up to setoid equality. The nested epsilon syntax is organized by a well-founded dependency relation on formula labels. Concrete countermodels exhibit failure of excluded middle and show that formula conversion need not identify the selected witnesses. We also compare the full calculus with its epsilon-free and epsilon-only fragments. The principal constructions and metatheorems are formalized in Rocq. With setoid BiCCCs, proof irrelevance is a choice of equality, not the erasure of proofs: the proofs and their categorical operations remain available as the basis for a future proof-relevant categorical semantics.

A central object in the theory of proof complexity generators is Krajicek's local witness model. We construct a new such model as a definable ultrapower using a definable version of a selective ultrafilter over a model of arithmetic. We transfer some set theory of combinatorial ultrafilters to the definable nonstandard setting.

We give an explicit countably infinite orthomodular lattice generated by three specified elements and a direct argument that it admits no injective homomorphism into any $\sigma$-complete orthomodular lattice. In particular, it does not embed into any set-sized complete orthomodular lattice. The source is a generated subalgebra of a cofinite reduced product of finite-dimensional real subspace lattices. A nonzero finite term $a$ is orthogonal to the orbit of a terminal line under every finite word in three Sasaki projections, while another finite term $X$ satisfies $\pi_a\pi_X(t)=a$. If the image of this countable orbit has a supremum in a target orthomodular lattice, Sasaki adjunction forces that supremum to commute with the generator images. This forces the image of $a$ to vanish. The proof imposes no atomicity, modularity, Hilbert representation, cardinality bound on the target, or preservation of source infinitary operations. All target lemmas are derived from the orthomodular axioms.

We formulate a proof of Part~I of Martin's conjecture for order-preserving maps directly on the quotient of the reals by Turing equivalence. The assumptions are countable choice for reals, the perfect-set property for sets of reals, and continuous uniformization on a comeager domain. The argument applies under $\mathsf{AD}+\mathsf{DC}_{\R}$ and inside the choiceless Solovay model. We then determine the exact consistency strength of the unrestricted order-preserving dichotomy as an axiom over $\mathsf{ZF}+\mathsf{AC}_{\omega}(\R)$: it is equiconsistent with $\mathsf{ZFC}$ plus a strongly inaccessible cardinal.

Let $T$ be the theory of the valued field of complex Laurent series $\mathbb{C}(\!(t)\!)$ in the language of rings expanded by a constant for $t$ and by predicates for $n$-th powers. We introduce a $t$-adic analogue of Kochen's operator, namely $\gamma(x)=x/(1+tx^{2})$, and the associated Kochen ring $\Lambda_{L}$ of a field extension $L$ of a model $K$ of $T$. Our main result characterizes the field extensions of $K$ which embed into a model of $T$ (the formally $T$-adic} fields): $L$ is formally $T$-adic if and only if $1/t\notin\Lambda_{L}$. As an application we prove a Nullstellensatz for $\mathbb{C}(\!(t)\!)$: a polynomial $f\in K[X_{1},\dots,X_{n}]$ vanishes on the zero set of an ideal $I$ if and only if $f^{m}=\sum_{i}\omega_{i}f_{i}$ for some $m\geqslant 1$, generators $f_{i}$ of $I$ and coefficients $\omega_{i}$ in the ring $\Lambda_{K(X)}\cdot K[X]$. We derive the resulting correspondence between $R$-ideals and algebraic sets, and we compare natural incarnations of the associated $T$-spectrum: prime ideals, morphisms into models of $T$, and the space of types of $T$.

Andrews, Ganchev, Kuyper, Lempp, Miller, A.\ Soskova, and M.\ Soskova conjectured that skip-cototality coincides with weak cototality. We show that the conjecture is false by constructing a $\Pi^0_2$ set whose skip does not have a cototal degree. We further adapt this construction to obtain additional results. We prove that for each odd $n$, there is a $\Pi^0_{n+1}$ degree whose $n$-iterated skip does not have a cototal degree. We show that there is a $\Pi^0_2$ degree which does not contain an introenumerable set.