pith. machine review for the scientific record. sign in

math.LO

Logic

Logic, set theory, point-set topology, formal mathematics

0
math.LO 2026-05-13 Recognition

Sequent calculi for CS, CSM, ER prove Lyndon interpolation

Proof Theory for Bimodal Provability Logics

First non-labelled systems for these bimodal provability logics also deliver cut-elimination and uniform interpolation.

Figure from the paper full image
abstract click to expand
We provide the first (non-labelled) sequent calculi for bimodal provability logics with "usual" provability predicates. In particular, we introduce calculi for the logics CS, CSM and ER. Additionally, we present non-wellfounded versions of our calculi, and use them to establish a cut-elimination procedure. Finally, we prove the first interpolation results for these logics showing that they all enjoy the uniform Lyndon interpolation property.
0
0
math.LO 2026-05-13 2 theorems

Model theories reduce to infinite-dimensional spaces over simpler bases

Trace definability III: Infinite dimensional space over a model of T

Trace equivalence shows that complex T* match the theory of κ-dimensional vector space over a model of simpler T.

abstract click to expand
We show that for a number of theories $T^*$ of model-theoretic interest there is a simpler theory $T$ and $\kappa \ge \aleph_0$ such that $T^*$ is trace equivalent to the theory of $\kappa$-dimensional space over a model of $T$.
0
0
math.LO 2026-05-13 Recognition

Field appears in Shelah completion of group-free weakly o-minimal structure

Trace definability II: model-theoretic linearity

The example shows algebraic structure can emerge after completing an NIP structure that originally interprets no infinite groups.

abstract click to expand
We give examples of $\mathrm{NIP}$ structures in which new algebraic structure appears in the Shelah completion. In particular we construct a weakly o-minimal structure $\mathscr{M}$ such that $\mathscr{M}$ does not interpret an infinite group but the Shelah completion of $\mathscr{M}$ interprets an infinite field. We introduce a weak notion of interpretability called local trace definability between first order structures and an associated weak notion of equivalence. We give a dichotomy between ``linearity" and ``field structure" for dp-minimal expansions of archimedean ordered abelian groups. We also prove several other results about trace definability and local trace definability between various classes of structures.
0
0
math.LO 2026-05-12 Recognition

ZFC proves adp equals dp

Almost Disjointness Principles and Q-Space Cardinals

The almost disjointness principle matches the dominating number in ZFC, while its tree version at can be forced strictly larger than ap.

Figure from the paper full image
abstract click to expand
Banakh and Bazylevych introduced separation-axiom variants $\mathfrak q_i$, for $i=1,2,2\frac{1}{2}$, of the cardinal $\mathfrak q$, together with a cardinal $\mathfrak{adp}$ lying between $\mathfrak{dp}$ and $\mathfrak{ap}$. They asked whether $\mathfrak{adp}$ coincides with either of these two cardinals. We prove in ZFC that $\mathfrak{adp}=\mathfrak{dp}$. We define a dual variant $\mathfrak{adp}_2$ and show that $\mathfrak{adp}_2=\mathfrak{ap}$. We further study the relation between $\mathfrak{ap}$ and the weakened $Q$-space cardinals. We introduce a tree analogue $\mathfrak{at}$ of $\mathfrak{ap}$ and prove $\mathfrak q_1\leq\mathfrak{at}\leq\mathfrak q_{2\frac{1}{2}}$, hence $\mathfrak{ap}\leq\mathfrak q_{2\frac{1}{2}}$. Assuming the Generalized Continuum Hypothesis, we construct ccc forcing extensions with $\mathfrak{ap}=\omega_1<\mathfrak{at}=\mathfrak q_{2\frac{1}{2}}=\mathfrak c$, so $\mathfrak{ap}<\mathfrak{at}$ is consistent with ZFC.
0
0
math.LO 2026-05-12 3 theorems

Non-definable sets in R^2 become approximately definable in the reals

Some model-theoretic consequences of high-arity uniform convergence, part I

High-arity uniform convergence allows this approximation even without bounded VC-dimension or exact definability.

abstract click to expand
We show that certain families of sets in $\mathbb{R}^2$ (or $\mathbb{R}^n$) which are neither definable nor have bounded VC-dimension are nonetheless uniformly approximately definable in the real field, an o-minimal structure.
0
0
math.LO 2026-05-11 2 theorems

Algebraic closure properties define pseudo-elementary classes

Algebraic characterisation of pseudo-elementary and second-order classes

Characterisations cover PC and PC delta classes as well as second-order definable classes

abstract click to expand
In this paper we provide purely model-theoretic (algebraic) characterisations for classes definable in second-order logic and for pseudo-elementary classes (including PC and PC_{\Delta} classes). Classical results of this flavour include Keisler-Shelah type theorems (characterising first-order definability by closure under ultraproducts and ultraroots) and Birkhoff's HSP theorem; a key starting point for this paper is S\'agi's work, which provides an algebraic description of classes definable by existential second-order sentences. Here we resolve several open problems from the literature. Our main results are the following. We solve the long-standing problem of giving a purely algebraic characterisation of pseudo-elementary classes: we characterise PC_{\Delta} classes by intrinsic closure properties. We also give a characterisation for the basic pseudo-elementary classes (PC). We provide a structural classification of second-order equivalent structures, and we obtain purely algebraic characterisations of the classes definable by second-order formulas as well as those definable by finitely many second-order sentences.
0
0
math.LO 2026-05-11 Recognition

Skewed ultralimits map Ramsey ultrafilter types to omega ultrapowers

On skew ultralimits and their applications in ultrafilter theory

The construction yields an order-isomorphism between the C-class of types and the ultrapower of ordered naturals.

abstract click to expand
We define a special version of the ultralimit, called the skewed ultralimit. Using this tool, we show that the set of ultrafilter types in the $C$-equivalence class of a Ramsey ultrafilter $\mathfrak u\in \beta\omega$ with the Rudin-Keisler order is isomorphic to the ultrapower of $(\omega, \leq)$.
0
0
math.LO 2026-05-11 Recognition

Box topologies define κ-meagre sets for singular cardinals

Topology and category for singular product spaces

Function spaces equipped with the <κ-box topology let cardinal invariants of the meagre ideal be studied when κ is singular.

Figure from the paper full image
abstract click to expand
For $\kappa$ a regular uncountable cardinal, the higher Baire and Cantor spaces ${}^\kappa\kappa$ and ${}^\kappa2$ (endowed with the ${<}\kappa$-box topology) have been relatively well-studied, but less is known about the case where $\kappa$ is singular. We will consider several spaces of functions and box topologies that could serve as higher Baire and Cantor spaces for singular cardinals. The ultimate focus of the article lies in studying cardinal characteristics of the ideal of $\kappa$-meagre subsets of these spaces.
0
0
math.LO 2026-05-11 Recognition

Combinatorial property identifies all projections of strongly compact Prikry forcing

On the Intermediate Models of Strongly Compact Prikry Forcing

For supercompact κ, a basic condition determines exactly which forcings of size ≤λ arise as projections from the λ-version.

abstract click to expand
We analyze the intermediate models of the strongly compact Prikry forcing. We exhibit a simple combinatorial property which, for a given supercompact cardinal $\kappa$, characterize the projections of all projections of the strongly compact Prikry forcing using $\kappa$-complete fine measures. Considering level-by-level results, if $\kappa$ is $2^\lambda$-strongly compact, we characterize the forcings of size $\leq\lambda$ which are projections of that $\lambda$-strongly compact Prikry forcing. Our characterization generalizes several known results, including those of Benhamou-Hayut-Gitik and folklore results regarding the class of $\kappa$-distributive forcing notions which are embedded into the supercompact Prikry forcing. Fixing a $\kappa$-complete fine measure $\mathcal{U}$ on $P_\kappa(\lambda)$, we also provide Rudin-Keisler like critiria for the existence projections from the strongly compact Prikry forcing with $\mathcal{U}$. Finally, we prove that among all projections of the $\lambda$-strongly compact Prikry forcing, the class of forcings of cardinality $\lambda$ are exactly those for which there is a projection map which depends only on the stem of the Prikry condition. We also give partial results regarding projections of arbitrary cardinality.
0
0
math.LO 2026-05-11 2 theorems

Ultrafilter quotients characterize self-divisible ultrafilters

Reply to Some Questions of Quotients when ultrafilters divide ultrafilters

When v strongly divides u the defined u/v yields stability for idempotents and characterizes multiplicative delta sets.

abstract click to expand
For ultrafilters u,v on N, the operation u/v is introduced and formalised which acts as quotient-like structures when v strongly divides u.Central to our study is the characterization of self-divisible ultrafilters in connection with the divisibility of u by u/v.Some results on the algebraic stability of multiplicative udempotents are presented.The paper also connects the combinatorial notions such as multiplicative delta sets,provoding characterization via self-divisible ultrafilters.
0
0
math.LO 2026-05-11 Recognition

Base lattice unifies logics to track information evolution

On Many-logic modal structures and information-based logics

Many-logic modal structures anchor LET+K and its sublattices so modal accessibility can connect worlds with different truth values and model

abstract click to expand
This paper proposes an approach to information-based logics using many-logic modal structures (MLMS). These structures can express accessibility relations between worlds with different underlying logics by anchoring them to a base lattice, which contains the semantics of each logic as a down-complete sublattice. MLMS are suitable for representing connections between information states (i.e., configurations of databases) and the evolution of information states over time. We will illustrate the application of MLMS by means of the six-valued logic of evidence and truth LET+K , related to the lattice L6, and some four-, three-, and two-valued logics related to down-complete sublattices of L6. These logics are capable of representing paracomplete, paraconsistent, and classical contexts with six-, four-, three-, and two-valued scenarios.
0
0
math.LO 2026-05-11 Recognition

Torsion-free groups yield first natural non-tame AECs

Examples of non-tame abstract elementary classes of abelian groups

K1 is not finitely tame but is countably tame; K2(2^μ) fails tameness below each regular uncountable μ below the first measurable cardinal.

abstract click to expand
We construct an abstract elementary class $K_1$ of torsion-free abelian groups such that $K_1$ is not $(<\aleph_0)$-tame but is $\aleph_0$-tame. This answers a question of [BoVa17]. Furthermore, for every regular uncountable cardinal $\mu$ less than the first measurable cardinal, we construct an abstract elementary class $K_2(2^\mu)$ of torsion-free abelian groups such that $K_2(2^\mu)$ is not $(<\mu)$-tame. $K_1$ and $K_2(2^\mu)$ are non-tame for algebraic reasons. Furthermore, they constitute the first examples of non-tame abstract elementary classes in a natural language.
0
0
math.LO 2026-05-11 1 theorem

One equation captures bounded depth in Hilbert algebras

Bounded depth in Hilbert algebras

The property transfers from Heyting algebras to their implication-only reducts, yielding an equational axiomatization for each fixed bound n

abstract click to expand
Hilbert algebras are the implicative subreducts of Heyting algebras. It is shown that having depth at most n is an equational condition in Hilbert algebras. This generalizes an analogous well-known result in the setting of Heyting algebras.
0
0
math.LO 2026-05-11 2 theorems

LUBs on well-ordered subsets imply maximal elements

Bourbaki--Zorn Normal Forms for Maximality Arguments

A normal-form argument shows that the least upper bound condition on chains guarantees a maximal element via tower fixed points.

abstract click to expand
We isolate a normal-form mechanism underlying Bourbaki--Witt fixed-point arguments and least-upper-bound versions of Zorn-type maximality principles. Given a progressive self-map on a partially ordered set, we define a Bourbaki tower as a well-ordered trajectory whose successor stages are generated by the map and whose limit stages are given by least upper bounds of earlier stages. We prove that least upper bounds for nonempty well-ordered subsets are sufficient to force a fixed point for every progressive self-map. Thus the fixed-point statement is obtained under a weaker completeness hypothesis than the usual chain-complete form of the Bourbaki--Witt theorem. The proof proceeds by constructing a largest Bourbaki tower. The least upper bound of this largest tower belongs to the tower itself and is a fixed point of the map. As a consequence, strictly progressive self-maps cannot exist in such posets. Combining this obstruction with a choice selector on strict upper cones yields a concise maximality principle: if every nonempty well-ordered subset has a least upper bound, then the poset has a maximal element. The contribution is methodological rather than axiomatic. The paper makes explicit a reusable proof architecture connecting well-ordered Bourbaki--Witt fixed points, strict progression obstructions, and least-upper-bound versions of Zorn-type maximality arguments.
0
0
math.LO 2026-05-11 2 theorems

Well-ordered LUBs suffice for fixed points and maximal elements

Bourbaki--Zorn Normal Forms for Maximality Arguments

If every nonempty well-ordered subset has a least upper bound then every progressive map has a fixed point and the poset has a maximal one.

abstract click to expand
We isolate a normal-form mechanism underlying Bourbaki--Witt fixed-point arguments and least-upper-bound versions of Zorn-type maximality principles. Given a progressive self-map on a partially ordered set, we define a Bourbaki tower as a well-ordered trajectory whose successor stages are generated by the map and whose limit stages are given by least upper bounds of earlier stages. We prove that least upper bounds for nonempty well-ordered subsets are sufficient to force a fixed point for every progressive self-map. Thus the fixed-point statement is obtained under a weaker completeness hypothesis than the usual chain-complete form of the Bourbaki--Witt theorem. The proof proceeds by constructing a largest Bourbaki tower. The least upper bound of this largest tower belongs to the tower itself and is a fixed point of the map. As a consequence, strictly progressive self-maps cannot exist in such posets. Combining this obstruction with a choice selector on strict upper cones yields a concise maximality principle: if every nonempty well-ordered subset has a least upper bound, then the poset has a maximal element. The contribution is methodological rather than axiomatic. The paper makes explicit a reusable proof architecture connecting well-ordered Bourbaki--Witt fixed points, strict progression obstructions, and least-upper-bound versions of Zorn-type maximality arguments.
0
0
math.LO 2026-05-08 2 theorems

Definable fields in t-minimal theories are finite or large

Definable groups and fields in t-minimal theories

Any smooth curve with one rational point then has infinitely many; groups receive manifold topologies when the theory is visceral.

abstract click to expand
Let $T$ be a theory which is t-minimal, meaning that with respect to some definable topology, a unary definable set $D \subseteq M$ has non-empty interior iff it is infinite. If $K$ is a definable field in $T$, then $K$ is finite or "large" in the sense of Pop: any smooth algebraic curve $C$ over $K$ with at least one $K$-rational point has infinitely many $K$-rational points. We also assign a canonical topology to any abelian definable group $G$ in a t-minimal theory. In the case where the t-minimal theory is "visceral" in the sense of Dolich and Goodrick, meaning that the definable topology is induced by a definable uniformity, we can drop the assumption of abelianity of $G$, and the resulting topology on $G$ is a definable manifold in the style of Acosta L\'opez and Hasson.
0
0
math.LO 2026-05-07

Choice-switches remain dependent on button systems

A note on the modal logic of symmetric extensions

Independent families of the new toggles always link to standard button examples in the modal logic of symmetric extensions.

abstract click to expand
Taking symmetric extensions can be considered as a generalisation of forcing, which produces a richer multiverse of models with and without the axiom of choice. We can study the structure of this multiverse using modal logic. In particular, we define the concept of of choice-switches, and show any independent system of choice-switches is not itself independent from any standard example of an independent system of buttons.
0
0
math.LO 2026-05-07 2 theorems

Inferon replaces truth as information's core unit

Towards an Inferentialist Account of Information Through Proof-theoretic Semantics

Proof-theoretic semantics offers a reasoning-based alternative for modeling information flow in complex systems.

Figure from the paper full image
abstract click to expand
Information is one of the most widely-discussed concepts of the current era. However, a great deal of insightful work notwithstanding, it is yet to be given wholly convincing logical or mathematical foundations. Without them, we lack adequate reasoning tools for understanding the complex ecosystems of systems upon which the society depends. We seek to rectify this by taking a first step towards developing an inferentialist semantic theory of information. There are three key interacting components. First, conceptual analysis: the metaphysics of information. Dretske expressed the key concepts of information in terms of intentionality, truth, and transmissibility. We replace truth with inferability, and trace the consequences of this replacement. Second, logic: proof-theoretic semantics (P-tS) provides a mathematical-logical realization of inferentialist reasoning. Using P-tS, we develop the first steps towards a mathematical-logical theory of an inferentialist primitive unit of information, the 'inferon'. This proof-theoretic approach counterpoints the model-theoretic view of information articulated in situation theory. Furthermore, we argue that it facilitates addressing all three components of van Benthem and Martinez's categorization of the understandings of information, as range, as correlation, and as code. Our focus is on information-as-correlation. Third, systems: the P-tS tools we develop provide the basis for a mathematical account of distributed systems modelling -- a key tool from informatics for understanding the organization of information processing systems. This yields a reasoning-based theory of information flow in models of distributed systems. Overall, we seek to give a conceptually rigorous mathematical-logical account of information and its role within informatics, grounded in inference and reasoning.
0
0
math.LO 2026-05-07

Inferentialist account replaces truth with inferability in information theory

Towards an Inferentialist Account of Information Through Proof-theoretic Semantics

Proof-theoretic semantics yields the inferon as primitive unit and models information flow in distributed systems.

Figure from the paper full image
abstract click to expand
Information is one of the most widely-discussed concepts of the current era. However, a great deal of insightful work notwithstanding, it is yet to be given wholly convincing logical or mathematical foundations. Without them, we lack adequate reasoning tools for understanding the complex ecosystems of systems upon which the society depends. We seek to rectify this by taking a first step towards developing an inferentialist semantic theory of information. There are three key interacting components. First, conceptual analysis: the metaphysics of information. Dretske expressed the key concepts of information in terms of intentionality, truth, and transmissibility. We replace truth with inferability, and trace the consequences of this replacement. Second, logic: proof-theoretic semantics (P-tS) provides a mathematical-logical realization of inferentialist reasoning. Using P-tS, we develop the first steps towards a mathematical-logical theory of an inferentialist primitive unit of information, the 'inferon'. This proof-theoretic approach counterpoints the model-theoretic view of information articulated in situation theory. Furthermore, we argue that it facilitates addressing all three components of van Benthem and Martinez's categorization of the understandings of information, as range, as correlation, and as code. Our focus is on information-as-correlation. Third, systems: the P-tS tools we develop provide the basis for a mathematical account of distributed systems modelling -- a key tool from informatics for understanding the organization of information processing systems. This yields a reasoning-based theory of information flow in models of distributed systems. Overall, we seek to give a conceptually rigorous mathematical-logical account of information and its role within informatics, grounded in inference and reasoning.
0
0
math.LO 2026-05-07

λ-complete sets extend to saturated models over predicates

On lam-existence over a predicate

In countable fully stable theories, completeness conditions guarantee extensions without altering the predicate part.

abstract click to expand
We prove that in a countable theory $T$ fully stable over a predicate $P$, any $\lam$-complete set $A$ has the $\lam$-existence property. This means that $A$ can be extended to a $\lam$-saturated model of $T$ without changing the $P$-part. The notion of $\lam$-completeness, introduced in this paper, captures some obvious necessary conditions for such an extension to be possible (for example, the $P$-part of $A$ has to be a $\lam$-saturated model of the appropriate theory). So in a fully stable theory $T$, $\lam$-existence can only fail for trivial reasons. This generalizes results of Chatzidakis in the context of difference fields of characteristic 0.
0
0
math.LO 2026-05-07

Strong n-distality yields hypergraph regularity in NIP theories

On n-distality, n-triviality and hypergraph regularity in NIP theories

The result generalizes distal regularity, shows the n-distality hierarchy is strict among stable theories via forking triviality, and forces

abstract click to expand
We study Keisler measures in strongly n-distal NIP theories, generalizing some results of Simon and Chernikov-Starchenko for distal theories and addressing some questions of Walker. In particular, we establish a hypergraph version of the distal regularity lemma, compact domination for definable fsg groups, and demonstrate that the strong n-distality hierarchy is strict among stable theories using a connection to Poizat's total triviality of forking. We also show that infinite strongly n-distal NIP fields have characteristic 0 using a discrepancy result of Babai-Hayes-Kimmel from multiparty communication complexity.
0
0
math.LO 2026-05-07

Continuations embody semantic intuitions in intuitionistic logic

Continuations and Completeness in Proof-theoretic Semantics

Reanalysis of Sandqvist's completeness proof shows how syntactic continuations capture meaning-use relations.

abstract click to expand
This is a short paper about the relationship between logic and computation. More specifically, it is about a relationship between the completeness proof for intuitionistic propositional logic within the form of proof-theoretic semantics that is known as base-extension semantics and a fundamental idea from the theory of computation called continuation-passing semantics. The latter is explained herein both in terms of reduction in natural deduction and the lambda calculus and in terms of proof-search. The relationship between completeness and continuations is explored through an analysis of Sandqvist's proof of the completeness theorem as seen from the mathematical perspective of Kripke's and Heyting's semantics. Our analysis can be seen to reveal how syntactic representations of continuations embody intensional semantical intuitions about the relationship between their meaning and use. These intuitions are made precise using the tools of proof-theoretic semantics.
0
0
math.LO 2026-05-07

Subshift finite determination equals co-language Ziegler reducibility

Comparing the Effective Content of Subshifts

This transfers a group-theory computability result to symbolic dynamics for direct comparison of effective content.

Figure from the paper full image
abstract click to expand
Motivated by Ziegler's computability-theoretic characterisation of finite absolute presentability between groups, we prove an analogous theorem in symbolic dynamics. We introduce the notion of one subshift being finitely determined over another and show that this relation is characterised by Ziegler reducibility between their co-languages. We further investigate a notion of existential closure for subshifts.
0
0
math.LO 2026-05-07

Friedman-Stanley map preserves Scott sentence complexity

Computable Scott Sentences and the Friedman-Stanley embedding

For X-computable ordinals, graphs and image labeled trees match on computable infinitary Scott sentences, so fixed-rank tree classes are all

abstract click to expand
Friedman and Stanley developed the notion of Borel reducibility and illustrated its use in comparing classification problems for some familiar classes of countable structures. For many embeddings, the fact that the embedding is $1-1$ on isomorphism types is explained by the existence of simple formulas that, uniformly, interpret the input structure in the output structure. For the embeddings of graphs in trees, and in linear orderings, there is no uniform interpretation. We focus on a version of the Friedman-Stanley embedding introduced by Harrison-Trainor and Montalban that takes each structure $A$ for the language of graphs to a labeled tree $T_A$. Gonzalez and Rossegger showed that this embedding preserves Scott complexity. We refine this result, showing that for an $X$-computable ordinal, if one of $A$, $T_A$ has a computable infinitary Scott sentence, then so does the other, and the complexities match. Let $\mathbb{T}$ be the class of labeled trees isomorphic to those in the range of the embedding, and let $\mathbb{T}^\alpha$ be the subclass consisting of structures of Scott rank at most $\alpha$. It follows from results of Gao that $\mathbb{T}$ is not Borel. We show that for each $\alpha$, $\mathbb{T}^\alpha$ is Borel. In fact, if $\alpha$ is an $X$-computable ordinal, then $\mathbb{T}^\alpha$ is complete $X$-effective $\Pi_{2\alpha+2}$.
0
0
math.LO 2026-05-06

One model fixes true or false for every core math statement about reals

A Foundation for the Core Mathematician

A new foundation replaces varying truths across set-theoretic models with fixed answers for structures built from the reals.

Figure from the paper full image
abstract click to expand
The foundations of mathematics have long been considered settled by the Zermelo-Fraenkel-Choice axioms. But set theory abounds in models with different truths and even classical questions such as the measurability of projective sets can vary between models. The core of mathematics resides in the study of structures built from the set R of real numbers. This paper proposes a foundation for core mathematics, with both a system of axioms and a definite model of those axioms, in which essentially all core mathematics is incorporated. This definite model delivers a definite truth-value, either true or false, to any core mathematical assertion.
0
0
math.LO 2026-05-06 3 theorems

Every countable-to-one coloring on ω₂ has an injective closed ω₁ copy

A Topological Rainbow Ramsey Theorem

This holds consistently relative to suitable large cardinals and strengthens two earlier theorems while answering an open question.

abstract click to expand
We show that it is consistent relative to the existence of suitable large cardinals that for any countable-to-one coloring $c: [\omega_2]^2\to \omega_2$, there exists a closed subset $A\subseteq \omega_2$ of order type $\omega_1$ such that $c\restriction [A]^2$ is injective. This theorem simultaneously strengthens two theorems, one by Abraham, Cummings and Smyth and another one by Garti and Zhang, as well as answers a question raised by Garti and Zhang. New combinatorial principles involving towers of countable elementary submodels, games concerning regressive functions and variants of strong Chang's conjecture, which are key elements of the proof, are investigated.
0
0
math.LO 2026-05-06

Closed ω₁ rainbow for any countable-to-one pair coloring on ω₂

A Topological Rainbow Ramsey Theorem

The consistency result strengthens two earlier theorems and settles an open question using new combinatorial tools.

abstract click to expand
We show that it is consistent relative to the existence of suitable large cardinals that for any countable-to-one coloring $c: [\omega_2]^2\to \omega_2$, there exists a closed subset $A\subseteq \omega_2$ of order type $\omega_1$ such that $c\restriction [A]^2$ is injective. This theorem simultaneously strengthens two theorems, one by Abraham, Cummings and Smyth and another one by Garti and Zhang, as well as answers a question raised by Garti and Zhang. New combinatorial principles involving towers of countable elementary submodels, games concerning regressive functions and variants of strong Chang's conjecture, which are key elements of the proof, are investigated.
0
0
math.LO 2026-05-06

Free-set and rainbow theorems extend to barriers

Free sets, thin sets and rainbows for barriers

Generalizations preserve computability bounds and fix their reverse-mathematics strength.

abstract click to expand
We formulate and prove the generalizations of Friedman's free set and thin set theorems and of the rainbow Ramsey theorem to colorings of barriers. We analyze the strength of these theorems from the point of view of computability theory proving some upper and lower bounds on the complexity of solutions for computable instances and some uniform computable reductions. We obtain as corollaries some proof-theoretical results on the logical strength of the theorems, in the spirit of reverse mathematics.
0
0
math.LO 2026-05-05

Model yields Π¹₂ equivalence relation without projective generators

A locally countable graph of second projective class not generated by countably many projective functions

A countable second-projective relation on a subset of the reals has no generating family of projective or ROD functions, resolving a prior q

abstract click to expand
To answer a question by Rettich and Serafin, we define a model of set theory in which there exists a countable $\Pi^1_2$ equivalence relation on a subset of the real line, which is not generated by a countable family of projective (or even ROD) functions. Its irreflexive part is accordingly a locally countable $\Pi^1_2$ graph not generated in the same way.
0
0
math.LO 2026-05-05 Recognition

Model yields Π¹₂ equivalence relation not generated by projective functions

A locally countable graph of second projective class not generated by countably many projective functions

Answers whether every countable Π¹₂ relation on reals must arise from countably many projective functions.

abstract click to expand
To answer a question by Rettich and Serafin, we define a model of set theory in which there exists a countable $\Pi^1_2$ equivalence relation on a subset of the real line, which is not generated by a countable family of projective (or even ROD) functions. Its irreflexive part is accordingly a locally countable $\Pi^1_2$ graph not generated in the same way.
0
0
math.LO 2026-05-05

Some c.e

A Computably Enumerable tt-Degree Without Computably Enumerable Irreducible m-Degrees

Negative answer to Odifreddi's problem shows Jockusch's theorem is optimal and cannot require the m-degree to be c.e.

abstract click to expand
In this paper, we provide a negative solution to Problem 3 formulated by P.~Odifreddi in his survey articles \textit{``Strong Reducibilities''} (1981) and \textit{``Reducibilities''} (1999). The problem asks whether every computably enumerable (c.e.) $tt$-degree contains a c.e.\ \textit{irreducible} $m$-degree (i.e., an $m$-degree consisting of only one $1$-degree). We answer this question in the negative by proving the existence of a c.e.\ $tt$-degree that does not contain any c.e.\ irreducible $m$-degree. Our proof relies on the structural properties of c.e.\ semirecursive sets with a rigid complement, originally constructed by A.~N.~Degtev. We show that the unique c.e.\ $m$-degree contained within the $tt$-degree of such a set consists of simple sets, which cannot be cylinders, and therefore necessarily splits into multiple $1$-degrees. Furthermore, our result demonstrates that a classical 1969 theorem by C.~G.~Jockusch Jr. -- which guarantees the existence of an irreducible $m$-degree within every c.e.\ $tt$-degree -- is strictly optimal and cannot be generally strengthened to require such an $m$-degree to be computably enumerable.
0
0
math.LO 2026-05-05

Universal theories capture extension satisfiability in finitary logics

More on expressibility of satisfiability in submodels and extensions

Even when no single sentence works, a universal theory always expresses whether a sentence holds in some extension of a model, unlike thesub

abstract click to expand
We study expressibility in infinitary languages of the modal operators associated with satisfiability of sentences of these languages in submodels and extensions of models. We give a syntactic criterion for expressibility in finitary predicate languages, show that in many cases infinitary languages are closed under the operator associated with submodels, and that this is so in any language with a purely monadic signature. Finally, we prove that in finitary or strongly compact languages, the operator associated with extensions, though can be inexpressible by a single sentence, is always expressible by a universal theory, in striking contrast with the submodel case.
0
0
math.LO 2026-05-04 3 theorems

EML expressions yield only computable reals

Inexpressibility in Exp-Minus-Log

Chaitin's Omega cannot be reached from 1 by the exp-minus-log operation, establishing a hard limit on this system.

abstract click to expand
Odrzywo\l{}ek defined a system Exp-Minus-Log (EML) that reduces all elementary functions over complex numbers down to a constant `$1$', and a single two place function $E(\alpha, \beta) = \exp(\alpha) - \log(\beta)$. This paper shows that in this system, equivalent to Chow's EL numbers, every EML-expressible number is computable. We go on to prove that the canonical example of a non-computable real, Chaitin's $\Omega_U$, is inexpressible in EML. This gives a formal inexpressibility theorem for this system.
0
0
math.LO 2026-05-04

Categoricity in one nonzero arithmetic degree implies it in all

Categoricity without Power

For arithmetically definable theories, being categorical at a single nonzero degree forces the property at every other nonzero degree and, Z

abstract click to expand
We prove an analogue of Morley's categoricity theorem where cardinality is replaced by the recursion-theoretic notion of arithmetic degree. We say that a complete arithmetically definable theory $T$ is $D$-categorical if any two arithmetically extendible models of $T$ of arithmetic degree $D$, considered over a common elementary submodel with arithmetical elementary diagram, are isomorphic over that submodel by an isomorphism which preserves the complexity of sets of degree $D$. Here an arithmetically extendible model means an elementary substructure of a model whose elementary diagram is arithmetical. Our main result is: If $T$ is $D_1$-categorical for some nonzero arithmetic degree $D_1$, then $T$ is $D_2$-categorical for every nonzero arithmetic degree $D_2$. We also show that, assuming ZFC, $D$-categoricity for some nonzero arithmetic degree is equivalent to uncountable categoricity.
0
0
math.LO 2026-05-04

Lexicographic orders on ^α2 classified for countable partition arrows

Infinite-Exponent Partition Relations on Higher Analogues of the Real Line

The arrow to (τ)^τ holds for each countable τ exactly when α meets conditions proved in ZF.

abstract click to expand
We present a number of results concerning infinite-exponent partition relations on linear orders of the form $\langle {}^\alpha 2,<_{\text{lex}}\rangle$ for $\alpha$ an ordinal, generalising the setting of the real line, working throughout in ZF without the Axiom of Choice. As a particular consequence of our results, we obtain a full classification of the relation $\langle {}^\alpha 2,<_{\text{lex}}\rangle \rightarrow (\tau)^\tau$ for $\tau$ countable.
0
0
math.LO 2026-05-04

Intuitionistic common knowledge gets complete cyclic calculi

Intuitionistic Common Knowledge

Axiomatizations and proof systems for ICK and its S4 and S5 variants are sound, complete, and decidable in exponential time.

Figure from the paper full image
abstract click to expand
We study an intuitionistic version of common knowledge logic (CK), called ICK, which was introduced by J\"ager and Marti. ICK extends intuitionistic propositional logic (IPL) by multiple box modalities interpreted as knowledge operators for various agents and a common knowledge operator. Formulae are interpreted over birelational Kripke models satisfying a simple interaction principle between the intuitionistic order and the modal accessibility relations. Furthermore, we consider the restriction to reflexive, S4 and S5 models. We present axiomatizations as well as analytic cyclic sequent calculi for all considered logics and prove them to be sound and complete. Furthermore, we establish the finite model property and decidability, show that proof-search in the cyclic calculi can be automated, provide a translation of CK over S5 into ICK over S5 and establish that the proof-search and validity problems of all considered logics can be solved in exponential time.
0
0
math.LO 2026-05-01

Primitive recursive selector verifies every consistency instance for strong theories

Uniformity of Consistency in Arithmetic and G\"odel's Second Incompleteness Theorem: Ein M\"archen

The construction works for all sufficiently strong arithmetizable T even though the single uniform consistency sentence stays unprovable.

abstract click to expand
In much discussed work Artemov has recently shown that, for $\mathrm{PA}$, the consistency schema admits a form of uniform verification via selector proofs, despite the unprovability of the corresponding uniform consistency sentence $\mathrm{Con}(\mathrm{PA})$. In this note, we recast that this phenomenon extends to all sufficiently strong arithmetizable theories: For such theories $T$, there exists a primitive recursive selector producing proofs of all instances of the associated consistency schema. This results -- a soft version of a classical result of Pudl\'ak -- yields a form of computational uniformity, despite the fact that it cannot be internalized as the uniform consistency sentence of G\"odel's Second Incompleteness Theorem. Our main goal is to analyze this gap and to locate selector proofs within the broader framework of provability and reflection.
0
0
math.LO 2026-05-01

Abstention restricts safe answer domains in formal systems

Hallucination, abstention, and computable inseparability

Avoiding wrong definite answers by abstaining forces computable separators, which cannot exist for certain pairs of sets.

abstract click to expand
The impossibility of eliminating hallucination, understood here as incorrect definite answers, in sufficiently expressive yes-or-no formal domains is an immediate consequence of classical undecidability theorems. This note does not revisit that forced-answer obstruction as its main claim. Instead, it attempts to formally describe the corresponding limitation for abstaining systems. Abstention can trivially avoid hallucination if the system is allowed to abstain on every input; the substantive question is how large the domain of guaranteed correct non-abstaining answers can be. We formulate this question using separation in the arithmetical hierarchy. Given disjoint sets $A$ and $B$, any system that answers Yes on all queries indexed by $A$ and No on all queries indexed by $B$ induces a separator of $A$ from $B$. By combining this observation with the classical existence theorem of $\Delta_{n}^{0}$-inseparable pairs of $\Sigma_{n}^{0}$-sets, we yield a computability-theoretic trade-off between avoiding hallucination by abstention and maintaining a large domain of guaranteed coverage.
0
0
math.LO 2026-05-01

Abstention restricts guaranteed coverage to avoid hallucinations

Hallucination, abstention, and computable inseparability

In domains that encode the arithmetical hierarchy, systems cannot answer correctly across inseparable sets without abstaining on part of the

abstract click to expand
The impossibility of eliminating hallucination, understood here as incorrect definite answers, in sufficiently expressive yes-or-no formal domains is an immediate consequence of classical undecidability theorems. This note does not revisit that forced-answer obstruction as its main claim. Instead, it attempts to formally describe the corresponding limitation for abstaining systems. Abstention can trivially avoid hallucination if the system is allowed to abstain on every input; the substantive question is how large the domain of guaranteed correct non-abstaining answers can be. We formulate this question using separation in the arithmetical hierarchy. Given disjoint sets $A$ and $B$, any system that answers Yes on all queries indexed by $A$ and No on all queries indexed by $B$ induces a separator of $A$ from $B$. By combining this observation with the classical existence theorem of $\Delta_{n}^{0}$-inseparable pairs of $\Sigma_{n}^{0}$-sets, we yield a computability-theoretic trade-off between avoiding hallucination by abstention and maintaining a large domain of guaranteed coverage.
0
0
math.LO 2026-05-01

VC-density in group pairs bounded by twice the parameter count

VC-Density in Divisible Oriented Abelian Groups and Their Pairs

The sharp bound forces such pairs of divisible oriented abelian groups to have dp-rank 2.

abstract click to expand
We show that the VC-density in certain theories of oriented abelian groups is at most the size of parameter variables, which yields dp-minimality. We further prove that the VC-density of formulas in pairs of such models is bounded by twice the size of parameter variables. This uniform upper bound is shown to be sharp, and as a consequence, we show that such pairs have dp-rank 2.
0
0
math.LO 2026-05-01

Computable étale spaces match maps into overt-discrete spaces

A note on computable \'{e}tale spaces

TTE computable topology equates local homeomorphisms over Y with computable functions from Y to the effective category of overt-discrete qu

abstract click to expand
An \'{e}tale space over a topological space $Y$ is defined as a local homeomorphism from a topological space $X$ into $Y$. They often come up in topos theory because of the equivalence between sheaves and \'{e}tale spaces over a space. In this note, we define computable \'{e}tale spaces over a computable topological space $Y$ within the TTE framework of computable topology, and show they are naturally equivalent to computable functions from $Y$ to $\mathsf{ODS}$, the effective quasi-Polish category of overt-discrete quasi-Polish spaces. More generally, if $\cal C$ is a computable category (or groupoid), then there is an equivalence between computable functors from $\cal C$ to $\mathsf{ODS}$, and computable \'{e}tale spaces equipped with a computable action by $\cal C$.
0
0
math.LO 2026-04-30

Hilbert inner product needs exp(1/ε) samples for stability

A note on quantitative stability in Hilbert spaces

Proves (k,ε)-stability holds for k ≥ exp(π/ε) but fails below exp(log 2/ε), with adjusted rates under powering.

abstract click to expand
We study stability theory in Hilbert spaces quantitatively. We prove that the inner product on the unit ball is $(k,\epsilon)$-stable for all $k\ge \exp(\pi/\epsilon)$, and it is not $(k,\epsilon)$-stable for $k\le \exp(\log 2/\epsilon)$, showing that the growth is necessarily exponential in $1/\epsilon$. We then analyze how stability scales under nonlinear connectives applied to the inner product. In particular, for power-type predicates $f(x,y)=\langle x,y\rangle_+^\beta$ with $\beta<1$ we obtain upper and lower bounds of the form $\exp(C\epsilon^{-1/\beta})$, and for $\beta>1$ and integer powers $\langle x,y\rangle^d$ we retain the bilinear scale $\exp(C/\epsilon)$.
0
0
math.LO 2026-04-30

Ramsey property eliminates maximal almost disjoint families

Ramsey Property and Pathological Sets: Almost Disjointness, Independence and Other Maximal Objects

Under ZF plus countable choice for reals, this confirms Mathias' 1977 conjecture for sets in good pointclasses.

Figure from the paper full image
abstract click to expand
We show that under $\mathsf{ZF} + \mathsf{CC}_{\mathbb R}$, if the Ramsey property holds for all sets in a good pointclass $\Gamma$, then there is no MAD family in $\Gamma$, proving a long-standing conjecture made by A.R.D.\ Mathias in 1977. This also holds for $\mathcal I$-MAD families with respect to analytic ideals $\mathcal I$ including $\mathcal{ED}$, $\mathcal{ED}_{\mathrm{fin}}$, and $\finalpha{\alpha}$ for all countable ordinals $\alpha$. Under the same assumption, we show that if any one of the Baire property, Lebesgue measurability or Ramsey property holds for all sets in $\Gamma$, then there is no maximal independent family in $\Gamma$. Under the stronger assumption $\mathsf{ZF} + \mathsf{DC}_{\mathbb R}$, we further prove that if the Ramsey property holds for all sets in $\Gamma$, then $\Gamma$ contains no Vitali sets and thus no Hamel bases.
0
0
math.LO 2026-04-30

Necessary conditions govern Pfaffian solutions of algebraic ODEs

Special classes of functions

Model theory and differential algebra yield conditions for complex Pfaffian solutions and examples without real ones on open intervals.

abstract click to expand
Using model theory and differential algebra, we give necessary conditions for algebraic ordinary differential equations to have a complex Pfaffian solution on some complex domain. These tools also allow us to give many examples of algebraic ordinary differential equations that do not have real Pfaffian solution on any open interval. We also give a sufficient condition for a function to be d-irreducible, in the sense of Nishioka. These characterizations are used to give several answers to questions of Bianconi (2016) and strengthen a theorem of Nguyen (2009).
0
0
math.LO 2026-04-29

Formulas in F_q((Q)) reduce to one existential polynomial equation

Elimination results for tame fields with finite residue fields

Tame Hahn series fields with finite residues allow every first-order statement to be rewritten using a single integer polynomial and one new

abstract click to expand
Building on work of Kuhlmann and Lisinski, we study the theory of the Hahn series field $\mathbb{F}_{q}(\!(\mathbb{Q})\!)$, over a finite field $\mathbb{F}_{q}$, equipped with the $t$-adic valuation, in a language of valued fields. We prove that every formula is equivalent to a formula $\exists y\colon f(x_{1},\ldots,x_{n},y)=0$, for a polynomial $f\in\mathbb{Z}[x_{1},\ldots,x_{n},y]$.
0
0
math.LO 2026-04-29

Finite Kripke models embed into arithmetic via provability predicates

Finite Kripke models and provability interpretations in quantified modal logic

Σ₂ Fefermanian and Σ₁ D2^G predicates realize modal structures for conversely well-founded and constant-domain cases in quantified logic.

abstract click to expand
In this paper, we investigate arithmetical completeness with respect to finite Kripke models of quantified modal logic. We adapt the finite-model embedding techniques of Artemov and Japaridze to two settings involving finite Kripke models. First, for conversely well-founded finite Kripke models of quantified modal logic, we construct a $\Sigma_2$ Fefermanian provability predicate together with an arithmetical interpretation that embeds the model into arithmetic. Second, for finite constant domain Kripke models of quantified modal logic, we construct a $\Sigma_1$ provability predicate satisfying $\mathbf{D2^G}$ and an arithmetical interpretation yielding such an embedding.
0
0
math.LO 2026-04-29

S^1_2 stays consistent with EXP not in P/poly

From G\"odel incompleteness to the consistency of circuit lower bounds

Godel-style separations of V^1_2 imply that weak arithmetic cannot refute the circuit lower bound

abstract click to expand
We prove that the bounded arithmetic theory $S^1_2$ is consistent with EXP $\not\subseteq$ P/poly. More generally, we show that certain separations of $V^1_2$ from a theory $T$ imply the consistency of $T$ with EXP $\not\subseteq$ P/poly. For $T=S^1_2$, Takeuti (1988) established such a separation using a variant of G\"odel's consistency statement. Analogous results hold for PSPACE $\not\subseteq$ P/poly but the required separations of theories are yet unknown. Finally, we give magnification results for the hardness of proving almost-everywhere versions of these lower bounds.
0
0
math.LO 2026-04-28

Inferential omega-rule gives arithmetic a unique model

Carnapian Frameworks and Categoricity of Arithmetic via Inferential ω-logics

Weaker than second-order logic, the system secures number concepts without circular appeal to them.

abstract click to expand
We provided in \cite{BaldwinBrincusI} extensions of first order logic by modified inferential definitions of the classical $\omega$-rule in $1$ or $2$ sorts. These logics are categorical in the inferential sense. Arithmetic has a unique countable model in each case, e.g. first order PA is categorical in our first logic. The 2-sorted case interprets $L_{\omega_1,\omega}$. In this paper, we discuss two philosophical problems raised by Button and Walsh \cite{ButtonWalshbook} concerting the identification of a unique isomorphism class. First, we argue that the doxological challenge (on referential determinacy) gets a clear answer if placed in an appropriate (Carnapian) linguistic framework and is meaningless otherwise. To clarify this approach, we address Button-Walsh's dismissal of concepts-modelism by developing the notion of {\em cognitive modelism}, according to which classical mathematics is a complex process of constructing and developing a distinctive class of concepts. Second, we argue that the inferential $\omega$-logics, that are much weaker than second order logic, do not appeal to the arithmetical concepts that the categoricity theorems proved within these logics aim to secure.
0
0
math.LO 2026-04-28

NTP2 expansions preserve constructibility of definable sets

NTP2 topological structures

Tame expansions of the reals and ordered groups by constructible sets keep definable sets simple and functions piecewise continuous.

abstract click to expand
A subset of a topological space is constructible if it is a finite Boolean combination of closed sets. We prove that every NTP$_2$ expansion of $(\mathbb{R},<,+)$ by constructible sets defines only constructible sets, and that definable functions are generically piecewise continuous. The result also holds for all NTP$_2$ expansions of $(\mathbb{Q}_p,+,\cdot)$, and all NTP$_2$ definably complete expansions of ordered groups. In the latter case, the structure is generically locally o-minimal, has definable choice, and carries a well-behaved notion of naive topological dimension. For NIP uniform topological structures, constructibility of definable sets is preserved in the Shelah expansion. We classify strong expansions of $(\mathbb{R},<,+)$ by constructible sets, and obtain results on NTP$_2$ d-minimal structures.
0
0
math.LO 2026-04-28

Almost free algebras make isomorphism polynomial-time decidable

Almost free algebras: from the word problem to elimination of quantifiers

Quotients of term algebras by ground equations have polynomial time solutions to finiteness and isomorphism plus quantifier elimination with

abstract click to expand
Term algebras are important objects in computer science and are correspondingly well-studied. A natural generalization is to quotient these algebras by finitely many ground term equations, obtaining what we call almost free algebras. One of the earliest results on almost free algebras is that their word problem is polynomial time decidable. In this paper, we show that other natural problems: finding canonical representatives; computing the cardinality of a congruence class; checking if all congruence classes are infinite; checking if the algebra is finite; checking if two algebras are isomorphic, are all polynomial time decidable. Another famous result regarding term algebras is that they admit quantifier elimination in a suitably expanded language. Following this pattern, we also show that almost free algebras admit quantifier elimination by expanding the language with the standard tester predicates. While this is implied by existing results, we view our main contribution here as providing a different approach, which we posit can be easily extended to a larger class that is not covered by existing works. Finally, we provide an application to the quantifier elimination procedure, constructing examples of non-initial algebras over arbitrary signatures with a polynomial time word problem.
0
0
math.LO 2026-04-27

Closed Ramsey numbers for ω·n+1 lie between ω^4 and ω^5

On closed Ramsey numbers of small countable ordinals

For every n ≥ 3 the value R^{cl}(ω·n+1, 3) sits strictly above ω^4·(n-2)+1 yet below ω^5, sharpening earlier estimates.

Figure from the paper full image
abstract click to expand
This paper is a contribution to the investigation of closed partition relations for pairs of countable ordinals. As our main result, we prove that \[\omega^4 \cdot (n-2)+1 < R^{cl}(\omega \cdot n+1,3)<\omega^5\] for every integer $n \geq 3$. This result significantly improves the existing upper and lower bounds for these closed Ramsey numbers. In addition, we prove that \[\omega^{\theta}\nrightarrow_{cl} (\omega^{\alpha},3)^2\] whenever $1 \leq \alpha \leq \theta<\omega_1$ satisfy $\theta < R(\alpha,3)$. This result asymptotically improves the existing lower bounds for $R^{cl}(\omega^n,3)$ and slightly strengthens the existing necessary condition for being a topological partition ordinal.
0
0
math.LO 2026-04-27

Multiple topologies give complete semantics for intuitionistic modal logics

Polytopological Semantics for Intuitionistic Modal Logics

Using closure and derivative operators on polytopological spaces, the approach proves soundness and strong completeness for K4 and S4  vari

Figure from the paper full image
abstract click to expand
We develop polytopological semantics for various constructive, intuitionistic, and G\"odel--Dummett variations of $\mathsf{K4}$ and $\mathsf{S4}$. In our models, intuitionistic and modal operators are interpreted via various topologies over a single set, equipped with either the closure or derivative operators. We identify regularity conditions to ensure that spaces validate each of our target logics and prove that all the logics considered are sound and strongly complete with respect to their respective semantics.
0
0
math.LO 2026-04-24

Craig interpolation proven for the six open extensions of S4

Interpolation above S4

This completes the classification of which normal extensions satisfy the property.

Figure from the paper full image
abstract click to expand
We complete Maksimova's classification of the normal extensions of S4 with interpolation. In particular, we prove Craig interpolation for the six extensions of S4 for which Craig interpolation was still open. The proof strategy builds upon the ideas of Smory\'nski, but employs a novel approach using Fine's frame formulas for splitting clusters.
0
0
math.LO 2026-04-24

Definable well-order equates projective and ordinary chromatic numbers

Projective Chromatic Numbers

For locally countable graphs, the minimal number of definable colors matches the classical chromatic number once a projective well-order of

abstract click to expand
We extend classical notions of definable colourability of graphs to the general projective setting and investigate whether known results, mainly about the $G_0$ dichotomy and the $2n + 1$ conjecture, hold in the context of higher projective pointclasses. We establish that for $n \ge 2$, the presence of a $\mathbf{\Delta}^1_n$-definable well-order of the reals implies $\chi_{\mathbf{\Delta^1_n}}(G) = \chi(G)$ for all locally countable $\mathbf{\Delta^1_n}$-definable graphs $G$, and that the presence of a $\mathbf{\Delta^1_2}$-definable well-order of the reals implies $\chi_{\mathbf{\Delta^1_2}}(G) = \chi(G)$ for all locally countable Borel graphs $G$.
1 0
0
math.LO 2026-04-24

Restricted class logics match large cardinals

Model theory of class-sized logics

Downward Löwenheim-Skolem equals Weak Vopěnka's Principle and Ord-Woodin; compactness equals Shelah cardinals, some in ZFC.

abstract click to expand
We study compactness and L\"owenheim-Skolem properties of fragments of the class-sized logic $\mathcal{L}_{\infty \infty}$ and of class-sized versions of second-order and sort logics. In these fragments, certain combinations of infinitary quantifiers and boolean connectives are banned. While model-theoretic properties fail for unrestricted class logics, this drastically changes in our more restricted setting. We show that model-theoretic properties of class logics characterise a wide array of large cardinals, and that some of them can even be obtained in ZFC. In particular, we give a characterisation of Weak Vop\v{e}nka's Principle and Ord is Woodin by downwards L\"owenheim-Skolem properties, and a characterisation of Shelah cardinals by a compactness property of class-sized logics. We further strengthen many known results about properties of set-sized logics by studying how they transfer to class-sized extensions.
0
0
math.LO 2026-04-23

Fraïssé structure has universal automorphism group without extensible age

An unusual example of a universal automorphism group

The example shows the two properties are not equivalent even though one clearly implies the other.

abstract click to expand
Let $M$ be a Fra\"{i}ss\'{e} structure (a countably infinite ultrahomogeneous structure). We refer to the class of structures embeddable in $M$ as the $\omega$-age of $M$. We consider the following two properties of $M$: we say that $M$ has a universal automorphism group if, for each $A$ in the $\omega$-age of $M$, there is an embedding $\textrm{Aut}(A) \to \textrm{Aut}(M)$, and we say that $M$ has group-extensible $\omega$-age if, for each $A$ in the $\omega$-age of $M$, there is an embedding $A \to M$ such that each automorphism of the image extends to an automorphism of $M$ and the extension map preserves group composition. It is immediate that if $M$ has group-extensible $\omega$-age, then $M$ has a universal automorphism group. We give an example of a Fra\"{i}ss\'{e} structure with a universal automorphism group whose $\omega$-age is not group-extensible, showing that the above two properties are not equivalent.
0
0
math.LO 2026-04-22

Model separates boldface Σ¹₃ uniformization from lightface Σ¹₄

On boldsymbol{Sigma}¹₃- and Sigma¹₄-uniformization

A universe is built where the boldface version holds at level 3 but the lightface version fails at level 4, showing the two principles are独立

abstract click to expand
Assuming the consistency of $\mathsf{ZFC}$, we construct a model of set theory in which the boldface $\mathbf{\Sigma}^1_3$-uniformization property holds, yet the lightface $\Sigma^1_4$-uniformization property fails, separating these two principles for the first time. We also indicate how to create a universe where $\Sigma^1_3$-uniformization holds, but $\Sigma^1_4$-uniformization fails using inner models with large cardinals.
0
0
math.LO 2026-04-21

QLETF+ is sound and complete for six-valued semantics

Positive, Negative, and Reliable Information in a First-Order Logic of Evidence and Truth

The logic uses o-extensions to track reliable information alongside positive and negative data for predicates.

abstract click to expand
In this paper we present the first-order logic QLETF+, a quantified version of the logic LETF+, introduced in Coniglio and Rodrigues (Studia Logica 112:561-606, 2024). QLETF+ exhibits several properties that are not always enjoyed by logics equipped with classicality operators. We show that it satisfies the replacement property and admits conjunctive, disjunctive, and prenex normal forms. Alongside extensions and anti-extensions, as in the previously studied first-order semantics for LETs, we make use here of what we call o-extensions: given an n-ary predicate symbol P, the o-extension of P is the set of n-tuples of individuals that satisfy the predicate oP. We prove the soundness and completeness of the deductive system of QLETF+ with respect to the six-valued first-order semantics.
0
0
math.LO 2026-04-21

Missing top grade makes any passing grade acceptable in deontic logic

Classification and deontic explosion for contrary-to-duty obligations

Latest system permits every intermediate success; 1997 system classifies all models by one forbidden world.

abstract click to expand
Carmo and Jones have presented a sequence of candidate axiom systems for conditional obligation between 1997 and 2022. For their most recent system we demonstrate a limited form of deontic explosion: given that a student does not get the highest possible grade on a test, any other passing grade is acceptable. In addition to that negative result, we give a positive one: revisiting the strongest version of Carmo and Jones' 1997 system, we provide a surprising classification of all satisfying models in terms of a single forbidden possible world.
0
0
math.LO 2026-04-20

Generalized model theory reduces stability to Borel complexity

The generalized continuous model theory, Borel complexity and stability

Iso(Y)-spaces for Polish spaces turn model-theoretic properties into subsets of Effros spaces whose definability can be measured.

abstract click to expand
Given Polish space $\mathcal{Y}$ and a continuous language $L$ we study the corresponding logic $\mathsf{Iso}(\mathcal{Y})$-space $\mathcal{Y}_L$. We build a framework of generalized model theory towards analysis of Borel complexity of families of subsets of Effros spaces $\mathcal{F}(\mathcal{Y})^k_L\times \mathcal{F}(\mathsf{Iso} (\mathcal{Y}))^l$ corresponding to standard model-theoretic properties. In this paper we mainly apply this approach to stability.
0
0
math.LO 2026-04-20

Two modalities model strict potentialism and mirror to simpler logics

Strict potentialism in modal mirrors

Disabling object generation yields restricted plural logic; disabling truth determination yields intuitionistic logic, shown in predicative,

abstract click to expand
Potentialism is the view that objects are successively generated in an incompletable process. A strict version of the view adds that truths are successively determined. Strict potentialism can be analyzed using two modalities: one for the generation of objects, another for truths becoming determined. The result is a classical bimodal logic. We obtain simpler and more user-friendly theories by invoking so-called mirroring theorems to ``switch off'' one or both modalities, in return for a less classical logic. When the modality of object generation is switched off, we obtain a restricted plural logic. When the modality of truth determination is switched off, the logic becomes intuitionistic. Finally, the value of this general approach to strict potentialism is illustrated by applications to a Weyl-inspired predicative set theory, Cantor's domain principle, and strict potentialism about Cantorian sets.
0
0
math.LO 2026-04-20

Complete theories are relatively decidable exactly via one-formula model-complete add-on

Characterizing relative decidability in terms of model completeness

The equivalence holds precisely when the theory proves the added formula is realizable and the extension is conservative and model complete.

abstract click to expand
A theory $T$ is said to be relatively decidable if for every model of $T$, one can compute the elementary diagram of that model from its atomic diagram together with $T$. We verify a conjecture of Chubb, Miller, and Solomon by showing that for complete theories $T$, $T$ is relatively decidable if and only if $T$ has a conservative model complete extension of the form $T \cup \{\varphi(\bar{c})\}$ where $T \models \exists \bar{x} \; \varphi(\bar{x})$. We also show that no such characterization works for incomplete theories.
0
0
math.LO 2026-04-20

Equivalence links orthomodular lattices to finitary dynamic algebras

Categorical Equivalence Between Finitary Orthomodular Dynamic Algebras and Orthomodular Lattices

This connects algebraic models of quantum logic and extends directly to Hilbert space lattices.

abstract click to expand
This paper reveals a categorical equivalence connecting two distinct quantum logic structures. The first is the orthomodular lattice, an algebraic system designed to formalize the properties of quantum systems. The second is a finitary orthomodular dynamic algebra, a specialized development of the orthomodular dynamic algebra where the underlying quantum actions are restricted to be finitary. The applicability of the result extends to more specialized lattices, such as Hilbert lattices of closed subspaces of a Hilbert space, beyond general orthomodular lattices. As these lattice structures exhibit connections to a diverse array of quantum structures, the established equivalence categorically bridges unital involutive m-semilattices with a broad spectrum of quantum formalisms.
0
0
math.LO 2026-04-20

D-maximal many-one degrees contain least finite-one degrees

texorpdfstring{D}{D}-maximal many-one degrees contain least finite-one degrees

The result holds for every nonrecursive such degree that contains a D-maximal set, via known results plus a new duplicate-cover construction

abstract click to expand
Richter, Stephan, and Zhang asked whether every nonrecursive many-one degree contains a least finite-one degree. We prove this for every nonrecursive \ce\ many-one degree containing a $D$-maximal set. The proof handles the simple cases via known results and develops a duplicate-cover method for the remaining $D$-maximal types in the classification of Cholak, Gerdes, and Lange.
0
0
math.LO 2026-04-20

Forcing yields ω₃-long almost-nested chain of subsets of ω₁

Long Strong Chains of Subsets of ω₁

The construction preserves the first three uncountable cardinals and improves earlier upper bounds on chain length.

abstract click to expand
We force the existence of a chain of length $\omega_3$ in $[\omega_1]^{\omega_1}$ increasing modulo finite. The construction involves symmetric systems of models of two types as side conditions, introduced by the second author. This improves previous results of Koszmider and Veli\v{c}kovi\'{c}-Venturi.
0
0
math.LO 2026-04-20

Quotient encodings bound C*-algebra properties in the Borel hierarchy

Polish spaces for countable and separable structures through quotient encodings

Kernels form Polish spaces under Wijsman topology so nuclearity is Borel, AF-ness is Pi^0_3 and K-groups receive internal Borel codes.

abstract click to expand
We develop a unified framework for locating natural properties of algebraic and analytic structures within the Borel hierarchy. Objects are presented as quotients of a universal generator and definability is read directly from the quotient data. For separable Banach-type structures (Banach algebras, $C^*$-algebras, Banach lattices, TROs) the kernel space is Polish under the Wijsman topology, and the quotient-norm functional $K\mapsto \|x+K\|$ is continuous, yielding a uniform definability scheme whose Borel ranks are bounded by quantifier alternation depth. For countable algebraic structures (groups, rings, lattices) we work on compact Polish spaces of congruences where atomic predicates are clopen. We obtain explicit Borel upper bounds: in the \emph{unital} $C^*$-algebra coding based on $C^*_{\max}(F_\infty)$, stable finiteness is closed, nuclearity is Borel, simplicity is~$G_\delta$, AF-ness lies in~$\Pi^0_3$, nuclear dimension~$\le n$ lies in~$\Pi^0_3$, and for fixed exact~$D$, $D$-absorption is analytic. For countable groups, soficity is~$G_\delta$; for abelian groups, slenderness is~$\Pi^0_3$. We give an internal Borel coding of the $K_0$-assignment in the quotient/Wijsman framework; for each fixed coordinate the corresponding section is $F_\sigma$, and suspension together with Bott periodicity yields Borel codings of all higher $K$-groups. We also show that several bounds are optimal ($\Sigma^0_2$- and $\Pi^0_2$-complete). To calibrate the method's reach, we exhibit a $\Pi^1_1$-complete property (separable dual in the commutative $C^*$-setting), provably outside the Borel hierarchy.
0
0
math.LO 2026-04-16

Rank function realizes every countable ordinal in Fraïssé classes

A rank function for Fra\"{i}ss\'{e} classes and the rank property

For graphs, tournaments and orders, structures exist at every level of distance to the universal Fraïssé limit.

abstract click to expand
Given a hereditary class $\mathcal{F}$ of finite relational structures, the rank function $\mathsf{rk}:\sigma\mathcal{F}\to\omega_1\cup\{\infty\}$, introduced by Kubi\'{s} and Shelah, measures how far a countable structure is from being universal within its class: $\mathsf{rk}(X)=\infty$ if and only if the Fra\"{\i}ss\'{e} limit embeds into $X$. We say that $\mathcal{F}$ has the Rank Property (RP) if every countable ordinal is realized as the rank of some $X\in\sigma\mathcal{F}$. We develop the basic theory of the rank function and establish RP for three families of classes: those satisfying the free amalgamation property and the full extension property (covering graphs, hypergraphs, and many others); finite tournaments; and finite linear orders. For the latter, we compute the rank of every countable ordinal: if $\omega^{\beta_1}\cdot c_1$ is the leading Cantor normal form term of $\alpha\geq\omega$, then $\mathsf{rk}(\alpha)=\omega\cdot\beta_1+\lfloor\log_2 c_1\rfloor$.
0
0
math.LO 2026-04-16 1 theorem

Rank function realizes every countable ordinal

A rank function for Fra\"{i}ss\'{e} classes and the rank property

For amalgamation classes, tournaments and linear orders the universality measure covers all ordinals via an explicit Cantor-normal-form rule

abstract click to expand
Given a hereditary class $\mathcal{F}$ of finite relational structures, the rank function $\mathsf{rk}:\sigma\mathcal{F}\to\omega_1\cup\{\infty\}$, introduced by Kubi\'{s} and Shelah, measures how far a countable structure is from being universal within its class: $\mathsf{rk}(X)=\infty$ if and only if the Fra\"{\i}ss\'{e} limit embeds into $X$. We say that $\mathcal{F}$ has the Rank Property (RP) if every countable ordinal is realized as the rank of some $X\in\sigma\mathcal{F}$. We develop the basic theory of the rank function and establish RP for three families of classes: those satisfying the free amalgamation property and the full extension property (covering graphs, hypergraphs, and many others); finite tournaments; and finite linear orders. For the latter, we compute the rank of every countable ordinal: if $\omega^{\beta_1}\cdot c_1$ is the leading Cantor normal form term of $\alpha\geq\omega$, then $\mathsf{rk}(\alpha)=\omega\cdot\beta_1+\lfloor\log_2 c_1\rfloor$.
0
0
math.LO 2026-04-16

Logic model characterizes harmonic manifolds for n at most 2

Saturation and isomorphism of abstract harmonic spaces

Abstract harmonic spaces embed in continuous Banach logic, giving U-rank descriptions of M^n and measure bijections.

abstract click to expand
This paper models the theory of abstract harmonic spaces in the syntax of the continuous first-order logic of Banach lattices. It addresses a topological question asking when a one-to-one harmonic map onto smooth manifolds $M^n$ is a diffeomorphism. We give $M^n$ ($n\le 2$) a characterization by $U$-rank and elementary saturation for large cardinals. Polar sets are characterized by several equivalent conditions from the omitting type theorem. Consequently, harmonic measures on the ideal boundary in Martin representation are bijectively mapped to Keisler measures supported on non-principal types. Further problems concerning o-minimality and non-local potentials are finally discussed.
0
0
math.LO 2026-04-15

Three exactness levels for SCI on problem families

From Witness-Space Sharpness To Family-Pointwise Exactness For The Solvability Complexity Index

Witness-space sharpness equals worst-case exactness but is weaker than family-pointwise, with upgrade theorems that bridge them.

abstract click to expand
We study how exact Solvability Complexity Index (SCI) statements should be formulated for families of computational problems rather than for single problems. While the equality \(\operatorname{SCI}_G (\mathcal P)=k\) is unambiguous for an individual computational problem \(\mathcal P\), the family setting requires one to distinguish family-pointwise exactness, witness-space sharpness, and worst-case exactness. We formalize this trichotomy, prove that witness-space sharpness coincides with worst-case exactness but is, in general, strictly weaker than family-pointwise exactness, and show that certain Koopman-operator classification results are sharp only in this worst-case sense. We then establish two positive upgrade theorems: an abstract pullback principle and a concrete finite-query criterion guaranteeing that witness-space sharpness upgrades to family-pointwise exactness. Next, we introduce a decoder-regular finite-query transport preorder on SCI computational problems, prove that it is a preorder, derive a transport-saturation sufficient criterion extending the principal-source package, and show that the associated transport degrees need not form a lattice in full generality. We analyze the natural decoder classes \(\mathscr R_{\mathrm{cont}}\) and \(\mathscr R_{\mathrm{Bor}}\): on the full class the corresponding quotients are not upper semilattices, while on the nondegenerate subclass the preorder is upward and downward directed. Finally, we exhibit two natural positive families realizing the principal transport mechanism: exact integration on compact intervals and a fixed-window spectral decision family obtained by block-diagonal stabilization.
0
0
math.LO 2026-04-15

New model theory defines isomorphism for formal languages

On a new theory of models for formal mathematical systems

Isomorphic and homomorphic structures allow mappings between formal systems and adaptation of reduced set theory.

abstract click to expand
We study a new model theory for formal mathematical systems that we developed in a previous paper. We introduce isomorphic and homomorphic structures for formal languages, present some results and examples and conclude our paper with a discussion about the reduced set theory RST adapted to our new theory.
0
0
math.LO 2026-04-14

Transitive extensions exist only for power-of-two colors or even arity

Transitive Extensions of Automorphism Groups of Generic Structures

The classification applies to automorphism groups of generic hypergraphs and hypertournaments, extending finite-group results to infiniteFra

abstract click to expand
This work addresses the existence of transitive extensions of certain infinite permutation groups which arise as the automorphism groups of model-theoretic structures which are generic in the Fra\"iss\'e sense. The study of transitive extensions has hitherto largely concerned itself with finite permutation groups. Moving beyond the finite realm, we develop combinatorial tools to prove that transitive extensions exist for edge-colored k-hypergraphs only when the number of colors is a power of two and that transitive extensions exist for k-hypertournaments (in the Cherlin sense) only when k is even, among other results.
0
0
math.LO 2026-04-14

A c.e

A computably enumerable many-one degree with no least finite-one degree

The construction yields a nonrecursive c.e. set A where no member of its many-one degree is finite-one reducible from all the others.

abstract click to expand
Richter, Stephan, and Zhang asked whether every nonrecursive many-one degree contains a least finite-one degree. We solve this question in the negative, already within the class of computably enumerable many-one degrees. Positive answers are known in two disjoint natural settings: for a measure-one and comeager class of $m$-rigid sets, and, in a companion paper, for computably enumerable many-one degrees containing a $D$-maximal set. We construct a nonrecursive \ce\ set $A$ such that for every set $X \eqm A$ there exists a c.e.\ set $B \eqm A$ with $X \not\lfo B$. Hence the many-one degree of $A$ contains no least finite-one degree. The proof is a finite-injury priority construction based on virtual target sets and a dynamic trap mechanism forcing any putative finite-one reduction either to violate finite-oneness or to compute an incorrect reduction.
1 0
0
math.LO 2026-04-13

Generalised perfect set forcing iterates along well-founded orders

Iterating Generalised Perfect Set Forcing Along Well-Founded Orders

Geometric iteration with ≤κ supports preserves cardinals up to κ⁺ when κ^{<κ}=κ.

abstract click to expand
Vladimir Kanovei \cite{zbMATH01335192} developed the technique of geometric iteration and used it to prove that the perfect set forcing can be iterated with countable supports along any partial order, while preserving $\aleph_1$. In \cite{Property-B} we considered a generalised perfect set forcing with respect to a filter on a cardinal $\kappa$ satisfying $\kappa^{<\kappa}=\kappa$, which we denoted ${\mathbb P} (\mathcal F)$, and proved that its iteration with supports of size $\le\kappa$ along any ordinal preserves cardinals up and including $\kappa^+$. We show that there is a version of the geometric iteration technique that applies to ${\mathbb P} (\mathcal F)$, to yield that for $\kappa$ satisfying $\kappa^{<\kappa}=\kappa$, the forcing ${\mathbb P} (\FF)$ can be iterated with supports of size $\le\kappa$ along any well-founded partial order, while preserving cardinals up and including $\kappa^+$.
0
0
math.LO 2026-04-13 Recognition

Iteration theorem keeps strong closure and stationary cc under <λ supports

A note on iterating strongly (<λ)-closed stationary λ^+-cc forcing

Exposition shows how to combine (<λ)-closed λ⁺-cc forcings with small supports while preserving both properties, and relates the result to

abstract click to expand
We give an exposition of an iteration theorem for iterating $(<\lambda)$-closed stationary $\lambda^+$-cc forcing with supports of size $<\lambda$ and preserving these two properties. We discuss the relation of this theorem with other iteration theorems and forcing axioms that have appeared in the literature, notably the one from \cite{Sh80}.
0
0
math.LO 2026-04-13

Almost free non-Archimedean Banach spaces are free under large cardinals

Almost Free Non-Archimedean Banach Spaces and Relation to Large Cardinals

Weak compactness or ℵ₁-strong compactness of the cardinality implies the space has an orthonormal Schauder basis, mirroring the Abelian case

abstract click to expand
Let $k$ be a complete valuation field. We formulate a free Banach $k$-vector space as a Banach $k$-vector space with an orthonormal Schauder basis, and an almost free Banach $k$-vector space as a non-Archimedean analogue of an almost free Abelian group. As non-Archimedean analogues of the classical facts that an almost free Abelian group is free under the assumption of the $\aleph_1$-strong compactness or the weak compactness of the cardinality, we show that an almost free Banach $k$-vector space is free under similar assumptions.
0
0
math.LO 2026-04-13

PA automorphism fixer groups have only meagre normal subgroups

The automorphism group of countable recursively saturated models of Peano arithmetic and strong cuts

Extending Lascar genericity to strong-cut fixers yields small index property, uncountable cofinality and no homomorphism onto Z.

abstract click to expand
In this paper, we extend the concept of a Lascar generic automorphism in the setting of models of Peano arithmetic ($\mathrm{PA}$) to the subgroup of the automorphism group of a countable recursively saturated model $\mathcal{M}$ of $\mathrm{PA}$ that fixes pointwise a strong cut $I$ of $\mathcal{M}$, denoted by $(\mathrm{Aut}(\mathcal{M}))_{(I)}$. Then, we prove that: (1) $(\mathrm{Aut}(\mathcal{M}))_{(I)}$ has the small index property. (2) The cofinality of $(\mathrm{Aut}(\mathcal{M}))_{(I)}$ is uncountable. (3) Any nontrivial normal subgroup of $(\mathrm{Aut}(\mathcal{M}))_{(I)}$ is meagre in it. In particular, the infinite cyclic group $\mathbb{Z}$ is not a homomorphic image of $(\mathrm{Aut}(\mathcal{M}))_{(I)}$.
0
0
math.LO 2026-04-13

Cohesive products describe infinite Galois groups of computable fields

On Cohesive Products of Fields

Hyper-automorphisms of these effective ultraproducts recover the classical Galois groups for a large class of extensions.

abstract click to expand
We develop the foundations of effective ultraproducts of fields and their Galois groups using the methods of computability theory. These computability-theoretic analogs of ultraproducts are called cohesive products, since the role of an ultrafilter is played by a cohesive set. A set of natural numbers is cohesive if it is infinite and cannot be partitioned into two infinite subsets by any computably enumerable set. In particular, we investigate the way cohesive products interact with field extensions with emphasis on both finite and infinite Galois extensions, and the associated Galois groups. We study the first-order theories and definability of cohesive powers of number fields, and characterize the infinite Galois groups of cohesive powers for a large class of infinite Galois extensions. Finally, we introduce hyper-automorphisms, which are automorphisms of a cohesive power that respect non-standard field operations, and give a complete description of the hyper-automorphism groups of cohesive powers of a large class of computable Galois extensions, and use them to describe the classical infinite Galois groups of such fields.
0

browse all of math.LO → full archive · search · sub-categories