The Gold Standard of Universal Algebra | Using a Malcev Term to Reverse Two Congruence Steps

Let α and β be congruences on the same algebra A. A congruence is an equivalence relation compatible with every basic operation. The two relations may identify different pairs. A path a α b β c means that a and b lie in one α-class, while b and c lie in one β-class.

The reversal problem asks for an element d with a β d α c. It does not ask whether the original intermediate element b works in reverse. Usually a different witness is needed. Nor does it ask whether α and β are equal relations. Two different partitions can still allow every path to be reversed.

We will use α∘β to mean first an α-step and then a β-step: a(α∘β)c when some b satisfies a α b β c. Some sources reverse the order convention for relation composition. The displayed path fixes our meaning and avoids relying on the symbol alone.

The relations permute when α∘β=β∘α. Equality requires every path of the first kind to have a reversed witness and every path of the second kind to have a witness in the original order. Finding one successful path illustrates the property but does not prove it for all paths.

A useful first exercise is to write the allowed intermediate candidates. The reversed witness must lie in both the β-class of a and the α-class of c. Reversal therefore succeeds exactly when those two classes intersect. The term construction will produce an element of that intersection whenever the stated identities hold.

Contents · Next chapter

An equivalence relation is reflexive, symmetric and transitive. These properties let us treat it as a partition and move within its classes. Compatibility adds the algebraic condition: applying a basic operation to coordinatewise related inputs must produce related outputs.

For a binary operation m, if a α a′ and b α b′, then m(a,b) α m(a′,b′). The same requirement applies to every other operation in the signature. A partition that works for addition might fail after an unrelated unary operation is added.

Compatibility extends from basic operations to all term operations. Prove this by following the expression tree. Variables preserve the given input relations. Constants are related to themselves. Each operation node carries related values of its subterms to related outputs. The conclusion holds for the whole finite term.

This extension is what allows a ternary term to manipulate congruence paths. We need not separately add p as a basic operation if it is already expressible from the declared operations. Its compatibility follows from the existing congruence requirements.

The word term is therefore essential. An arbitrary function A³→A can satisfy the two desired equations while failing to preserve α or β away from those special input patterns. Without compatibility, the reversal calculation breaks. Before using a proposed p, check both its term construction and its identities rather than accepting an attractive output table on trust.

Contents · Previous chapter · Next chapter

A Malcev term has three input positions. The identity p(x,y,y)=x says that when its last two inputs agree, the result returns the first input. The identity p(x,x,y)=y says that when its first two inputs agree, the result returns the last input.

These are universal identities: they must hold for every allowed x and y in the algebra under discussion. They are not equations to be solved for selected values. Testing a few equal-input triples can reveal a failure, but a proof needs all pairs or a general argument.

The identities imply p(x,x,x)=x, so the term is idempotent along its full diagonal. The converse is false. Many ternary operations return x on (x,x,x) without satisfying either required cancellation pattern. Checking only the diagonal misses the main content of the condition.

Think of the middle input as the point where the original two-step path changes relation. The two identities let the same term collapse to the left endpoint after one substitution and to the right endpoint after another. Compatibility then carries the term value into the needed classes.

This explanation is a guide to the proof, not a replacement for it. Write both identities in the exact input order you will use. Swapping variables casually can turn a correct candidate into a formula with the wrong cancellation behaviour, especially when the underlying algebra is noncommutative.

Contents · Previous chapter · Next chapter

Assume a α b and b β c. Define d=p(a,b,c). We want a β d and d α c. For the first relation, compare the triples (a,b,b) and (a,b,c). Their first two coordinates are equal, hence β-related, and their last coordinates are β-related by the original assumption b β c.

Compatibility of β with the term p gives p(a,b,b) β p(a,b,c). The first Malcev identity turns the left value into a, and the right value is d. Therefore a β d. This establishes the first half of the reversed path.

For the second half, compare (a,b,c) with (b,b,c). The first coordinates are α-related by a α b, while the other coordinates are equal. Compatibility gives p(a,b,c) α p(b,b,c). The second identity turns the right value into c, yielding d α c.

Combining the two conclusions produces a β d α c. Nothing in the argument required α=β or a special choice of endpoints. Repeating the same reasoning with α and β exchanged proves the opposite inclusion of composite relations. Thus the two congruences permute.

The witness formula is useful because it is constructive. It does not merely assert that an intersection of classes is nonempty; it names an element in that intersection. A learner can verify each substitution, identify which congruence is used, and see exactly where each identity enters the argument.

Contents · Previous chapter · Next chapter

In any abelian group written additively, p(x,y,z)=x−y+z is a term using addition and inverse. It satisfies p(x,y,y)=x−y+y=x and p(x,x,y)=x−x+y=y. The cancellation identities hold for arbitrary inputs, so the term gives a uniform reversal certificate.

For a finite worked case, use addition modulo 12. Let α identify residues with the same remainder modulo 3, and let β identify residues with the same remainder modulo 4. Both are congruences of the additive-group signature because the respective reduction maps preserve addition, inverse and zero.

Choose a=1, b=4 and c=8. We have 1 α 4 because their difference is 3, and 4 β 8 because their difference is 4. The term gives d=1−4+8=5 modulo 12.

Check the reversed path explicitly. The difference 5−1 is 4, so 1 β 5. The difference 8−5 is 3, so 5 α 8. The new intermediate element 5 belongs to the β-class {1,5,9} of 1 and the α-class {2,5,8,11} of 8.

The arithmetic verifies this particular instance, while the term proof explains every instance. Do not confuse those roles. A collection of successful numerical paths would still leave untested cases; the two identities and compatibility establish the result for the whole algebra and, with the same formula, for every abelian group.

Contents · Previous chapter · Next chapter

Commutativity is not needed for groups. In multiplicative notation, use p(x,y,z)=xy⁻¹z. Associativity and inverse cancellation give p(x,y,y)=x(y⁻¹y)=x and p(x,x,y)=(xx⁻¹)y=y. No exchange of factors occurs.

This matters in permutation groups and other noncommutative examples. The formula xzy⁻¹ generally behaves differently. Its first required pattern is xyy⁻¹=x, but its second pattern is xyx⁻¹, which need not equal y. Satisfying one cancellation identity does not compensate for failing the other.

For an explicit check, use permutations of three symbols, with composition performed right to left. Let x be the transposition exchanging 1 and 2, and y the transposition exchanging 2 and 3. Conjugating y by x gives the transposition exchanging 1 and 3, so xyx⁻¹ differs from y.

Thus the incorrectly ordered candidate fails p(x,x,y)=y in this group. The correct xy⁻¹z formula remains valid. The distinction is not a matter of notation preference: the operation's order changes the function and therefore the identity being claimed.

When transferring an additive formula to multiplicative notation, preserve the term tree and cancellation positions. Additive notation can hide noncommutative issues because familiar numerical examples allow reordering. A symbolic proof that cancels adjacent inverses without swapping factors is stronger evidence for the general group claim.

Contents · Previous chapter · Next chapter

Take the first projection p(x,y,z)=x. It is a term in every algebra because variables themselves are terms. It satisfies p(x,y,y)=x automatically. However, p(x,x,y)=x, which equals y only when x=y or the carrier has one element. It fails the second required identity on any nontrivial carrier.

If we nevertheless use d=p(a,b,c), the proposed witness is simply a. The relation a β d holds by reflexivity, but d α c becomes a α c. The original path only supplied a α b and b β c; it did not establish a α c. The missing identity is exactly the missing bridge.

The last projection p(x,y,z)=z gives the opposite failure. It satisfies p(x,x,y)=y, but p(x,y,y)=y rather than x. Its proposed witness c supplies the α-step trivially while leaving the β-step unjustified. These two examples show the distinct work performed by the two equations.

An idempotent ternary operation can fail for the same reason. Returning the correct value when all three inputs agree says nothing about the mixed patterns (x,y,y) and (x,x,y) with x≠y. A test suite limited to diagonal triples would accept both bad projections.

For a finite candidate term, test the two identity families separately and retain a witness pair for either failure. A failed equation should stop the reversal claim immediately. There is no benefit in inspecting more congruence paths when the universal certificate itself does not satisfy its defining requirements.

Contents · Previous chapter · Next chapter

Let A be the four-element chain 0<1<2<3 with minimum and maximum as basic operations. Define α by the two blocks {0,1} and {2,3}. Define β by the three blocks {0}, {1,2} and {3}. Both partitions have interval blocks.

They are congruences of this chain lattice. The class maps to the corresponding quotient chains are order-preserving, and an order-preserving map between chains preserves minimum and maximum. Thus the partitions satisfy operation compatibility, not merely the equivalence requirements.

There is an α-then-β path 0 α 1 β 2. For a reversed path, an intermediate d would have to be β-related to 0. Its only possibility is d=0 because the β-class of 0 is a singleton. But 0 is not α-related to 2. No reversed witness exists.

Therefore α∘β differs from β∘α, and the algebra does not have permuting congruences. The failure is witnessed by a particular endpoint pair and a complete check of the possible intermediate class. It does not depend on a diagram that might be misread.

Consequently this algebra cannot possess a Malcev term in its lattice signature. If it did, the general witness construction would reverse the displayed path, contradicting the explicit impossibility. This is a structural obstruction to term existence, stronger than failing to guess a formula after trying several candidates.

Contents · Previous chapter · Next chapter

Every term built from minimum and maximum on a chain is order-preserving in all inputs. Variables have this property, constants also have it if included, and compositions of order-preserving operations preserve it. Induction through a term therefore gives a monotonicity invariant.

Now choose distinct chain elements 0<1. The triples (0,0,1) and (0,1,1) are ordered coordinatewise, with the first no larger than the second. A Malcev term would give p(0,0,1)=1 by its second identity and p(0,1,1)=0 by its first.

That would send an increasing input tuple to a decreasing output: 1 would have to be at most 0. This contradicts monotonicity. Hence no nontrivial chain lattice can define a Malcev term using only minimum, maximum and any fixed chain constants.

This proof has a different purpose from the previous congruence counterexample. It rules out every possible lattice term directly, without enumerating the congruences. It also applies to the two-element chain, whose own congruence situation will reveal an important distinction later.

The general technique is useful well beyond this example. To prove that a desired operation is not term-definable, identify a property shared by the basic operations and preserved under composition. Then exhibit a required behaviour that violates that property. A universal construction invariant replaces an unbounded search through candidate expressions.

Contents · Previous chapter · Next chapter

The join α∨β is the least congruence containing both α and β. In general, one may need a chain of several alternating steps to connect a pair in the join. When α and β permute, their two-step composite α∘β is already that join.

Here is the reason. The composite is reflexive because both relations are. Its inverse relation is β∘α, since reversing a two-step path reverses the order; permutability makes this equal to α∘β, so the composite is symmetric. For transitivity, a pair of two-step paths gives α,β,α,β in succession.

Swap the middle β,α steps using permutability, producing α,α,β,β. Transitivity inside α and inside β shortens this to α,β. Thus the composite is transitive. Compatibility follows by choosing intermediate witnesses for each input coordinate and applying the basic operation to those witnesses.

The composite therefore is a congruence. It contains α and β by inserting a reflexive step of the other relation. Conversely, every congruence containing both relations contains their composite by transitivity. These two facts prove that the composite equals the least such congruence, namely their join.

Do not confuse this with the raw union α∪β. The union may still fail transitivity even when the congruences permute. The composite includes the necessary two-step consequences. The existing guide on generated congruences explains union and closure; the special term here supplies a condition under which two steps already describe the whole join.

Contents · Previous chapter · Next chapter

A majority operation returns the repeated value when two of its three inputs agree. Its identities include M(x,x,y)=x and M(x,y,y)=y. Compare these with the Malcev identities, which return y in the first pattern and x in the second. The repeated-input patterns are the same, but their required outputs differ.

On a chain lattice, the median term M(x,y,z)=max(min(x,y),min(x,z),min(y,z)) is a majority term. For inputs 0,0,1, it returns 0. A Malcev term would have to return 1 on those same inputs. The median therefore cannot serve as the desired reversal certificate.

The four-element chain has this majority term but also has the nonpermuting congruences from Chapter 8. This gives a concrete counterexample to the claim that any useful ternary term with repeated-input identities must force congruence permutability.

In the two-element additive group, the ternary sum x+y+z modulo 2 is a Malcev term because subtraction equals addition there. It returns the nonrepeated bit when two inputs agree. That behaviour differs from majority, even though both operations return x when all inputs are x.

Read term conditions literally. Names such as majority, minority and Malcev refer to different identity patterns, and different structural consequences require different hypotheses. A shared arity or diagonal behaviour does not make the conditions interchangeable. Checking one mixed repeated-input triple is often enough to expose the mistaken substitution.

Contents · Previous chapter · Next chapter

A variety is a class of algebras of a fixed signature defined by identities. The classical Malcev theorem says that a variety has permuting congruences in every member exactly when one ternary term satisfies the two Malcev identities throughout the variety. The quantifier “every member” is crucial.

For a single algebra, having a Malcev term is sufficient for all its congruences to permute, as our witness proof established. But merely observing that all congruences of one algebra permute does not in general imply that it has such a term in its language.

Consider the two-element chain lattice. Its only equivalence relations are equality and the universal relation, so these are its only congruences. Equality composes neutrally, and the universal relation composes as universal with either relation. All its congruences therefore permute.

Yet the monotonicity argument from Chapter 9 proves that it has no Malcev term in its lattice signature. There is no contradiction with the variety theorem: the variety generated by that algebra contains other algebras, including a three-element chain realised as a sublattice of a square of the two-element chain, whose congruences do not all permute.

The three-element sublattice can be written {00,01,11} with coordinatewise minimum and maximum. Its two adjacent-pair collapse congruences give the same failed reversal pattern. This provides an explicit witness beyond the original two-element algebra, showing why a theorem about an entire generated class cannot be inferred from one member's small congruence list.

Contents · Previous chapter · Next chapter

The forward implication is local and constructive: a term satisfying two identities produces the reversed witness in every congruence path. The converse at the variety level needs a way to turn the existence of witnesses into one uniform term. A free algebra supplies that bridge.

In a free algebra on generators x,y,z for the variety, consider the congruences generated by identifying x with y and y with z. The generators give a two-step path from x to z. If the variety is congruence-permutable, that path has an intermediate element in the opposite order.

Every element of the free algebra is represented by a term in its generators. Write the intermediate element as p(x,y,z). The two congruence memberships, interpreted through the corresponding generator identifications, yield the two required identities throughout the variety. Freeness supplies the uniformity that an arbitrary witness in one small algebra would lack.

This is an outline of the converse mechanism, not a replacement for the formal theorem and its quotient arguments in the references. Its role here is to explain why the hypothesis ranges over the whole variety and why a finite list of successful paths in one algebra is not enough.

The companion lesson on finite free algebras makes the universal-property part concrete through complete Boolean evaluation tables. Together the examples show two uses of terms: evaluating a known expression to produce a witness, and representing an abstract free-algebra element to obtain an expression with a class-wide property.

Contents · Previous chapter · Next chapter

Suppose we take the four-element chain and expand its signature by adding p(x,y,z)=x−y+z modulo 4 on the same labelled carrier. This new basic operation satisfies the Malcev identities. Therefore the expanded algebra has permuting congruences, even though the old lattice reduct did not.

The apparent conflict disappears because adding an operation can remove congruences. A partition must now be compatible with minimum, maximum and p. The old α partition {0,1},{2,3} fails the new requirement, so it is no longer a congruence of the expansion.

Check the failure directly. The inputs 0 and 1 are α-related. Keep the second input at 0 and the third at 1. Then p(0,0,1)=1 and p(1,0,1)=2 modulo 4. These outputs lie in different α-classes. Compatibility fails in a single coordinate replacement.

Thus the theorem applies to the congruences that remain compatible with the expanded signature, not to every partition that was once compatible with the reduct. One cannot retain the old nonpermuting pair as a counterexample after changing the operations that define congruence.

This example is a useful modelling check. Adding a powerful operation may provide new algebraic tools while invalidating old abstractions. If a quotient is supposed to survive an interface expansion, verify that its equivalence relation respects the new operation. The carrier staying unchanged does not protect the old quotient structure.

Contents · Previous chapter · Next chapter

First record the algebra's signature and the candidate term. Check that every operation symbol is permitted and every fixed element is either a designated constant or explicitly justified. A table supplied independently of the signature is not automatically a term operation, even if its two identity patterns look correct.

Second verify the identities. For a finite carrier of size n, direct testing checks p(x,y,y)=x and p(x,x,y)=y on all n² ordered pairs for each family. Record any failing pair. For a general class, give symbolic derivations using laws valid throughout that class.

Third check the relations in any worked example. They must be congruences of the full signature, not merely partitions or congruences of a reduct. Verify equivalence and compatibility. If they come from homomorphism kernels, identify the maps and establish their operation-preservation requirements.

Fourth calculate the proposed witness d=p(a,b,c) and verify both halves of the reversed path. Use different labels for the original and new intermediate elements. If a numerical check fails, inspect the operation convention, the identity order and the relation definitions before deciding that the theorem itself has failed.

Finally state the scope. A certificate may prove permutability for one algebra or uniformly for a variety. A single algebra's permuting congruences do not supply the converse term conclusion by themselves. The completed audit should make the quantifiers as visible as the arithmetic, because that is where many plausible overstatements begin.

Contents · Previous chapter · Next chapter

Use the additive group modulo 18. Let α mean equality modulo 3 and β mean equality modulo 2. Choose a=2, b=8 and c=11. Verify the original two-step path, calculate a reversed witness using p(x,y,z)=x−y+z, and identify the two classes whose intersection must contain that witness.

The first step holds because 8−2=6 is divisible by 3. The second proposed step does not hold: 11−8=3 is not divisible by 2. Therefore the supplied data do not satisfy the hypothesis. Computing p gives 5, but the theorem does not promise the reversed relations for an invalid starting path.

Repair only c by changing it to 14. Now 8 and 14 are β-related, so the path is valid. The formula gives d=2−8+14=8 modulo 18. The β-class of 2 is the even residues, and the α-class of 14 consists of residues congruent to 2 modulo 3. Their intersection contains 2,8,14.

The computed witness 8 belongs to that intersection. The witness is not necessarily unique: the theorem supplies one, not a claim that the class intersection has only one element. In this repaired example the original intermediate element also works in reverse, but that was not true in the earlier modulo-12 calculation.

For a second change, replace the candidate term by the first projection. It passes one identity and fails the other, so it is not a general certificate even if it happens to reverse a selected path. This exercise tests hypotheses, calculation and scope separately, rather than rewarding a formula substitution that ignores an invalid starting relation.

Contents · Previous chapter · Next chapter

Does permuting congruences mean their classes have equal sizes? No such requirement appears in the definition or witness proof. The property concerns reversal of two-step relation paths. Group congruence classes have additional size regularities from group structure, but those should not be imported into arbitrary algebras as part of the definition.

Must the reversed witness be unique? No. It lies in an intersection of two classes, which can contain several elements. A Malcev term selects a particular witness from the original triple. Different terms or different paths may provide different valid witnesses without changing the permutability conclusion.

Can I use a polynomial operation with fixed parameters? For a single algebra, polynomial operations preserve its congruences, so an operation with the two identities can support the same local witness argument. However, a parameter-dependent construction is not automatically the parameter-free term required for a uniform variety-level theorem. Keep the two claims separate.

Do all groups have a Malcev term? Yes, in the usual group signature the term xy⁻¹z works, including in noncommutative groups. The proof uses inverse cancellation and associativity. If the signature is reduced, verify that the necessary inverse and product functions remain term-definable before reusing that statement.

Why not just enumerate all congruence paths? For a small finite algebra, enumeration can verify a local property. A term certificate explains the mechanism and can work uniformly across infinitely many algebras. Neither approach should be advertised beyond its evidence: finite enumeration is local, while a uniform term requires identities valid throughout the claimed class.

Contents · Previous chapter · Next chapter

Start by writing the two path orders in words and symbols. Given finite partitions, find a failed reversal by intersecting the required classes. This trains you to distinguish absence of a witness from failure to notice a convenient one. Use the four-element chain to produce a complete impossibility check.

Next reconstruct the term witness proof without looking at the earlier derivation. Name the two triples compared under β, then the two compared under α. State which identity simplifies each endpoint. If you can explain every coordinate replacement, you understand why the construction works.

Then verify the group term in both additive and multiplicative notation. Test the incorrectly ordered multiplicative candidate with noncommuting permutations. This forces attention to algebraic laws rather than familiarity with a numerical formula where reordering happens to be harmless.

Finally compare the two-element lattice with the variety it generates. Explain why its own congruences permute, why monotonicity excludes a Malcev term, and how a small sublattice of its square reveals a nonpermuting example. The contrast is a compact test of whether your conclusion tracks the right quantifier.

The capability to retain is controlled reversal with a verifiable witness. A pair of ternary identities can turn an abstract existence question into a calculation, but only when the operation preserves the relations and the hypotheses actually hold. Keeping those obligations explicit lets you use the theorem confidently while recognising exactly where it stops.

Contents · Previous chapter · Continue to related reading