Papers

In the last years, a number of proofs of the fact that $O_2$ is a multiple context-free grammar (MCFG) were given. Such results can be exploited in the fields of both computational linguistics and of computational algebra. Here, we focus on a recent such proof spelled in terms of factorizations of string tuples, and give a new result with a stronger characterization of such factorizations than in existing theorems.

Let $K$ be an algebraically closed field of characteristic 0 and transcendence degree at least 2. Let $C\subset K^2$ be an irreducible curve defined over $K$ but not defined over the algebraic closure of $\mathbb Q$. There is $(x ,y)$ a $K$-point of $C$ such that $x$ and $y$ are algebraically independent. Moreover, if $C_0$ and $C_1$ are two such curves and there is a finite-to-finite algebraic correspondence between them defined over $K$, then there are corresponding $K$-points $(x_0,y_0)\in C_0$ and $(x_1,y_1)\in C_1$ such that $x_0$ and $y_0$ are algebraically independent and $x_1$ and $y_1$ are algebraically independent. We use the latter result to construct non-Archimedean real closed fields of transcendence degree $\kappa$ with no non-trivial automorphisms for all $2\le\kappa\le \aleph_1$.

We give a finite symbolic characterization of the strong topological Rokhlin property in terms of globally realizable finite pattern systems. We use this characterization to prove finite-index ascent: if $H\leq G$ has finite index, $G$ is finitely generated, and $H$ has STRP, then $G$ has STRP. Consequently every finitely generated virtually free group has STRP, whereas among countable locally virtually free groups STRP holds exactly for the finitely generated ones. In the compact coding space $\operatorname{NSub}(F_\omega)$ of countable groups, the STRP locus belongs to ${\boldsymbol \Pi}^0_4$, is ${\boldsymbol \Sigma}^0_3$-hard; the locus of finitely generated virtually free groups is ${\boldsymbol \Sigma}^0_3$-complete. For quotients $F_\omega/N$ with $N$ recursively enumerable, every projectively isolated subshift has decidable finite tuple-language and contains an $N$-recursive configuration. This yields effective SFT obstructions to STRP, including subgroup and direct-product obstructions, and implies that $\mathrm{SL}_n(\mathbb Q)$ does not have \STRP for any $n\geq2$.

A theorem of Dougherty–Jackson–Kechris states that any equivalence relation generated by a single Borel function is hypersmooth. A well-known open problem is whether this can be generalized to equivalence relations generated by countable families of pairwise commuting Borel functions. We give an affirmative answer in the case where the functions are bounded-to-one. This generalizes the theorem of Gao–Jackson on Borel actions of countable abelian groups.

Grounded arithmetic is a family of formal systems for reasoning about computation in which a statement may be asserted only when a terminating computation backs it; the logics are paracomplete - for a sentence whose backing computation never settles, neither the sentence nor its negation is derivable, so paradoxes like the Liar are harmless rather than explosive. The reflective member of the family, RGA, can quantify over its own computations, but cannot certify that its own unbounded searches have definite yes-or-no answers. This paper studies what happens when that openness is closed by exactly one rule - ATI, the $\omega$-grounded universal: if every numeric instance of a universal sentence is certified decided, the universal is certified decided. The resulting system, OGA, shares RGA's syntax and rules symbol-for-symbol otherwise, and every consequence is developed as a machine-checked theorem. Decidedness certificates become abundant - every totality question about a computable function is certified to have an answer, whether or not anyone can produce it - and this is exactly the provable separation between the two systems. OGA is complete for its own semantics; certified-but-unresolved sentences receive values built from the system's own open questions. Provability remains recursively enumerable, with a primitive-recursive certificate checker, while $\omega$-truth deliberately is not. Within that asymmetry, incompleteness takes a new form. The Gödel sentence is classified, unconditionally, as a genuine fiction: neither provable nor refutable, yet valued, and carrying a computable pedigree recording exactly what adopting it as an axiom commits one to. The adoption is itself a theorem suite: extending OGA by any finite stock of true fictions is consistent, and independently certified adoptions can never collide.

We answer Kourovka Notebook Problem~18.16 affirmatively in the pure language of ordered abelian groups, with parameters allowed. The piecewise-affine description of definable functions reduces the question to an algebraic rigidity theorem: an additive endomorphism of a torsion-free abelian group that is covered by finitely many rational-affine laws has one global rational slope. The parameter-free pure-language case is included, whereas the unrestricted expansion-language variant admits a simple counterexample.

For finite-domain constraint satisfaction problems (CSPs), the polymorphism clone provides an algebraic framework for studying the associated constraint language. A central question in clone theory is whether a clone is finitely related, that is, whether it is determined by the operations preserving a finite set of relations. Here, we study this question through the action algebra of a clone on its own $n$-ary part. We prove that a clone $\mathcal{C}$ on a finite domain $C$ is finitely related if and only if its action algebra $\widetilde{\mathcal{C}} = \mathcal{C} \curvearrowright \mathcal{C}^{(n)}$ is finitely related, provided that $n \geq |C|$. We also apply natural clone isomorphisms to obtain a finite-relatedness criterion for free algebras: a finite algebra is finitely related if and only if its free algebra of sufficiently large finite rank is finitely related.

For a ring $R$, let $\mathcal{GP}(R)$, $\mathcal{GF}(R)$, and $\mathcal{PGF}(R)$ denote the classes of Gorenstein projective, Gorenstein flat, and projectively coresolved Gorenstein flat left $R$-modules, respectively. We isolate the local ultrafilter hypothesis $\textsf{LUH}$: the existence of a strongly compact cardinal implies $\textsf{LUH}$, while $\textsf{LUH}$ implies the existence of a measurable cardinal. Assuming $\textsf{LUH}$, we construct a left and right coherent ring $R$ and a strongly Gorenstein projective left $R$-module $G$ which is not Gorenstein flat; hence $\mathcal{PGF}(R)\subsetneq\mathcal{GP}(R)$.

Starting from a model of $\mathrm{ZFC}$, we force the simultaneous failure of the Very Weak Club Guessing and the $\mho$ principles at $S_\kappa^{\kappa^+}$, for any regular cardinal $\kappa$. Our results are obtained by means of a forcing iteration technique, due to Krueger, that incorporates models as side conditions. At $\omega_1$, the failure of these principles is a well-known consequence of $\mathrm{PFA}$.

We prove in ZFC that every torsion-free Abelian group of cardinality $\mathfrak c$ admits a Hausdorff countably compact group topology without nontrivial convergent sequences. In particular, this applies to the free Abelian group $\mathbb{Z}^{(\mathfrak c)}$, the Baer-Specker group $\mathbb{Z}^\omega$ and $\mathbb{Q}^{(\mathfrak c)}$. For the topology constructed on $\mathbb{Z}^{(\mathfrak c)}$, the coordinatewise nonnegative cone is countably compact in the subspace topology. Consequently, there exists in ZFC a commutative Tychonoff countably compact topological semigroup which has two-sided cancellation but is not a group, giving a negative answer to Wallace's question. Combined with earlier results, the main theorem also yields in ZFC a Tychonoff countably compact topological semigroup containing a copy of the bicyclic semigroup and a functionally Hausdorff countably compact paratopological group that is not a topological group.

Let $L$ be the frame of opens of a $T_0$-space $X$. We prove that if $X$ is sober and $T_1$, then the double negation nucleus on $L$ is Scott continuous iff $X$ is discrete. It follows that if, in addition, $X$ is compact then double negation is Scott continuous iff $X$ is finite. We show that both the sober and $T_1$ assumptions are essential, and generalize the above results to all boolean nuclei on $L$. A pointfree characterization of when $X$ is sober and $T_1$ is also given by proving that it is equivalent to Scott continuous nuclei on $L$ being closed.

This paper captures and extends some of the core results from the tech memo "A New Semantics for Belief Revision in Simplicial Complexes". As such, we set out to explore the implementation of action models in the setting of simplicial semantics for modal logic. Such an idea is not entirely new to the literature, showing up in both "A simplicial complex model for dynamic epistemic logic to study distributed task computability" and "Knowledge and Simplicial Complexes". However, we will explore action models in a more general setting. In particular, we will allow for action models for simplicial models for belief, as in "A Semantics for Belief in Simplicial Complexes". This will let us incorporate the notion of belief revision, as developed in "Simplicial Semantics for Belief Revision", into these action models. Moreover, we explicitly connect action models in the simplicial setting to distributed protocols as defined in the textbook "Distributed Computing Through Combinatorial Topology". We conclude with some speculation on how we might interpret distributed protocols with revision.

We extend a construction of Marker and Steinhorn for producing countable non-archimedean real closed fields which have no non-trivial automorphisms. The original construction produces such a field of transcendence degree two over the field of real algebraic numbers. We show how to use the same method to produce examples of all finite transcendence degrees and of countably infinite transcendence degree over the real algebraic numbers, answering a question of Marker and Steinhorn.

Let $\theta$ be a regular cardinal, $R$ a ring, and $M$ a left $R$-module. We prove that for every ordinal $\alpha$ there is a set $I_\alpha \subseteq M^{<\theta}$ of size at most $\beth_\alpha(|R| + \theta)$ such that every parameter-free $L_{\infty,\theta}$ formula of rank at most $\alpha$ is equivalent in $M$ to an infinitary Boolean combination of cosets $\overline{a} + \phi(M)$, where $\overline{a} \in I_\alpha$ and $\phi$ is an infinitary positive existential formula of rank at most $\alpha$. The main ingredient in the proof is a combinatorial lemma which says that given $\kappa$ subgroups of an abelian group, there is a set of at most $2^\kappa$ points which tests whether any family in which each member is either empty or a coset of the corresponding subgroup covers the whole group. The proof proceeds by applying this lemma fiberwise to show that the relevant complete Boolean algebras of positive-existentially definable cosets are closed under projections.

We classify a broad family of weak first-order set theories, under ordinary parameter-free interpretability, by the first-order arithmetical theories with which they are mutually interpretable. This also determines their consistency strength. Set theories that correspond to the same arithmetical theory are often related by deductive extension. It is therefore enough to interpret a stronger set theory in the arithmetical theory and to recover the arithmetical theory in a weaker set theory; all intermediate cases then follow. The set theories under consideration fall roughly into three classes: theories with neither Power Set nor Infinity, theories with Power Set but without Infinity, and theories with Infinity but without Power Set. We conclude with a brief account of the higher levels that remain to be investigated.

We generalize the Stone space of ultrafilters on Boolean algebras and prove a generalization of Stone duality which is applicable to locally compact Polish spaces. Using this, we obtain complete invariants for simplicial complexes up to PL-homeomorphism and for non-compact $2$- and $3$-manifolds up to homeomorphism. We prove that the homeomorphism relation on non-compact $2$-manifolds without boundary, the homeomorphism relation on non-compact $3$-manifolds with or without boundary, the homeomorphism relation on open subsets of $\mathbb{R}^2$ and $\mathbb{R}^3$, and conjugacy of Cantor sets in $\mathbb{R}^3$ are classifiable by countable structures. Together with known lower bounds, this implies that these relations are Borel bireducible with isomorphism of countable graphs. We also show that PL-homeomorphism of Heine-Borel simplicial complexes and PL-homeomorphism of PL $n$-manifolds, for every $n$, are classifiable by countable structures.

By Tarski's undefinability theorem, no consistent classical formal system that includes arithmetic can define its own truth predicate. Reflective Grounded Arithmetic (RGA) is a powerful arithmetic whose universal quantifier is grounded in its own reflected proof search, and whose paracompleteness circumvents Tarski's theorem. This paper presents a machine-checked Isabelle/HOL development that defines a truth predicate for RGA's full language, quantifiers included, as an internal term of RGA itself. This term is compiled from a primitive-recursive decider for its operational semantics, and proven adequate in both directions. Around this predicate the development closes a square of metatheorems: for every formula RGA proves, RGA derives the formula's internal truth; every grounded-true formula is internally provable; internal truth implies internal provability; and the consistency of RGA follows. The two directions run on disjoint internal machines—a certified decider and a certified proof-checker, both RGA terms. Reaching these results involved substantial ordinary reasoning carried out within RGA: coded syntax and substitution, compiled primitive-recursive functions with symbolic unfolding laws, internal strong induction, and a verified proof-checker for the system written in the system's own formal language. The development thus demonstrates along the way that RGA is a workable formal system supporting nontrivial mathematical reasoning.

Shelah and Usvyatsov proposed the Generalized Gaifman Conjecture [SU25, Conjecture 1.1]. We give a negative answer.

Solovay reducibility is studied intensively as a tool to compare the approximability and the degree of randomness of left-c.e. reals. By definition, a real is left-c.e. if it has a left-c.e. approximation, that is, it is the limit of an effective nondecreasing sequence of rationals. If reals $\alpha$ and $\beta$ have left-c.e. approximations $a_0, a_1, \ldots$ and $b_0, b_1, \ldots$, respectively, such that the approximation ratios \[ \frac{\alpha-a_n}{\beta-b_n} \] are bounded from above by a constant, the real $\alpha$ is Solovay reducible to $\beta$. The latter is the case for any such $\alpha$ and $\beta$ and their left-c.e. approximations whenever $\beta$ is Martin-Löf random by the Kučera-Slaman Theorem [DOI:10.1137/S0097539799357441]. This result was substantially strengthened by Barmpalias and Lewis-Pye [DOI:10.1016/j.jcss.2017.06.002], who demonstrated that, under the given assumptions, the approximation ratios are not only bounded but actually converge to a limit, which does not depend on the considered left-c.e. approximations. There is a quest for a suitable extension of Solovay reducibility to the class of all reals. Promising candidates include S2a-reducibility on the set of computably approximable reals by Zheng and Rettinger [DOI:10.1007/978-3-540-27798-9_39] and monotone Solovay reducibility by Titov [DOI:10.1007/978-3-031-95908-0_33]. For the latter, Titov [DOI:10.1017/jsl.2025.10157] demonstrated that the theorems of Kučera and Slaman and of Barmpalias and Lewis-Pye extend to all reals. He conjectured further [DOI:10.1017/jsl.2025.10157, Conjecture 3.2] that similar extensions hold for S2a-reducibility in terms of its functional characterization by Kumabe, Miyabe, and Suzuki [DOI:10.3233/COM-230486]. In this work, we refute this conjecture by proving that the analogue of the Barmpalias-Lewis-Pye Limit Theorem does not hold for S2a-reducibility.

In this paper we study Borel graphs generated by finitely many commuting Borel functions. We give a geometric analysis of the free part of such graphs based on marker sets and marker regions. Assuming the existence of $r$-forward-independent hitting sets with bounded syndeticity, we obtain marker decompositions of the free part into rootless and rooted regions with controlled geometry. As applications, we derive finite Borel asymptotic dimension and hyperfiniteness, and obtain upper bounds for Borel edge chromatic numbers which improve previously known results. For the case in which each of the commuting Borel functions is bounded-to-one, we verify the existence of $r$-forward-independent hitting sets with syndeticity $Cr$ for some constant $C$. This gives another proof of a recent theorem of Shinko-Weilacher-Yu, and is used to show that if one of the commuting Borel functions is injective and another one is bounded-to-one and exactly even-to-one, then the graph has a Borel perfect matching.

We consider for an arbitrary fixed $\rho$ and for each positive integer $n$ a multilayer feedforward artificial neural network with $\rho$ layers, $n$ neurons in the first layer (the input layer) and only one neuron, the output neuron, in the last layer. Very roughly formulated, the main result is that if the distribution of weights of connections from a layer to the next are, for all large $n$, approximated well by a fixed continuous (but otherwise arbitrary) curve which does not depend on $n$, and if the values of the $n$ input neurons are independently and identically distributed with a continuous probability density function, then there is a number $\psi$ such that for all $\varepsilon > 0$ the probability that the value of the output neuron is in $[\psi - \varepsilon, \psi + \varepsilon]$ tends to 1 as $n$ tends to infinity.

We establish a duality between quotients and comprehensions in relational doctrines, a class of indexed posets modelling (a minimal fragment of) the calculus of relations. We show that every relational doctrine determines an “opposite" relational doctrine and that one has quotients if and only if the other has comprehensions. This duality extends to the 2-categorical level, yielding a 2-dual isomorphism between the 2-categories of relational doctrines with quotients and that with comprehensions, allowing to derive results on relational doctrines with comprehensions from their dual counterparts for quotients, and viceversa. We also study the interaction between quotients and comprehensions and their relative completions, giving sufficient conditions for the induced 2-monads to be composable, \ie sufficient conditions ensuring that applying both the completions, the second one preserves the properties added by the first one.

Let $\varphi$ be a minimal counterexample to Vaught's conjecture in the sense of Montalban; such a $\varphi$ exists if Vaught's conjecture fails, by Steel and Harnik-Makkai. We bring into contact, at the level of statements, two bodies of work on the models of such a $\varphi$: the analysis of Gonzalez-Rossegger-Turetsky, in which at every countable level $\beta$ exactly one back-and-forth class $C_\beta$ is uncountable and, at fixed points of an associated function, has a distinguished member of least Scott rank (its label); and the supply of models with prescribed $\omega_1^A$ from higher recursion theory, namely Montalban's Gandy-basis lemma and Sacks' $\Sigma_1$-hull club. All results are theorems of ZFC under standing hypotheses (H0)-(H3). We prove: (i) a per-witness trichotomy – for every limit $\lambda$ in the fixed-point club above $qr(\varphi)$, every model $A$ of $\varphi$ with $\omega_1^A=\lambda$ and Scott rank at least $\lambda$ either is the label $K_\lambda$, or lies outside $C_{\lambda+1}$ and so forces two non-isomorphic models of Scott rank $\lambda+1$, or is the label $K_{\lambda+1}$ and attains the Nadel bound; (ii) coordinate identities: the first and third branches are equivalent, level by level, to computations of $\omega_1$ of the labels; (iii) a seeding theorem: on a club, Sacks' construction supplies at every level a model of top rank with prescribed $\omega_1$, and his atomic chain consists of the labels; (iv) an unconditional stationary dichotomy: on that club, either stationarily many successor levels carry two non-isomorphic models of Scott rank $\lambda+1$, or stationarily many labels attain the Nadel bound. On the fiber of models with $\omega_1=\lambda$ we further prove uniqueness of the node-saturated model and give a complete isomorphism invariant with countable spectrum. We prove nothing bearing on Vaught's conjecture itself.

We study conditions for a countable group acting on a connected locally finite hyperbolic graph to induce a hyperfinite orbit equivalence relation on the Gromov boundary of the graph in terms of tree-decompositions of the graph. We prove that for a connected locally finite hyperbolic graph $X$ equipped with an action of a countable group $G$, if $(T, \beta)$ is a $G$-invariant tree-decomposition of $X$ such that each bag induces a connected subgraph $X_t$ of $X$ for each $t \in V(T)$, each adhesion set is finite and such that there are only finitely many $G$-orbits of edges of $T$, then the orbit equivalence relation of $G$ acting on the Gromov boundary $\partial X$ is hyperfinite provided the orbit equivalence relation of $G$ acting on $\partial T$ is hyperfinite and the orbit equivalence relations of the bag stabilizers acting on $\partial X_t$ are all hyperfinite. We show that the converse also holds if $(T, \beta)$ satisfies the additional property that each adhesion set distinguishes at least two ends of $X$.

For a real $f\in \mathbb{N}^\mathbb{N}$, it is in general not the case that every set which is both $\Sigma^1_1(f)$ and $\Pi^1_1(f)$ is the $f$-section of a $\Delta^1_1$ set. However, there are reals $f$ for which this, in fact, does happen; we say that such a real strongly relativizes $\Delta^1_1$. In this paper, we will prove that the reals which strongly relativize $\Delta^1_1$ are exactly the hyperlow reals, i.e., the $f\in \mathbb{N}^\mathbb{N}$ with $\omega_1^f=\omega_1^{\text{ck}}$. We will also study reals that strongly relativize the classes $\Delta^0_\alpha$ for $1\leq \alpha<\omega_1^{\text{ck}}$. We characterize the reals that strongly relativize $\Delta^0_1$ subsets of $\mathbb{N}$ as the reals which are computably dominated. For $1\leq \alpha<\omega_1^{\text{ck}}$, we show that there are continuum many reals which strongly relativize $\Delta^0_\alpha$ subsets of $\mathbb{N}$. We will also find non-trivial examples of reals which strongly relativize $\Delta^0_{\alpha}$ ($1\leq \alpha<\omega_1^{\text{ck}}$) subsets of Baire space.

This paper presents a first-order multimodal logic programming system called MMLP. The system accepts arbitrary formulas as both programs and queries, without restricting either side to Horn clauses or a separate goal grammar. Its declarative semantics is given independently by a Hilbert system for selected D, T, I, B, 4, and 5 modal principles. Execution uses a nested proof calculus with finite grammar certificates for modal propagation. Certificate reachability is equivalent to the associated Horn closure, certificate existence is decidable, and the calculus is cut-free complete. For quantified answer computation, we give a unification algorithm based on permission sets that controls eigenparameter scope. The algorithm always terminates and fails exactly when no admissible solution exists. A successful run returns a unifier that is itself admissible and through which all admissible solutions factor. Computed answers are declaratively correct, and each declaratively correct answer is an ordinary output instance of a computed answer. In proof search, MMLP admits syntactic focalization and a fair and complete enumeration of focused answers. It represents exactly the same answer substitutions as Nguyen's pure logical KDI4s5-MPROLOG on their common fragment, while admitting a strictly larger program and query language.

We study Hausdorff limits of definable families over arbitrary models of o-minimal expansions of real closed fields. Over the real field, van den Dries proved that Hausdorff limits of definable families are definable, giving a geometric interpretation of the Marker–Steinhorn theorem. We prove a non-Archimedean analogue for definable families which are Lipschitz cells with a fixed cell presentation and a uniform Lipschitz bound. The proof replaces compactness of closed and bounded subsets of $\mathbb R^n$ by dense completions and long Cauchy sequences, and treats the Hausdorff distance as a metric valued in an ordered completion. We show that Hausdorff limits of such families are standard parts of external fibers over tame extensions, and use stable embeddedness of tame pairs to prove that every such limit is definable in the dense completion of the base model. We also prove a uniform version: the collection of these Hausdorff limits forms a definable family in the dense completion.

The Hardin-Taylor theorem, a consequence of the axiom of choice, gives a strategy to predict future values of an arbitrary function of time $f:\mathbb{R}\to S$ given its past values. The times in $\mathbb{R}$ at which the strategy fails are shown to form a countable nowhere dense set for any function $f$. The theorem is often presented as a striking result about predicting the future. In this note we discuss the operational content of the theorem and clarify this frequent interpretation. The Hardin–Taylor prediction strategy is online: at time $t$ it depends only on the observed past $f \upharpoonright (-\infty,t)$. Its performance guarantee, however, is offline: the exceptional set consisting of times at which the predictor fails is defined only after the entire function has been realized. We spell out the precise definition of the predictor, discuss a simple two-function example as a sanity check, and emphasize the retrospective nature of verifying the predictor's success. We also examine the proper probabilistic setting in which the success likelihood of the predictor as a forecasting procedure should be evaluated. Our conclusion is that the theorem is best understood as a result about the smallness of the set of times at which the predictor must be course-corrected, rather than as a prospectively verifiable procedure for forecasting the future.

This paper will give a definition of belief revision within simplicial semantics. Starting from the work presented in "A Semantics for Belief in Simplicial Complexes" as a baseline, this paper modifies the semantics for belief given there to allow atomic formulae to be assigned to nodes, not facets. Conceptually and philosophically, this version of the semantics is better suited if one wishes to interpret the nodes of a simplicial model of epistemic logic as a "perspective" assigned to a particular agent. If nodes are perspectives, it then follows that worlds, or the facets of a simplicial model, are composed themselves of perspectives. This allows us to say that two worlds are more similar, or "nearer", if they share more perspectives. With this conceptual notion of nearness in hand, two different formal presentations of revision are given. We conclude by exploring some conceptual pitfalls surrounding these definitions under iterated revision, and motivate a few potential solutions that involve giving the agents a "memory" of what has been announced so far.

This article shows that the exact completion as a regular category of the homological category of Polish groups and continuous group homomorphisms is the category of groups with a Polish cover and Borel-definable group homomorphisms. We also obtain several equivalent characterizations for the morphisms in the exact completion. An analogous description is deduced for several important subcategories of the category of Polish groups.