A Malcev operation on a set $X$ is a ternary operation, a function
which satisfies the identities $t(x,x,z)=z$ and $t(x,z,z)=x$. An important motivating example is the operation $t$ of a heap, for example the operation on a group defined by $t(x, y, z) = x y^{-1} z$.
An algebraic theory $T$ is a Malcev theory when $T$ contains a Malcev operation. An algebraic theory is Malcev iff one of the following equivalent statements is true:
in the category of $T$-algebras, every internal reflexive relation is a congruence;
in the category of $T$-algebras, the composite (as internal relations) of any two congruences is a congruence;
in the category of $T$-algebras, the composition of equivalence relations is commutative.
Statement (1) is one of the motivations to introduce the notion of Malcev category.
A Malcev variety is the category of $T$-algebras for a Malcev theory $T$, thought of as a variety of algebras.
If $R \hookrightarrow X \times Y$ is a binary relation on sets, write $R(x, y)$ to say that $(x, y) \in R$. If $X$, $Y$ are $T$-algebras, then $R$ is an internal relation in $T$-$Alg$ if the conditions $R(x_1, y_1) \wedge \ldots \wedge R(x_n, y_n)$, and $\theta(x_1, \ldots, x_n) = x$, $\theta(y_1, \ldots, y_n) = y$ for any $n$-ary operation $\theta$ of $T$, jointly imply $R(x, y)$.
The set-theoretic composite of two internal relations in $T$-$Alg$ is also an internal relation, and the equality relation is always internal, so we may (and will) apply ordinary set-theoretic reasoning in our proofs below.
If $T$ is a Malcev theory, then any internal reflexive relation in $T$-$Alg$ is an internal equivalence relation.
If $t$ is a Malcev operation and $R$ is any internal reflexive relation on a $T$-algebra $X$, then $R$ is transitive because given $R(x, y) \wedge R(y, z)$, we infer $R(x, y) \wedge R(y, y) \wedge R(y, z)$, and this together with $t(x, y, y) = x$ and $t(y, y, z) = z$ gives $R(x, z)$ since $R$ is internal. Also $R$ is symmetric, because if $R(x, y)$, we infer $R(x, x) \wedge R(x, y) \wedge R(y, y)$, which together with $t(x, x, y) = y$ and $t(x, y, y) = x$ gives $R(y, x)$.
If every internal reflexive relation is an internal equivalence relation, then the composite of any two internal equivalence relations is also an internal equivalence relation.
The hypothesis is that internal reflexive relations and internal equivalence relations coincide. But (internal) reflexive relations are clearly closed under composition: $\Delta = \Delta \circ \Delta \subseteq R \circ S$.
If internal equivalence relations are closed under composition, then composition of internal equivalence relations is commutative.
If $R$ and $S$ are equivalence relations and so is $S \circ R$, then
as desired.
If composition of internal equivalence relations in $T$-$Alg$ is commutative, then the theory $T$ has a Malcev operation $t$.
According to the yoga of (Lawvere) algebraic theories, $n$-ary operations are identified with elements of $F(n)$, the free $T$-algebra on $n$ generators (more precisely, the Lawvere theory is the category opposite to the category of finitely generated free $T$-algebras). Thus we must exhibit a suitable element $t$ of $F(3)$.
Let $x, y, z$ be the generators of $F(3)$, and let $a, b$ be the generators of $F(2)$. Let $\phi$ be the unique algebra map $F(3) \to F(2)$ taking $x$ and $y$ to $a$ and $z$ to $b$, and let $\psi$ be the unique algebra map $F(3) \to F(2)$ taking $x$ to $a$ and $y$ and $z$ to $b$. An operation $t \in F(3)$ is Malcev precisely when
Let $R$ be the equivalence relation on $F(3)$ given by the kernel pair of $\phi$, and let $S$ be the kernel pair of $\psi$. Then $R(x, y)$ and $S(y, z)$, so $(S \circ R)(x, z)$. Then, since composition of equivalence relations is assumed commutative, $(R \circ S)(x, z)$. This means there exists $t$ such that $S(x, t)$ and $R(t, z)$, or that $\psi(x) = \psi(t)$ and $\phi(t) = \phi(z)$. This completes the proof.
The theory of groups, where $t(x, y, z) = x y^{-1} z$, is Malcev.
The theory of Heyting algebras, where
is Malcev.
If $T$ is Malcev, and if $T \to T'$ is a morphism of algebraic theories, then $T'$ is Malcev. From this point of view, the theory of groups is Malcev because the theory of heaps is Malcev, and the theory of Heyting algebras is Malcev because the theory of cartesian closed meet-semilattices is Malcev.
See also Malcev category.
In any finitely complete category, the intersection of two congruences (equivalence relations) on an object $X$ is a congruence, so that the set of equivalence relations $Equiv(X)$ is a meet-semilattice.
In a regular category such as a variety of algebras, where there is a sensible calculus of relations and relational composition, it is a simple matter to prove that if $Equiv(X)$ is closed under relational composition, then $R \circ S$ is the join $R \vee S$ in $Equiv(X)$. For, if $R, S \in Equiv(X)$, then
while if $R, S \subseteq T$ in $Equiv(X)$, then
In a regular category, if $Equiv(X)$ is closed under relational composition (equivalently, if composition of equivalence relations is commutative), then $Equiv(X)$ is a modular lattice.
The (poset-enriched) category of relations in a regular category is an allegory, and hence satisfies Freyd’s modular law
whenever $T: X \to Y$, $S: Y \to Z$, $R: X \to Z$ are relations. As we have just seen, the hypothesis implies that joins in $Equiv(X)$ are given by composition (so $Equiv(X)$ is a lattice), and so for $R, S, T \in Equiv(X)$ we have
Therefore, if $S \subseteq R$, we have both
and also $S \vee (R \wedge T) \subseteq R \wedge (S \vee T)$. Thus $S \subseteq R$ implies $R \wedge (T \vee S) = (R \wedge T) \vee S$: the modular law is satisfied in $Equiv(X)$.
If $T$ is a Malcev theory, then the lattice of congruences $Equiv(X)$ on any $T$-algebra $X$ is a modular lattice.
A similar argument shows that congruence lattices for $T$-algebras $X$, for $T$ a Malcev theory, satisfy the following property (stronger than the modular property):
Freyd-Scedrov’s Categories, Allegories (2.157, pp. 206-207) gives the following argument: given relations $R_1, S_1, T_1: X \to Y$, $R_2, S_2, T_2: Y \to Z$ between sets, it is “easily verified” that
Then, under the assumption that equivalence relations internal to $T$-$Alg$ commute (so that the join of equivalence relations $R, S$ on $X$ is their relational composite $R S = R \circ S$), the Desarguesian axiom follows immediately.
An algebra $A$ for a theory is unorderable if there is no non-trivial compatible partial order structure on it. It is absolutely unorderable if whenever there is an embedding $A \to B$, then $B$ is unorderable.
Every algebra in a Malcev variety is absolutely unorderable. For if $t\leq u$, then
hence $t=u$. More generally:
An algebra has a generalized Malcev operation if and only if it is absolutely unorderable.
Here, a generalized Malcev operation is a finite sequence of ternary operations $M_1\dots M_n$ such that
Orders are often used to explain recursion, by saying that a recursive definition has a solution via Kleene's fixed point theorem. Since the lambda calculus is a famous calculus for computation and recursion, there is a question (attributed to Gordon Plotkin) of whether the lambda calculus is necessarily orderable to some extent. Peter Selinger then asked, is the lambda calculus inconsistent with Malcev operators?
(Plotkin, Simpson, Selinger) There can be no generalized Malcev operator with $n=1$ or $n=2$ in the lambda calculus.
For $n\gt 2$, it is an open question whether generalized Malcev operators are consistent with the lambda calculus.
See the monograph Borceux-Bourn.
For the connection to unorderability and recursion, see the following article and references therein:
For the characterisation of categories which are localizations? of Maltsev varieties:
The original is ‘Мальцев’; Malcev spelled his name as ‘Malcev’ in his non-Russian papers. This has also been transliterated ‘Mal’cev’, ‘Mal’tsev’ and ‘Maltsev’.
Last revised on October 23, 2023 at 07:33:44. See the history of this page for a list of all contributions to it.