Jamie Wannenburg
February 2017 (Supervisor: James Raftery)
An algebra $\mathbf{A} = \langle A; \vee, \wedge, \bdot, \neg, e \rangle$ is a De Morgan monoid whenever
A lattice is a set with a partial order, $\leq$, such that all elements $x$ and $y$ have
Notice that $x \leq y$ iff $x \vee y = y$ (i.e., $x \wedge y = x$)
It is distributive if $x \wedge (y \vee z) = (x \wedge y) \vee (x \wedge z)$
$\langle A; \bdot, e \rangle$ is a commutative monoid if
We define $y \to z = \neg(y \bdot \neg z)$. Then the 'Law of residuation' holds $$ x \bdot y \leq z \;\text{ iff }\; x \leq y \to z $$
For example, consider the set of positive integers :
What is $2 \to 6$?
A variety $\mathsf{V}$ is a class of algebras that is axiomatised by equations, or equivalently, $\mathbb{HSP}(\mathsf{V})=\mathsf{V}$.
We define $\mathbb{V}(\mathbf{A}) = \mathbb{HSP}(\mathbf{A})$.
The class of all De Morgan monoids, $\mathsf{DMM}$, is a variety.
A subvariety of $\mathsf{V}$ a subclass of $\mathsf{V}$ that is itself a variety.
The subvarieties of $\mathsf{V}$ form a lattice.
A logic $\mathbf{L}$ is a set of 'rules' which satisfy certain conditions. A rule is a pair $\Gamma / \alpha$ where $\alpha$ and the elements of $\Gamma$ are terms.
When $\Gamma / \alpha$ belongs to $\mathbf{L}$ we write $$ \Gamma \,\vdash_{\mathbf{L}} \alpha, $$ and we say $\Gamma / \alpha$ is derivable in $\mathbf{L}$.
For axioms and theorems $\Gamma = \emptyset$.
We define the logic $\mathbf{R^t}$ as follows, $$ \gamma_1, \dots, \gamma_n \vdash_{\mathbf{R^t}} \alpha $$ $$ \text{iff} $$ $$\mathsf{DMM} \models (e \leq \gamma_1 \;\&\; \dots \;\&\; e \leq \gamma_n) \Rightarrow e \leq \alpha.$$
$$\vdash_{\mathbf{R^t}} x \to x $$ $\mathsf{DMM} \vDash e \bdot x = x$, in particular $\mathsf{DMM} \vDash e \bdot x \leq x$. So by the law of residuation $\mathsf{DMM} \vDash e \leq x \to x$.
$$ x, x \to y\vdash_{\mathbf{R^t}} y $$ Suppose that $e \leq x$ and $e \leq x \to y$. By the law of residuation $e \bdot x \leq y$, i.e. $x \leq y$. Therefore $\mathsf{DMM} \vDash (e \leq x \,\&\, e \leq x \to y) \implies e \leq y,$ by transitivity of $\leq$.
AAL
An (axiomatic) extension of a logic $\mathbf{L}$ is a logic obtained by adding new axioms to $\mathbf{L}$.
The axiomatic extensions of a logic form a lattice, ordered by inclusion.
$p \to (q \to p)$ (weakening) is not a theorem of $\mathbf{R^t}$.
Slaney (1985) showed that there is no infinite 0-generated De Morgan monoid. However there are infinite 0-generated algebras if we drop either distributivity or the square-increasing law.
Urquhart (1984) showed that the equational theory of $\mathsf{DMM}$ is undecidable. However if we drop either distributivity or the square-increasing law, the corresponding theories become decidable.
The algebra of relevance logic is also relatively unexplored.
Sugihara monoids are idempotent ($x \bdot x = x$) De Morgan monoids
Let $\mathbf{A}$ be a De Morgan monoid. TFAE:
A De Morgan monoid is simple if $e$ has exactly one strict lower bound.
An algebra is 0-generated if it has no proper subalgebra.
Let $\mathbf{A}$ be such a De Morgan monoid. Let $f = \neg e$.
| simple | subdirectly irreducible (SI) | finitely subdirectly irreducible (FSI) | |
|---|---|---|---|
| In congruence lattice | |||
| In De Morgan monoids |
If $\mathsf{K}=\mathbb{V}(\mathbf{A})$ is congruence distributive, then the SI members of $\mathsf{K}$ belong to $\mathbb{HSP_u}(\mathbf{A})$.
If $f < e$, then $f$ is the bottom element of $\mathbf{A}$, by simplicity. Then $\mathbf{A} \cong \mathbf{2}$.
If $e = f$ then $\{e\}$ is a subalgebra, a contradiction.
If $e < f$, then $\mathbf{A} \cong \mathbf{C_4}$.
If $f$ is incomparable with $e$, then $e \wedge f = \neg(f^2)$, so that $\mathbf{A} \cong \mathbf{D_4}$.
What about $\bdot$ ?
Relevant algebras: $ \mathsf{RA} = $ $$\{ \text{Subalgebras of } \langle A; \vee, \wedge, \bdot,\neg \rangle \text{ where } \mathbf{A} \in \mathsf{DMM} \}. $$
Relevance logic: $\mathbf{R}$ is the set of rules of $\mathbf{R^t}$ that do not involve $t$.
$\mathsf{RA}$ algebraizes $\mathbf{R}$ just as $\mathbf{DMM}$ algebraizes $\mathbf{R^t}$, except we replace every $e \leq \alpha$ with $\alpha \to \alpha \leq \alpha$, to which it is equivalent in $\mathsf{DMM}$.
Finitely generated relevant algebras are reducts of De Morgan monoids.
Slaney: Every homomorphism from an FSI De Morgan monoids into a 0-generated De Morgan monoid is an isomorphism or maps onto $\mathbf{C_4}$.
Let $\mathsf{K}$ be a cover of $\mathbb{V}(\mathbf{2})$ in $L_{\mathbb{V}}(\mathsf{RA})$. We show that $\mathsf{K}$ is one of $\mathbb{V}(\mathbf{C_4})$, $\mathbb{V}(\mathbf{D_4})$ or $\mathbb{V}(\mathbf{S_3})$.
Notice that $\mathsf{K} = \mathbb{V}(\mathbf{A})$ for any non-boolean $\mathbf{A} \in \mathsf{K}$.
There exists a non-Boolean finitely generated SI $\mathbf{A} \in \mathsf{K}$ such that $\mathbb{V}(\mathbf{A}) = \mathsf{K}$. Then $\mathbf{A}$ is a reduct of some f. g. SI $\mathbf{A^+} \in \mathsf{DMM}$.
By the result above, one of $\mathbf{C_4}$, $\mathbf{D_4}$, $\mathbf{S_3}$ or $\mathbf{2}$ belongs to $\mathbb{V}(\mathbf{A^+})$. Except for the case where only $\mathbf{2} \in \mathbb{V}(\mathbf{A^+})$ we are done, since the reducts of members of $\mathbb{V}(\mathbf{A^+})$ belong to $\mathbb{V}(\mathbf{A})$.
Suppose $\mathbf{2} \in \mathbb{V}(\mathbf{A^+})$, then $\mathbf{2} \in \mathbb{HSP_u}(\mathbf{A^+})$, i.e., there exists a De Morgan monoid $\mathbf{B}$ that has $\mathbf{2}$ as a homomorphic image and can be embedded into an ultrapower of $\mathbf{A^+}$. In particular $\mathbf{B}$ is FSI. So, by the theorem above, $\mathbf{B} \cong \mathbf{2}$. But then $\mathbf{2} \in \mathbb{SP_u}(\mathbf{A^+})$. In particular, this means that $\mathbf{A^+}$ is a non-Boolean Sugihara monoid. This implies that $\mathbf{S_3} \in \mathbb{V}(\mathbf{A^+})$.
Raftery and Świrydowicz (2016) used the stucture of the bottom part of $L_\mathbb{V}(\mathsf{RA})$ to determine the 'structurally complete' subvarieties of $L_\mathbb{V}(\mathsf{RA})$.
We are currently working on finding the structurally complete members of $L_\mathbb{V}(\mathsf{DMM})$, as well as finding the covers of the atoms.
Thank you