Adam Přenosil - Open Problems

Q: How do you get a mathematician to read a paper of yours?

A: Get them interested in an open problem.

Below I list some of the open problems that have come up in my research. This is not to say that I came up with all of them, only that they relate to some paper of mine.

Pointed lattice subreducts of residuated lattices. Every lattice is a subreduct of an integral commutative residuated lattice: simply add a a bottom element 0 and a top element 1 together with a second largest element and consider the drastic multiplication (xy = 0 unless x = 1 or y = 1). The problem of describing the pointed lattice subreducts of integral residuated lattices (subreducts in the lattice signature expanded by the constant 1) is more complicated. For example, the diamond and the pentagon lattice cannot occur as unital lattice subreducts of any residuated lattice. In the paper below, I show that the class of unital subreducts of integral residuated lattices, and also of integral commutative residuated lattices, is precisely the quasivariety generated by pointed lattices where 1 is the join irreducible top element. However, the answer to the analogous problem for arbitrary residuated lattices is still missing.

Describe the pointed lattice subreducts of (commutative) residuated lattices.

Syntactic description of nuclear quasivarieties. The nuclear image construction is an important construction in the theory of residuated lattices and ordered monoids more generally. This constructions operates more generally at the level of ordered universal algebra, where nuclear images are special kinds of order-preserving homomorphic images. Accordingly, nuclear quasivarieties (quasivarieties closed under nuclear images) sit somewhere between arbitrary quasivarieties (axiomatized by quasiequations) and varieties (axiomatized by equations). In the paper below I provided a syntactic description of nuclear quasivarieties, showing that they are precisely the classes axiomatized by quasi-inequalities of a particularly simple shape (each premise is an inequality of the form: term is less than or equal to a variable). This is an analogue of Birkhoff's HSP theorem, which states that each class of algebras closed under homomorphic images, subalgebras, and products is axiomatized by equations. However, the proof method depends on the particular properties of semilattice-ordered monoids. The following problem therefore remains open:

Give a syntactic characterization of nuclear quasivarieties of ordered algebras.

Conuclear images of MV-algebras. A classical result of McKinsey and Tarski identifies Heyting algebras as the algebras of open elements of interior algebras, i.e. of Boolean algebras equipped with an interior operator preserving finite meets. Beyond the Boolean case, interior algebras generalize to residuated lattices equipped with a so-called conucleus. The image of a conucleus on a residuated lattice yields another residuated lattice, thus given a class of residuated lattices, one might wish to describe their conuclear images. For example, Montagna and Tsinakis showed that the conuclear images of Abelian ℓ-groups are precisely the commutative cancellative residuated lattices. The following question, however, still remains open:

Describe the conuclear images of MV-algebras.

An unpublished result of William Young states that this problem is equivalent to the following one:

Describe the unit intervals of integral cancellative commutative residuated lattices.

Compare the well-known fact that the unit intervals of lattice-ordered groups are precisely MV-algebras. In the paper below, I develop some methods which might be useful for describing these intervals.

Logics of upsets of Boolean algebras. A logic of upsets of Boolean algebras is a propositional logic determined by some class of matrices consisting of a Boolean algebra with an upward closed set of designated values. There are infinitely many such logics. For example, a countable chain of such logics consists of those determined by a finite Boolean algebra with the upset of non-zero elements being designated.

Are there continuum many finitary logics of upsets of Boolean algebras?

The question can be rephrased without the jargon of propositional logics. A universal Horn property of a set is a property expressible by a set of universal Horn sentences whose atomic subformulas state that the value of some term lies in the given set. For example, being a filter is a universal Horn property while being a prime filter is not.

Are there continuum many distinct universal Horn properties of upsets of Boolean algebras?

While the logic of upsets of all Boolean algebras and the logic of upsets of finite Boolean algebras agree on the finitary rules that they validate, the latter logic satisfies some infinitary rules that the former logic does not.

Axiomatize the logic of upsets of finite Boolean algebras.

In the paper below, I study logics of upsets of distributive lattices and Boolean algebras. In particular, I answer the above questions for distributive lattices instead of Boolean algebras.

Split interpolation. A logic enjoys the interpolation property (in its crudest form) if A ⊢ C implies the existence of a formula B such that A ⊢ B ⊢ C and each variable occurring B occurs both in A and in C. Milne observed that this property could be refined by splitting it between two logics. In particular, he showed that if A ⊢ C classically, then there is a formula B satisfying the same variable inclusion condition such that A ⊢ B in the strong three-valued Kleene logic and B ⊢ C in Priest's three-valued Logic of Paradox. In the paper below, I provide an alternative proof of Milne's theorem and develop a syntactic method for proving such theorems in the context of so-called super-Belnap logics. However, further non-trivial examples of this phenomenon are lacking.

Find further natural examples of the split interpolation property.

Moreover, it remains to find an algebraic method for establishing this kind of interpolation.

What is the semantic correlate of the split interpolation property?

De Morgan clones. The lattice of all clones on the two-element set (i.e. of algebras up to term equivalence) was famously described by Post. On sets of three or more elements, the lattice of all clones has the cardinality of the continuum and defies any simple description. Nonetheless, one might hope to describe some particular pieces of these lattices. In the paper below, I study the lattice of clones which extend the clone DMA of term functions of the four-element De Morgan algebra over the four truth values of the logic of Belnap and Dunn (True, False, Neither, and Both). The clone consists of all functions which, roughly speaking, treat truth and non-falsity in the same way and which are persistent with respect to acquiring further information in the same way that intuitionistic connectives are.

It seems reasonable to demand that a logical connective, as opposed to an arbitrary operation on the four truth values, should satisfy these two conditions. In that case, the lattice of four-valued clones which are contained in the above clone has a natural logical significance and might form a tractable analogue of the Post lattice.

Describe the lattice of four-valued clones below the clone DMA. Is this lattice countable?

More generally, given a subset F of a set A, each clone on A determines a logic. Clones on A can thus be classified according to the properties of such logics. This leads to a whole host of questions, such as:

Describe the minimal protoalgebraic clones on a given set (relative to a choice of F). Describe the maximal selfextensional clones.

Distributivity of ℓ-pregroups. A pregroup is a partially ordered monoid equipped with two unary operations xℓ, xr such that xℓ x ≤ 1 ≤ x xℓ and x xr ≤ 1 ≤ xr x. In particular, this is a partially ordered group if xℓ = xr. A lattice-ordered pregroup (ℓ-pregroup) is a pregroup whose partial order is a lattice. It is well known that each lattice-ordered group is distributive. The major open problem in the theory of ℓ-pregroups is:

Is every ℓ-pregroup distributive?

In the paper below, we show that every ℓ-pregroup is semidistributive. The problem therefore amounts to deciding whether the pentagon may occur as a sublattice of an ℓ-pregroup.

Related paper: Lattice-ordered pregroups are semidistributive (with Nick Galatos, Peter Jipsen, and Michael Kinyon)