Epimorphisms in varieties of De Morgan monoids

Ordered Algebras and Logic Workshop, Switzerland

T. Moraschini and J.J. Wannenburg and J.G. Raftery

Department of Philosophy, University of Barcelona, Spain
Institute of Computer Science, Czech Academy of Sciences, Czech Republic
Department of Mathematics and Applied Mathematics, University of Pretoria, South Africa

March 2022

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

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 finitely subdirectly irriducible (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.

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.

De Morgan monoids

A De Morgan monoid \(\mathbf{A} = \langle A; \wedge, \vee, \cdot, \neg, e \rangle\) comprises

a distributive lattice \(\langle A; \wedge, \vee \rangle\),
a commutative monoid \(\langle A; \cdot, e \rangle\) that is square-increasing (\(x \leqslant x^2 := x \cdot x\))
an involution \(\neg\) satisfying \(\neg \neg x = x\) and \[x \cdot y \leqslant z \text{ iff } x \cdot \neg z \leqslant \neg y.\]

One can define a residual \(x \to y \colon= \neg(x \cdot \neg y)\) satisfying the law of residuation \[x \cdot y \leqslant z \text{ iff } x \leqslant y \to z,\] and the constant \(f := \neg e\).

The class \(\mathsf{DMM}\) of all De Morgan monoids form a variety.

Dunn monoids are the \(\neg\)-less (\(\wedge,\vee,\cdot,\to,e\)) subreducts of De Morgan monoids.

Negative generation

An element \(a\) of a De Morgan monoid \(\mathbf{A}\) is negative if \(a \in A^{-} := \{b \in A \colon b \leqslant e\}\). And \(\mathbf{A}\) is said to be negatively generated if \(\mathbf{A} = \textup{Sg}(A^{-})\).

In any Dunn/De Morgan monoid if \(x,y \leqslant e\) then \(x \cdot y = x \wedge y\).
A Brouwerian algebra is a integral (\(x \leqslant e\)) Dunn monoid in which \(\cdot\) coinsides with \(\wedge\).
The negative cone \(A^{-}\) can be turned into a Brouwerian algebra \(\mathbf{A}^{-} = \langle A^{-}; \wedge,\vee, \to^{-}, e \rangle\), by restricting \(\wedge, \vee\) to \(A^{-}\) and defining \[ a \to^{-} b = (a \to b) \wedge e, \text{ for } a,b \in A^{-}. \]

Depth

Let \(\mathbf{A}\) be De Morgan monoid.

A set \(F \subseteq A\) is a deductive filter of \(\mathbf{A}\) if it is a lattice filter which contains \(e\).
A filter \(F\) is prime if \(F=A\) or \(A \setminus F\) is a lattice ideal.
Let \(\textup{Pr}(\mathbf{A})\) be the set of prime deductive filters of \(\mathbf{A}\).
The depth of \(F\) in \(\textup{Pr}(\mathbf{A})\) is the greatest \(n \in \omega\) (if it exists) such that there is a chain in \(\textup{Pr}(\mathbf{A})\) of the form \(F=F_0 \subsetneq F_1 \subsetneq \dots \subsetneq F_n = A\). If no such \(n\) exists, the depth of \(F\) is \(\infty\).
We define \(\textup{depth}(\mathbf{A}) := \textup{sup}\{\textup{depth}(F)\colon F \in \textup{Pr}(\mathbf{A})\}\), and
for a variety \(\mathsf{K}\) of De Morgan monoids \(\textup{depth}(\mathsf{K}) := \textup{sup}\{\textup{depth}(\mathbf{A})\colon \mathbf{A} \in \mathsf{K}\}\).

If a variety of De Morgan monoids is finitely generated, then it has finite depth (but not conversely). The depth of \(\mathbf{A}\) coincides with the usual definition of the depth of \(\mathbf{A}^{-}\).

Theorem 1

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

\(\mathbf{A} = \textup{Sg}(A^{-})\) for every FSI member of \(\mathsf{K}\), and
\(\mathsf{K}\) has finite depth.

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

The proof of this theorem does not require distributivity.
It holds in the presence of bounds and for \(\neg\)-less subreducts (so that it generalizes a result in Bezhanishvili, M. and R. (2017) which concerned Brouwerian (and Heyting) algebras).

Condition (1) can’t be dropped

Urquhart (1999) showed that the crystal lattice has a proper epic subalgebra in \(\mathsf{DMM}\).

Notice that it is not negatively generated.

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}) := \mathbb{V}(\{R(\mathbf{D}) : \mathbf{D} \in \mathsf{K}\})\).

Properties of reflections

Let \(\mathbf{D}\) be a Dunn monoid and \(\mathsf{K}\) a variety of Dunn monoids.

\(\mathbf{D}\) is negatively generated iff \(R(\mathbf{D})\) is.
\(\mathsf{K}\) is locally finite iff \(\mathbb{R}(\mathsf{K})\) is.
\(\mathsf{K}\) has surjective epimorphisms iff \(\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{R}(\mathsf{K})\).
The map \(\mathsf{K} \mapsto \mathbb{R}(\mathsf{K})\) from the subvariety lattice of Dunn monoids into the subvariety lattice of De Morgan monoids is injective.

Condition (2) can’t be dropped

Bezhanishvili, M., and R. exhibits a Brouwerian algebra \(\mathbf{A}_1\) that generates a variety without the ES property.

\(R(\mathbf{A}_1)\) has infinite depth and has a proper \(\mathbb{R}(\mathbf{A}_1)\)-epic subalgeba.

For every \(n \in \omega\), consider the depicted Brouwerian algebra \(\mathbf{B}_n\). Let \(F := \{\mathbf{B}_n : n \in \omega \}\). Adapting Bezhanishvili\(^2\) and de Jongh (2008): 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{A}_1)\) is locally finite and fails to have the ES property, and the map \[\mathbb{V}(T) \mapsto \mathbb{V}(T,\mathbf{A}_1)\] is injective.

Using reflections we get:

Thm

There is \(2^{\aleph_0}\) (locally finite) varieties of De Morgan monoids (of infinite depth) that don’t have the ES property.

Semilinearity

A De Morgan monoid will be called semilinear if it is a subdirect product of totally ordered algebras. These form a variety axiomatized by \(e \leqslant (x \to y) \vee(y \to x)\).

Recall that idempotent (\(x=x \cdot x\)) De Morgan monoids are called Sugihara monoids. They are negatively generated generated and form a locally finite variety.

The variety of Sugihara monoids is 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\).

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

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 \to e) \vee y &\text{if } x \leqslant y \\ (a \to e) \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 Dunn monoid. Moreover, every totally ordered idempotent Dunn monoid has this form.

Generalized Sugihara monoids are negatively generated semilinear idempotent Dunn monoid, 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}\).

Thm (M., R. 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.

Theorem 2

Every variety of negatively generated semilinear De Morgan monoids has surjective epimorphisms.

The same is true for their \(\neg\)-less reducts, i.e., for generalized Sugihara monoids.

This result therefore generalizes the following results, see (Bezhanishvili, M. and R., 2017):

Every variety of semilinear Brouwerian algebras (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 variety of generalized Sugihara monoids has a weak version of the ES property (Galatos and Raftery, 2015).

Negative generation can’t be dropped

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 De Morgan monoid 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\).

Thm

Epimorphisms are surjective in the variety of semilinear idempotent Dunn monoids.
The variety generated by all simple semilinear idempotent Dunn monoids 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\).

Logics

Variety	Logic
De Morgan monoids	\(\mathbf{R^t}\)
Dunn monoids	\(\mathbf{R^{t}_{+}}\)
Sugihara monoids	\(\mathbf{RM^t}\)
Relative Stone algebras	positive Gödel-Dummett logic

Subvarieties correspond to axiomatic extensions.

Semilinearity	Gödel-Dummett \((p \to q) \vee (p \to q)\)
Idempotence	Mingle \(p \to (p \to p)\)
Negative generation	Complicated

thank you