Mathematics - Logic and Mathematics - Category Theory

Abstract

The aim of this paper is to relate the classical result of Gabriel-Ulmer to the geometry of topoi. The usage of the attribute 'left exact' when dealing with functors involved in this duality is indeed not casual and it is related to the geometrical side of the story, i.e. topos theory, as in \cite{SGA}. Thought to be a very basic introduction to the subject, it is mostly self-contained. The reader is assumed to be familiar with the fundamentals of category theory, no further prerequisite knowledge is required. The proof of Gabriel-Ulmer duality follows \cite{MP}.

Mathematics - Logic, Computer Science - Logic in Computer Science, and 03C90 (Primary) 03B52 (Secondary)

Abstract

We explore a kind of first-order predicate logic with intended semantics in the reals. Compared to other approaches in the literature, we work predominantly in the multiplicative reals [0,\infty], showing they support three generations of connectives, that we call non-linear, linear additive, and linear multiplicative. Means and harmonic means emerge as natural candidates for bounded existential and universal quantifiers, and in fact we see they behave as expected in relation to the other logical connectives. We explain this fact through the well-known fact that min/max and arithmetic mean/harmonic mean sit at opposite ends of a spectrum, that of p-means. We give syntax and semantics for this quantitative predicate logic, and as example applications, we show how softmax is the quantitative semantics of argmax, and R\'enyi entropy/Hill numbers are additive/multiplicative semantics of the same formula. Indeed, the additive reals also fit into the story by exploiting the Napierian duality -log \dashv 1/exp, which highlights a formal distinction between 'additive' and 'multiplicative' quantities. Finally, we describe two attempts at a categorical semantics via enriched hyperdoctrines. We discuss why hyperdoctrines are in fact probably inadequate for this kind of logic. Comment: (21 pages, 1 figure, 2 tables)

Mathematics - Logic and 03C15, 37B05, 20B27, 05C55, 05D10

Abstract

We consider the topological dynamics of the automorphism group of a particular sparse graph M_1 resulting from an ab initio Hrushovski construction. We show that minimal subflows of the flow of linear orders on M_1 have all orbits meagre, partially answering a question of Tsankov regarding results of Evans, Hubicka and Nesetril on the topological dynamics of automorphism groups of sparse graphs. Comment: 17 pages

Mathematics - Logic, Mathematics - Metric Geometry, and 03E50, 51N20

Abstract

For all \( d \geq 3 \) we show that the cardinality of \( \mathbb{R} \) is at most \( \aleph_n \) if and only if \( \R^d \) can be covered with \( ( n + 1 ) ( d - 1 ) + 1 \) sprays whose centers are in general position in a hyperplane. This extends previous results by Schmerl when \( d = 2 \). Comment: 31 pages

We introduce a new definition of a model for a formal mathematical system. The definition is based upon the substitution in the formal systems, which allows a purely algebraic approach to model theory. This is very suitable for applications due to a general syntax used in the formal systems. For our models we present a new proof of the downward L\"owenheim-Skolem Theorem for elementary submodels. Comment: 28 pages

Mathematics - Logic and 03F03, 03F15, 03F35, 03E10

Abstract

The current ordinal analysis provides the proof-theoretic ordinal of a theory, which calibrates the robustness of the $\Pi^1_1$-consequences of the theory. We can ask whether there is an ordinal characteristic capturing more complex consequences, and it turns out that we can define the $\Sigma^1_2$-proof-theoretic ordinal capturing the robustness of the $\Sigma^1_2$-consequences of a theory. In this paper, we study the behavior of $\Sigma^1_2$-proof-theoretic ordinal, and it turns out that $\Sigma^1_2$-proof-theoretic ordinal also follows an analogue of Walsh's characterization of proof-theoretic ordinal. Comment: 32 pages

Mathematics - Logic and Mathematics - General Topology

Abstract

In this Phd. thesis, a structural analysis of construction schemes is developed. The importance of this study will be justified by constructing several distinct combinatorial objects which have been of great interest in mathematics. We then continue the study of capturing axioms associated to construction schemes. From them, we construct several uncountable structures whose existence is known to be independent from the usual axioms of Set Theory. Comment: 181 pages. This is the author's Phd. thesis, submitted under the supervision of Osvaldo Guzman and Michael Hrusak

Mathematics - General Topology, Mathematics - Logic, and 03A35 54D35

Abstract

We show that it is consistent to have regular closed non-clopen copies of $\mathbb N^*$ within $\mathbb N^*$ and a non-trivial self-map of $\mathbb N^*$ even if all autohomeomorphisms of $\mathbb N^*$ are trivial.

Mathematics - Logic and Computer Science - Logic in Computer Science

Abstract

We develop a method to recognize admissibility of $\Pi_{2}$-rules, relating this problem to a specific instance of the unification problem with linear constants restriction, called here "unification with simple variable restriction". It is shown that for logical systems enjoying an appropriate algebraic semantics and a finite approximation of left uniform interpolation, this unification with simple variable restriction can be reduced to standard unification. As a corollary, we obtain the decidability of admissibility of $\Pi_{2}$-rules for many logical systems. Comment: 22 pages, Accepted at AIML 2024

We revisit the duality between Kripke and algebraic semantics of intuitionistic and intuitionistic modal logic. We find that there is a certain mismatch between the two semantics, which means that not all algebraic models can be embedded into a Kripke model. This leads to an alternative proposal for a relational semantics, the stable semantics. Instead of an arbitrary partial order, the stable semantics requires a distributive lattice of worlds. We constructively show that the stable semantics is exactly as complete as the algebraic semantics. Categorifying these results leads to a 2-duality between two-dimensional stable semantics and categories of product-preserving presheaves, i.e. models of algebraic theories in the style of Lawvere. Comment: Accepted at MFPS 2024

Jaakkola, Reijo, Kuusisto, Antti, and Vilander, Miikka

Subjects

Mathematics - Logic, Computer Science - Logic in Computer Science, 03C13 (Primary) 68R01, 94A17, 68Q30 (Secondary), F.4.1, G.2.0, and E.4

Abstract

The description complexity of a model is the length of the shortest formula that defines the model. We study the description complexity of unary structures in first-order logic FO, also drawing links to semantic complexity in the form of entropy. The class of unary structures provides a simple way to represent tabular Boolean data sets as relational structures. We define structures with FO-formulas that are strictly linear in the size of the model as opposed to using the naive quadratic ones, and we use arguments based on formula size games to obtain related lower bounds for description complexity. We also obtain a precise asymptotic result on the expected description complexity of a randomly selected structure. We then give bounds on the relationship between Shannon entropy and description complexity. We extend this relationship also to Boltzmann entropy by establishing an asymptotic match between the two entropies. Despite the simplicity of unary structures, our arguments require the use of formula size games, Stirling's approximation and Chernoff bounds.

Mathematics - Logic, Mathematics - Combinatorics, and 05C55, 18D25

Abstract

One of the consequences of the Compactness Principle in structural Ramsey theory is that the small Ramsey degrees cannot exceed the corresponding big Ramsey degrees, thereby justifying the choice of adjectives. However, it is unclear what happens in the realm of dual Ramsey degrees due to the lack of the compactness argument that applies to that setting. In this paper we present a framework within which both ``direct'' and dual Ramsey statements can be stated and reasoned about in a uniform fashion. We introduce the notion of approximability which yields a general compactness argument powerful enough to prove statements about both ``direct'' and dual Ramsey phenomena. We conclude the paper with an application of the new strategies by generalizing Voigt's $\star$-version of the Infinite Ramsey Theorem to a large class of relational structures and deriving a Ramsey statement for ``loose colorings'' of enumerated Fra\"{\i}ss\'{e} limits.

Mathematics - Logic, Mathematics - Commutative Algebra, Mathematics - Category Theory, and Mathematics - Rings and Algebras

Abstract

We clarify some results of Bagaria and Magidor \cite{MR3152715} about the relationship between large cardinals and torsion classes of abelian groups, and prove that (1) the Maximum Deconstructibility principle introduced in \cite{Cox_MaxDecon} requires large cardinals; it sits, implication-wise, between Vop\v{e}nka's Principle and the existence of an $\omega_1$-strongly compact cardinal. (2) While deconstructibility of a class of modules always implies the precovering property by \cite{MR2822215}, the concepts are (consistently) non-equivalent, even for classes of abelian groups closed under extensions, homomorphic images, and colimits.

Mathematics - Combinatorics, Mathematics - Logic, and 03E15

Abstract

We prove that for any generating set $S$ of $\Gamma=\mathbb {Z}^n$, the continuous edge chromatic number of the Schreier graph of the Bernoulli shift action $G=F(S,2^\Gamma)$ is $\chi'_c(G)=\chi'(G)+1$. In particular, for the standard generating set, the continuous edge chromatic number of $F(2^{\mathbb {Z}^n})$ is $2n+1$.

The notion of an existentially closed model is generalised to a property of geometric morphisms between toposes. We show that important properties of existentially closed models extend to existentially closed geometric morphisms, such as the fact that every model admits a homomorphism to an existentially closed one. Other properties do not generalise: classically, there are two equivalent definitions of an existentially closed model, but this equivalence breaks down for the generalised notion. We study the interaction of these two conditions on the topos-theoretic level, and characterise the classifying topos of the e.c. geometric morphisms when the conditions coincide. Comment: 30 pages

Let $\lambda$ be a limit of Woodin cardinals. It was shown by the second author that the pointclass of ${<\lambda}$-homogeneously Suslin sets has the scale property. We give a new proof of this fact, which avoids the use of stationary tower forcing. Comment: 11 pages

This paper presents an expository reverse-mathematical analysis of two fundamental theorems in commutative algebra: Hilbert's Nullstellensatz and Basis Theorem. In addition to its profound significance in commutative algebra and algebraic geometry, the Basis Theorem is also historically notable for its nonconstructive proof. The Nullstellensatz, on the other hand, is noteworthy as it establishes a fundamental connection between the more algebraic notion of ideals and the more geometric notion of varieties. We explore the conscious shift from computational to conceptual approaches in mathematical argumentation, contextualizing Hilbert's contributions. We formalize the relative constructivity of these theorems using the framework of reverse mathematics, although we do not presuppose familiarity with reverse mathematics. Drawing from contemporary mathematical literature, we analyze the Basis Theorem's reliance on nonconstructive methods versus the more constructive nature of the Nullstellensatz. Our study employs the standard tools of reverse mathematics, in particular subsystems of second-order arithmetic, to outline the minimal set-existence axioms required for these theorems. We review results showing that certain formulations of the Nullstellensatz are provable in the weak axiom system of $\mathsf{RCA}_0$, while the Basis Theorem requires stronger axioms, such as $\Sigma^0_2$-Induction. Consequently, we position these theorems separately within the Friedman-Simpson hierarchy. This analysis contributes to a deeper understanding of the foundational requirements for these pivotal results in algebra. Comment: 35 pages, 2 figures

Mathematics - Logic and Mathematics - General Topology

Abstract

We introduce a new way of encoding general topology in second order arithmetic that we call hybrid maximal filter (hybrid MF) spaces. This notion is a modification of the notion of a proper MF space introduced by Montalb\'an. We justify the shift by showing that proper MF spaces are not able to code most topological spaces, while hybrid MF spaces can code any second countable MF space. We then answer Montalb\'an's question about metrization of well-behaved MF spaces to this shifted context. To be specific, we show that in stark contrast to the original MF formalization used by Mummert and Simpson, the metrization theorem can be proven for hybrid MF spaces within $\text{ACA}_0$ instead of needing $\Pi_2^1-\text{CA}_0$. Comment: 12 Pages

Gonzalez, David, Harrison-Trainor, Matthew, and Ho, Meng-Che "Turbo"

Subjects

Mathematics - Logic

Abstract

For any limit ordinal $\lambda$, we construct a linear order $L_\lambda$ whose Scott complexity is $\Sigma_{\lambda+1}$. This completes the classification of the possible Scott sentence complexities of linear orderings. Previously, there was only one known construction of any structure (of any signature) with Scott complexity $\Sigma_{\lambda+1}$, and our construction gives new examples, e.g., rigid structures, of this complexity. Moreover, we can construct the linear orders $L_\lambda$ so that not only does $L_\lambda$ have Scott complexity $\Sigma_{\lambda+1}$, but there are continuum-many structures $M \equiv_\lambda L_\lambda$ and all such structures also have Scott complexity $\Sigma_{\lambda+1}$. In contrast, we demonstrate that there is no structure (of any signature) with Scott complexity $\Pi_{\lambda+1}$ that is only $\lambda$-equivalent to structures with Scott complexity $\Pi_{\lambda+1}$. Our construction is based on functions $f \colon \mathbb{Z}\to \mathbb{N}\cup \{\infty\}$ which are almost periodic but not periodic, such as those arising from shifts of the $p$-adic valuations. Comment: 15 pages