Topic overview

math.LO

1661 works1796 researchers0 institutions

Topic snapshot

What this area looks like now

1661works

1796authors

0experts visible

0communities

Next steps

Move from topic reading into action

The graph preview below keeps the nearby papers, people and communities visible in the same reading flow.

Inspect nearby papers, researchers, institutions and communities without opening a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2024arXiv

The ZFC analogue of the Halpern-Levy theorem

Here we present ZFC theorems yielding the Halpern-L\a"uchli theorem and avoiding metamathematical notions in their formulations.

preprint2021arXiv

Extensions of definable local homomorphisms in o-minimal structures and semialgebraic groups

We state conditions for which a definable local homomorphism between two locally definable groups $\mathcal{G}$, $\mathcal{G^{\prime}}$ can be uniquely extended when $\mathcal{G}$ is simply connected (Theorem 2.1). As an application of this result we obtain an easy proof of [3, Thm. 9.1] (see Corollary 2.2). We also prove that Theorem 10.2 in [3] also holds for any definably connected definably compact semialgebraic group $G$ not necessarily abelian over a sufficiently saturated real closed field $R$; namely, that the o-minimal universal covering group $\widetilde{G}$ of $G$ is an open locally definable subgroup of $\widetilde{H\left(R\right)^{0}}$ for some $R$-algebraic group $H$ (Thm. 3.3). Finally, for an abelian definably connected semialgebraic group $G$ over $R$, we describe $\widetilde{G}$ as a locally definable extension of subgroups of the o-minimal universal covering groups of commutative $R$-algebraic groups (Theorem 3.4)

preprint2022arXiv

A note on infinite partitions of free products of Boolean algebras

If $A$ is an infinite Boolean algebra the cardinal invariant $\mathfrak{a}(A)$ is defined as the smallest size of an infinite partition of $A$. The cardinal $\mathfrak{a}(A\oplus B)$, where $A\oplus B$ is the free product of the Boolean algebras $A$ and $B$ (whose dual topological space is the product of the dual topological spaces of $A$ and $B$), is below both $\mathfrak{a}(A)$ and $\mathfrak{a}(B)$. The equality $\mathfrak{a}(A\oplus B)=\min\lbrace\mathfrak{a}(A),\mathfrak{a}(B)\rbrace$ is not known to hold for all infinite Boolean algebras $A$ and $B$. Here some lower bounds of $\mathfrak{a}(A\oplus B)$ are provided.

preprint2022arXiv

A Mathematician Reads the Kalam Cosmological Argument

Some Christian apologists, notably William Lane Craig, have championed something called the kalam cosmological argument for the existence of God. One version of the argument leans heavily on the claim that the existence of an actual infinite in the physical world is a metaphysical impossibility. We strongly criticize this claim, showing that it involves dogmatically insisting that certain metaphysical premises are absolutely inviolable, when in fact said premises are not only optional, but are far flimsier than other metaphysical claims (eventually shown to be untenable) that great thinkers of the past, including Einstein, have misguidedly clung to. While our criticisms strike most mathematicians and physicists as straightforward and uncontroversial, they have encountered resistance from philosophers, suggesting that there is a communication gap between the scientific and philosophical communities. We hope this paper will help bridge that gap.

preprint2023arXiv

Algebraic classifications for fragments of first-order logic and beyond

Complexity and decidability of logics is a major research area involving a huge range of different logical systems. This calls for a unified and systematic approach for the field. We introduce a research program based on an algebraic approach to complexity classifications of fragments of first-order logic (FO) and beyond. Our base system GRA, or general relation algebra, is equiexpressive with FO. It resembles cylindric algebra but employs a finite signature with only seven different operators. We provide a comprehensive classification of the decidability and complexity of the systems obtained by limiting the allowed sets of operators. We also give algebraic characterizations of the best known decidable fragments of FO. Furthermore, to move beyond FO, we introduce the notion of a generalized operator and briefly study related systems.

preprint2022arXiv

A Logic for Dually Hemimorphic Semi-Heyting Algebras and its Axiomatic Extensions

In this paper, we focus on the variety DHMSH of dually hemimorphic semi-Heyting algebras from a logical point of view. Firstly, we present a Hilbert-style axiomatization of a new logic called Dually hemimorphic semi-Heyting logic (DHMSH, for short), as an expansion of semi-intuitionistic logic SI (also called SH) introduced by the first author by adding a weak negation (to be interpreted as a dual hemimorphism). We then prove that it is implicative in the sense of Rasiowa and that it is complete with respect to the variety DHMSH. It is deduced that the logic DHMSH is algebraizable in the sense of Blok and Pigozzi, with the variety DHMSH as its equivalent algebraic semantics and that the lattice of axiomatic extensions of DHMSH is dually isomorphic to the lattice of subvarieties of DHMSH. A new axiomatization for Moisil's logic is also obtained. Secondly, we characterize the axiomatic extensions of DHMSH in which the Deduction Theorem holds. Thirdly, we present several new logics, extending the logic DHMSH, corresponding to several important subvarieties of the variety DHMSH. These include logics corresponding to the varieties generated by two-element, three-element and some four-element dually quasi-De Morgan semi-Heyting algebras, as well as a new axiomatization for the 3-valued Lukasiewiczlogic. Surprisingly, many of these logics turn out to be connexive logics, a few of which are presented in this paper. Fourthly, we present axiomatizations for two infinite sequences of logics namely, De Morgan-Goedel logics and dually pseudocomplemented Goedel logics, Fifthly, axiomatizations are also provided for logics corresponding to many subvarieties of regular dually quasi-De Morgan Stone semi-Heyting algebras, of regular De Morgan semi-Heyting algebras of level 1, and of JI-distributive semi-Heyting algebras of level 1. We conclude the paper with some open problems.

preprint2022arXiv

On the independence of Robinson's set of axioms for propositional calculus

We give a normal five-valued truth-table proving independence of one of the axioms in Robinson's set of axioms for propositional calculus from 1968, answering a question raised in his article, where he uses a non-normal truth-table. We also give a normal four-valued truth-table proving independence of one of the other axioms, where he uses a normal five-valued truth-table.

preprint2025arXiv

Simple Models of Randomization and Preservation Theorems

The main purpose of this paper is to present a new and more uniform model-theoretic/combinatorial proof of the theorem ([5]): The randomization $T^{R}$ of a complete first-order theory $T$ with $NIP$ is a (complete) first-order continuous theory with $NIP$. The proof method is based on the significant use of a particular type of models of $T^{R}$, namely simple models, certain indiscernible arrays, and Rademacher mean width. Using simple models of $T^R$ gives the advantage of re-proving this theorem in a simpler and quantitative manner. We finally turn our attention to $NSOP$ in randomization. We show that based on the definition of $NSOP$ given [13], $T^R$ is stable if and only if it is $NIP$ and $NSOP$.

preprint2022arXiv

Measures on perfect e-free PAC fields

We construct measures on definable sets in $e$-free perfect PAC fields, as well as on perfect PAC fields whose absolute Galois groups are free pro-$p$ of finite rank. We deduce the definable amenability of all groups definable in such fields. As a corollary, we additionally prove the definable amenability of all groups definable in perfect $ω$-free PAC fields via ultralimit measures.

preprint2024arXiv

Hensel minimality: Geometric criteria for $\ell$-h-minimality

Recently, Cluckers, Halupczok and Rideau-Kikuchi developed a new axiomatic framework for tame non-Archimedean geometry, called Hensel minimality. It was extended to mixed characteristic together with the author. Hensel minimality aims to mimic o-minimality in both strong consequences and wide applicability. In this article, we continue the study of Hensel minimality, in particular focusing on $ω$-h-minimality and $\ell$-h-minimality, for $\ell$ a positive integer. Our main results include an analytic criterion for $\ell$-h-minimality, preservation of $\ell$-h-minimality under coarsening of the valuation and $\ell$-dimensional dimensional geometry.

preprint2022arXiv

Model Theoretic Characterizations of Large Cardinals Revisited

In [Bon20], model theoretic characterizations of several established large cardinal notions were given. We continue this work, by establishing such characterizations for Woodin cardinals (and variants), various virtual large cardinals, and subtle cardinals.

preprint2022arXiv

Robinson consistency in many-sorted hybrid first-order logics

In this paper we prove a Robinson consistency theorem for a class of many-sorted hybrid logics as a consequence of an Omitting Types Theorem. An important corollary of this result is an interpolation theorem.

preprint2026arXiv

Towards an Inferentialist Account of Information Through Proof-theoretic Semantics

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.

preprint2022arXiv

Choice-free duality for orthocomplemented lattices by means of spectral spaces

The existing topological representation of an orthocomplemented lattice via the clopen orthoregular subsets of a Stone space depends upon Alexander's Subbase Theorem, which asserts that a topological space $X$ is compact if every subbasic open cover of $X$ admits of a finite subcover. This is an easy consequence of the Ultrafilter Theorem - whose proof depends upon Zorn's Lemma, which is well known to be equivalent to the Axiom of Choice. Within this work, we give a choice-free topological representation of orthocomplemented lattices by means of a special subclass of spectral spaces; choice-free in the sense that our representation avoids use of Alexander's Subbase Theorem, along with its associated nonconstructive choice principles. We then introduce a new subclass of spectral spaces which we call \emph{upper Vietoris orthospaces} in order to characterize (up to homeomorphism and isomorphism) the spectral space of proper lattice filters used in our representation. It is then shown how our constructions give rise to a choice-free dual equivalence of categories between the category of orthocomplemented lattices and the dual category of upper Vietoris orthospaces. Our duality combines Bezhanishvili and Holliday's choice-free spectral space approach to Stone duality for Boolean algebras with Goldblatt and Bimbó's choice-dependent orthospace approach to Stone duality for orthocomplemented lattices.

preprint2025arXiv

The fractal Goodstein principle

The original Goodstein process is based on writing numbers in hereditary $b$-exponential normal form: that is, each number $n$ is written in some base $b\geq 2$ as $n=b^ea+r$, with $e$ and $r$ iteratively being written in hereditary $b$-exponential normal form. We define a new process which generalises the original by writing expressions in terms of a hierarchy of bases $B$, instead of a single base $b$. In particular, the `digit' $a$ may itself be written with respect to a smaller base $b'$. We show that this new process always terminates, but termination is independent of Kripke-Platek set theory, or other theories of Bachmann-Howard strength.

preprint2025arXiv

On pre-local tabularity above $\mathrm{S4}\times \mathrm{S4}$

We investigate pre-local tabularity in normal extensions of the logic $\mathrm{S4}\times \mathrm{S4}$. We show that there are exactly four pre-locally tabular logics in normal extensions of products of finite height, and that every non-locally tabular logic in this family is contained in one of them. We also give an axiomatic criterion of local tabularity above the logic of products with Noetherian skeletons. Finally, we discuss examples of pre-locally tabular extensions of $\mathrm{S4}\times \mathrm{S4}$ outside this class, including logics with the converse and universal modalities.

preprint2025arXiv

Quasipolynomial behavior via constructibility in multigraded algebra

Piecewise quasipolynomial growth of Presburger counting functions combines with tame persistent homology module theory to conclude piecewise quasipolynomial behavior of constructible families of finely graded modules over constructible commutative semigroup rings. Functorial preservation of constructibility for families under local cohomology, $\operatorname{Tor}$, and $\operatorname{Ext}$ yield piecewise quasipolynomial, quasilinear, or quasiconstant growth statements for length of local cohomology, $a$-invariants, regularity, depth; length of $\operatorname{Tor}$ and Betti numbers; length of $\operatorname{Ext}$ and Bass numbers; associated primes via $v$-invariants; and extended degrees, including the usual degree, Hilbert-Samuel multiplicity, arithmetic degree, and homological degree.

preprint1992arXiv

Critical points in an algebra of elementary embeddings

Given two elementary embeddings from the collection of sets of rank less than $λ$ to itself, one can combine them to obtain another such embedding in two ways: by composition, and by applying one to (initial segments of) the other. Hence, a single such nontrivial embedding $j$ generates an algebra of embeddings via these two operations, which satisfies certain laws (for example, application distributes over both composition and application). Laver has shown, among other things, that this algebra is free on one generator with respect to these laws. The set of critical points of members of this algebra is the subject of this paper. This set contains the critical point $κ_0$ of $j$, as well as all of the other ordinals $κ_n$ in the critical sequence of $j$ (defined by $κ_{n+1} = j(κ_n)$). But the set includes many other ordinals as well. The main result of this paper is that the number of critical points below $κ_n$ (which has been shown to be finite by Laver and Steel) grows so quickly with $n$ that it dominates any primitive recursive function. In fact, it grows faster than the Ackermann function, and even faster than a slow iterate of the Ackermann function. Further results show that, even just below $κ_4$, one can find so many critical points that the number is only expressible using fast-growing hierarchies of iterated functions (six levels of iteration beyond exponentials).

preprint2000arXiv

Solutions to congruences using sets with the property of Baire

Hausdorff's paradoxical decomposition of a sphere with countably many points removed (the main precursor of the Banach-Tarski paradox) actually produced a partition of this set into three pieces A,B,C such that A is congruent to B (i.e., there is an isometry of the set which sends A to B), B is congruent to C, and A is congruent to (B union C). While refining the Banach-Tarski paradox, R. Robinson characterized the systems of congruences like this which could be realized by partitions of the sphere with rotations witnessing the congruences. The purpose of the present paper is to characterize those systems of congruences which can be satisfied by partitions of the sphere or related spaces (any complete metric space acted on in a sufficiently free way by a free group of homeomorphisms) into sets with the property of Baire. Dougherty and Foreman proved that the Banach-Tarski paradox can be achieved using such sets, and gave versions of this result using open sets and related results about partitions of spaces into congruent sets. The same methods are used here. We also characterize the systems solvable on the sphere using sets with the property of Baire but allowing all isometries (instead of just rotations).

preprint2022arXiv

Borel sets without perfectly many overlapping translations, II

For a countable ordinal epsilon we construct a Sigma^0_2 subset of the Cantor space for which one may force aleph_epsilon translations with intersections of size 2i, but such that it has no perfect set of such translations in any ccc extension. These sets have uncountably many translations with intersections of size 2i in ZFC, so this answers Problem 3.4 of arxiv:1711.04058 .

preprint2026arXiv

Every Feedforward Neural Network Definable in an o-Minimal Structure Has Finite Sample Complexity

We show that, in a precise sense, a broad class of feedforward neural networks learn (have finite sample complexity) in the PAC model: every fixed finite feedforward architecture whose layers are definable in an o-minimal structure has finite sample complexity in the agnostic PAC setting, even with unbounded parameters. This covers standard fixed-size MLPs, CNNs, GNNs, and transformers with fixed sequence length, together with the operations and layers typically used in such architectures, including linear projections, residual connections, attention mechanisms, pooling layers, normalization layers, and admissible positional encodings. Hence, distribution-free learnability for modern non-recurrent architectures is not an exceptional property of particular activations or architecture-specific VC arguments, but a consequence of tame feedforward computation. Our results reposition finite-sample PAC learnability as a baseline rather than a differentiator: they shift the focus of architectural comparison toward inductive biases, symmetries and geometric priors, scalability, and optimization behaviour.

preprint2023arXiv

Absolute integral closures of commutative rings

Absolute integral closures of general commutative unital rings are explored. All rings admit absolute integral closures, but in general they are not unique. Among the reduced rings with finitely many minimal prime ideals, finite products of domains are the only rings for which they are unique. Arguments using model theory suggest that the same holds for all infinite rings that are finite products of connected rings. Universal absolute integral closures, which contain every aic of a given ring, are shown to exist for certain subrings of products of domains.

preprint1996arXiv

On disjoint Borel uniformizations

Larman showed that any closed subset of the plane with uncountable vertical cross-sections has aleph_1 disjoint Borel uniformizing sets. Here we show that Larman's result is best possible: there exist closed sets with uncountable cross-sections which do not have more than aleph_1 disjoint Borel uniformizations, even if the continuum is much larger than aleph_1. This negatively answers some questions of Mauldin. The proof is based on a result of Stern, stating that certain Borel sets cannot be written as a small union of low-level Borel sets. The proof of the latter result uses Steel's method of forcing with tagged trees; a full presentation of this method, written in terms of Baire category rather than forcing, is given here.

preprint2024arXiv

Fundamental sequences and fast-growing hierarchies for the Bachmann-Howard ordinal

We prove that Buchholz's system of fundamental sequences for the $\vartheta$ function enjoys various regularity conditions, including the Bachmann property. We partially extend these results to variants of the $\vartheta$ function, including a version without addition for countable ordinals. We conclude that the Hardy functions based on these notation systems enjoy natural monotonicity properties and majorize all functions defined by primitive recursion along $\vartheta(\varepsilon_{Ω+1})$.