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)

TACL 2019

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

Heyting algebras

A Heyting algebra \(\mathbf{A} = \langle A; \wedge, \vee, \to, 1, 0 \rangle\) is a distributive lattice with bounds \(1\) and \(0\) 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 distributive lattice is a Heyting algebra.

Varieties of Heyting algebras algebraize axiomatic extensions of intuitionistic logic (i.e., intermediate logics).

In this talk I’ll discuss some results by myself and Tommaso Morachini about when epimorphisms are surjective in varieties of Heyting algebras, and when they are not.

Let’s start by refreshing what Heyting algebras are. They are bounded distributive lattices which satisfy the law of residuation over the \(\wedge\) operation. It says that \(y \to z\) must exists, which is the largest element whose meet with \(y\) is below \(z\).

Therefore, they are determined by their lattice reducts, so I can draw them for you without any loss of information. Furthermore, it is clear that every finite distributive lattice is a Heyting algebra.

Our interest in Heyting algebras stems from the fact that varieties of Heyting algebras algebraize the axiomatic extensions of intuitionistic logic, i.e., intermediate logics or superintuitionistic logics.

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 \(\leq\) 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 \leq 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 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. \]

Duality

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

\((-)_*\):

Let \(\mathrm{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 \mathrm{Pr}\,\mathbf{A} : a \in F \}. \]

The structure \(\mathbf{A}_* := \langle \mathrm{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} \}\).

The category of Esakia spaces (with Esakia maps) is dually equivalent to the category of Heyting algebras. Although this is familiar to most of you, I will quickly explain the functors between them.

First the functor from Heyting algebras to Esakia spaces. Let \(\mathbf{A}\) be a Heyting algebra. Recall that a filter of a lattice is prime if no two elements outside it join into it. We let \(\gamma\) of any element be the set of prime filters containing that element. We generate a topology on the set of non-empty proper prime filters of \(\mathbf{A}\) from subbasic sets of this form: for every element of \(\mathbf{A}\) we take all prime filters that contain \(a\), but also all prime filters that don’t contain \(a\). We order the prime filters by set inclusion. This structure is an Esakia space we denote by bottom star.

The dual of a homomorphism just takes inverse images of prime filters.

The dual of a variety of algebras is the isomorphic closure of the duals of all its members.

\((-)^*\):

Given an Esakia space \(\mathbf{X}\), we let \(\mathrm{Cu}\,\mathbf{X}\) denote the set of clopen up-sets of \(\mathbf{X}\). Then the structure \(\mathbf{X}^* := \langle \mathrm{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

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 a (non-surjective) 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.

The map from the the 3-element chain into the 4-element diamond is a non-surjective epimorphism in the variety of distributive lattices. This is true, because, whenever you have homomorphisms from the diamond into a distributive lattice that agree on this three element subset, the behavior of the relative complement is determined completely by the behavior of the middle element. This reflects the fact that relative lattice complements 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 (otherwise they would be Boolean algebras).

Another familiar example of something that is implicitly defined is multiplicative inverses in rings; they need not exist, but when they do, they are unique.

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

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

Equivalent conditions

Let \(\mathsf{K}\) be a variety of Heyting algebras that algebraizes an intermediate logic \(\,\vdash\). The following are equivalent:

\(\mathsf{K}\) has surjective epimorphisms.
\(\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 intermediate logics.

A subalgebra \(\mathbf{A} \leq \mathbf{B} \in \mathsf{K}\) is epic if the inclusion map \(\mathbf{A} \hookrightarrow \mathbf{B}\) is an epimorphism, i.e., homomorphisms from \(\mathbf{B}\) to members of \(\mathsf{K}\) are determined by their restrictions to \(A\).

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

Let \(\mathsf{K}\) be a variety of Heyting algebras. The following are equivalent:

\(\mathsf{K}\) lacks the ES property.
There is a member of \(\mathsf{K}\) with a proper epic subalgebra.
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 \(f,g : \mathbf{Y} \rightarrow \mathbf{X}\), if \(\langle f(y),g(y) \rangle \in R\) for every \(y \in Y\), then \(f = g\).

Known results

Thm (Maksimova)

Only finitely many varieties of Heyting algebras \(\mathsf{K}\) satisfy the following stronger variant of the ES property:

If \(f : \mathbf{A} \rightarrow \mathbf{B}\) is a hom. in \(\mathsf{K}\) and \(b \in B \setminus f[A]\), then there are homs. \(g,h : \mathbf{B} \rightarrow \mathbf{C} \in \mathsf{K}\) 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 \(\mathsf{K}\) 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 \(\mathsf{K}\), where \(\mathbf{B}\) is generated by \(f[A]\) plus finitely many elements of \(B\), 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: Every finitely generated variety \(\mathsf{K}\) of Heyting algebras has surjective epimorphisms.
Proof: Suppose, on the contrary, that \(\mathsf{K}\) lacks 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 usefulness of this result by giving an elementary proof of the following theorem, which was first proved as a corollary 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 it 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 such 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.

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.

One of the more general positive results which was recently proved by James, Guram and Tommaso 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. 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 depth 3, 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.

By the previous results, if we are looking for 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 helps us create such algebras.

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 \(\top\) (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. 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\):

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

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.

We sketch the proof for \(n=2\), making use of the following technical Lemma.

Lemma

For \(0 < n \in \omega\), let \(\mathbf{X}\) and \(\mathbf{Y}\) be Esakia spaces of width \(\leq n\), such that \(\mathbf{Y}\) has a bottom element \(\bot\). Let \(f : \mathbf{Y} \rightarrow \mathbf{X}\) be an Esakia morphism and define \[ X' = \{ x \in X : f(\bot) \leq x \text{ and } x \text{ is non-maximum} \}. \] Suppose that whenever \(f(\bot) < x \in X'\) there is an antichain of \(n\) elements in \(X'\) which contains \(x\).

Then there is a subposet \(Z\) of \(\mathbf{Y}\) such that the restriction \[ f : Z \rightarrow X'\] is a poset isomorphism.

Proof for \(n=2\)

Let \(\mathbf{Y} \in (\mathsf{W}_2)_*\) and \(f,g : \mathbf{Y} \rightarrow \mathbf{X}_2^\infty\) different Esakia morphisms such that \(\langle f(y), g(y) \rangle \in R\) for every \(y \in Y\).

One can show that there exists \(\bot \in Y\) such that \(f(\bot)=\alpha\) and \(g(\bot)=\beta\) in some component of \(\mathbf{X}_2^\infty\).

We may suppose w.l.o.g. that \(Y = {\uparrow}\bot\).

By the Lemma, there is a subposet \(Z \subseteq Y\) such that the restriction \[ f: Z \rightarrow {\uparrow} \alpha \setminus \{\top\} \] is a poset isomorphism.

We label every element of \(Z\) as the ‘prime’ of its copy under \(f\) in \(X\).

We can show that for \(x' \in Z\) \[g(x') = \max(x/R).\]

Since \(g(\bot) = \beta \leq c\), there exists \(y \in Y\) such that \(g(y) = c\).

Since \(c\) is incomparable with \(d=g(b')\), we have \(y\) incomparable with \(b'\).

Then \(y\) is comparable with \(a'\), since \(\mathbf{Y}\) has width \(\leq 2\).

But then, \(g(y) = c\) is comparable with \(g(a') = a\).

From this contradiction it follows that \(f = g\).

Associated failure of the Beth property

Each of the elements, labeled \(a_1, a_2, \dots\) above, can be considered a sibling of (each member of) a subset of the epic subalgebra.

Then, siblinghood is not explicitly definable.

Rieger-Nishimura lattice

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

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

Implicit definitions

Let \(\mathsf{K}\) be a variety of Heyting algebras. The following are equivalent:

\(\mathsf{K}\) has surjective epimorphisms.
Whenever an expression \(\exists \vec{y} \Sigma(\vec{x},\vec{y},v)\)-where \(\Sigma\) is a set of equations-defines \(v\) implicitly i.t.o \(\vec{x}\) over \(\mathsf{K}\) (in the sense that \(\mathsf{K}\) satisfies \[ \& \big(\Sigma(\vec{x},\vec{y},v_1) \cup \Sigma(\vec{x},\vec{z},v_2)\big) \implies v_1 \approx v_2)\] and all elements of some \(\mathbf{B} \in \mathsf{K}\) are define implicitly i.t.o. elements of a subalgebra \(\mathbf{A}\) of \(\mathbf{B}\) (in the same sense, i.e., \[ \forall b \in B \quad \exists \vec{a} \in A \quad \exists \vec{y} \in B \quad \Sigma(\vec{a},\vec{y},b) ),\] then \(\mathbf{A} = \mathbf{B}\).

Let \(\,\vdash\) be an intermediate logic .

Consider two disjoint sets \(X\) and \(Z\) of variables, with \(X \neq \emptyset\), and a set \(\Gamma\) of formulas over \(X \cup Z\). We say that \(Z\) is defined implicitly in terms of \(X\) by means of \(\Gamma\) in \(\vdash\) if \[ \Gamma \cup \sigma[\Gamma] \vdash z \leftrightarrow \sigma(z) \] for every substitution \(\sigma\) such that \(\sigma(x) = x\) for all \(x \in X\). On the other hand, \(Z\) is said to be defined explicitly in terms of \(X\) by means of \(\Gamma\) in \(\vdash\) when, for every \(z \in Z\), there exists a formula \(\varphi_{z}\) over \(X\) such that \[ \Gamma \vdash z \leftrightarrow \varphi_{z}. \] Then the infinite Beth property postulates the equivalence of implicit and explicit definability in \(\vdash\) (for all \(X,Z,\Gamma\) as above).