The Gold Standard of Universal Algebra | Using a Majority Term to Keep Congruence Paths Inside a Class

An algebra A consists of a nonempty carrier and specified total operations. A congruence on A is an equivalence relation compatible with every basic operation. Its classes describe identifications that permit well-defined quotient operations. Throughout this lesson, α, β and γ name congruences of one fixed algebra.

There are two levels of objects to track. Elements such as a,b,c belong to A. Relations such as α and β belong to the collection Con(A) of congruences. A statement about a and b being related is different from a statement comparing α and β as relations.

For a chain with minimum and maximum as operations, congruences partition the levels into intervals. One partition might merge the middle four levels while leaving the endpoints separate. Another might merge alternating neighbouring pairs. Both are relations on the same carrier, but they retain different distinctions.

We order congruences by inclusion as sets of related pairs. A smaller congruence identifies fewer pairs and therefore retains more distinctions. Equality is the least congruence; the universal relation identifying every pair is the greatest. This ordering can feel opposite to an informal use of “more information,” so keep the pair interpretation explicit.

The theorem we will prove is a law in this ordered collection of congruences. It is not initially a law about the original elements or their basic operations. Keeping those levels separate prevents a major misunderstanding: congruence distributivity does not mean that every algebra has an operation called multiplication distributing over an operation called addition.

Contents · Next chapter

The meet α∧β is their intersection. A pair belongs to it precisely when the pair is both α-related and β-related. Intersections of congruences remain congruences: reflexivity, symmetry, transitivity and operation compatibility hold in each relation and therefore hold simultaneously in their intersection.

The join β∨γ is the least congruence containing both. It is generally larger than the raw union. If a β b and b γ c, the join must relate a to c by transitivity even when neither original relation directly relates that pair. The join adds whatever is needed to connect such steps.

For two congruences, belonging to the join can be described by a finite path of β-steps and γ-steps. Repeated steps of the same relation can be combined, and reflexive steps may be inserted, so the presentation of the path is not unique. Its endpoints, rather than its exact length, determine the membership question.

Why is this path relation compatible with operations? Change one input coordinate along its path while keeping the other coordinates fixed. Compatibility with each step gives a corresponding path between outputs. Repeat for every input coordinate. This places the final output pair in the same path relation and proves the required closure.

Thus meet asks for two constraints at once, while join allows finite travel using either relation. The distributive statement will compare applying an α-constraint after such travel with insisting that each allowed step already respects α. The difference between those two descriptions is precisely where the majority construction does its work.

Contents · Previous chapter · Next chapter

A ternary majority term M satisfies M(x,x,y)=x, M(x,y,x)=x and M(y,x,x)=x for all x and y. Each possible position of the exceptional input is covered. When two inputs agree, the output is their repeated value. Setting y=x also gives M(x,x,x)=x.

The word term means an expression constructed from the algebra's declared basic operations and variables. If minimum and maximum are available, a median expression is a term. An arbitrary three-input function placed beside an algebra is not automatically a term of that algebra, even if its table has the required repeated-input outputs.

Majority identities do not completely specify the output when all three inputs are distinct. A chain median picks the middle value, but a different majority operation may behave differently on distinct triples. The general proof uses only the three repeated-input identities and compatibility, rather than assuming an undeclared ordering.

All three positions matter. A first projection M(x,y,z)=x passes M(x,x,y)=x and M(x,y,x)=x, but fails M(y,x,x)=x when x and y differ. Testing only two patterns would falsely accept this candidate. Diagonal tests alone are even weaker: every projection passes them.

Before attempting the path construction, write the three equations and verify each in the intended algebra. In a finite carrier, check every pair of values for each pattern. In a general structure, give a symbolic argument. Calling a function “majority-like” is not a substitute for the identities that the proof actually uses.

Contents · Previous chapter · Next chapter

Suppose two input tuples are coordinatewise α-related. A basic operation sends them to α-related outputs by the definition of congruence. The same property extends to every term because a term is a finite composition of those basic operations, variables and any named constants.

At a variable leaf, the related-input assumption supplies the required pair. At a constant leaf, the two evaluations are equal and hence related by reflexivity. At an operation node, the inductively related values of its input subterms give related outputs. Following this argument to the root proves compatibility of the whole term.

For the path repair, we will often change only the middle input of M. If c β d, then M(a,c,b) β M(a,d,b), since the first and third coordinates are unchanged and therefore β-related to themselves. This preserves the label of a β-step exactly. The same argument works for γ.

We will also change an endpoint input using α. If a α b, compare M(a,c,b) with M(a,c,a). Compatibility gives an α-relation between those outputs. A majority identity then reduces the second output to a. This is the step that forces every transformed intermediate value into the desired class.

An arbitrary majority function need not preserve the algebra's congruences, so its repeated-input table alone does not justify these moves. The term requirement connects the identities to the existing operations. Alternatively, a separately proved congruence-preserving function could support a local argument, but that additional proof must be supplied rather than silently assumed.

Contents · Previous chapter · Next chapter

Assume a α b and choose a finite path c0=a,c1,…,ck=b in which every adjacent pair is β-related or γ-related. Define di=M(a,ci,b) for every position. The proposed new path is d0,d1,…,dk. It has the same number of positions, although several successive values may collapse to one.

The first endpoint is fixed because d0=M(a,a,b)=a. The last is fixed because dk=M(a,b,b)=b. The second equality is the majority pattern with b repeated. Thus the construction does not merely find some path in the right region; it retains the original endpoints exactly.

For each i, compare M(a,ci,b) with M(a,ci,a). Since b α a, compatibility gives di α M(a,ci,a). The identity with repeated first and third input makes the latter value a. Therefore every di lies in the α-class of a, regardless of whether ci did.

If ci β ci+1, compatibility in the middle coordinate gives di β di+1. Both transformed values are also α-related, because each is α-related to a. Thus this edge belongs to α∧β. A γ-edge similarly becomes an edge in α∧γ.

We have converted a path using β and γ between α-related endpoints into a path using their intersections with α. No ordering, numerical formula or finiteness of A was required. The construction follows directly from the term identities and congruence compatibility, which makes it reusable across very different algebras.

Contents · Previous chapter · Next chapter

Suppose the pair (a,b) belongs to α∧(β∨γ). This supplies two pieces of information: a α b and a path from a to b using β and γ. The previous chapter transforms that path into one using α∧β and α∧γ. Therefore (a,b) belongs to (α∧β)∨(α∧γ).

This proves the less immediate inclusion α∧(β∨γ)⊆(α∧β)∨(α∧γ). It is a statement about every pair in the relation on the left, not a claim based on one chosen numerical example. The endpoint-and-path construction explains why the inclusion holds uniformly.

The reverse inclusion is straightforward. Both α∧β and α∧γ are contained in α, and both are contained in β∨γ. Their join is therefore contained in each of those upper bounds and hence in the intersection α∧(β∨γ). Combining the inclusions gives equality.

The resulting law is α∧(β∨γ)=(α∧β)∨(α∧γ). Since α,β,γ were arbitrary congruences, Con(A) is a distributive lattice. This is the precise conclusion for an algebra possessing a majority term. If one term satisfies the identities throughout a variety, every member has this conclusion.

The proof also gives more than an abstract equality symbol: from a supplied witness path on the left, it produces a witness path on the right. That constructive feature is useful for learning and finite verification. A reader can calculate every intermediate di and check the exact relation used on each new edge.

Contents · Previous chapter · Next chapter

Let A={0,1,2,3,4,5}, ordered as written, with minimum and maximum as basic operations. Define α with blocks {0}, {1,2,3,4}, {5}. Define β with blocks {0,1}, {2,3}, {4,5}. Define γ with blocks {0}, {1,2}, {3,4}, {5}.

These are genuine congruences because every block is an interval. The map sending each level to its block, ordered from bottom to top, is order-preserving. Between chains, an order-preserving map preserves minimum and maximum: the smaller input has the smaller or equal image, and similarly for the larger input.

This argument establishes compatibility with both operations rather than merely noting that the displayed blocks form partitions. A partition with noninterval blocks can fail. If 0 and 2 were identified while 1 remained separate, applying minimum with 1 would identify 0 with 1, contradicting that proposed partition.

Our endpoints will be a=1 and b=4. They are α-related because both lie in the middle α-block. The relations β and γ provide several routes between them, including routes that take unnecessary excursions through 0 or 5. Those excursions make the repair mechanism visible.

Keep the three block lists beside the calculation. Relation membership can then be checked by locating both values in a common block. This is more reliable than relying on an imagined diagram, especially when the same number participates in different blocks under different congruences. The labels α,β,γ identify relations, not three interchangeable meanings of equality.

Contents · Previous chapter · Next chapter

On a chain, define M(x,y,z)=max(min(x,y),min(x,z),min(y,z)). The output is the middle of the three values. If two inputs equal x, one minimum is x and the others are no larger than x, so the maximum is x. This verifies the repeated-input identities directly.

With endpoints 1 and 4, the unary map c↦M(1,c,4) sends 0 to 1, keeps 1,2,3,4 unchanged, and sends 5 to 4. It clamps a level into the interval from 1 to 4. The numerical description is specific to this chain example; the earlier general proof did not require a clamp or even an order.

Now use the path 1 β 0 β 1 γ 2 β 3 γ 4 β 5 β 4. Every displayed edge can be verified from the block lists. Its endpoints are 1 and 4, but it visits 0 and 5, which lie outside their α-class.

Applying the clamp to every value gives 1,1,1,2,3,4,4,4. The transformed path remains in {1,2,3,4}. The original β-edges at the extremes become reflexive edges, while the central edges retain their β or γ membership. Deleting repeated values leaves the simpler path 1 γ 2 β 3 γ 4.

The simplification is optional. The theorem only needs a valid finite path, and reflexive edges are valid. What matters is that the path's endpoints and edge permissions have been retained while every intermediate value now satisfies the α-constraint. This is an explicit calculation of the abstract transformation from Chapter 5.

Contents · Previous chapter · Next chapter

We can verify the distributive equality in this example without following just one pair. The join β∨γ is the universal relation. Across the chain, the adjacent pairs 0–1,2–3,4–5 belong to β, while 1–2 and 3–4 belong to γ. Together they connect all six levels.

Therefore α∧(β∨γ)=α∧∇=α, where ∇ denotes the universal relation. The left-hand partition is {0}, {1,2,3,4}, {5}. This calculation uses the complete connectivity pattern, not just the fact that the selected endpoints 1 and 4 can be joined.

For α∧β, only the nontrivial β-block {2,3} remains merged inside an α-block. The result has blocks {0},{1},{2,3},{4},{5}. The β-merges 0–1 and 4–5 are removed because their endpoints belong to different α-blocks.

For α∧γ, the blocks are {0},{1,2},{3,4},{5}. Taking the join of these two intersections connects 1 to 2, then 2 to 3, then 3 to 4. Neither 0 nor 5 gains a connection to that middle block. The resulting partition is exactly α.

Thus both sides agree as relations on every pair of the six-element carrier. The transformed path provides a witness-level explanation, while the partition calculation confirms the complete equality for these three selected congruences. Neither finite check alone would prove the theorem for all algebras; the majority-term argument provides that broader justification.

Contents · Previous chapter · Next chapter

We have shown that interval partitions of a chain are congruences for minimum and maximum. The converse also holds. Suppose a congruence identifies u with v and u≤w≤v. Apply minimum with the fixed element w to the related pair u,v. The outputs are u and w, so u is related to w.

Transitivity then puts every intermediate w in the same class. Hence every congruence block is an interval. This characterizes all congruences of a finite chain lattice, rather than merely producing some convenient examples. It also gives a short diagnostic for rejecting an invalid proposed block list.

For six levels there are five adjacent boundaries. At each boundary, choose whether to merge the two neighbouring levels across it. A chosen set of merged boundaries determines interval blocks by connectivity. Every interval partition arises exactly once this way, so there are 2⁵=32 congruences.

In this encoding, meet corresponds to intersecting the sets of merged boundaries, and join corresponds to taking their union. The set identities for intersection and union therefore give a second proof that this particular congruence lattice is distributive. The encoding makes all 32 relations manageable without printing 32 large pair tables.

This alternative proof is deliberately narrower than the majority theorem. It relies on the original carrier being a finite chain and on its operations being minimum and maximum. A general majority algebra may have no useful boundary encoding. Comparing the two proofs trains you to retain the scope attached to each method rather than treating a convenient representation as universal.

Contents · Previous chapter · Next chapter

When A itself is a lattice, two different uses of meet and join can appear. Its elements have lattice operations, often written ∧ and ∨. Its congruences also form a lattice, whose meet and join are operations on relations. The notation is similar, but the objects being combined are different.

The majority-term theorem concerns Con(A). It does not assume that the original lattice A is distributive. In any lattice, the term M(x,y,z)=(x∧y)∨(x∧z)∨(y∧z) satisfies the majority identities using absorption. For instance, substituting x,x,y gives x∨(x∧y)∨(x∧y)=x.

The other repeated-input patterns reduce in the same way. Thus lattice congruences are distributive even when the original lattice fails the element identity x∧(y∨z)=(x∧y)∨(x∧z). There is no contradiction, because that failed equation and the congruence equation belong to different carriers.

To see the distinction, consider the five-element diamond lattice with bottom 0, top 1 and three incomparable middle elements p,q,r. Its element calculation gives p∧(q∨r)=p∧1=p, while (p∧q)∨(p∧r)=0∨0=0. The lattice itself is not distributive.

Nevertheless its majority term still satisfies the three repeated-input equations by absorption, so its congruence lattice has the theorem's distributivity property. This example is a useful guard against a misleading verbal shortcut. Say “the congruence lattice is distributive,” naming what is being distributed, rather than simply declaring an unspecified algebra “distributive.”

Contents · Previous chapter · Next chapter

A Malcev term p satisfies p(x,y,y)=x and p(x,x,y)=y. A majority term gives the opposite repeated-input outputs in those two patterns: M(x,y,y)=y and M(x,x,y)=x. The formulas are not interchangeable, even though both involve ternary terms and congruence paths.

The Malcev construction begins with a two-step path a α c β b and finds a path with the order reversed. The majority construction begins with α-related endpoints and a path using other relations, then moves that path into one α-class. Its output preserves edge types rather than reversing their order.

Our six-level chain illustrates the distinction. It has a majority term. But its congruences need not permute. Let δ have blocks {0,1},{2},{3},{4},{5}, and ε have blocks {0},{1,2},{3},{4},{5}. There is a δ-then-ε path 0 δ 1 ε 2.

A reversed path would need an intermediate value ε-related to 0, which forces that value to be 0. But 0 is not δ-related to 2. Thus reversal fails despite the available majority term. This directly refutes the claim that majority identities also supply the Malcev conclusion.

Conversely, a Malcev term alone does not promise the majority identities or congruence distributivity. The companion article develops its correct scope. A practical comparison should name the task first—reverse a path, constrain a path, or describe a join—then choose the term condition that actually proves that task.

Contents · Previous chapter · Next chapter

Having a majority term is sufficient for the congruence lattice to be distributive. The converse is not justified merely by inspecting one algebra. A small congruence lattice can satisfy the distributive law for reasons that do not supply any majority term in the available signature.

Consider the additive group with two elements, using addition modulo two, inverse and zero. Its only congruences are equality and the universal relation, so its congruence lattice has two elements and is distributive. We can nevertheless prove directly that no majority term exists in this group language.

Every ternary term operation has the form ax+by+cz modulo two, where each coefficient is zero or one. This follows by induction on the term: zero contributes no variables, addition adds coefficients modulo two, and inverse has no effect in this group. Repeated occurrences are counted modulo two.

If such a term were majority, M(x,x,y)=x would force c=0 and a+b=1. The identity M(x,y,x)=x would force b=0 and a+c=1. The identity M(y,x,x)=x would force a=0 and b+c=1. The three forced zero coefficients contradict these required sums.

Thus distributivity of one algebra's congruence lattice does not reverse the term implication. More general characterization theorems for whole varieties require their own hypotheses and term systems. The present lesson proves one sufficient condition and its constructive mechanism. It does not advertise that condition as an automatic equivalence at either the single-algebra or general variety level.

Contents · Previous chapter · Next chapter

Suppose an algebra already has a majority term and we expand its signature by adding another basic operation. The old term remains an available expression and keeps its identities on the same carrier. Therefore the expanded algebra still has a majority term, provided the old operations have not been changed.

However, the expanded algebra may have fewer congruences. A relation must now preserve the new operation as well as all the old ones. An old congruence that fails this extra compatibility check can no longer be used as input to the theorem in the expanded signature.

For a concrete change, add a unary operation f to our chain, with f(0)=0, f(1)=0, f(2)=5, f(3)=5, f(4)=5 and f(5)=5. The old α relates 1 to 2, but their outputs 0 and 5 lie in different α-blocks. Thus α is not a congruence of the expansion.

Minimum and maximum still define the same majority term. Its theorem applies to whatever congruences remain compatible with f. There is no conflict between the continued existence of the term and the disappearance of an old partition: the objects quantified over by “every congruence” have changed.

If instead an old basic operation is replaced, even the majority expression may need rechecking. A formula built from changed operations can become a different function. Keep three changes separate: adding operations, removing operations and altering operations. Each affects available terms or compatible relations in a different way, so each requires an explicit new contract.

Contents · Previous chapter · Next chapter

Start by verifying the operation tables and the three candidate congruences. Check equivalence and compatibility with every basic operation. If the relations are kernels of verified homomorphisms, record those maps and their preservation checks. A majority calculation cannot rescue a partition that was never a congruence of the declared algebra.

Next verify the term expression and all three majority identities. For a carrier of size n, there are n² pairs for each identity pattern. These tests are much smaller than evaluating every possible long path, but their significance comes from the general proof connecting the identities to arbitrary paths.

Check the supplied endpoints a,b are α-related. Check every edge of the original path against its stated β or γ label. Then calculate di=M(a,ci,b) at each position. The report should display the original value, transformed value and relation used for the following edge.

Finally verify that the first and last values are unchanged, every transformed value belongs to the α-class of a, and each new edge lies in the appropriate intersection. If a check fails, retain the first failed row. It can reveal an invalid starting path, an incorrect term evaluation or a relation incompatible with the chosen signature.

For the complete six-level example, an additional exhaustive check can enumerate all 32 interval congruences and all triples of them. That verifies the distributive law locally across 32³ choices. It is useful corroboration, but the symbolic proof is what extends the conclusion beyond this finite chain to every algebra with the required term.

Contents · Previous chapter · Next chapter

Change the chain to {0,1,2,3,4,5,6}, still with minimum and maximum. Let α have blocks {0,1},{2,3,4,5},{6}. Let β have blocks {0},{1,2},{3,4},{5,6}, and γ have blocks {0,1},{2,3},{4,5},{6}. All blocks are intervals, so these are congruences.

Use endpoints a=2 and b=5, and the path 2 β 1 β 2 γ 3 β 4 γ 5 β 6 β 5. Before calculating the term, verify the endpoint condition and every edge. The path leaves the desired α-class at values 1 and 6.

The transformed values M(2,c,5) clamp c to the interval from two to five. The new sequence is 2,2,2,3,4,5,5,5. It stays in the middle α-block, fixes both endpoints and preserves the stated β or γ label on every edge. Removing repeats leaves 2 γ 3 β 4 γ 5.

Now deliberately change only the final endpoint to 6 while leaving α unchanged. The new endpoints 2 and 6 are not α-related. The general theorem no longer promises a path entirely inside one α-class joining them. Indeed such a path cannot exist, since its two endpoints lie in different classes.

This failed variation is as useful as the successful one. The formula still produces outputs if you substitute the new endpoint, but a computable formula is not a theorem without its hypotheses. A complete transfer answer identifies the violated endpoint condition before interpreting any resulting numbers as a successful class-preserving repair.

Contents · Previous chapter · Next chapter

Must a majority operation choose one of its inputs when all three differ? The defining identities do not impose that rule. They control repeated-input cases. The chain median does choose an input, but the general proof needs only the stated identities and congruence preservation, not an additional choice property on distinct triples.

Does the transformed path always become shorter? Not necessarily. The construction gives the same sequence length before repeated values are removed. Some steps may collapse, as in the chain example, but the theorem concerns relation membership rather than shortest paths. A minimal-length path would require a separate optimization problem.

Why is the middle argument allowed to vary freely? The endpoint relation a α b lets us compare M(a,c,b) with M(a,c,a) for any c. The latter is always a by one majority identity. That comparison forces the output into the class even when c itself is outside it.

Can I use an arbitrary median on a labelled set? Only after checking compatibility with the relations you use. A set of numerical labels may carry operations unrelated to their order. The order median is a term for chain minimum and maximum, but it need not preserve congruences of some different algebra on the same labels.

Does this prove every distributive congruence lattice comes from a majority term? No. The two-element group example disproves that reverse inference for one algebra. The lesson establishes a sufficient term condition and a constructive proof. Stronger classification claims must be read with their exact quantifiers and hypotheses in the mathematical references.

Contents · Previous chapter · Next chapter

First take the six-level example and reconstruct its three partitions. Verify their interval property and evaluate the median on the two endpoint values and each intermediate level. Produce the transformed path without consulting its listed answer. A correct calculation should make every retained relation visible.

Next compute α∧β, α∧γ and β∨γ as full partitions. Compare the resulting two sides of the distributive law. This connects a single witness path with a statement about all pairs in the selected relations, preventing the example from becoming a collection of unexplained median values.

Then reproduce the general proof in words. Explain why endpoints stay fixed, why intermediate outputs enter one class, and why each edge keeps its old relation. Name the majority identity or compatibility fact at each step. These three obligations are the mechanism; a memorised final equality omits the useful reasoning.

Finally compare the majority and Malcev tasks, and test the added-operation example. Explain why a term can remain available while an old congruence disappears. This checks whether the proof is attached to the actual operations and relations, rather than to labels that happened to work in an earlier model.

The lasting skill is controlled transformation of a witness. Instead of merely asserting that a relation inclusion holds, you can start with evidence on one side and manufacture evidence on the other. The majority identities make that transformation possible, and the explicit hypotheses tell you when the construction can safely be carried into a new algebra.

Contents · Previous chapter · Continue to related reading