Epimorphisms in Varieties of Heyting Algebras

T. Moraschini and J. J. Wannenburg

Academy of Sciences of the Czech Republic, Czech Republic
University of Pretoria, South Africa, funded by DST-NRF Centre of Excellence in Mathematical and Statistical Sciences (CoE-MaSS)

UP Postgraduate seminar, May 2019

Opinions expressed and conclusions arrived at are those of the author and are not necessarily to be attributed to the CoE-MaSS.

Review of lattices

A lattice is a set \(A\) with a partial order, \(\leq\), such that all pairs of elements \(x\) and \(y\) have

a least upper bound, denoted by \(x \vee y\),
a greatest lower bound, denoted by \(x \wedge y\).

Note that \(x \leq y\) if and only if \(x \vee y = y\),

so we may consider a lattice to be an algebra \[\mathbf{A} = \langle A; \vee, \wedge \rangle.\]

A bounded lattice \(\mathbf{A} = \langle A; \vee, \wedge,1,0 \rangle\) has greatest and least elements \(1\) and \(0\).

Intro

This work was done in collaboration with Tommaso Moraschini last year in Prague. I will eventually get to epimorphisms and Heyting algebras, but the focus of this talk will be on the machinery used in one of our main results. This tool, called Esakia duality, might be interesting to analysts.

I hope you get enough understanding you can understand the structures we found at the end.

Lattices

A lattice is a partially ordered set in which any two elements have a least upper bound, called their join, and a greatest lower bound, called their meet.

Note that we can recover the order using these operations. We can thus think of lattices as algebras, and so retain familiar notions of homomorphism (i.e., a map between algebras that preserve the operations), subalgebra (i.e., a substructure closed under the operations) and direct products.

A bounded lattice has a top and bottom element, denoted by these symbols.

A lattice is distributive if \(x \wedge (y \vee z) = (x \wedge y) \vee (x \wedge z)\),

or, equivalently, if it does not have \(\mathbf{M}_3\) or \(\mathbf{N}_5\) as a sublattice.

A Boolean algebra \(\mathbf{B} = \langle B; \wedge,\vee,\neg,1,0 \rangle\) is a bounded distributive lattice in which every element \(x\) has a complement \(\neg x\), i.e., \[ x \vee \neg x = 1 \text{ and } x \wedge \neg x = 0. \] Recall that the powerset \(\langle \mathrm{P}(X); \cap, \cup, (-)^c, X, \emptyset \rangle\) of any set is a Boolean algebra, where \(A^c = X \setminus A\) for any \(A \subseteq X\).

What about the converse?

For finite Boolean algebras this is the case.

Thm: Any finite boolean algebra \(\mathbf{B}\) is isomorphic to \(\mathrm{P}(A)\), where \(A\) is the set of atoms of \(\mathbf{B}\).

But for infinite Boolean algebras this is not the case. For example, there are infinite Boolean algebras with no atoms.

This limitation was overcome by Marshall Stone.

Let \(\mathbf{A}\) be a lattice. Recall that \(F \subseteq A\) is a filter of \(\mathbf{A}\) if

it is an upset, i.e., if \(y \geq x \in F\), then \(y \in F\), and
\(x \wedge y \in F\) whenever \(x,y \in F\).

For \(U \subseteq A\) and \(x \in A\), we use the following notation:

\({\uparrow}U = \{ z \in X : z \geq y \text{ for some } y \in U \}\), and similar for \({\downarrow}U\);
\({\uparrow} x = {\uparrow}\{x\}\) and \({\downarrow} x = {\downarrow}\{x\}\).

A prime filter \(F\) is a non-empty proper filter satisfying \[ \text{if } x \vee y \in F \text{ then } x \in F \text{ or } y \in F.\] Let \(\mathrm{Pr}\,\mathbf{A}\) denote the set of prime filters of \(\mathbf{A}\).

Thm: A filter \(F\) of a finite Boolean algebra is prime iff \(F = {\uparrow}x\) for some atom \(x\).

Recall that a filter of a lattice is an upset, i.e., upward closed w.r.t. the order, and closed under finite meets. For any set \(U\), \({\uparrow}U\) indicates the set of points above some element in \(U\) and, similarly, for a point \(x\), \({\uparrow}x\) indicates the upward-closure of \(x\).

A prime filter is a non-empty non-total filter, where, if the join of two elements are in the filter, then one of the elements must be in the filter. For Boolean algebras, prime filters are the same as ultrafilters or maximal proper filters.

Also, for a finite Boolean algebra, every prime filter is the upward-closure of an atom.

In the representation theorem on the previous slide, we might as well have used the power set generated by the set of prime filters instead of the set of atoms. It is this observation which supplies the right framework for the generalization to the infinite case.

Stone duality

A Stone space \(\mathbf{X} = \langle X; \tau \rangle\) is a compact Hausdorff space in which every open set is a union of clopen sets.

Let \(\mathbf{A}\) be a lattice. For any \(a \in A\), define \[ \gamma^{\mathbf{A}}(a) := \{ F \in \mathrm{Pr}\,\mathbf{A} : a \in F \}. \]

For any Boolean algebra \(\mathbf{B}\), let \(\tau\) be the topology on \(\mathrm{Pr}\,\mathbf{B}\) with subbasis \(\{ \gamma^{\mathbf{B}}(a): a \in B \} \cup \{ \gamma^{\mathbf{B}}(a)^c : a \in B \}\). Then \(\mathbf{B}_* = \langle \mathrm{Pr}\,\mathbf{B}; \tau \rangle\) is a Stone space. Furthermore, for every homomorphism \(f : \mathbf{B} \rightarrow \mathbf{C}\), the map \(f_* : \mathbf{C}_* \rightarrow \mathbf{B}_*\), defined by \(F \mapsto f^{-1}[F]\), is continuous.

Every Stone space arises in this way, up to homeomorphism.

A Stone space is a compact Hausdorff topological space in which every open set is a union of clopen sets, i.e., sets that are both open and closed. Notice the because the are Hausdorff, the topology of finite Stone spaces are discrete, i.e., it is the powerset of the underlying space. This turns out to be correct generalization of the powerset idea.

For any Boolean algebra we can create a Stone space (bottom star) on its set of prime filters by generating a topology with a subbasis that consist of sets of prime filters of this form: for every element of the Boolean algebra we have the set of prime filters containing the element, and also the set of prime filters that don’t contain it.

Notice that by definition each of these set are clopen in the topology.

We can also associate every Boolean homomorphism with a continuous map in the opposite direction, which is defined by taking the inverse image of a prime filter in the target under the homomorphism.

It is a fact that every Stone space arises in this way.

Dually, given a Stone space \(\mathbf{X}\), let \(C\) be the set of clopen sets of \(\mathbf{X}\).

Then the structure \(\mathbf{X}^* := \langle C; \cap, \cup,(-)^c, X, \emptyset \rangle\) is a Boolean algebra, and every Boolean algebra arises in this way, up to isomorphism.

For every continuous map \(f : \mathbf{X} \rightarrow \mathbf{Y}\), we similarly define \(f^* : \mathbf{Y}^* \rightarrow \mathbf{X}^*\) to be \(\mathcal{U} \mapsto f^{-1}[\mathcal{U}]\).

Thm: The category of Boolean algebras (with algebraic homomorphisms) is dually equivalent to the category of Stone spaces (with continuous maps), as witnessed by the covariant functors \((-)_*\) and \((-)^*\).

Can this be generalized to bounded distributive lattices (without \(\neg\))?

Given a Stone space we can build a Boolean algebra (top star) whose universe is the set of clopen sets of the Stone space, it is ordered by inclusion and complements are taken in the space, this makes sense because the complement of a clopen set is clopen. Notice that when the space is finite, the set of clopens is just the powerset, so this really is a generalization of the first representation theorem.

We can associate every continuous map with a star version going in the opposite direction that is a Boolean homomorphism, defined similar to the previous case.

When two categories are equivalent, all properties the can be expressed as a composition of morphisms are preserved between the two. Many important properties can be expressed this way. Then a category is dually equivalent to another, it is equivalent to the other category, except that the morphisms go in the opposite direction. The category of Boolean algebras (with algebraic homomorphisms) is dually equivalent to the category of Stone spaces (with continuous maps). A category equivalence given by two functors between the categories, which in this case is \((-)_*\) and \((-)^*\), the word ‘covariant’ captures the idea of the change in direction.

Can generalize this representation to bounded distributive lattices?

Priestley duality

A Priestley space \(\mathbf{X} = \langle X; \tau, \leq \rangle\) is a Stone space enriched with a partial order \(\leq\), such that, whenever \(x \not\leq y\), then \(x \in \mathcal{U}\) and \(y \notin \mathcal{U}\) for some clopen upset \(\mathcal{U} \subseteq X\).

Let \(\mathrm{Cu}\,\mathbf{X}\) denote the set of clopen up-sets of \(\mathbf{X}\).

Then \(\mathbf{X}^* = \langle \mathrm{Cu}\,\mathbf{X}; \cap, \cup, X, \emptyset \rangle\) is a bounded distributive lattice.

If \(\mathbf{A} = \langle A; \wedge, \vee, 1, 0 \rangle\) is a bounded distributive lattice, then \(\mathbf{A}_* := \langle \mathrm{Pr}\,\mathbf{A}; \tau, \subseteq \rangle\) is a Priestley space, where \(\tau\) is the same topology as before.

Thm: The category of bounded distributive lattices is dually equivalent to the category of Priestley spaces (with continuous order-preserving maps), as witnessed by the functors \((-)_*\) and \((-)^*\).

This can be done, by enriching the space with a partial order, which should satisfy the following property, called the Priestley separation axiom: whenever an element is not below another there is a clopen upset containing the first but not the second.

Given such a Priestley space, we can construct a bounded distributive lattice, defined the same way as in the Stone case, except the universe is the set of clopen upsets. This is a generalization of the Stone space construction when all the elements are incomparable w.r.t. the partial order, in this case every set is an upset.

Given a bounded distributive lattice, we can construct a Priestly space with the same Stone topology, where the partial order is just set inclusion on the set of prime filters.

Then the category bounded distributive lattices is dually equivalent to the category of Priestley spaces, taking the morphisms to be with continuous order-preserving maps. The maps between morphisms are the same as before.

Let me show you an example of how we construct a Priestly space from a distributive lattice.

Example of \((-)_*\)

Heyting algebras

A Heyting algebra \(\mathbf{A} = \langle A; \wedge, \vee, \to, 1, 0 \rangle\) is a bounded distributive lattice which satisfies \[ x \wedge y \leq z \text{ iff } x \leq y \to z. \]

Heyting algebras are fully determined by their lattice reducts, because \[ y \to z = \bigvee \{x : x \wedge y \leq z\}. \] Thus any finite bounded distributive lattice is a Heyting algebra.

The class of Heyting algebras is the algebraic counterpart of intuitionistic propositional logic, in the same way that the class of Boolean algebras is the algebraic counterpart of classical propositional logic.

Esakia spaces

An Esakia space \(\mathbf{X} = \langle X; \tau, \leq \rangle\), is a Priestley space in which \({\downarrow}\mathcal{U}\) is clopen for every clopen \(\mathcal{U} \subseteq X\).

An Esakia morphism \(f : \mathbf{X} \rightarrow \mathbf{Y}\) between Esakia spaces \(\mathbf{X}\) and \(\mathbf{Y}\) is a continuous order-preserving map such that for every \(x \in X\), \[ \text{if } f(x) \leq y \in Y, \text{ then } y = f(z) \text{ for some } z \geq x. \]

A correct partition \(R\) on an Esakia space \(\mathbf{X}\) is a equivalence relation on \(X\) such that for every \(x,y,z \in X\)

if \(\langle x,y \rangle \in R\) and \(x \leq z\), then \(\langle z,w \rangle \in R\) for some \(w \geq y\), and
if \(\langle x,y \rangle \notin R\), then there is a clopen \(\mathcal{U}\) which is a union of equivalence classes of \(R\) such that \(x \in \mathcal{U}\) and \(y \notin \mathcal{U}\).

We can specialize Priestley duality to get a duality of Heyting algebras.

An Esakia space is a Priestley space, where the downward closure of every clopen set is clopen.

An Esakia morphism is a continuous order-presering function satisfying the addition property that, for every \(x\) in the domain and \(y\) in the target, if \(x\) is mapped below \(y\), then there is an element above \(z\) which is mapped to \(y\).

Further, we need the notion of a correct partition on an Esakia space. It is an equivalence relation such that whenever two elements are related and there is an element above the first, then there must be an element related to it which is above the second. Also, if two elements are not related then they can be separated by a clopen set which is a union of equivalence classes.

Correct paritions are like congruences of algebras and and they are kernels of Esakia morphisms.

Esakia duality

If \(\mathbf{X}\) is an Esakia space, then \(\mathbf{X}^* = \langle \mathrm{Cu}\,\mathbf{X}; \cap, \cup, \to, X, \emptyset \rangle\) is a Heyting algebra, where \(\mathcal{U} \to \mathcal{V} = X \setminus {\downarrow}(\mathcal{U} \setminus \mathcal{V})\).

If \(\mathbf{A} = \langle A; \wedge, \vee, \to, 1, 0 \rangle\) is a Heyting algebra, then \(\mathbf{A}_* := \langle \mathrm{Pr}\,\mathbf{A}; \tau, \subseteq \rangle\), as before, is an Esakia space.

For a class \(\mathsf{K}\) of Heyting algebras, let \(\mathsf{K}_* := \{ \mathbf{A}_* : \mathbf{A} \in \mathsf{K} \}\).

Thm: The category of Heyting algebras is dually equivalent to the category of Esakia spaces (with Esakia morphisms), as witnessed by the functors \((-)_*\) and \((-)^*\).

Epimorphisms

Let \(\mathsf{K}\) be a variety of algebras and \(\mathbf{A},\mathbf{B} \in \mathsf{K}\). A homomorphism \(f : \mathbf{A} \rightarrow \mathbf{B}\) is an epimorphism if, whenever \(\mathbf{C} \in \mathsf{K}\) and \(g,h : \mathbf{B} \rightarrow \mathbf{C}\) are homomorphisms, \[ \text{if } g \circ f = h \circ f, \text{ then } g=h. \]

All surjective homomorphisms are epimorphisms, but, the converse need not be true.

Example: The embedding of the 3-element chain into the 4-element diamond is an epimorphism in the variety of distributive lattices. This reflects the fact that lattice complements are implicitly defined (i.e., unique or non-existent) for distributive lattices, even though there is no unary term that defines them explicitly.

We say \(\mathsf{K}\) has the epimorphism surjectivity (ES) property if all its epimorphisms are surjective.

A subalgebra \(\mathbf{A} \leq \mathbf{B} \in \mathsf{K}\) is epic if the inclusion map \(\mathbf{A} \hookrightarrow \mathbf{B}\) is an epimorphism.

Thm: \(\mathsf{K}\) has the ES property iff none of its members has a proper epic subalgebra.

The ES property is not in general inherited by subvarieties, because a (non-surjective) homomorphism in a variety may become an epimorphism in a subvariety.

Example: The variety of all lattices has the ES property but the variety of distributive lattices does not. The embedding above is not an epimorphism in the variety of lattices, because the above diagram extends in two distinct ways to \(\mathbf{M}_3\).

Connection with Logic

When a variety \(\mathsf{K}\) algebraizes a logic \(\,\vdash\), then \(\mathsf{K}\) has the ES property if and only if \(\,\vdash\) satisfies the infinite Beth property, i.e., all implicit definitions of propositional functions in \(\,\vdash\) can be made explicit.

We shall investigate the ES property for varieties of Heyting algebras, and by implication, the infinite Beth property for axiomatic extensions of intuitionistic logic (i.e., intermediate logics).

Little is known about which varieties of Heyting algebras have surjective epimorphisms. One of the few general positive results is the following:

Thm (G. Bezhanishvili, T. Moraschini, J. G. Raftery): Varieties of Heyting algebras with finite depth have surjective epimorphisms.

The above authors also provided one example of a variety of Heyting algebras which lacks the ES property.

We will recall this example shortly and exhibit the failure of the ES property for many more varieties.

Little is known about which varieties of Heyting algebras have surjective epimorphisms, although a lot is known about closely related properties.

One of the more general positive results which was recently proved by James, Tommaso, and Guram Bezhanishvili states that if a variety of Heyting algebras have finite depth, it has the ES property. The depth of a Heyting algebra is its longest chain of prime filters.

On the negative side, however, not much is known. James, Guram and Tommaso gave one example of a variety of Heyting algebras in which the ES property fails. This is up to this point the only example in the literature of a variety of Heyting algebras in which the ES property fails.

I will show you this example soon, as well as many other examples in which the ES property fails. To construct these examples we will exploit Esakia duality because of the following observation.

We will employ Esakia duality to construct non-surjective epimorphisms by using the following:

Observation: A variety \(\mathsf{K}\) lacks the ES property iff there is an Esakia space \(\mathbf{X} \in \mathsf{K}_*\) with a non-identity correct partition \(R\) such that for every \(\mathbf{Y} \in \mathsf{K}_*\) and every pair of Esakia morphisms \(g,h : \mathbf{Y} \rightarrow \mathbf{X}\), if \(\langle g(y),h(y) \rangle \in R\) for every \(y \in Y\), then \(g = h\).

Recall that to find varieties of Heyting algebras without the ES property, we must avoid varieties that have finite depth. The following construction proves useful in this regard.

Infinite Sums

Let \(\{\mathbf{Y}_n : n \in \omega \}\) be a family of Esakia spaces. Let \(\sum \mathbf{Y}_n\) denote the Esakia space obtained by stacking the components above one another, increasing with \(n\), and then adding a fresh top element (as in a topological one-point compactification).

Dually, if \(\{\mathbf{A}_n : n \in \omega \}\) is a family of Heyting algebras, we let \(\sum \mathbf{A}_n\) denote the Heyting algebra obtained by stacking the components, decreasing with \(n\), and identifying the bottom element of the component above with the top element of component below, and then adding a fresh bottom element.

Then \(\sum \mathbf{Y}_n^* \cong (\sum \mathbf{Y}_n)^*\).

Infinite Sums Example

Failure of the ES property

The variety discovered by Bezhanishvili, Moraschini and Raftery in which the ES property fails is \(\mathbb{V}((\mathbf{D}_2^\infty)^*)\). In this variety \((\mathbf{D}_2^\infty)^*\) has an epic subalgebra consisting of the chain of its left-most elements.

In this algebra every element has a unique ‘sibling’ (an element order-incomparable with it) or no sibling. Siblinghood cannot be explicitly defined.

New Failures of the ES property

Let \(n\) be a positive integer. An Esakia space has width \(\leq n\) if for every \(x \in X\), the up-set \({\uparrow}x\) does not contain antichains of \(n+1\) elements.

A Heyting algebra has width \(\leq n\) if its Esakia dual does.

Thm (Baker): The class \(\mathsf{W}_n\) of all Heyting algebras with width \(\leq n\) is a variety.

We shall show that \(\mathsf{W}_n\) lacks the ES property for any \(n \geq 2\).

Consider the following Esakia space, for \(n \geq 2\):

One can prove that for every \(\mathbf{Y} \in (\mathsf{W}_n)_*\) and every pair of Esakia morphisms \(g,h : \mathbf{Y} \rightarrow \mathbf{X}_n^\infty\), if \(\langle g(y), h(y) \rangle \in R\) for every \(y \in Y\), then \(g = h\).

Thm: For every integer \(n \geq 2\) and variety \(\mathsf{K} \subseteq \mathsf{W}_n\), if \(\mathbf{X}_n^\infty \in \mathsf{K}_*\), then \(\mathsf{K}\) lacks the ES property.

How can one understand this failure in terms of implicit definitions? Each of the elements, labeled \(a_1, a_2, \dots\) below, can be considered a sibling of (each member of) a subset of the epic subalgebra, in both of the following cases.

Apart from the examples above, which specify conditions under which certain varieties of Heyting algebras fail to have the ES property, we were able to give a structural characterization of the ES property in a more restrictive setting (subvarieties of the so-called Kuznetsov-Gerčiu variety).

The latter result yields new examples of varieties of Heyting algebras with surjective epimorphisms.

thank you