nLab Malcev variety

Redirected from "Malcev operation".
Contents

Contents

Definition

A Malcev operation on a set XX is a ternary operation, a function

t:X×X×XX,(x,y,z)t(x,y,z), t:X\times X\times X\to X,\,\,\,(x,y,z)\mapsto t(x,y,z) ,

which satisfies the identities t(x,x,z)=zt(x,x,z)=z and t(x,z,z)=xt(x,z,z)=x. An important motivating example is the operation tt of a heap, for example the operation on a group defined by t(x,y,z)=xy 1zt(x, y, z) = x y^{-1} z.

An algebraic theory TT is a Malcev theory when TT contains a Malcev operation. An algebraic theory is Malcev iff one of the following equivalent statements is true:

  1. in the category of TT-algebras, every internal reflexive relation is a congruence;

  2. in the category of TT-algebras, the composite (as internal relations) of any two congruences is a congruence;

  3. in the category of TT-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 TT-algebras for a Malcev theory TT, thought of as a variety of algebras.

Proofs of equivalence

If RX×YR \hookrightarrow X \times Y is a binary relation on sets, write R(x,y)R(x, y) to say that (x,y)R(x, y) \in R. If XX, YY are TT-algebras, then RR is an internal relation in TT-AlgAlg if the conditions R(x 1,y 1)R(x n,y n)R(x_1, y_1) \wedge \ldots \wedge R(x_n, y_n), and θ(x 1,,x n)=x\theta(x_1, \ldots, x_n) = x, θ(y 1,,y n)=y\theta(y_1, \ldots, y_n) = y for any nn-ary operation θ\theta of TT, jointly imply R(x,y)R(x, y).

The set-theoretic composite of two internal relations in TT-AlgAlg 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.

Proposition 1

If TT is a Malcev theory, then any internal reflexive relation in TT-AlgAlg is an internal equivalence relation.

Proof

If tt is a Malcev operation and RR is any internal reflexive relation on a TT-algebra XX, then RR is transitive because given R(x,y)R(y,z)R(x, y) \wedge R(y, z), we infer R(x,y)R(y,y)R(y,z)R(x, y) \wedge R(y, y) \wedge R(y, z), and this together with t(x,y,y)=xt(x, y, y) = x and t(y,y,z)=zt(y, y, z) = z gives R(x,z)R(x, z) since RR is internal. Also RR is symmetric, because if R(x,y)R(x, y), we infer R(x,x)R(x,y)R(y,y)R(x, x) \wedge R(x, y) \wedge R(y, y), which together with t(x,x,y)=yt(x, x, y) = y and t(x,y,y)=xt(x, y, y) = x gives R(y,x)R(y, x).

Proposition 2

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.

Proof

The hypothesis is that internal reflexive relations and internal equivalence relations coincide. But (internal) reflexive relations are clearly closed under composition: Δ=ΔΔRS\Delta = \Delta \circ \Delta \subseteq R \circ S.

Proposition 3

If internal equivalence relations are closed under composition, then composition of internal equivalence relations is commutative.

Proof

If RR and SS are equivalence relations and so is SRS \circ R, then

SR=(SR) op=R opS op=RS,S \circ R = (S \circ R)^{op} = R^{op} \circ S^{op} = R \circ S,

as desired.

Proposition 4

If composition of internal equivalence relations in TT-AlgAlg is commutative, then the theory TT has a Malcev operation tt.

Proof

According to the yoga of (Lawvere) algebraic theories, nn-ary operations are identified with elements of F(n)F(n), the free TT-algebra on nn generators (more precisely, the Lawvere theory is the category opposite to the category of finitely generated free TT-algebras). Thus we must exhibit a suitable element tt of F(3)F(3).

Let x,y,zx, y, z be the generators of F(3)F(3), and let a,ba, b be the generators of F(2)F(2). Let ϕ\phi be the unique algebra map F(3)F(2)F(3) \to F(2) taking xx and yy to aa and zz to bb, and let ψ\psi be the unique algebra map F(3)F(2)F(3) \to F(2) taking xx to aa and yy and zz to bb. An operation tF(3)t \in F(3) is Malcev precisely when

ϕ(t)=bψ(t)=a\phi(t) = b \qquad \psi(t) = a

Let RR be the equivalence relation on F(3)F(3) given by the kernel pair of ϕ\phi, and let SS be the kernel pair of ψ\psi. Then R(x,y)R(x, y) and S(y,z)S(y, z), so (SR)(x,z)(S \circ R)(x, z). Then, since composition of equivalence relations is assumed commutative, (RS)(x,z)(R \circ S)(x, z). This means there exists tt such that S(x,t)S(x, t) and R(t,z)R(t, z), or that ψ(x)=ψ(t)\psi(x) = \psi(t) and ϕ(t)=ϕ(z)\phi(t) = \phi(z). This completes the proof.

Examples

  • The theory of groups, where t(x,y,z)=xy 1zt(x, y, z) = x y^{-1} z, is Malcev.

  • The theory of Heyting algebras, where

    t(x,y,z)=((zy)x)((xy)z),t(x, y, z) = ((z \Rightarrow y) \Rightarrow x) \wedge ((x \Rightarrow y) \Rightarrow z),

    is Malcev.

  • If TT is Malcev, and if TTT \to T' is a morphism of algebraic theories, then TT' 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.

The lattice of congruences Equiv(X)Equiv(X)

Equiv(X)Equiv(X) is a modular lattice

In any finitely complete category, the intersection of two congruences (equivalence relations) on an object XX is a congruence, so that the set of equivalence relations Equiv(X)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)Equiv(X) is closed under relational composition, then RSR \circ S is the join RSR \vee S in Equiv(X)Equiv(X). For, if R,SEquiv(X)R, S \in Equiv(X), then

R=RΔRS,S=ΔSRSR = R \circ \Delta \subseteq R \circ S, \qquad S = \Delta \circ S \subseteq R \circ S

while if R,STR, S \subseteq T in Equiv(X)Equiv(X), then

RSTTT.R \circ S \subseteq T \circ T \subseteq T.
Proposition

In a regular category, if Equiv(X)Equiv(X) is closed under relational composition (equivalently, if composition of equivalence relations is commutative), then Equiv(X)Equiv(X) is a modular lattice.

Proof

The (poset-enriched) category of relations in a regular category is an allegory, and hence satisfies Freyd’s modular law

R(ST)S((S opR)T)R \wedge (S \circ T) \subseteq S \circ ((S^{op} \circ R) \wedge T)

whenever T:XYT: X \to Y, S:YZS: Y \to Z, R:XZR: X \to Z are relations. As we have just seen, the hypothesis implies that joins in Equiv(X)Equiv(X) are given by composition (so Equiv(X)Equiv(X) is a lattice), and so for R,S,TEquiv(X)R, S, T \in Equiv(X) we have

R(ST)S((SR)T).R \wedge (S \vee T) \subseteq S \vee ((S \vee R) \wedge T).

Therefore, if SRS \subseteq R, we have both

R(ST)S(RT)R \wedge (S \vee T) \subseteq S \vee (R \wedge T)

and also S(RT)R(ST)S \vee (R \wedge T) \subseteq R \wedge (S \vee T). Thus SRS \subseteq R implies R(TS)=(RT)SR \wedge (T \vee S) = (R \wedge T) \vee S: the modular law is satisfied in Equiv(X)Equiv(X).

Corollary

If TT is a Malcev theory, then the lattice of congruences Equiv(X)Equiv(X) on any TT-algebra XX is a modular lattice.

Equiv(X)Equiv(X) is a Desarguesian lattice

A similar argument shows that congruence lattices for TT-algebras XX, for TT a Malcev theory, satisfy the following property (stronger than the modular property):

  • Desarguesian property?: if R i,S i,T iEquiv(X)R_i, S_i, T_i \in Equiv(X) for i=1,2i = 1, 2, then
    (R 1R 2)(S 1S 2))T 1T 2implies(R 1S 1)(R 2S 2)((R 1T 1)(R 2T 2))((S 1T 1)(S 2T 2))(R_1 \vee R_2) \wedge (S_1 \vee S_2)) \subseteq T_1 \vee T_2 \qquad implies \qquad (R_1 \vee S_1) \wedge (R_2 \vee S_2) \subseteq ((R_1 \vee T_1) \wedge (R_2 \vee T_2)) \vee ((S_1 \vee T_1) \wedge (S_2 \vee T_2))

Freyd-Scedrov’s Categories, Allegories (2.157, pp. 206-207) gives the following argument: given relations R 1,S 1,T 1:XYR_1, S_1, T_1: X \to Y, R 2,S 2,T 2:YZR_2, S_2, T_2: Y \to Z between sets, it is “easily verified” that

R 2R 1S 2S 2T 2T 1impliesS 1R 1 opS 2 opR 2(S 1T 1 opS 2 opT 2)(T 1R 1 opT 2 opR 2)R_2 R_1 \cap S_2 S_2 \subseteq T_2 T_1 \qquad implies \qquad S_1 R_{1}^{op} \cap S_{2}^{op} R_2 \subseteq (S_1 T_{1}^{op} \wedge S_{2}^{op} T_2)(T_1 R_{1}^{op} \cap T_{2}^{op}R_2)

Then, under the assumption that equivalence relations internal to TT-AlgAlg commute (so that the join of equivalence relations R,SR, S on XX is their relational composite RS=RSR S = R \circ S), the Desarguesian axiom follows immediately.

Generalized Malcev operations and connection to unorderability and recursion

An algebra AA 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 ABA \to B, then BB is unorderable.

Every algebra in a Malcev variety is absolutely unorderable. For if tut\leq u, then

u=M(t,t,u)M(t,u,u)=t,u= M(t,t,u) \leq M(t,u,u) = t,

hence t=ut=u. More generally:

Theorem

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 1M nM_1\dots M_n such that

t=M 1(t,u,u);M 1(t,t,u)=M 2(t,u,u);M 2(t,t,u)=M 3(t,u,u);M n(t,t,u)=u. t = M_1(t,u,u);\ \ M_1(t,t,u)=M_2(t,u,u);\ \ M_2(t,t,u) = M_3(t,u,u);\ \ \dots M_n(t,t,u)=u.

Recursion and the lambda calculus

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?

Theorem

(Plotkin, Simpson, Selinger) There can be no generalized Malcev operator with n=1n=1 or n=2n=2 in the lambda calculus.

Question

For n>2n\gt 2, it is an open question whether generalized Malcev operators are consistent with the lambda calculus.

References

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:

Spelling

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.