GALAI Seminar
General Algebra, Logic and Artificial Intelligence Seminar
The seminar is typically held every Wednesday afternoon 4-5 pm (local time) in Keck 370.
A zoom link is available: https://chapman.zoom.us/j/96264248877
Spring 2024
May 1, 2024, 4pm: Melissa Sugimoto (Chapman University) Decompositions and glueings of locally integral involutive residuated structures
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
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.