GALAI Seminar
General Algebra, Logic and Artificial Intelligence Seminar
The seminar is typically held every Wednesday afternoon 2:15-3:15 pm (Pacific time UTC-7 in northern summer) in Keck 370.
A zoom link is available: https://chapman.zoom.us/j/96264248877
Spring 2025
February 12, 2025, Time TBA: Charlotte Aten (University of Colorado at Boulder)
Fall 2024
November 6, 2024, 2:15pm: Miles Milosevic (Chapman University) Circuit Discovery in Large Language Models
Abstract: Mechanistic interpretability of neural networks aims at the discovery of interpretable subgroups of model weights, or circuits. Well-known examples include both low-level and high-level features in images. We will review recent progress in the automated discovery of circuits in LLMs. Our aim is to then explore potential applications of this technology to mathematics. For example, can theorems and lemmas from Lean's Mathlib be transcribed into RASP (a programming language mapped to components of a Transformer), enabling automatic circuit discovery for these building blocks? Could modularity of circuits lead to proofs represented entirely within Transformer activations, increasing LLM accuracy in proof generation? What implications would this have for automated formalization and automated theorem building?
colab.research.google.com/drive/19ecdH70YduhGJulQ-1uiXuivAmN672Pq?usp=sharing#scrollTo=VUgn_2xCUFbT
October 30, 2024, 2:15pm: José Gil-Férez (Chapman University) Jónsson’s Lemma for Partially-Ordered Varieties
Abstract: One of the main features of non-classical logics is the fact that their algebraic semantics may contain more than just two truth values (true/false). And very often, these truth values are ordered in one way or another and the fundamental operations respect or reverse this order. Sometimes, this order is definable in terms of the algebraic operations, and thus the study of such partially ordered algebras (po-algebras) falls into the realm of Universal Algebra. But, when the order is not term-definable, the tools and techniques of Universal Algebra may prove insufficient. For that reason, D. Pigozzi initiated the study of a genuine theory of po-algebras. He proved several results that show that the universal theory of po-algebras runs in parallel to classical Universal Algebra. In this talk, we continue this development, showing that Jónsson’s Lemma—one of the most celebrated results of Universal Algebra—also holds, mutatis mutandis, for partially-ordered varieties.
October 16, 2024, 2:15pm: Chun-Yu Lin (Institute of Computer Science, Czech Academy of Sciences) Nonclassical Polyadic Algebra: Soft and Hard
Abstract : In this talk, I will characterize the polyadic algebra arising from algebraic implicative predicate logic, and prove a functional representation theorem. Then the connection between non-classical polyadic algebra and cylindric algebra will be discussed.
October 9, 2024, 2:15pm: Marta Bilkova (Institute of Computer Science, Czech Academy of Sciences) Belnapian logics for uncertainty
Abstract: Reasoning about information, its potential incompleteness, uncertainty, and contradictoriness need to be dealt with adequately. To reason with conflicting information, positive and negative support---evidence in favour and evidence against---a statement can be quantified separately in the semantics. This two-dimensionality gives rise to logics interpreted over twist-product algebras or bi-lattices, the well known Belnap-Dunn logic of First Degree Entailment being a prominent example. Belnap-Dunn logic with its bilateral semantics can in turn be taken as a base logic for defining various uncertainty measures on de Morgan algebras, e.g. Belnapian (non-standard) probabilities or belief functions.
In this talk, we first show how to expand Łukasiewicz or Gödel many-valued logics with a de Morgan negation and interpret the resulting logics over twist-product algebras based on the [0,1] real interval, which can account for the two-dimensionality of positive and negative component of (the degree of) belief or likelihood based on potentially contradictory information, quantified by an uncertainty measure. The resulting logics inherit both (finite) standard completeness, decidability and complexity properties from the original logic in question, and allow for an efficient reasoning using the constraint tableaux calculi formalism. Second, we utilise the apparatus of two-layered modal logics: Many-valued logics with a two-dimensional semantics mentioned above are used on the outer layer to reason about Belnapian probability measure or a belief function, building on Belnap-Dunn logic as an inner logic of the underlying evidence.
- Reasoning with belief functions over Belnap--Dunn logic, MB, S. Frittella, D. Kozhemiachenko, O. Majer, and S. Nazari, Annals of Pure and Applied Logic, 2023. https://arxiv.org/abs/2203.01060
- Two-layered logics for probabilities and belief functions over Belnap--Dunn logic, MB, S. Frittella, D. Kozhemiachenko, O. Majer, submitted. https://arxiv.org/abs/2402.12953
October 2, 2024, 2:15pm: Informal discussion about adding the information on the MathStructures pages to Wikidata
September 25, 2024, 2:15pm: Juliana Bueno-Soler (FT and Centre for Logic, University of Campinas - UNICAMP, Brazil) Non-standard probabilities based on paraconsistent logics
Abstract: In this talk I explain the main ideas of our project on non-standard probabilities based on paraconsistent logics. I will focus on discussing the differences of approach depending on different logic systems, and finally I suggest some examples of applications.
References
[1] A. Rodrigues and J. Bueno-Soler and W. Carnielli. Measuring evidence: a probabilistic approach to an extension of Belnap-Dunn logic. Synthese 2021. https://doi.org/10.1007/s11229-020-02571-w
[2] W. Carnielli and J. Bueno-Soler. Paraconsistent probabilities, their significance and their uses. In C. Caleiro and F. Dionisio and P. Gouveia and P. Mateus and J. Rasga (eds). Essays in Honour of Amilcar Sernadas. College Publications, 2017.
[3] J. Bueno-Soler and W. Carnielli. Paraconsistent Probabilities: Consistency, Contradictions and Bayes' Theorem. Entropy, 2016. https://doi.org/10.3390/e18090325
September 18, 2024, 2:15pm: Peter Jipsen (Chapman University) Some thoughts about universal algebra in dependent type theories
Abstract: Universal algebra is traditionally positioned within set theory and first-order logic, although many of the main results are formulated in higher-order logic and some results have been extended and generalized to category theory in the form of Lawvere theories, monads and (categorical formulations of) algebraic theories. Recent efforts to formalize mathematics in interactive theorem prover libraries are mostly based on (various) dependent type theories, so it is natural to compare how the mathematical libraries of Agda, Lean, Rocq and Rzk aim to capture the unifying insights of universal algebra. In this informal talk I will survey some of the ideas and design decisions that are part of this landscape.
September 4, 2024, 2:15pm: Internal discussion about grant applications
August 28, 2024, 2:00pm: Organizational meeting to discuss speakers for this semester
Spring 2024
May 24, 2024, 2:00pm: Adam Přenosil (University of Barcelona) Hölder's theorem for totally ordered monoids
Abstract: The theory of residuated lattices was developed to uniformly treat the common features of a number of key motivating examples, two of the most prominent ones being the varieties of Heyting algebras and of lattice-ordered groups (l-groups). One fruitful perspective on residuated lattices is to place l-groups at its center and to think of other varieties of residuated lattices as obtained from l-groups by applying two simple constructions, namely so-called nuclear and conuclear images.
A variety of residuated lattices which still preserves much group-like behavior is the variety of GMV-algebras, which subsumes both l-groups and MV-algebras. This makes the variety a reasonable target for extending classical results about l-groups. In particular, Ledda, Paoli and Tsinakis have successfully extended Hölder's theorem, one of the early classical results about ordered groups, to GMV-algebras. The original theorem describes the totally ordered groups which embed into the ordered additive group of reals as precisely the ones which enjoy the Archimedean property (informally, no positive quantity is infinitely smaller than another). The extension similarly describes the GMV-algebras embeddable as residuated lattices into either the reals, the negative reals, or the standard MV-chain [0, 1].
In this talk I will review the above line of research and aim for an extension of Hölder's theorem to lattice- and semilattice-ordered monoids. Somewhat surprisingly, the appropriate substitute for the Archimedean property is the property that every congruence arises from an ideal. In particular, I will confirm a conjecture of Peter Jipsen and Luca Spada (where this key property was first identified) that the finite semilattice-ordered monoids with a zero which satisfy this property are exactly the reducts of finite MV-algebras in this signature.
May 8, 2024, 8:30am-4:30pm: Topos Institute / Chapman University Workshop (YouTube playlist)
May 1, 2024, 4pm: Melissa Sugimoto (Chapman University) Decompositions and glueings of locally integral involutive residuated structures (video)
Abstract: The study of integrality in residuated structures plays an important role in algebraic logic since residuated lattices are the algebraic semantics of substructural logics, and integrality (x ≤ 1) is equivalent to the proof-theoretical rule called weakening.
An involutive partially-ordered semigroup (ipo-semigroup) consists of a partial order, an associative binary operation, and a pair of order-reversing involutions, – and ∼ that satisfy double negation (∼ – x = x = – ∼ x) and residuation. If the semigroup has an identity, we refer to the structure as an ipo-monoid.
In this talk, we investigate the class of locally integral ipo-semigroups, in which the elements of the form x/x act locally as identities ((x/x)∙x = x). We show that every locally integral ipo-semigroup decomposes uniquely into a Płonka sum over a semilattice directed system of integral ipo-monoids. We also solve the reverse problem by providing necessary and sufficient conditions so that the glueing of a system of integral ipo-monoids becomes an ipo-semigroup. Finally, generalizing the work of Jipsen, Tuyt, and Valota (2021), we provide a construction by which a glueing of locally integral lattice-ordered monoids will also be lattice-ordered.
April 24, 2024, 4pm: Wessley Fussner (Institute of Computer Science, Czech Academy of Sciences) Interpolation in Substructural Logics: What We Know and What We'd Like to Know (video)
Abstract: "Interpolation" refers to a cluster of metalogical properties, intuitively corresponding to a range of different ways that the validity of given inferences in a logic may be explained in the object language. While interpolation has been studied quite thoroughly in different logical contexts, until recently there has been little in the way of a coherent picture. The deep connection between interpolation and various amalgamation properties (given in suitable categories of model structures) provides a route to developing a more systematic understanding. This talk surveys recent progress under this research program, with applications drawn from various substructural logics (including fuzzy, relevant, intuitionistic, and linear logics) as well as their modal extensions.
April 17, 2024, 4pm: Giovanni Sambin (Università di Padova), Dynamic constructivism and positive topology. An evolutionary vision of mathematics and its practice
Abstract: If one really believes that mathematics is a human construction, the result of a dynamic-evolutionary process, then it can be seen as a conquered and local truth, which means certain and reliable information, and not as a given and universal truth. It becomes crucial to avoid principles such as the Law of the Excluded Middle, the Power Set Axiom and the Axiom of Choice, which destroy the informational difference between 'exists' and 'not-forall-not', inductively generated domains and not, operations and functions. The resulting foundation does not suffer from the problems of the past.
This talk gives an overview of what mathematics, in particular topology, has been developed on this 'weak' foundation. Most importantly, it illustrates the vast new areas of mathematical thought that emerge, in particular the co-presence and connection between real-effective and ideal-infinitary aspects.
The challenge now is to show that this could lead to a new Kuhnian paradigm in mathematics, a prospect that clearly points to much future work.
April 10, 2024, 4pm: Drew Moshier (Chapman University), Yet Another Duality Theorem for Partially Ordered Sets
Abstract: We know the category Pos of partially ordered sets (posets) and monotonic functions is dually equivalent to the category Stone(DL) of Stone distributive lattices and continuous lattice homomorphisms. Likewise, Stone(DL) is equivalent to the category of completely distributive lattices and complete lattice homomorphisms
We present an apparently novel duality for Pos that arises from considering the category Pos*, of posets (or equivalently, Qos* of preordered sets) and weakening relations. In Pos* (or Qos*), we define a monad D — the “downset” monad, and show that (a) every poset is equipped uniquely with a D-algebra, (b), there are no other D-algebras, and (c) the D-algebra morphisms are precisely dual to monotonic functions between the carriers of these algebras. Thus Pos is dually equivalent to the category of D-algebras on Pos*.
April 3, 2024, 4pm: Valeria Giustarini, joint work with Sara Ugolini (Artificial Intelligence Research Institute (IIIA), CSIC, Barcelona, Spain), Structure theory and amalgamation failures in integral residuated chains (video)
Abstract: Residuated structures play an important role in the field of algebraic logic since they constitute the equivalent algebraic semantics, in the sense of Blok and Pigozzi, of substructural logics. The algebraic investigation of residuated lattices is a powerful tool in the systematic and comparative study of such logics. Thus, the development of constructions that allow one to obtain new structures from known ones is of utter importance for the understanding of both residuated lattices and substructural logics.
One of the most well known construction that allows one to get a new algebra starting from two known ones is the ordinal sum construction. Intuitively, we stack one algebra on top of the other gluing the top element. This construction preserves both products and divisions of the initial algebras. This is the main difference with the gluing construction introduced by Galatos and Ugolini, where the products are preserved but some of the divisions are redefined. In this work, we propose two possible iterations of this construction, which allows us to understand how some residuated chains can be decomposed and how their different parts interact. Moreover, we provide an axiomatization for the varieties generated by n-potent, archimedean chains that can be constructed via such iterated partial gluing.
Algebraic constructions of this kind are also important for the study of logical properties of the associated substructural logics. One of the most well-known bridge theorems is the connection between the amalgamation property in a variety of algebras and the Robinson property, or in some relevant cases the deductive interpolation property, of the corresponding logic.
In this work we focus on the study of amalgamation in classes of totally ordered residuated lattices, solving some open problems: most importantly, we establish that semilinear commutative (integral) residuated lattices and their pointed versions do not have the amalgamation property.
March 29, 2024, 3pm: Gavin St. John (University of Salerno, Italy), An algebraic study of irigs
Abstract: A special class of semirings, often referred to as rigs, are those semirings R=(R,+,*,0,1) where both operations are commutative, where multiplication distributes over addition, and in which 0 is multiplicatively absorbing; the name coming from the pun "ring" to "rng" (ring without Identity), where a "rig" is a "ring" without iNverses. As they encompass (commutative) rings (by taking the appropriate fragment), rigs are pervasive structures in mathematics, finding applications in fields as diverse as algebraic geometry, computer science, and mathematical logic.
Of special importance are the classes of additively-idempotent rigs and integral rigs (i.e., satisfying 1+x=x), often referred to as 2-rigs and irigs, respectively, both of which define varieties of algebras and, moreover, the former subsuming the latter. Since addition is idempotent in these structures, the additive fragment is a semilattice inducing a partial order in which 0 is the least element, and in the case of irigs, also has 1 as largest element. While the names "2-rigs" and "irigs" originate from algebraic-geometric considerations, they also constitute the {v,*,1,0}-fragments of (commutative) residuated structures, namely FLe and FLew-algebras, respectively. In particular, bounded distributive lattices are exactly those irigs in which multiplication is (also) idempotent.
While the literature of semirings is vast, due to their diverse application, a serious study of basic universal algebraic properties, specifically for 2-rigs and irigs, seems to be lacking. This talk will therefore be concerned with exactly this. We will investigate subdirectly irreducibles, free algebras, the finite model property, etc. This talk is ongoing and joint work with Peter Jipsen and Luca Spada.
March 13, 2024, 4 pm: Sara Ugolini (IIIA, CSIC, Barcelona, Spain), Gluings of integral residuated lattices
Abstract: Residuated structures play an important role in the field of algebraic logic since they constitute the equivalent algebraic semantics of a large class of logics, including classical logic and many of the most well-known systems of nonclassical logics, e.g. intuitionistic logic, intermediate logics, fuzzy logics, relevance logics and more. While many deep results have been obtained in the last decades, at the present moment large classes of residuated lattices lack a structural description; because of this, we are interested in constructions that allow one to obtain new structures from known ones. We start this talk by discussing a well-understood construction, the ordinal sum (also called 1-sum), that glues together two integral residuated lattices intersecting at their top; this construction has been successfully used to represent totally-ordered divisible integral residuated lattices. We will discuss the relevance and the limits of the ordinal sum with respect to the description of (non-divisible) integral chains, and show that if divisibility is dropped altogether, one cannot obtain the same kind of results. We will then explore two directions: on the one hand, we introduce a hierarchy of (non-divisible) varieties that can be effectively described by ordinal sums, and on the other hand, we generalize the ordinal sum construction by allowing one to glue residuated structures that intersect at a deductive filter. This is joint work with Nick Galatos.
March 6, 2024, 4 pm: Stefano Bonzio (University of Cagliari, Italy), Regularized varieties and Płonka sums of algebras
Abstract: A variety of algebras is called regular when it does satisfy regular identities only, where an identity σ ≈ τ (in a fixed algebraic language) is regular provided that exactly the same variables actually occur in both the terms σ and τ. Examples of regular varieties include semigroups, (commutative) monoids and semilattices. A variety is irregular if it is not regular. In particular, a variety V is strongly irregular if it possesses a term-definable (binary) operation f(x,y) such that V satisfies f(x,y) ≈ x, i.e. the operation f behaves in V as a projection in the first component. Strongly irregular varieties are very common, as they include, for instance, groups, rings and any variety having a lattice (or group) reduct.
Given a variety V, one can consider its regularization R(V), namely the variety satisfying only the regular identities holding in V. In case V is strongly irregular, then the elements of R(V) admit a well-behaved structure theory: any algebra in R(V) can be represented as a Płonka sum over a semilattice direct system of algebras in V, a construction introduced by the Polish algebraist J. Płonka.
After formally introducing the construction of the Płonka sum, in this seminar, I will provide the details of the Płonka representation theorem for regularized varieties and show some of its applications, such as the description of the lattice of the subvarieties of R(V), of the subdirectly irreducible members in R(V) and of the equational basis (for R(V) from V, and vice versa). Finally, I will briefly explain how the theory of Płonka sums has been applied in algebraic logic.
1st GALAI Workshop, Friday, Jan 26, 2024
Invited Speakers: Alexandru Baltag (University of Amsterdam), Caleb Schultz Kisby (Indiana University Bloomington), Sonja Smets (University of Amsterdam).
1000-1045: Drew Moshier: Relations in Point-Free Topology
1100-1145: Peter Jipsen: Using Prover9/Mace4 to Investigate Kripke Frames of Distributive Quasi Relation Algebras
1145-1345: Break
1345-1430: Jose Gil-Ferez: A Formal Deductive System for Euclid's Elements (Book I)
1500-1545: Alexander Kurz: The Blacktriangle Calculus
1600-1645: Caleb Schultz Kisby: Logical Dynamics of Neural Network Learning
1700-1745: Alexandru Baltag: The Topology of Surprise
1800-1845: Sonja Smets: Logic and Computation of Social Behaviour
Past seminars:
Jan 17, 2024, 4pm: Bernardus Wessels (University of Stellenbosch, South Africa), On the posets of connected elements in a locally connected frame
Abstract: In pointfree topology, one abstracts the poset of open subsets of a topological space, by replacing it with a frame (a complete lattice, where finite meet distributes over arbitrary joins). In this talk, we propose an analogous abstraction of the poset of connected subsets of a topological space. To motivate this abstraction, we use it to characterise posets of connected elements in a locally connected frame, and establish the intuition underlying the proof of this result.
Fall 2023
Nov 29, 2023, 4pm: Nick Galatos (University of Denver), Lattice-ordered groups and pregroups (video)
Abstract: Lattice-ordered groups are well-studied structures in ordered algebra and they enjoy a Cayley-style representation theorem, which can be used to show that their variety is generated by the order-permutations on the reals and that their equational theory is decidable. Lattice-ordered pregroups are generalizations with two 'inverses' (left and right) and they stem from the study of mathematical linguistics. Distributive lattice-ordered pregroups (DLpG) also enjoy an embedding theorem into functional algebras F(C) on chains C. We improve on this representation by showing that it is enough to consider integral chains: lexicographic products of the integers, and use it to show that the variety of DLpGs is generated by F(Z) and that it has a decidable equational theory. Time permitting, we also discuss the subvarieties of n-periodic DLpGs, for different naturals n (lattice-ordered groups are exactly the 1-periodic ones) and obtain a generation result for each of them, as well. The decidability of the equational theory is much harder for the periodic case and we obtain it by controlling the size of the associated diagram (a finitary object encapsulating the failure of an equation).
Oct 25, 2023, 4pm: Discussion
Oct 18, 2023, 4pm: Søren Brinck Knudstorp (University of Amsterdam, Netherlands), Modal Information Logics: Axiomatizations and Decidability
Abstract: In this talk, I will be presenting results from my Master of Logic thesis “Modal Information Logics”, supervised by Johan van Benthem and Nick Bezhanishvili.
The thesis studies formal properties of a family of so-called modal information logics (MILs)—modal logics first proposed in van Benthem (1996) as a way of using possible-worlds semantics to model a theory of information. They do so by extending the language of propositional logic with a binary modality defined in terms of being the supremum of two states.
Although MILs have been around for some time, not much is known: van Benthem (2017, 2019) pose two problems, namely (1) axiomatizing the two basic MILs of suprema on preorders and posets, respectively, and (2) proving (un)decidability.
The main results of the first part of the talk are solving these two problems: (1) by providing an axiomatization [with a completeness proof entailing the two logics to be the same], and (2) by proving decidability. These results are then build upon to axiomatize and prove decidable the MILs attained by endowing the language with an ‘informational implication’—in doing so a link is also made to the work of Buszkowski (2021) on the Lambek Calculus.
Broadening the study, the basic MIL of suprema on join-semilattices is axiomatized with an infinite scheme. This constitutes the by far most substantive part of the thesis, hence we will only be lending an informal focus to accenting key ideas.
Finally, if time allows, we will comment on the connection between truthmaker semantics and MILs and extend the (compactness and) decidability results in Fine and Jago (2019), chiefly via defining and proving a truthmaker analogue of the FMP.
Oct 11, 2023, 4pm: Andrew Craig (University of Johannesburg, South Africa), Dual digraphs of finite non-distributive lattices
Abstract: We build on work by Ploščica (1995) who used digraphs with topology to represent bounded lattices. The dual digraphs of arbitrary finite lattices were described as TiRS digraphs by Craig, Haviar and Gouveia (2015). Our goal is to characterise the digraphs dual to finite semidistributive and semimodular lattices. We do this by strengthening the defining conditions of TiRS digraphs. Our results lead to a new description of finite convex geometries. This is joint work with Miroslav Haviar (Matej Bel University), Klarise Marais (University of Johannesburg) and José São João (Stockholm University).
Oct 4, 2023, 4pm: Andrew Craig (University of Johannesburg, South Africa), Representable distributive quasi relation algebras
Abstract: The question of which relation algebras are representable has been studied intensively since the 1940s. More recently, Galatos and Jipsen (2013) described a class of algebras which generalises the class of relation algebras. These so-called quasi relation algebras have a decidable equational theory, but there are no known natural models of binary relations. As a first step in this direction, we will present a definition of representable distributive quasi relation algebras. Much like the case of relation algebras, the definition gives rise to many interesting questions. This is joint work with Claudette Robinson (University of Johannesburg).
Sept 20, 2023, 4pm: Alexander Kurz (Chapman University), Using AI for programming
Sept 13, 2023, 4pm: Peter Jipsen (Chapman University), The Galois duality between S-preclones and S-relational clones
Sept 6, 2023, 4pm: Organizational meeting, brief introduction to partially ordered algebras and S-preclones.