Varieties of De Morgan monoids

PhD Defense July 2020

J. J. Wannenburg

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

Supervisor: J. G. Raftery; Co-supervisor: T. Moraschini

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

De Morgan monoids

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

a distributive lattice \(\langle A; \wedge, \vee \rangle\)

(in which \(x \leqslant y\) means \(x \wedge y = x\));
a commutative monoid \(\langle A; \cdot, e \rangle\) satisfying \(x \leqslant x \cdot x\),
and an ‘involution’ \(\neg : A \to A\) satisfying \(\neg \neg x = x\) and

\[x \cdot y \leqslant z \text{ if and only if } x \cdot \neg z \leqslant \neg y.\]

Defining \(y \to z = \neg(y \cdot \neg z)\) and \(f=\neg e\),

we obtain the law of residuation: \[ x \cdot y \leqslant z \text{ iff } x \leqslant y \to z, \] and \(\neg x = x \to f\).

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

De Morgan monoids are algebras in the sense of universal algebra, meaning that they are sets with accompanying operations on the elements of the set.

A De Morgan monoids comprise firstly a distributive lattice:

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. We can recover the partial order using just these operations, and this equation. So, for us the inequality abbreviates this equation.

A lattice is distributive if meets distribute over joins, in the same way that multiplication distributes addition over in normal arithmetic.

A De Morgan monoid secondly comprises a commutative monoid: which has an associative and commutative binary operation, with an identity element we denote by \(e\). When we include a constant in the signature of an algebra, we insist that subalgebras must contain the same constant. De Morgan monoids further satisfy the square-increasing law.

Lastly, De Morgan monoids have an involution, sometimes pronounced as ‘not’, which satisfies the double negation law, and this law:

if we make \(x\) the identity \(e\), then this law states that the involution reverses order, but since this law holds for all \(x\), it is stronger.

We define a residual, arrow, as indicated. Notice that if we where to replace the dot with a meet, then arrow would be the classical material implication. Using this definition, the so-called law of residuation holds.

The meaning of this law is that, for all elements \(y\) and \(z\) , there’s always a largest element of \(A\) whose product with \(y\) falls below \(z\); that element is always \(y \to z\).

The existence of residuals compensates to some extent for the lack of multiplicative inverses in \(A\).

\(y \to z\) behaves as \(y^{-1}\cdot z\) would if \(y^{-1}\) existed. Notice that the action of the law is to move the \(x\) from the left to the right of the \(\leqslant\).

We define the constant \(f\) to be \(\neg e\), which determines the involution, by using the residual.

The class of all De Morgan monoids, denote by \(\mathsf{DMM}\) is a variety: meaning that it is axiomatised by equations, as opposed to something more general like a first-order sentence.

Equivalently, due to a beautiful theorem by Birkhoff, varieties are classes of algebras that are closed closed under taking homomorphic images, subalgebras and direct products.

\(\mathbf{R^t}\)

The relevance logic \(\mathbf{R^t}\) can be characterized as follows, \[ \vdash_{\mathbf{R^t}} \alpha \;(\alpha \text{ is a theorem of } \mathbf{R^t}) \;\text{ iff }\; \mathsf{DMM} \models e \leqslant \alpha. \;(\text{Dunn 1966})\]

More generally, in the deducibility relation of the usual formal system for \(\mathbf{R^t}\), we have \(\gamma_1 , \dots, \gamma_n \vdash_{\mathbf{R^t}} \alpha\) iff \[ \mathsf{DMM} \models \overbrace{(e \leqslant \gamma_1\, \& \dots \&\, e \leqslant \gamma_n) \implies e \leqslant \alpha}^{\text{a quasi-equation}}. \]

One of the main motivations for studying De Morgan monoids is their connection to the relevance logic \(\mathbf{R^t}\) of Anderson and Belap. This connection was first discovered by Dunn.

Although \(\mathbf{R^t}\) is normally introduced as a set of theorems that can be deduced from a formal system consisting of axioms and inference rules, we can characterize it as follows: a formula in the language of De Morgan monoids is a theorem of \(\mathbf{R^t}\), exactly when this formula always evaluates to an element above the identity in every De Morgan monoid.

More generally, we can say that such a formula \(\alpha\) is derivable from a set of premises, just when, for any value of the variables of \(\gamma_1\) to \(\gamma_n\) and \(\alpha\) in any De Morgan monoid, \(\alpha\) is an upper bound of \(e\), provided that \(\gamma_1\) to \(\gamma_n\) are.

Remember that for us these inequalities really abbreviate equations. A statement of this form (namely an equation which follows from a set of equations) is called a quasi-equation. A quasivariety is a class of algebras that is axiomatized by a set of quasi-equations (just like varieties are axiomatized by sets of equations).

There is a lattice anti-isomorphism from the subquasivarieties of \(\mathsf{DMM}\) to the extensions of \(\mathbf{R^t}\), taking subvarieties onto axiomatic extensions.

Some history

Relevance logic began in protest at ‘paradoxes’ of material implication, e.g., the weakening axiom \(p \to (q \to p)\).

It has multiple interpretations, however, and now fits under the ideology-free umbrella of substructural logics.

Relative to these, \(\mathbf{R^t}\) adds \(\wedge\), \(\vee\) distributivity and the contraction axiom \((p \to (p\to q))\to(p\to q)\).

Urquhart (1984): \(\mathbf{R^t}\) is undecidable.

I’ll now quick describe some of the origins of Relevance logic, and how it fits into the the broader study of logic.

Relevance logic began in protest at ‘paradoxes’ of material implication, e.g., the weakening axiom \(p \to (q \to p)\). Intuitively it says that whenever \(p\) is true, then \(q\) will imply \(p\). The paradox lies in the fact that \(q\) can be anything, even something unrelated to \(p\).

(They therefore wanted a logic where \(q\) will imply \(p\) just when \(q\) is related to \(p\), and this demand found it expression in the form of a fragile ‘relevance principle’, which says that a statement will only imply another statement if they share a variables. \(\mathbf{R^t}\) does not satisfy this principle but a related logic called \(\mathbf{R}\) does, and we will look at a more robust relevance principle later.)

However, these days Relevance logic falls under the ideology umbrella of substructural logics (which have diverse motivations), along side other logics such as linear logic and the Lambek calculus.

Relative to these, \(\mathbf{R^t}\) adds \(\wedge\), \(\vee\) distributivity and the contraction axiom \((p \to (p\to q))\to(p\to q)\).

This combination gives \(\mathbf{R^t}\) some special properties. For example, Urquhart showed that \(\mathbf{R^t}\) is undecidable, in the sense that there is no algorithm that can check formula for theoremhood, while if one drops either distributivity or contraction from \(\mathbf{R^t}\), then the resulting logics become decidable.

The algebraic effects of adding distribution and contraction were less explored, thus prompting this thesis, and I’ll illuminate some of them now.

Algebraic effects

Contraction amounts to the square-increasing law \(x\leqslant x^2\) of \(\mathsf{DMM}\). Its effects include:

Algebras are simple iff \(e\) has just one strict lower bound.
Finitely generated algebras are bounded. (If \(\bot\leqslant x\leqslant\top\) for all \(x\), then \(\bot \cdot x=\bot\).)

On the other hand, \(\wedge,\vee\) distributivity gives:

Algebras are (finitely subdirectly) irreducible iff \(e\) is join-prime: \(e\leqslant x \vee y \Longrightarrow e\leqslant x\text{ or }e\leqslant y\).

Contraction of the logical side amounts to the square-increasing law of De Morgan monoids. Its effects include:

The fact the such algebras are simple when the identity element as just one strict lower bound. Here simple means the same as in for example group theory, that you can not map a simple algebra homomorphically onto another non-trivial algebra, except by an isomorphism.
Finitely generated algebras (generated by a finite set of elements) are bounded, in the sense that they have a greatest and smallest element (in which case the bottom element always absorbs products).

In the presence of distributivity, we can characterize ‘irreducible’ algebras as those in which the identity element is join-prime, i.e., if \(e\) is below the join of two elements, then \(e\) is below one of the two.

Irreducible algebras are the building block of any variety, in the sense that every algebra is a subdirect product of irreducible algebras, analogous to how, in number theory, every number is a product of prime numbers.

Special features of De Morgan monoids:

\(f^3=f^2\).
If a De Morgan monoid is \(0\)-generated (i.e., it has no proper subalgebra), then it is finite (Slaney, 1980s). Just eight such algebras are irreducible.
If \(\mathbf{A}\in\mathsf{DMM}\) is irreducible, then \(A=[e)\cup(f]\). Here, we may have \(e\leqslant f\). But if \(f<e\), then \(e\) covers \(f\).

Fact: In a De Morgan monoid, the demand \(f\leqslant e\) is equivalent to idempotence of the whole algebra: \(x^2=x\) (for all \(x\)).

So, non-idempotent algebras lack idempotent subalgebras.

The combination of distributivity and contraction gives us De Morgan monoids, and their special properties include the following:

When a De Morgan monoid is irreducible and bounded, then they are rigorously compact in the sense that the top element absorbs everything except the bottom.
The cube of \(f\) equals \(f\) square.
Slaney proved in the 1980’s that \(0\)-generated De Morgan monoids are finite (where \(0\)-generated means that they have no proper subalgebra. And just eight of these are irreducible (we’ll show them later).
Irreducible De Morgan monoids are composed of the upper bounds of \(e\) and the lower bounds of \(f\). Unlike with many algebras of logic, \(e\) need not be the top element, and we may even have that \(f\) is above \(e\) (as we shall see). But if \(f\) is strictly below \(e\), then \(e\) covers \(f\), meaning that \(e\) is above \(f\) and there is nothing between them.

We showed that idempotent De Morgan monoids (i.e., ones in which the square of each element is equal to itself (as apposed to just greater than or equal to), are exactly the De Morgan monoids in which \(f\) is below \(e\).

So, idempotence is fully captured by a demand on these constants. Since subalgebras must preserve constants, non-idempotent algebras don’t have idempotent subalgebras.

Sugihara monoids

Idempotent De Morgan monoids (a.k.a. Sugihara monoids) form a locally finite variety \[\mathsf{SM} = \mathbb{V}(\mathbf{S}^*)\] \[\;\;(:= \text{ smallest variety containing } \mathbf{S}^*),\] where \(\mathbf{S}^*\) 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{S}^*\) has a homomorphic image \(\mathbf{S}\) in which just \(1\) and \(-1\) are identified.

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

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

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

The \(n\)-element (unique) convex subalgebra of \(\mathbf{S}^*\) or \(\mathbf{S}\) is denoted \(\mathbf{S}_n\).

E.g. \(\mathbf{S}_2\) is the Boolean algebra \(-1<1\);

\(\mathbf{S}_3\) is \(-1 < 0 < 1\);

\(\mathbf{S}_4\) is \(-2<-1<1<2\);

\(\mathbf{S}_5\) is \(-2 < -1 < 0 < 1 < 2\), etc.

These are exactly the finitely generated irreducible Sugihara monoids (Dunn, 1970s), so \(\mathsf{SM}\) is semilinear (i.e., Sugihara monoids are subdirect products of chains).

For \(\mathbf{A} \in \mathsf{DMM}\), the variety \(\mathbb{V}(\mathbf{A})\) contains no nontrivial Sugihara monoid iff \(\mathbf{A}\) satisfies \(x \leqslant f^2\). Then call \(\mathbf{A}\) ‘anti-idempotent’.

Beyond Sugihara monoids, the structure of De Morgan monoids is not fully understood, but here’s a new structure theorem:

Thm

Let \(\mathbf{A}\) be an irreducible De Morgan monoid. Then, either

\(\mathbf{A}\) is a totally ordered Sugihara monoid, with \(f<e\), or
\(\mathbf{A}\) is the union of an anti-idempotent interval subalgebra \([\neg(f^2),f^2] := \{x\in A : \neg(f^2)\leqslant x\leqslant f^2\}\) and two chains of idempotent elements, \((\neg(f^2)]\) and \([f^2)\).

The algebra \(\mathbf{A}/\Theta(\neg(f^2),e)\) is an odd Sugihara monoid, and the \(\Theta(\neg(f^2),e)\)-classes other than \([\neg(f^2),f^2]\) are singletons.

Atoms

The simple \(0\)-generated De Morgan monoids are just \(\mathbf{2} \,(=\mathbf{S}_2), \mathbf{C}_4\) and \(\mathbf{D}_4\) below (Slaney, 1980s).

Thm

A variety of De Morgan monoids consists of Sugihara monoids iff it omits \(\mathbf{C}_4\) and \(\mathbf{D}_4\).

Cor

The minimal varieties of De Morgan monoids are just \(\mathbb{V}(\mathbf{2})\,(=\{\text{Boolean algebras}\})\), \(\mathbb{V}(\mathbf{S}_3)\), \(\mathbb{V}(\mathbf{C}_4)\) and \(\mathbb{V}(\mathbf{D}_4)\).

On general grounds, \(\mathbb{V}(\mathbf{2})\), \(\mathbb{V}(\mathbf{S_3})\), \(\mathbb{V}(\mathbf{C}_4)\) and \(\mathbb{V}(\mathbf{D}_4)\) are also minimal as quasivarieties, but they are not the only ones.

Thm

There are just 68 minimal quasivarieties of De Morgan monoids.

The proof uses Slaney’s (1985) description of the 3088-element free \(0\)-generated De Morgan monoid.
We now investigate the covers of the four atoms in the subvariety lattice of \(\mathsf{DMM}\). This is a distributive lattice, since \(\mathsf{DMM}\) is congruence distributive.

Covers of \(\mathbb{V}(\mathbf{2})\) and \(\mathbb{V}(\mathbf{S}_3)\)

The join of any two atoms is a cover of both.
The remaining covers are precisely the join-irreducible (JI) covers.

Thm

\(\mathbb{V}(\mathbf{2})\) has no JI cover.
The only JI cover of \(\mathbb{V}(\mathbf{S}_3)\) is \(\mathbb{V}(\mathbf{S}_5)\).

Covers of \(\mathbb{V}(\mathbf{D}_4)\)

Thm

Every join-irreducible cover of \(\mathbb{V}(\mathbf{D}_4)\) has the form \(\mathbb{V}(\mathbf{A})\) for some simple 1-generated De Morgan monoid \(\mathbf{A}\), where \(\mathbf{D}_4\) is a proper subalgebra of \(\mathbf{A}\).

For every prime \(p\), the algebra \(\mathbf{B}_p\) generates a cover of \(\mathbb{V}(\mathbf{D}_4)\).
There are infinitely many finitely generated covers of \(\mathbb{V}(\mathbf{D}_4)\).

Not all covers of \(\mathbb{V}(\mathbf{D}_4)\) are finitely generated.

E.g., \(\mathbf{B}_\infty\) is the subalgebra generated by \(a\) in an ultraproduct of the algebras \(\mathbf{B}_p\).
The variety \(\mathbb{V}(\mathbf{B}_\infty)\) covers \(\mathbb{V}(\mathbf{D}_4)\) but it is not generated by its finite members.

Covers of \(\mathbb{V}(\mathbf{C}_4)\)

Distinctive, as \(\mathbf{C}_4\) has diverse homomorphic pre-images:

Thm (Slaney 1989)

If \(h : \mathbf{A} \to \mathbf{B}\) is a homomorphism from an irreducible De Morgan monoid into a non-trivial 0-generated De Morgan monoid, then \(h\) is an isomorphism or \(\mathbf{B} \cong \mathbf{C}_4\).

There is a largest subvariety \(\mathsf{U}\) of \(\mathsf{DMM}\) such that every non-trivial member of \(\mathsf{U}\) has \(\mathbf{C}_4\) as a homomorphic image.
\(\mathsf{U}\) is finitely axiomatized.
There is a largest subvariety \(\mathsf{M}\) of \(\mathsf{DMM}\) such that \(\mathbf{C}_4\) is a retract of all non-trivial members of \(\mathsf{M}\).
Thus, \(\mathbb{V}(\mathbf{C}_4) \subseteq \mathsf{M} \subseteq \mathsf{U}\).
\(\mathsf{M}\) is axiomatized, relative to \(\mathsf{U}\), by \(e \leqslant f\).

Thm

If \(\mathsf{K}\) is a join-irreducible cover of \(\mathbb{V}(\mathbf{C}_4)\), then exactly one of the following holds:

\(\mathsf{K} = \mathbb{V}(\mathbf{A})\) for some simple 1-generated De Morgan monoid \(\mathbf{A}\), such that \(\mathbf{C}_4\) is a proper subalgebra of \(\mathbf{A}\).
\(\mathsf{K} = \mathbb{V}(\mathbf{A})\) for some (finite) non-trivial 0-generated irreducible De Morgan monoid \(\mathbf{A} \in \mathsf{U} \setminus \mathsf{M}\).
\(\mathsf{K} \subseteq \mathsf{M}\).

Condition 1

\(\mathsf{K} = \mathbb{V}(\mathbf{A})\) for some simple 1-generated De Morgan monoid \(\mathbf{A}\), such that \(\mathbf{C}_4\) is a proper subalgebra of \(\mathbf{A}\).

For each prime \(p\), the algebra \(\mathbf{A}_p\) generates a cover of \(\mathbb{V}(\mathbf{C}_4)\).
Thus there are infinitely many finitely generated covers of \(\mathbb{V}(\mathbf{C}_4)\) that satisfy condition 1.
Some covers of \(\mathbb{V}(\mathbf{C}_4)\) are not finitely generated,
for example \(\mathbf{A_\infty}\) generates a cover of \(\mathbb{V}(\mathbf{C}_4)\).

Condition 2

\(\mathsf{K} = \mathbb{V}(\mathbf{A})\) for some (finite) non-trivial 0-generated irreducible De Morgan monoid \(\mathbf{A} \in \mathsf{U} \setminus \mathsf{M}\).

Slaney (1989) characterized all the \(0\)-generated irreducible De Morgan monoids. They are all finite, and apart from the simple and non-trivial ones, they are:

Condition 3

\(\mathsf{K} \subseteq \mathsf{M}\).

Every irreducible algebra in \(\mathsf{M}\) arises by a construction of Slaney (1993) from a Dunn monoid \(\mathbf{B}\) (essentially a De Morgan monoid without an involution \(\neg\)), i.e.,

a square-increasing distributive lattice-ordered commutative monoid \(\langle B; \vee,\wedge,\cdot,\to,e\rangle\) satisfying the law of residuation \[ x \leqslant y \to z \text{ iff } x \cdot y \leqslant z.\]

Let’s call this construction skew reflection.

Skew reflection

Declare that \(a < b'\) for certain \(a,b \in B\) in such a way that \(\langle B \cup B' \cup \{\bot,\top\}; \leqslant \rangle\) is a distributive lattice, \(e < e'\) and for all \(a,b \in B\), \[a < b' \text{ iff } e < (a \cdot b)'.\] Then there is a unique way of turning the structure into a De Morgan monoid \[S^<(\mathbf{B}) = \langle B \cup B' \cup \{ \bot ,\top \}; \vee, \wedge, \cdot, \neg, e \rangle \in \mathsf{M},\] of which \(\mathbf{B}\) is a subreduct, where \(\neg\) extends \('\).

In particular, if we specify that \(a < b'\) for all \(a,b \in B\), then we get the reflection construction—an older idea, see Meyer (1973).

In this case we write \(R(\mathbf{B})\) for \(S^<(\mathbf{B})\).

Covers of \(\mathbb{V}(\mathbf{C}_4)\) within \(\mathsf{M}\)

Thm

Let \(\mathsf{K}\) be a cover of \(\mathbb{V}(\mathbf{C}_4)\) within \(\mathsf{M}\). Then \(\mathsf{K} = \mathbb{V}(\mathbf{A})\) for some finite skew reflection \(\mathbf{A}\) of an irreducible Dunn monoid \(\mathbf{B}\), where \(\bot\) is meet-irreducible in \(\mathbf{A}\), and \(\mathbf{A}\) is generated by the greatest strict lower bound \(c\) of \(e\) in \(\mathbf{B}\).

There are just six such algebras:

Singly generated varieties

Consider a logic \(\,\vdash\), algebraized by a variety \(\mathsf{K}\) of algebras.

It may happen (as in classical prop. logic) that the derivable inference rules of \(\,\vdash\) are determined by a single set of ‘truth tables’, i.e., by the operation tables of a single member of \(\mathsf{K}\).

This happens just in case \(\mathsf{K}=\mathbb{Q}(\mathbf{A})\) for some \(\mathbf{A}\in\mathsf{K}\).

Thm [essentially Maltsev 1966; Łoś & Suszko 1958]

The following conditions on a variety \(\mathsf{K}\) are equivalent.

\(\mathsf{K}=\mathbb{Q}(\mathbf{A})\) for some \(\mathbf{A}\in\mathsf{K}\) (i.e., \(\mathsf{K}\) is ‘singly generated’).
\(\mathsf{K}\) has the joint embedding property (JEP), i.e., any two non-trivial members of \(\mathsf{K}\) both embed into some third member.
(a robust ‘relevance principle’): For any finite set \(\Gamma\cup\Delta\cup\{\alpha\thickapprox\beta\}\) of equations, where \(\Gamma\) is satisfiable in a nontrivial member of \(\mathsf{K}\) and involves different variables from \(\Delta\cup\{\alpha\thickapprox\beta\}\), if \(\mathsf{K}\models (\&(\Gamma\cup\Delta))\Rightarrow\alpha\thickapprox\beta\), then \(\mathsf{K}\models (\&\Delta)\Rightarrow\alpha\thickapprox\beta\).

Known variants of the JEP:

A variety \(\mathsf{K}\) is

structurally complete (SC) if \(\mathsf{K}=\mathbb{Q}(\mathbf{F}_{\mathsf{K}}(\aleph_0))\);
passively structurally complete (PSC) if any two nontrivial members of \(\mathsf{K}\) satisfy the same existential positive sentences \(\exists x_1\,\dots\,\exists x_n\,\Phi\)

(\(\Phi\) a disjunction of conjunctions of equations).

Note: PSC is hereditary. Also, SC implies PSC.

Thm

Every PSC variety has the JEP (hereditarily).

\[\text{SC} \Rightarrow \text{PSC} \Rightarrow \text{JEP}\quad(\not\Leftarrow)\]

Thm

A variety \(\mathsf{K}\) of De Morgan monoids has the JEP iff one of the following (mutually exclusive) conditions holds.

\(\mathsf{K}\) is PSC (classified further in the next theorem).
\(\mathsf{K}=\mathbb{V}(\mathbf{A})\) for a simple De Morgan monoid \(\mathbf{A}\) that has \(\mathbf{D}_{4}\) as a proper subalgebra.
\(\mathsf{K}=\mathbb{Q}(\mathbf{A})\) for a De Morgan monoid \(\mathbf{A}\) that has a simple subalgebra \(\mathbf{B}\), where \(\mathbf{C}_{4}\) is a proper subalgebra of \(\mathbf{B}\).

In the subvariety lattice of \(\mathsf{DMM}\), all join-irreducible covers of the atoms have the JEP, except the four in \(\mathsf{U} \setminus \mathsf{M}\).

Thm

A variety \(\mathsf{K}\) of De Morgan monoids is PSC iff one of the following (mutually exclusive) conditions holds.

\(\mathsf{K}\) is \(\mathbb{V}(\mathbf{2})\) or \(\mathbb{V}(\mathbf{D}_{4})\).
\(\mathsf{K}\) consists of odd Sugihara monoids, i.e., it is one of \[ \mathbb{V}(\mathbf{S}_1) \subsetneq \mathbb{V}(\mathbf{S}_3) \subsetneq \mathbb{V}(\mathbf{S}_5) \subsetneq \dots \subsetneq \mathbb{V}(\mathbf{S})\]
\(\mathsf{K}\) is a nontrivial subvariety of \(\mathsf{M}\).

In (1) and (2), \(\mathsf{K}\) is structurally complete (SC).

So, except for (1),(2), all SC subvarieties of \(\mathsf{DMM}\) lie within \(\mathsf{M}\).

In contrast with (1),(2), we can prove:

Thm

\(\mathsf{M}\) has \(2^{\aleph_0}\) (locally finite) subvarieties \(\mathsf{K}\) that are structurally incomplete—i.e., \(\mathsf{K}=\mathbb{V}(\mathsf{L})\) for some proper subquasivariety \(\mathsf{L}\) of \(\mathsf{K}\); in particular, \(\mathbb{Q}(\mathbf{F}_{\mathsf{K}}(\aleph_0))\subsetneq\mathsf{K}\).

(Where \(\mathsf{K}\) algebraizes a logic \(\,\vdash\), this means that \(\,\vdash\) possesses proper extensions having no new theorems.)

Thm

In the join \(\mathsf{J}\) of the six covers of \(\mathbb{V}(\mathbf{C}_4)\) within \(\mathsf{M}\), every subquasivariety is a variety, i.e., every subvariety of \(\mathsf{J}\) is structurally complete.

Epimorphisms

In a variety \(\mathsf{K}\) of algebras, a homomorphism \(h\colon\mathbf{A}\rightarrow\mathbf{B}\) is called a

(\(\mathsf{K}\)-)epimorphism provided that

\(f \circ h= g\circ h\) implies \(f=g\) (for all \(\mathsf{K}\)-morphisms \(f,g \colon\mathbf{B}\rightarrow\mathbf{C}\)).

Note

Surjective homomorphisms are epimorphisms.
We say that \(\mathsf{K}\) has the ES property if all \(\mathsf{K}\)-epimorphisms are surjective.
\(h\) is an epimorphism iff the inclusion \(h[\mathbf{A}]\rightarrow \mathbf{B}\) is.
\(\mathsf{K}\) has the ES property iff no \(\mathbf{B}\in \mathsf{K}\) has a proper (\(\mathsf{K}\)-)epic subalgebra \(\mathbf{D}\), i.e., one such that every \(\mathsf{K}\)-morphism \(f\colon\mathbf{B}\rightarrow\mathbf{C}\) is determined by \(f|_{\mathbf{D}}\).

Beth property

If a variety \(\mathsf{K}\) algebraizes a logic \(\,\vdash\), then

\(\mathsf{K}\) has the ES property iff \(\,\vdash\) has the infinite (deductive) Beth (definability) property, i.e.,

whenever a set \(Z\) of variables is defined implicitly in terms of a disjoint set \(X\) of variables by means of some set \(\Gamma\) of formal assertions about \(X \cup Z\), then \(\Gamma\) also defines \(Z\) explicitly in terms of \(X\).

‘implicitly defined’ \(\equiv\) ‘uniquely determined or non-existent’, e.g.,

multiplicative inverses in rings;
complements in distributive lattices.

Question: Which varieties of De Morgan monoids have surjective epimorphisms?

A Brouwerian algebra \(\mathbf{B}=\langle B; \wedge, \vee, \to, e\rangle\) is a distributive lattice with a binary \(\to\) satisfying \[ x \leqslant y \to z \;\text{ iff }\; x \wedge y \leqslant z.\] I.e., it’s a Dunn monoid in which \(x \cdot y = x \wedge y\)

(so \(e\) is its top element).

In any De Morgan monoid \(\mathbf{A}\), if \(x,y \leqslant e\) then \(x \cdot y = x \wedge y\).

The negative cone \(A^- := \{ a \in A : a \leqslant e\}\) of \(\mathbf{A}\) can be turned into a Brouwerian algebra \(\mathbf{A}^- = \langle A^-; \wedge, \vee, \to^-, e \rangle\), by restricting the operations \(\wedge, \vee\) to \(A^-\) and defining \[ a \to^- b = (a \to b) \wedge e, \text{ for } a,b \in A^-.\]

A prime filter of a Brouwerian algebra \(\mathbf{B}\) is a lattice-filter \(F\) such that \(B \setminus F\) is closed under \(\vee\).

The depth of \(F\) is the greatest \(n \in \mathbb{N}\) (if it exists) such that there’s a chain of prime filters in \(\mathbf{B}\) of the form \(F = F_0 \subsetneq F_1 \subsetneq \dots \subsetneq F_n = B\).

If no greatest such \(n\) exists, we say \(F\) has depth \(\infty\).

Define \(\text{depth}(\mathbf{B}) = \sup\{\text{depth}(F): F \text{ a prime filter of } \mathbf{B}\}.\)

If \(\mathbf{A}\) is a De Morgan monoid and \(\mathsf{K}\) a variety of De Morgan monoids, we define \[\text{depth}(\mathbf{A}) = \text{depth}(\mathbf{A}^-);\quad \text{depth}(\mathsf{K}) = \sup\{\text{depth}(\mathbf{A}) : \mathbf{A} \in \mathsf{K}\}.\]

Thm

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

Each irreducible member of \(\mathsf{K}\) is generated by its negative cone;
\(\mathsf{K}\) has finite depth.

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

(1) and (2) are hereditary (unlike ES itself).
Each of the 10 covers of \(\mathbb{V}(\mathbf{C}_4)\) within \(\mathsf{U}\) has ES.
Neither (1) nor (2) may be dropped from the theorem.

Thm

Let \(\mathsf{C}\) be the class of all semilinear De Morgan monoids that are generated by their negative cones. Then

\(\mathsf{C}\) is locally finite variety with ES (despite infinite depth);
every subvariety of \(\mathsf{C}\) has ES.

Thm

There are \(2^{\aleph_0}\) locally finite varieties of De Morgan monoids without the ES property.

thank you

Implicit definitions

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