# Fall 2019 Seminars

**Time**: Monday, December 2, 4:10 PM

**Place:**SC 1312

**Title:**Bipartite graphs inside relatively complemented lattices

**Abstract:**As discussed before, one way of approaching SSP ?= RC conjecture is to consider a minimal antichain of non-shattered elements. For some particularly simple antichains (for example, generated by n=1 or 2 elements), the desired properties can be proven. At the moment, n=3 is the simplest problematic case.

**Time:**Friday, November 22, 4:10 PM

**Place:**SC 1312

**Speaker:**Nick Galatos (University of Denver)

**Title:**Heyting residuated lattices: congruences and conuclei

**Abstract:**Separation logic is used in computer science in pointer management and memory allocation. Its basic metalogic is Bunched-Implication logic, a substructural logic whose algebraic semantics are Heyting residuated lattices. We describe the congruences on Heyting RL’s and show that they form an ideal-determined variety. Moreover, we define the notion of a double-division conucleus on a Heyting RL and show that it preserves discriminator terms of specific form.

**Time:**Monday, November 18, 4:30 PM

**Place:**SC 1312

**Peter Jipsen (Chapman University)**

Speaker:

Speaker:

**Title:**A full description of finite commutative idempotent involutive residuated lattices

**Abstract:**An involutive residuated lattice is an algebra (A,v,*,~,-,0) such that (A,v) is a semilattice, (A,*) is a semigroup and x <= y if and only if -y*x <= 0 if and only if x*~y <= 0 where <= is the semilattice order. It is commutative if x*y = y*x holds and idempotent if x*x=x holds for all x,y in A. In joint research with Olim Tuyt (University of Bern) and Diego Valota (University of Milan) we have obtained a description of all finite commutative idempotent involutive residuated lattices. The multiplicative order of these algebras is a distributive semilattice that is a disjoint union of Boolean algebras, with involution as complementation within each Boolean algebra. The top elements of the Boolean algebras form a distributive lattice, and given this family of Boolean algebras indexed by the distributive lattice, there is an algorithm for reconstructing the original residuated lattice.

We give an example of an infinite one-generated commutative idempotent involutive residuated lattice, hence this variety is not locally finite. We will also discuss possible extensions of the structural description to commutative idempotent involutive posets (ongoing research with Melissa Sugimoto, Chapman University). All idempotent involutive posets with up to 16 elements are commutative, and we present some evidence that this may be true for all finite models.

**Time: **Monday, November 4, 4:10 PM

**Place: **SC 1312

**Speaker:** José Gil-Férez

**Title:** Semilinear idempotent residuated lattices

**Abstract: **The aim of this talk is to explain some of the properties of the variety of Semilinear Idempotent Residuated Lattices. In particular we prove that the subvariety of commutative residuated lattices satisfies the Amalgamation Property. We also present a noncommutative subvariety with the Amalgamation Property. In order to prove these results, we give first a complete description of the idempotent chains.

**Time: **Monday, October 28, 4:10 PM

**Place: **SC 1312

**Speaker:** Stephen Simpson

**Title:** Degrees of unsolvability: a two-hour tutorial

**Abstract: **Given a problem P, one associates to P a *degree of unsolvability *deg(P). Here deg(P) is a quantity which measures the “difficulty” of P, i.e., the amount of algorithmic unsolvability which is inherent in P. We focus on two degree structures: the semilattice of Turing degrees DT, and its completion Dw, the lattice of Muchnik degrees. We emphasize specific, natural degrees in DT and Dw. We remark that Dw gives rise to a natural recursion-theoretic interpretation of Kolmogorov’s non-rigorous “calculus of problems.” We also emphasize the analogy between ET, the countable subsemilattice of DT consisting of the Turing degrees associated with recursively enumerable subsets of NN, and Ew, the countable sublattice of Dw consisting of the Muchnik degrees of nonempty Pi^0_1 subsets of {0,1}^NN.

Slides are available here.

**Time: **Monday, October 21, 4:10 PM

**Place: **SC 1312

**Speaker:** Stephen Simpson

**Title:** Degrees of unsolvability: a two-hour tutorial

**Abstract: **Given a problem P, one associates to P a *degree of unsolvability *deg(P). Here deg(P) is a quantity which measures the “difficulty” of P, i.e., the amount of algorithmic unsolvability which is inherent in P. We focus on two degree structures: the semilattice of Turing degrees DT, and its completion Dw, the lattice of Muchnik degrees. We emphasize specific, natural degrees in DT and Dw. We remark that Dw gives rise to a natural recursion-theoretic interpretation of Kolmogorov’s non-rigorous “calculus of problems.” We also emphasize the analogy between ET, the countable subsemilattice of DT consisting of the Turing degrees associated with recursively enumerable subsets of NN, and Ew, the countable sublattice of Dw consisting of the Muchnik degrees of nonempty Pi^0_1 subsets of {0,1}^NN.

**Time: **Monday, October 14, 4:10 PM

**Place: **SC 1312

**Speaker:** Matthew Moore (University of Kansas)

**Title:** Supernilpotence is not super nilpotence

**Abstract: **Supernilpotence is a generalization of nilpotence using a recently developed theory of higher-arity commutators for universal algebras. Many important structural properties have been shown to be associated with supernilpotence, and the exact relationship between nilpotence and supernilpotence has been the subject of investigation. We construct an algebra which is not solvable (and hence not nilpotent) but which is supernilpotent, thereby showing that in general supernilpotence does not imply nilpotence.

**Time:** Monday, October 7, 4:10 PM

**Place: **SC 1312

**Speaker:** Bogdan Chornomaz

**Title:** SSP ?= RC (continued)

**Abstract:** In this talk we will address the SSP ?= RC conjecture, which we were discussing last semester. SSP is a class of finite lattices satisfying Sauer-Shelah-Perles, that is, lattices in which every set of elements shatters at least as many elements as it has. The conjecture says that those are exactly finite relatively complemented lattices, and, while it is almost trivial to show that SSP implies RC, the opposite direction does not seem to be easy. We will briefly recall the basic properties of RC lattices and a sufficient condition for SSP. Then we present recent advancements towards the proof.

**Time:** Monday, September 30, 4:10 PM

**Place: **SC 1312

**Speaker:** Bogdan Chornomaz

**Title:** SSP ?= RC (continued)

**Abstract:** In this talk we will address the SSP ?= RC conjecture, which we were discussing last semester. SSP is a class of finite lattices satisfying Sauer-Shelah-Perles, that is, lattices in which every set of elements shatters at least as many elements as it has. The conjecture says that those are exactly finite relatively complemented lattices, and, while it is almost trivial to show that SSP implies RC, the opposite direction does not seem to be easy. We will briefly recall the basic properties of RC lattices and a sufficient condition for SSP. Then we present recent advancements towards the proof.

**Time:** Monday, September 23, 4:10 PM

**Place: **SC 1312

**Speaker:** Bogdan Chornomaz

**Title:** SSP ?= RC

**Abstract:** In this talk we will address the SSP ?= RC conjecture, which we were discussing last semester. SSP is a class of finite lattices satisfying Sauer-Shelah-Perles, that is, lattices in which every set of elements shatters at least as many elements as it has. The conjecture says that those are exactly finite relatively complemented lattices, and, while it is almost trivial to show that SSP implies RC, the opposite direction does not seem to be easy. We will briefly recall the basic properties of RC lattices and a sufficient condition for SSP. Then we present recent advancements towards the proof.

**Time:** Monday, September 16, 4:10 PM

**Place: **SC 1312

**Speaker:** Adam Přenosil

**Title:** Glivenko theorems and semisimple companions

**Abstract:** The Glivenko theorem connecting intuitionistic and classical logic by means of a double negation translation, as well as its analogues connecting the modal logic S4 with S5 and the fuzzy logic BL with Lukasiewicz logic, will be shown to be instances of a general phenomenon where a logic with a well-behaved negation displays a Glivenko-like connection to what we call its semisimple companion.

**Time:** Monday, September 9, 4:10 PM

**Place: **SC 1312

**Speaker:** Adam Přenosil

**Title:** Semisimplicity and the excluded middle (continued)

**Abstract:** I will present some recent joint research with Tomáš Lávička concerning the logical interpretation of semisimplicity. We shall see that, under some mild assumptions, a quasivariety (or a logic) is semisimple if and only if it enjoys a certain general form of the law of the excluded middle. We then apply this general result to provide a simple proof of the result of Kowalski that a variety of FLew-algebras (i.e. bounded commutative integral residuated lattices) is semisimple if and only if it validates the equation 1 = x v ~(x^n) for some n. In addition to being brief and purely syntactic, our proof also has the virtue of immediately extending to varieties of bounded commutative residuated lattices without any additional work.

**Time:** Monday, August 26, 4:10 PM

**Place: **SC 1312

**Speaker:** Adam Přenosil

**Title:** Semisimplicity and the excluded middle

**Abstract:** I will present some recent joint research with Tomáš Lávička concerning the logical interpretation of semisimplicity. We shall see that, under some mild assumptions, a quasivariety (or a logic) is semisimple if and only if it enjoys a certain general form of the law of the excluded middle. We then apply this general result to provide a simple proof of the result of Kowalski that a variety of FLew-algebras (i.e. bounded commutative integral residuated lattices) is semisimple if and only if it validates the equation 1 = x v ~(x^n) for some n. In addition to being brief and purely syntactic, our proof also has the virtue of immediately extending to varieties of bounded commutative residuated lattices without any additional work.

©2020 Vanderbilt University ·

Site Development: University Web Communications