Papers

The Laver Partition Theorem is a fundamental tool in the analysis of Laver and Hechler forcings. It is also connected to determinacy and the Galvin-Prikry theorem: indeed it can be seen as the common core of these two theorems. We study the reverse mathematics and Weihrauch degrees of the Laver Partition Theorem restricted to open and clopen sets. We obtain upper and lower bounds on the proof theoretic strength of this result, as well as a precise picture of the (arithmetical) Weihrauch degrees of the problems related to it.

Given a first-order theory $T$ (in discrete or continuous logic) and a Borel-definable global Keisler measure $\mu$ in $T$, we show that the following conditions are equivalent: $(i)$ $\mu$ is a frequency interpretation measure; $(ii)$ $\mu$ is definable and its canonical "random extension" $r_\mu$ is generically stable in the randomization theory $T^R$; $(iii)$ $\mu$ is "self-averaging". This result establishes a robust notion of generic stability for Keisler measures, which resolves a long-term research objective from previous work. The implications $(i)\Rightarrow(ii)\Rightarrow (iii)$ were previously established by the authors (for $T$ discrete). The primary focus of this paper is the reverse implications $(iii)\Rightarrow (ii)\Rightarrow(i)$. We also prove that generically stable measures are closed under Morley products, answering another well-known question that was open even in the case of types. These results are obtained through the use of AI models.

We continue the study of compactness phenomena between the set-theoretic universe and $\mathrm{HOD}$ initiated by Goldberg–Poveda \cite{GolPov}. We focus on compactness phenomena around the power-set functions of $V$ and $\mathrm{HOD}$. We prove: (1) A singular strong limit cardinal with uncountable cofinality cannot be the first place where $\mathcal{P}(\cdot )$ and $ \mathcal{P}^{\mathrm{HOD}}(\cdot)$ disagree. (2) Assuming the existence of a measurable cardinal, $\aleph_\omega$ can be the first place where $\mathcal{P}(\aleph_\omega)\neq \mathcal{P}^{\mathrm{HOD}}(\aleph_\omega)$, answering a question of Hayut. (3) If $\kappa$ is strong limit singular of uncountable cofinality, $\mathrm{HOD}$ is correct about cardinals less than or equal to $\kappa^+$ and the GCH holds in $\mathrm{HOD}$ below $\kappa^+$ then $(\mathrm{HOD}, V)$ has the $\mathrm{cf}(\kappa)^+$-cover property. We also show that the GCH assumption in (3) is necessary, which demonstrates that Magidor's classical Covering Theorem is optimal.

We construct the category of overt discrete quasi-Polish spaces and the category of compact Hausdorff quasi-Polish spaces (and some of their subcategories) as internal categories of the category of effective quasi-Polish spaces and computable maps. To demonstrate that the constructions are natural, we show that Stone duality is computable, in the sense that the dual contravariant functors and the natural transformations demonstrating their adjointness are computable.

The weak set theory $\mathsf{ReR}$ is obtained from Kripke-Platek Set Theory ($\mathsf{KP}$) by replacing the bounded collection scheme with the bounded replacement scheme. We show that $\mathsf{ReR}$ proves $\mathsf{TCo}$, which asserts that every set is contained in a transitive set. This is used to show that the theories obtained by adding the negation of the axiom of infinity to $\mathsf{ReR}$ and $\mathsf{KP}$ have the same consequences. Our proof of $\mathsf{TCo}$ relies on the availability of a fragment of class foundation in $\mathsf{ReR}$. To demonstrate the necessity of this reliance, even in the presence of infinity, we build a model of a significant fragment of $\mathsf{ZF}$ that includes bounded separation and collection, infinity, powerset, regularity and the axiom of choice, in which $\mathsf{TCo}$ fails.

We study the reverse-mathematical strength of frame definability in modal logic. The central principle is the Valuation Extension Lemma (VEL), which asserts that every assignment of propositional variables on a frame extends to a full valuation. We show that, over $\mathrm{RCA}_0$, VEL is equivalent to $\mathrm{ACA}^{+}_0$, and as are frame-definability principles for Geach axioms and for $\mathbf{GL}$. We also obtain analogous $\mathrm{ACA}^{+}_0$-equivalences for the Barcan and Converse Barcan formulas in modal predicate logic. Finally, we examine variants of VEL for $\mathbf{CTL}$ and $\mathbf{LTL}$ and locate their strengths between familiar subsystems of second-order arithmetic.

For every uncountable regular cardinal $\alpha$, $\mathbb S^{\ast}(\alpha)$ is an explicitly typed four-coordinate forcing motivated by the ladder-system construction of Hayut and Magidor. The forcing is $\sigma$-closed and, after adjoining a formal maximum, $\alpha$-strategically closed. For $\alpha\geq\omega_2$, every nonempty countable family of designated generic branches has a stationary and costationary common trace on the generic ladder-coordinate set $L_\alpha$, while no countable family of cofinal branches generates $L_\alpha$. These conclusions persist under a Kurepa-style level-size bound. In the unrestricted forcing, for every infinite cardinal $\mu<\alpha$ in the ground model, some level of the generic tree contains a copy of $({}^\mu 2)^V$. Consequently, the endpoint-corrected restriction family indexed by $\mathcal P_{\omega_2}\alpha$ is too wide, whereas the scaled restriction system indexed by $\mathcal P_\alpha\alpha$ has all levels of size less than $\alpha$ exactly when $\alpha$ is strongly inaccessible in the ground model. When these equivalent conditions hold, the branch-covering number of $L_\alpha$ relative to the scaled system is at least $\omega_1$. The low-cofinality empty-value convention also ensures that the set of domains of $L_\alpha$ contains no club in $\mathcal P_\alpha\alpha$. The unrestricted tree clause of the motivating presentation is retained, without asserting forcing equivalence.

We show that every increasing union of Borel graphs of pointwise volume growth at most $\exp(O(r^\gamma))$ is hyperfinite, where $\gamma \approx 0.1523$ is the unique real root of $(1 - \gamma)^3 - 4\gamma = 0$. This implies a positive answer to the special case of Weiss's question on the hyperfiniteness of Borel actions of countable amenable groups, for countable amenable groups locally of volume growth $\exp(O(r^\gamma))$ for $\gamma$ as above. We also show that every bounded degree Borel graph of subexponential volume growth has Borel Følner tilings, improving a result of Downarowicz and Zhang for graphs generated by free Borel actions of groups of subexponential volume growth. Our main tools are the development of a Borel analogue of the two-parameter dimension growth function of a metric space as introduced by Dranishnikov and Sapir, and ball carving algorithms from theoretical computer science. We end with a pair of conjectures relating Borel amenability, Borel subexponential dimension growth, and hyperfiniteness, which would imply a positive answer to Weiss's question.

Looking at some monoids and (semi)rings (natural numbers, integers and $p$-adic integers), and more generally, residually finite algebras (in a strong sense), we prove the equivalence of two ways for a function $f$ on such an algebra to behave like the operations of the algebra. The first way is to preserve congruences or stable preorders. The second way is to demand that, for any (recognizable) set $L$, a suitably chosen lattice (or Boolean algebra) generated by $L$ be closed under inverse images by the function $f$.

The exact nondeterministic automatic complexity $A_{Ne}(x)$ of a word $x$ is the minimum number of states of a nondeterministic finite automaton that accepts $x$ and no other word of length $|x|$; the unique nondeterministic automatic complexity $A_N(x)$ additionally requires the accepting computation to be unique. Chen, Kjos-Hanssen, Koswara, Richter, and Stephan (FSTTCS 2025) asked whether the two measures can differ. We answer this affirmatively: the binary word $w=1101000000100$ satisfies $A_{Ne}(w)=6<7=A_N(w)$. The separation is witnessed by a six-state automaton whose sole accepted word of length $13$ is $w$, accepted along exactly three computation paths. The matching lower bounds were established by exhaustive search and by SAT solvers, with proofs of unsatisfiability certified in the DRAT format. An exhaustive census shows that $13$ is the least length of a separating word over any alphabet, binary or not, and that up to renaming of letters the separating words of length $13$ are precisely $365$ letter-mergings of the single seven-letter word $0123444445126$, all with $A_{Ne}=6<7=A_N$; exactly eight of them are binary. The separating word and the core of the verification were found by an artificial intelligence agent.

We show that for every uniform family of affine algebraic sets, there is a formula in the parameters of the family and in $n$, expressing the cardinality of the set in the ring $\mathbb Z/n \mathbb Z$. In particular, we construct such a formula for the elliptic curves in Weierstrass normal form. These formulas are arithmetic terms: fixed finite compositions of additions, multiplications, subtractions, divisions with remainder and integer exponentiations.

Kostana [5] asked for natural conditions on a class $\mathcal{K}$ to ensure that forcing with finite members of $\mathcal{K}$ on an underlying set $X$ is forcing equivalent to Cohen forcing. We show that if $\mathcal{K}_{\triangle}$ is the class of finite triangle-free graphs and $|X|\geq\aleph_2$, then $ \mathbb{C}_X(\mathcal{K}_{\triangle}) \not\simeq \mathbb{C}[X]. $ We then use a characterization of Cohen algebras due to Milovich to obtain a positive result. We show that if $\aleph_n\leq|X|$ and $\mathcal{K}$ has $(n+1)$-disjoint amalgamation, then $\mathbb{C}_X(\mathcal{K})$ is Cohen.

Let $M$ be a countable transitive model of a sufficiently large finite fragment of ZFC, and let $E^{\mathbb B}_{M}$ be equivalence of random generics over $M$. Smythe proved that $E^{\mathbb B}_{M}$ is not Borel-reducible to the orbit relation of a free action of any countable group belonging to $M$, and asked whether the restriction on the target group can be removed. We prove that if $A$ is a positive-measure Borel set of random reals over $M$ and $F$ is an essentially free countable Borel equivalence relation, then every Borel homomorphism from $E^{\mathbb B}_{M}\upharpoonright A$ to $F$ maps a conull subset of $A$ into a single $F$-class. Hence no positive-measure restriction of $E^{\mathbb B}_{M}$ is essentially free, or even weakly Borel-reducible to an essentially free relation. The proof combines Thomas's consequence of Popa cocycle superrigidity with a perfect family of $2$-marked groups and a Fubini argument using two successive random reals.

For a tree $T$, let $[T]$ be the set of isomorphism classes of trees that are mutually topological minors of $T$. Bruno and Szeptycki proved that every locally finite tree satisfies $|[T]|\in\{1,2^{\aleph_0}\}$ and that every tree with a ray containing infinitely many vertices of degree at least $3$ has at least $2^{\aleph_0}$ topological twins. Hence equality holds in the latter case when the tree is countable. We treat the complementary countable case, without any bound on the degrees. For every such tree $T$, we prove that $|[T]|\in\{1,\aleph_0,2^{\aleph_0}\}$ and give a well-founded recursive description based on Schmidt rank. The proof uses a finite canonical subtree extracted from the subtree generated by the branching vertices and a counting theorem for countable multisets over a well-quasi-order. The same trichotomy follows for every countable tree and hence for every tree all of whose vertices have countable degree.

We investigate identities satisfied by monoids of triangular matrices over fields and over additively idempotent semirings with 0 and 1, and exhibit several new instances in which these identities admit no finite axiomatization.

Among the four well-known anti-foundation axioms, $\mathsf{BAFA}$, $\mathsf{FAFA}$, $\mathsf{SAFA}$, and $\mathsf{AFA}$, the latter three are all special cases of $\mathsf{AFA}^\sim$ ($\sim$ is one of the regular bisimulations). In this paper, we generalize it to $\mathsf{AFA}^\sim$ ($\sim$ is regular and has the so-called set property), and show that this generalization is substantial by constructing new anti-foundation axioms.

Let $\mathsf{BCT}_{\mathsf{WO}}$ assert that every well-orderable family of dense open subsets of a perfect Polish space has dense intersection, and let $\mathsf{RS}_{\mathsf{WO}}$ assert that for every nonempty countable partial order, there is a filter meeting every member of any given well-orderable family of dense subsets. Over $\mathsf{ZF}$ they are shown to be equivalent. We show that in Truss's model, they characterize those $A\subseteq2^\omega$ for which every $A$-indexed family of dense open sets has dense intersection. Assuming choice for well-orderable families of nonempty sets, we obtain an analogous characterization for total relations $R\subseteq X\times Y$ with meager vertical sections, whenever $Y$ is a surjective image of $2^\omega$. The Feferman-type model $\mathfrak N_{\aleph_1}$ studied by Truss \cite{Truss1974} satisfies these hypotheses and $\mathsf{DC}$. We study the ideal of well-orderable subsets of $2^\omega$ and its relations to other ideals in this model. We show, among other things: the well-orderable subsets of $2^\omega$ are exactly the sets which are Rothberger in every finite power, have strong measure zero, are universally null, are Marczewski null, or contain no perfect subset. The ideal of well-orderable subsets of $2^\omega$ is closed under well-ordered unions and is incomparable with the meager ideal. The equivalence with the Rothberger property does not extend to the Hurewicz property. Further more, in this model every set is Marczewski measurable, arbitrary maps into separable metric spaces have continuous perfect restrictions, and every set of positive outer measure contains a perfect subset.

Sequent-style tableaux are a refutation calculus in which each node of the refutation tree carries a finite block of formulae and the structural rules are absorbed into the data structure and the closure criterion. In their original, classical form they rest on an involutive De Morgan negation and on closure upon a complementary pair. We show that both may be dispensed with. Replacing unsigned formulae by signed ones, we obtain a block calculus $\mathbf{B}_{ti}$ for intuitionistic propositional logic in which the whole of intuitionism is carried by one rule, the rule decomposing $\mathsf{F}(A \to B)$, which deletes the $\mathsf{F}$-part of the context on passing to the child block. The rules so obtained are, up to the presentation, those of Fitting's signed tableaux; what is new is the block format, in which the structural rules are absorbed rather than admissible, and what follows from it. We identify the semantic reason for this rule and for the one other anomalous one: of the signed compounds of the language, exactly those governed by the implication fail to be locally decomposable, and the two failures are repaired, respectively, by retaining the principal formula and by purging the context. We prove that $\mathbf{B}_{ti}$ is the multiple-succedent sequent calculus $\mathbf{G}_{ti}$ read upside down, that $\mathbf{G}_{ti}$ admits the structural rules, and that $\mathbf{B}_{ti}$ is sound and complete for Kripke semantics, with the finite model property and a block-theoretic proof of the disjunction property.

We show that the isomorphism relation for countable Steiner triple systems is Borel complete, that is, the isomorphism relation for arbitrary countable structures is Borel reducible to that for countable Steiner triple systems. To prove it, we construct a faithful Borel reduction from countable graphs to countable Steiner triple systems, that is, a Borel assignment $\theta$ that associates every countable graph $G$ with a countable Steiner triple system $\theta(G)$ so that $G\cong G'$ if and only if $\theta(G)\cong\theta(G')$. Moreover, $\theta$ preserves automorphisms which means that $\mathrm{Aut}(G)\cong\mathrm{Aut}(\theta(G))$.

We investigate compactness properties with respect to list colouring, a certain form of graph colouring, with infinitely many colours. We introduce a new hierarchy of compactness cardinals, that also includes some well-established large cardinal notions, and use it to show that various types of large cardinals, including weakly compact, strongly compact, and $\delta$-strongly compact cardinals, can be characterized in terms of compactness for list colouring. We also obtain lower bounds on the size of our newly introduced compactness cardinals.

Remote attestation is a procedure by which a system (such as a Trusted Execution Environment) proves its own configuration to a remote peer. Here, the configuration includes the measurements (hash digests) of software components. When multiple nodes perform mutual attestation, each node must maintain the reference values for its peers' measurements. We refer to this as the reference-value bootstrapping problem for mutual attestation. In this paper, we formulate the problem as a fixed-point equation and solve it directly using Kleene's second recursion theorem. In our approach, nodes can reconstruct one another's source code, thereby allowing each node to derive the reference values at runtime. When a source code itself is deployed, as with a Python script, a node derives the peer's reference value directly from its reconstructed source. When a build artifact is deployed, as with AWS Nitro Enclaves, a node instead reproducibly builds the peer's artifact from its reconstructed source and derives the reference value from it. As a proof of concept, we develop transpilers in Python and Nix to generate mutually referencing programs. Using these transpilers, we demonstrate the mutual derivation of reference values for the two deployment models mentioned above. Our solution is architecture-independent, requires no trusted third party, and works with existing attestation stacks without modification.

The notion of a base of computability $\mathscr{C}$ in a category $\mathscr{C}$ was introduced as a tool to generate computability models, in the sense of Longley and Normann, from categories. In this paper we introduce the category $\mathsf{CatBaseComp}$ of categories with a base of computability, and we show that $\mathsf{CatBaseComp}$ has all pie limits. We prove that a Grothendieck fibration lifts a base of computability in the base category to a base of computability in the total category of the fibration, and conversely, a pullback-preserving Grothendieck fibration maps a base of computability in the total category to a base of computability in the base category of the fibration. Connecting $\mathsf{CatBaseComp}$ with the semantics of dependent type theory, we show that $\mathsf{CatBaseComp}$ is a type-category, or a (fam, $\Sigma$)-category with a terminal object. Moreover, we prove that CatBaseComp is a (2-fam, $\Sigma$)-category, a 2-categorical generalisation of a (fam, $\Sigma$)-category. Finally, we describe the canonical (2-dep, $\Sigma$)-structure of CatBaseComp, i.e., the canonical dependent arrows of CatBaseComp that are compatible with its (2-fam, $\Sigma$)-structure.

We present a systematic development of the arithmetic of the class of linear orders under the ordered sum $(LO, +)$ and prove a number of new results. Our approach is based on a Euclidean algorithm for pairs of linear orders that almost additively commute. Among our results: (i.) We generalize and give unified proofs of the main classical theorems for $(LO, +)$, including Lindenbaum's division theorem for $(LO, +)$ and a representation theorem for additively commuting pairs of linear orders due to Aronszajn. (ii.) We solve the following problem, posed by Tarski in 1956: is it true that for every pair of linear orders $A, B$ and quadruple of natural numbers $n, m, k, l \geq 1$, if $nA + mB \cong kB + lA$ then $A + B \cong B + A$? Tarski and Chang showed the answer is yes for certain choices of the coefficients $n, m, k, l$. We show the answer is yes in general. (iii.) We prove the following characterization of the additively commuting pairs in $LO$: $A + B \cong B + A$ if and only if $\omega A$ embeds initially in $\omega B$ and $\omega^* A$ embeds finally in $\omega^* B$, or vice versa. We show this can be viewed as a correctly revised version of a refuted conjecture of Tarski. (iv.) We characterize the commutative semigroups $(S, \oplus)$ that can be represented in $(LO, +)$ and show in particular they are all subsemigroups of naturally totally ordered semigroups in the sense of Clifford.

We prove that the orbit equivalence class of every free ergodic probability-measure-preserving (pmp) action of a free group contains a totally weak mixing action. Equivalently, every ergodic treeable pmp equivalence relation of cost $n\in\mathbf{N}\cup\{\infty\}$ is generated by a free totally weak mixing action of $\mathbf{F}_n$. This answers a question of Miller and Tserunyan. The proof goes by considering a Polish space of edge slidings along a fixed mixing transformation and proving that for every $w\not=e\in\mathbf{F}_n$ the set of edge slidings that produce an action with $w$ weakly mixing forms a comeager set.

Let $R$ be a ring. We organize the abstract elementary classes whose underlying class is the class of all $R$-modules and whose strong submodel relation lies between the submodule and direct summand relations into a lattice $\mathscr{L}_{R}$, ordered by reverse inclusion. We establish the basic lattice-theoretic properties of $\mathscr{L}_{R}$ and investigate its two natural sublattices, below and above purity. Below purity, we isolate relations defined by first-order pp-formulas for which amalgamation, tameness, and stability hold. Above purity, we introduce relations defined by infinitary pp-formulas and prove a broad stability result. Specializing to abelian groups, we show that the lattice $\mathscr{L}_{\mathbb{Z}}$ has the following properties: it has a strong submodel relation that is not positive syntactic, it contains an uncountable antichain and a strictly increasing proper-class-sized chain, and it has a broad region above purity where amalgamation fails.

Decisions and their consequences can be described and analyzed by means of decision trees. The decisions themselves depend on questions that, whenever possible, should be answered with yes or no. The original BSS machines over the real numbers are graphs with computation nodes and branching nodes for decisions. The evaluation of BSS machines and algebraic decision trees in computer-aided geometry which have been introduced for various types of numbers generally involves the evaluation of systems of literals of first-order logic. Flowchart-like representations and decision trees are also helpful for analyzing decisions made by BSS RAMs over first-order structures. All algorithms defined by machine-oriented programs of BSS RAMs can be illustrated using flowcharts, walks, and paths in program trees. The basic structures of these tools are graphs and their visual representations can help to characterize the behavior of individual BSS RAMs and other first-order machines. We offer a theoretical framework for linking various models. Here, we introduce program paths and transition systems for transforming partial configurations which are defined syntactically and can be extended and refined later. Finally, we define standard orders for program paths and present algorithms for enumerating finite program paths.

Recently, we showed that continuous definable maps defined on compact definable sets can be uniformly approximated by continuous definable maps of class $\mathcal{C}^p$ without changing their image. The aim of this paper is to extend the previous result, this time taking into account the (strong) Whitney topology, to continuous locally definable maps defined on locally compact locally definable sets. The argument is an interplay between o-minimal and PL geometry and makes essential use of Pawłucki's desingularization techniques as well as our aforementioned result for the compact case.

We introduce the universality property of a definable $\sigma$-ideal on a Polish space, which, on one hand, can serve as a benchmark for the properness of the associated idealized forcing of positive Borel sets ordered by inclusion, and, on the other hand, unifies many of the results that can be found in Zapletal's book. We show that under mild absoluteness assumptions, it implies properness, various dichotomy theorems, and closure under well-ordered unions in the Solovay model and under $\mathsf{AD}^+$, among other things. All major classes of proper idealized forcings studied in the book have this property. Further, we use this viewpoint to answer a question of Khomskii by showing that the naive idealized forcing for adding an eventually different real or a refining real is not proper below some condition. We also answer a question related to the definability of $\sigma$-ideals generated by Borel sets due to Kanovei, Sabok, and Zapletal.

Erdős Problem 1154 asks whether every number in $[0,1]$ occurs as the Hausdorff dimension of a subring or subfield of $\mathbb{R}$. Motivated by this problem, Liang Yu asked whether the reals of an inner model can have Hausdorff dimension strictly between zero and one when their dimension is computed in an outer model. We prove a stronger result: if $\mathcal I \subseteq 2^\omega$ is any Turing ideal, then $\dim_{\mathrm H} \mathcal I \in \{0,1\}$. Equivalently, the real-closed field whose reals have Turing degrees in $\mathcal I$ has Hausdorff dimension zero or one. The proof combines digit interleaving with the Furstenberg-set theorem of Orponen and Shmerkin.

On this article we provide a relation between two inherently different semantic structures for intuitionistic modal logic. We start by recalling the Heyting Algebras, then defining the language and the axioms for the iS4h intuitionistic calculus. We then proceed to analyse two structures discussed on [4] and their relation. Finally, we discuss about a structure defined on [3, Chapter 6], establishing properties in order for it to be sound with iS4h, and finally conclude that it is semantically equivalent to the other two structures defined by [4].