Epimorphisms in Varieties of Heyting Algebras

UJ Logic Workshop

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)

January 2019

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

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 is explained by the fact that lattice complements are implicitly defined (i.e., unique or non-existant) for distributive lattices, even though there is no unary term that defines them explicitly.

intro

I’m going to talk about the surjectivity of epimorphisms in varieties of Heyting algebras. This work was done in collaboration with Tommaso Moraschini while I visited him last year with the gratious support of Petr’s department in Prague. So I would like to take this opertunity to thank him in public for that opertunity.

start

First of all, I will systematically conflate a variety of algebras with the category whose objects are the members of the variety and whose morphisms are the algebraic homomorphisms between its memebers.

A homomorphism \(f\) between algebras in a variety is an epimorphism if it is right-cancelative, i.e., whenever it is composed with two homomorphisms in the variety such that the compositions are equal, then the homomorphisms are equal.

This is explained by the fact that lattice compliments are implicitly defined for distributive lattice, in the sense that if they exist they are uniquely determined, 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\).

A subalgebra is an epic subalgebra if the inclusion map into the larger algebra is an epimorphism.

A variety has the ES property if and onyly if none of its members have a proper epic subalgebra. This is easy to see, since the image of a non-surjective epimorphism is en epic subalgebra of the target.

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.

For 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 diamond can be embedded in two distrinct ways into \(\mathbf{M}_3\).

This means that it is often difficult to determine whether a given variety has the ES property.

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).

Heyting algebras

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

Heyting algebras are fully determined by their lattice reducts.

Known results

Thm (Maksimova)

There are only finitely many varieties of Heyting algebras satisfying the following stronger variant of the ES property:

If \(f : \mathbf{A} \rightarrow \mathbf{B}\) is a hom. in a variety \(\mathsf{K}\) and \(b \in B \setminus f[A]\), then there are \(\mathbf{C} \in \mathsf{K}\) and \(g,h : \mathbf{B} \rightarrow \mathbf{C}\) such that \(g \circ f = h \circ f\) and \(g(b) \neq h(b)\).

Varieties with this stronger property include the respective classes of all Boolean algebras, Gödel algebras, and Heyting algebras.

Thm (Kreisel)

Every variety of Heyting algebras has the following weak variant of the ES property:

If \(f: \mathbf{A} \rightarrow \mathbf{B}\) is a non-surjective hom. in a variety \(\mathsf{K}\), where \(\mathbf{B}\) is generated by \(f[A]\) plus finitely many elements of \(B \setminus f[A]\), then \(f\) is not an epimorphism.

Nevertheless, the (unqualified) ES property remains poorly understood.

Thm (Campercholi): Let \(\mathsf{K}\) be an arithmetical variety whose FSI members form a universal class. Then \(\mathsf{K}\) has the ES property iff its FSI members lack proper epic subalgebras.
Thm: Finitely generated varieties of Heyting algebras have surjective epimorphisms.
Proof: Suppose, on the contrary, that there is a finitely generated variety \(\mathsf{K}\) of Heyting algebras without the ES property. By Campercholi, there is a FSI \(\mathbf{B} \in \mathsf{K}\) with a proper epic subalgebra \(\mathbf{A}\). Since \(\mathsf{K}\) is fin. gen., Jónsson’s Lemma guarantees that \(\mathbf{B}\) is finite. But Kreisel’s result then implies that \(\mathbf{A}\) is not epic in \(\mathbf{B}\), a contradiction.

Then there is the recent result by Campercholi, which holds for arithmetical varieties, i.e., varieties that are congruence permutable (\(\alpha \circ \beta = \beta \circ \alpha\)) and congruence distributive, and whose Finitely Subdirectly Irreducible members form a universal class, i.e., is closed under subalgebras and ultraproducts.

Let me illustrate the usefullness of this result by giving an elementary proof of the following theorem, which was first proved as a corrolary of the next theorem I will show, that is: Every finitely generated variety of Heyting algebras have the ES property.

Suppose not. Then by Campercholi’s result, there exists a Finitely Subdirectly Irreducible algebra in the variety with a proper epic subalgebra. But since this variety is generated by finitely many finite algebras, Jònsson’s lemma tells us that the algebra must be finite. But then is generated by finitely many elements outside of its subalgebra, so Kreisel’s result applies, we obtain that the subalgebra can not be an epic subalgebra, yielding a contradiction.

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.

This implies that there is a continuum of varieties with the ES property.
The above authors also provided one example of a variety of Heyting algebras which lacks the ES property—thereby confirming a conjecture by Blok and Hoogland: the weak ES property is indeed strictly weaker than the ES property.

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

One of the more general positive results which was recently proved by James, Guram and Tommaso states that if a variety of Heting algebras have finite depth, it has the ES property. The depth of a Heyting algebra is its longest chain of prime filters. Since finitely generated varieties have finite depth, this implies the result we just proved. It is known that there is a continuum of varieties of width 2, so this theorem provides us with a continuum of positive examples.

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 was the first example showing that the weak ES property (which all Heyting algebras have) is strictly weaker than the standard ES property, as conjectured by Blok and Hoogland.

I will show you this example soon, as well as many other examples in which the ES property fails. To construct these examples we make use of Esakia duality, which I will now explain.

Esakia Duality

An Esakia space \(\mathbf{X} = \langle X; \tau, \leq \rangle\), is a compact Hausdorff space with topology \(\tau\) on \(X\) and a partial order \(\langle X; \leq \rangle\) such that

\({\uparrow}x\) is closed for all \(x \in X\), and
\({\downarrow}\mathcal{U}\) is clopen for every clopen \(\mathcal{U} \subseteq X\),

where \({\uparrow}x := \{ z \in X : z \geq x \}\) and \({\downarrow}\mathcal{U} := \{ z \in X : z \geq y \text{ for some } y \in \mathcal{U} \}\), and \({\downarrow}x\) and \({\uparrow}\mathcal{U}\) are defined similarly.

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}\).

Duality

The category of Heyting algebras (with algebraic homomorphisms) is categorically dual to the category of Esakia spaces (with Esakia morphisms), as witnessed by the covariant functors \((-)_*\) and \((-)^*\) which we now define.

\((-)_*\):

Let \(\text{Pr}\mathbf{A}\) denote the set of (non-empty, proper) prime filters of a Heyting algebra \(\mathbf{A}\). Define, for every \(a \in A\), \[ \gamma^{\mathbf{A}}(a) := \{ F \in \text{Pr}\mathbf{A} : a \in F \}. \]

The structure \(\mathbf{A}_* := \langle \text{Pr}\mathbf{A}; \tau, \subseteq \rangle\) is an Esakia space, where the topology \(\tau\) has subbasis \(\{ \gamma^{\mathbf{A}}(a): a \in A \} \cup \{ \gamma^{\mathbf{A}}(a)^c : a \in A \}\). Furthermore, for every homomorphism \(f : \mathbf{A} \rightarrow \mathbf{B}\), the map \(f_* : \mathbf{B}_* \rightarrow \mathbf{A}_*\) is defined by \(F \mapsto f^{-1}[F]\).

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

\((-)^*\):

Conversely, given an Esakia space \(\mathbf{X}\), we let \(\text{Cu}\mathbf{X}\) denote the set of clopen up-sets of \(\mathbf{X}\). Then the structure \(\mathbf{X}^* := \langle \text{Cu}\mathbf{X}; \cap, \cup, \to, \emptyset, X \rangle\) is a Heyting algebra, where \(\mathcal{U} \to \mathcal{V} := X \setminus {\downarrow}(\mathcal{U} \setminus \mathcal{V})\). For every Esakia morphism \(f : \mathbf{X} \rightarrow \mathbf{Y}\), we similarly define \(f^* : \mathbf{Y}^* \rightarrow \mathbf{X}^*\) to be \(\mathcal{U} \mapsto f^{-1}[\mathcal{U}]\).

Note: The topology of finite Esakia spaces is discrete (and can therefore be ignored).

Example of \((-)^*\)

Example of \((-)_*\)

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 are generated by finite algebras, and also ones containing algebras with finite depth. The following construction proves useful in this regard.

Sums

Given two (disjoint) Esakia spaces \(\mathbf{X}\) and \(\mathbf{Y}\), let \(\mathbf{X} + \mathbf{Y}\) denote the Esakia space that is the topologically disjoint union \(X \cup Y\), whose order extends the orders of \(\mathbf{X}\) and \(\mathbf{Y}\) and places all the elements of \(Y\) above those of \(X\).

Let \(\mathbf{A}\) and \(\mathbf{B}\) be Heyting algebras. Then \(\mathbf{A}+\mathbf{B}\) is the unique Heyting algebra obtained by placing \(\mathbf{B}\) below \(\mathbf{A}\) and identifying the top element of the former with the bottom element of the latter.

It is a fact that \(\mathbf{X}^* + \mathbf{Y}^* \cong (\mathbf{X} + \mathbf{Y})^*\).

Sums Example

Infinite Sums

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

Similarly, 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 ordering 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.

It remains the case that \(\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 incomparable with it) or no sibling. Siblinghood cannot be explicitly defined.

Epic Subalgebra of \({\mathbf{D}_2^\infty}^\) in \(\mathbb{V}({\mathbf{D}_2^\infty}^)\)

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. In particular, \(\mathsf{W}_1\) is the variety of Gödel algebras.

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\):

\(\mathbf{X}_n^\infty\)

Correct partition \(R\) on \(\mathbf{X}_n^\infty\)

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.

Rieger-Nishimura lattice

Recall that the Rieger-Nishimura lattice \(\mathbf{RN}\) is the one-generated free Heyting algebra depicted below.

Kuznetsov-Gerčiu Varieties

The Kuznetsov-Gerčiu variety is defined as \(\mathsf{KG} := \mathbb{V}\{ \mathbf{A}_1 + \dots + \mathbf{A}_n : 0 < n \in \omega \text{ and } \mathbf{A}_1, \dots, \mathbf{A}_n \in \mathbb{H}(\mathbf{RN}) \}\).

Thm: A variety \(\mathsf{K} \subseteq \mathsf{KG}\) has the ES property iff it excludes all sums of the form \(\sum \mathbf{A}_n\) where each \(\mathbf{A}_n\) is either \((\mathbf{X}_2)^*\) or \((\mathbf{D_2})^*\).

This provides an alternative explanation of the fact that all varieties of Gödel algebras have the ES property.
All subvarieties of \(\mathsf{KG}\) that have the ES property are locally finite.
Within \(\mathsf{KG}\), the ES property is inherited by subvarieties.
The variety \(\mathbb{V}(\mathbf{RN})\) lacks the ES property.

A Continuum of Varieties Lacking the ES Property

For every \(n \in \omega\), consider the depicted algebra \(\mathbf{B}_n\). Let \(F := \{\mathbf{B}_n : n \in \omega \}\). Bezhanishvili, Bezhanishvili and de Jongh showed that, for every different pair \(T,S \subseteq F\), we get \(\mathbb{V}(T) \neq \mathbb{V}(S)\).

For every \(T \subseteq F\), we show that \(\mathbb{V}(T,(\mathbf{D}_2^\infty)^*)\) is a locally finite subvariety of \(\mathbb{V}(\mathbf{RN})\), and the map \[\mathbb{V}(T) \mapsto \mathbb{V}(T,(\mathbf{D}_2^\infty)^*)\] is injective.

Thm: There is a continuum of locally finite subvarieties of \(\mathbb{V}(\mathbf{RN})\) without the ES property.

thank you

Epimorphisms in Varieties of Heyting Algebras

UJ Logic Workshop

Epimorphisms

Connection with Logic

Heyting algebras

Known results

Esakia Duality

Duality

\((-)_*\):

\((-)^*\):

Example of \((-)^*\)

Example of \((-)_*\)

Sums

Sums Example

Sums Example

Sums Example

Sums Example

Infinite Sums

Infinite Sums Example

Infinite Sums Example

Infinite Sums Example

Infinite Sums Example

Failure of the ES property

Epic Subalgebra of \({\mathbf{D}_2^\infty}^*\) in \(\mathbb{V}({\mathbf{D}_2^\infty}^*)\)

New Failures of the ES property

\(\mathbf{X}_n^\infty\)

Correct partition \(R\) on \(\mathbf{X}_n^\infty\)

Rieger-Nishimura lattice

Kuznetsov-Gerčiu Varieties

A Continuum of Varieties Lacking the ES Property

Epic Subalgebra of \({\mathbf{D}_2^\infty}^\) in \(\mathbb{V}({\mathbf{D}_2^\infty}^)\)