Epimorphisms in varieties of semilinear residuated lattices

Nonclassical Logic Webinar

J. J. Wannenburg

Institute of Computer Science, Czech Academy of Sciences, Czech Republic

October 2021

This work was carried out within the project Supporting the internationalization of the Institute of Computer Science of the Czech Academy of Sciences (no. CZ.02.2.69/0.0/0.0/18_053/0017594), funded by the Operational Programme Research, Development and Education of the Ministry of Education, Youth and Sports of the Czech Republic. The project is co-funded by the EU.

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.
Example: Epimorphisms are not surjective in the variety of rings, because multiplicative inverses are implicitly (but not explicitly) definable.

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

Beth property

Let \(\mathsf{K}\) be a variety of algebras that algebraizes a 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.

Residuated lattices

A commutative residuated lattice (RL) \(\mathbf{A} = \langle A; \wedge, \vee, \cdot, \to, e \rangle\) comprises

a lattice \(\langle A; \wedge, \vee \rangle\),
a commutative monoid \(\langle A; \cdot, e \rangle\)
and a binary operation \(\to\) satisfying the law of residuation \[x \cdot y \leqslant z \text{ iff } y \leqslant x \to z.\]

We may enrich the language of RLs with an involution, i.e., a unary operation \(\neg\) satifying \[ x = \neg \neg x \text{ and } x \to \neg y = y \to \neg x,\] thus obtaining IRLs. We define \(f := \neg e\).

Distributive RLs that are square-increasing (\(x \leqslant x \cdot x := x^2\)) are called Dunn monoids.
Distributive square-increasing IRLs are called De Morgan monoids.

An [I]RL will be called semilinear if it is a subdirect product of totally ordered [I]RLs. These form a variety.

A semilinear [I]RL is finitely subdirectly irreducible (FSI) iff it is totally ordered.

Note that every semilinear [I]RL is distributive.

Negative generation

An element \(a\) of an [I]RL \(\mathbf{A}\) is negative if \(a \leqslant e\). And \(\mathbf{A}\) is said to be negatively generated if it is generated by is negative elements.

In any Dunn/De Morgan monoid if \(x,y \leqslant e\) then \(x \cdot y = x \wedge y\).
Integral (\(x \leqslant e\)) semilinear Dunn monoids are called relative Stone algebras in which case \(\cdot\) coincides with \(\wedge\).

Sugihara monoids

Idempotent (\(x = x \cdot x\)) De Morgan monoids (a.k.a. Sugihara monoids) form a locally finite variety generated by the algebra \(\mathbf{Z}^*\), which is the natural chain of nonzero integers (with \(-\) as \(\neg\)), \[ x \cdot y = \begin{cases} \text{whichever of }x,y\text{ has} \\ \quad\text{ a greater absolute value} \\ \text{or } x \wedge y \text{ if } \lvert x \rvert = \lvert y \rvert. \end{cases}\]

Here, \(e = 1\), so \(f = -1\).

Notice that all Sugihara monoids are negatively generated.

\(\mathbf{Z}^*\) has a homomorphic image \(\mathbf{Z}\) in which just \(1\) and \(-1\) are identified.

Up to isomorphism, \(\mathbf{Z}\) could be defined like \(\mathbf{Z}^*\) on the set of all integers.

Then \(\mathbf{Z} \models f = e \,(= 0)\).

Algebras with \(f = e\) are called odd.

The variety of odd Sugihara monoids (\(\mathsf{OSM}\)) is generated by \(\mathbf{Z}\).

Idempotent RLs

We abbreviate \(x \to e\) as \(x^*\).

Let \(\mathbf{A}\) be a totally ordered idempotent RL.

Let \(\mathbf{A}^{**}\) denote the odd Sugihara monoid subalgebra of \(\mathbf{A}\) with universe \(\{ a^{**} : a \in A \}\).
For every \(c \in A^{**}\), define \(A_{c} := \{a \in A : a^{**}=c\}\) and \(\mathbb{A}_c := \langle A_c; \leqslant|_{A_c} \rangle\).
Let \(\mathcal{A} := \{\mathbb{A}_c : c \in A^{**}\}.\)

Let \(\mathbf{S}\) be a totally ordered odd Sugihara monoid and let \(\mathcal{X} = \{ \mathbb{X}_c : c \in S\}\) such that each \(\mathbb{X}_c\) is a chain with greatest element \(c\).

Let \(\mathbf{S} \otimes \mathcal{X}\) denote the algebra on \(\bigcup \{ X_c : c \in S \}\) with the lexicographic total order, where for \(a,b \in S\) and \(x \in X_a, y \in X_b\), \[ x \cdot y = \begin{cases} x \wedge y &\text{if } a=b \leqslant e \\ x \vee y &\text{if } e < a = b \\ x &\text{if } a \neq b \text{ and } a \cdot^{\mathbf{S}} b = a \\ y &\text{if } a \neq b \text{ and } a \cdot^{\mathbf{S}} b = b \end{cases} \] \[ x \to y = \begin{cases} a^{*} \vee y &\text{if } x \leqslant y \\ a^{*} \wedge y &\text{if } y < x \end{cases} . \]

Thm (Gil-Férez, Jipsen and Metcalfe, 2020): \(\mathbf{S}\oplus \mathcal{X}\) is a totally ordered idempotent RL satisfying \(\mathbf{S} = (\mathbf{S}\oplus \mathcal{X})^{**}\) and \((\mathbf{S}\oplus \mathcal{X})_c = X_c\) for every \(c \in S\). Moreover, \(\mathbf{A} = \mathbf{A}^{**} \oplus \mathcal{A}\) for every totally ordered idempotent RL \(\mathbf{A}\).

Generalized Sugihara monoids are negatively generated semilinear idempotent RLs, and they form a locally finite variety \(\mathsf{GSM}\) (Raftery, 2007).

The totally ordered members are \(\mathbf{S}\oplus \mathcal{X}\) as above, but \(X_c = \{c\}\) for every \(e \leqslant c \in S\).

Thm: If a totally ordered Dunn monoid is generated by idempotent elements, then it is idempotent.

Therefore, every variety of negatively generated semilinear Dunn monoids is a subvariety of \(\mathsf{GSM}\).

Previous results

Thm (Moraschini, Raftery and W., 2021)

Let \(\mathsf{K}\) be a variety of Dunn/De Morgan monoids such that

\(\mathbf{A}\) is negatively generated for every \(\mathbf{A} \in \mathsf{K}_{FSI}\) and
there is no infinite descending chain in the poset of prime deductive filters of any \(\mathbf{A} \in \mathsf{K}\).

Then \(\mathsf{K}\) has surjective epimorphisms.

Certain semilinear varieties of Dunn/De Morgan monoids enjoy strong positive ES results, see (Bezhanishvili, Moraschini and Raftery, 2017):

Every variety of relative Stone algebras has surjective epimorphisms.
Every variety of Sugihara monoids has surjective epimorphisms,
the same applies to the involution-less subreducts of Sugihara monoids.

Every subvariety of GSM has a weak version of the ES property (Galatos and Raftery, 2015).

Epic subalgebras

A subalgebra \(\mathbf{A} \leqslant \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\).

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

\(\mathsf{K}\) lacks the ES property.
There is a member of \(\mathsf{K}\) with a proper epic subalgebra.

Thm (Campercholi 2018): 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.

Let me now introduce an ideas that will help up disprove the ES property for certain varieties.

A subalgebra is called epic if the inclusion map into the larger algebra is an epimorphism, equivalently, the homomorphisms from the larger algebra are determined by their restrictions to the smaller.

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

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.

Homomorphisms between chains

Thm

Let \(\mathbf{A}\) and \(\mathbf{B}\) be totally ordered idempotent RLs. A map \(h: A \rightarrow B\) is a homomorphism iff all of the following holds

\(I := h^{-1}[\{e\}]\) is an interval containing \(e\) closed under \(^*\),
\(h\) is an order embedding from \(I_* := \{a \in A : a \notin I \text{ but } a^{*} \in I\}\) into \(B_e\setminus \{e\}\)
\(h\) is an order embedding from \(A^{**} \setminus I\) into \(B^{**}\setminus\{e\}\), preserving \(^{*}\)
For each \(a \in A^{**} \setminus I\), \(h\) is an order embedding from \(A_a\) into \(B_{h(a)}\)

Thm

Epimorphisms are surjective in the variety of semil. idemp. RLs.

Proof

Suppose not. Then by Campercholi’s Theorem there exists a totally ordered idempotent RL \(\mathbf{A}\) with a proper epic subalgebra \(\mathbf{B}\). Let \(a \in A \setminus B\). We have two cases \(a \in A^{**}\) and \(a \notin A^{**}\).

We contradict the fact that \(\mathbf{B}\) is epic in \(\mathbf{A}\) by constructing a totally ordered idemp. RL \(\mathbf{C}\) and two homomorphisms \(g,h : \mathbf{A} \rightarrow \mathbf{C}\) that agree on \(\mathbf{B}\) but differ at \(a\).

Thm

Epimorphisms are surjective in every subvariety of \(\mathsf{GSM}\).

Proof

As before.

Thm

The variety generated by all simple semilinear idempotent RLs has surjective epimorphisms.

Thm

The variety generated by the Dunn monoid \(\mathbf{A} = \mathbf{S}_3 \otimes \{\{-1\},\{0\},\{c>1\}\}\) does not have the ES property.

Proof

We show that the integer subalgebra of \(\mathbf{A}\) is epic. Let \(\mathbf{C}\) be a subdirectly irreducible member of \(\mathbb{V}(\mathbf{A})\), and \(g,h : \mathbf{A} \rightarrow \mathbf{C}\) agree on the integers. W.l.o.g. \(g\) and \(h\) is non-trivial. Since \(\mathbf{A}\) is simple, \(g,h\) are embeddings. So, by Jonsson’s theorem, \(\mathbf{C} = \mathbf{A}\). But then \(g=h\).

Thm

\(\text{Sg}^{\mathbf{A}_2}(4) = \{0,1,4,8\}\) is a proper epic subalgebra of \(\mathbf{A}_2\) in the variety of semilinear Dunn/De Morgan monoids.

Proof

Let \(\mathbf{C}\) be a totally ordered and \(g,h : \mathbf{A}_2 \rightarrow \mathbf{C}\) such that \(g(4) = h(4)\).

Suppose w.l.o.g. \(g(2) \leqslant h(2)\). \[g(2) \cdot h(2) \leqslant h(2) \cdot h(2) = h(4) = g(4)\] \[h(2) \leqslant g(2) \to g(4) = g(2)\] So, \(g(2) = h(2)\), but then \(g = h\).

\(\cdot\) is integer multiplication truncated at \(8\). Note that \(2 = 2 \to 4\).

Reflection

Let \(\mathbf{D}\) be a Dunn monoid.

There is a unique way of turning the structure into a De Morgan monoid \(R(\mathbf{D}) = \langle D \cup D' \cup \{\bot,\top\}; \wedge, \vee, \cdot, \neg, e \rangle\) of which \(\mathbf{D}\) is a subreduct and where \(\neg\) extends \('\).
If \(\mathsf{K}\) is a class of Dunn monoids we define \(\mathbb{R}(\mathsf{K}) := \{R(\mathbf{D}) : \mathbf{D} \in \mathsf{K}\}\).

Thm

A Dunn monoid \(\mathbf{D}\) is negatively generated iff \(R(\mathbf{D})\) is.

Thm (Moraschini, Raftery and W., 2021)

Let \(\mathsf{K}\) be a variety of Dunn monoids. Then \(\mathsf{K}\) has surjective epimorphisms iff \(\mathbb{V}(\mathbb{R}(\mathsf{K}))\) has. In particular, \(\mathbf{D}\) has a proper epic subalgebra in \(\mathsf{K}\) iff \(R(\mathbf{D})\) has a proper epic subalgebra in \(\mathbb{V}(\mathbb{R}(\mathsf{K}))\).

Thm (Moraschini, Raftery and W., 2019)

A totally ordered De Morgan monoid \(\mathbf{A}\) is negatively generated iff

\(\mathbf{A}\) is a Sugihara monoid, or
\(A = (\bot] \cup R(\mathbf{D}) \cup [\top)\) where \((\bot]\) and \([\top)\) are chains of idempotents, and \(\mathbf{D}\) is a totally ordered member of \(\mathsf{GSM}\).

This can be used to show that the class of negatively generated semilinear De Morgan monoids is a locally finite variety and epimorphisms are surjective in all of its subvarieties.

thank you