The Gold Standard of Universal Algebra | Using Jónsson Term Chains When No Majority Term Exists

A majority term gives an elegant way to keep a congruence path inside one class. Does every algebraic setting with distributive congruences have to contain such a term? The answer is no. Several terms can cooperate through matching endpoint identities even when no individual term can perform all three majority tasks. The cooperation is captured by a Jónsson term chain.

Our concrete example begins with just two values, zero and one, and one ternary operation. We will construct five terms, check their identities, and then prove that no majority term can be built from the operation. Both conclusions concern the same declared signature. This matters: silently adding another Boolean operation would change the question and could make majority available.

The practical reader job is to inspect a certificate made of several formulas. You will learn which equations connect neighbouring formulas, why their input patterns alternate, and how the connections support a path argument. A complete ten-function calculation will provide an independent check of the small example. Later we will change the underlying values and the available operations to test what survives.

This is a mathematical lesson about exact operations and equivalence relations. The word majority refers to three repeated-input identities, not an assertion about voting systems or social decisions. Likewise, a term chain is a finite list of formulas with specified links; the word chain does not by itself say that their outputs increase in an order. Keeping these meanings separate lets the calculations explain the terminology.

Contents · Next chapter

Use the carrier A={0,1}, ordered by zero less than one. Define b(x,y,z)=x∧(y∨z), where meet means minimum and join means maximum. Only b is a basic operation of our algebra. The meet and join notation describes its table; it does not automatically permit us to use both operations separately in a term.

For example, b(1,0,1)=1 and b(0,1,1)=0. The first input controls whether the output can be one. When that input is zero, the output is zero regardless of the other inputs. When it is one, at least one of the other two inputs must be one for the output to be one.

A term is built from variables by repeatedly applying b. The expression b(x,y,y) is allowed. It computes x∧y, so binary meet is available as a derived operation. By contrast, writing x∨y does not exhibit a b-term for join. We will later prove that join cannot be obtained in this signature.

There are no named constant operations here. An assignment may give a variable the value zero, but that is different from permitting a constant-zero symbol inside a formula. Every term built from b is idempotent: assigning the same value a to every variable returns a. This follows first for variables, and then through each b-node because b(a,a,a)=a. In particular, no such term is the constant-zero or constant-one function. Record the signature beside the carrier before making any claim about expressibility.

Contents · Previous chapter · Next chapter

Write a chain as d0,d1,…,dn, with every term regarded as having the three input positions x,y,z. The first term must return x and the last must return z. Every term must also satisfy di(x,y,x)=x. This common repeated-endpoint identity is the part that will keep transformed paths inside a chosen congruence class.

The remaining equations connect adjacent terms. When i is even, require di(x,x,z)=d(i+1)(x,x,z). When i is odd, require di(x,z,z)=d(i+1)(x,z,z). The notation d(i+1) means the next indexed term, not multiplication. Our indexing starts at zero, so the first join between terms is an even-index join.

It helps to call the patterns x,x,z and x,z,z the left and right endpoint patterns. Adjacent terms agree at the left pattern, then the right pattern, then the left again, and so on. They are not required to agree for arbitrary triples. Requiring that stronger equality would erase the movement from the first projection to the last.

These are identities, so every permitted choice of the displayed variables must satisfy them. Testing one triple is insufficient. In a finite algebra, a complete table can check the equations; for a whole class, an algebraic derivation can establish them uniformly. We use both kinds of evidence, with their scopes stated separately. Also distinguish the number n from the number of listed terms: d0 through dn contains n+1 formulas, including the two endpoint projections.

Reference: Burris and Sankappanavar, Theorem 12.6: Jónsson terms.

Contents · Previous chapter · Next chapter

Take d0(x,y,z)=x, d1(x,y,z)=b(x,y,z), d2(x,y,z)=b(x,z,z), d3(x,y,z)=b(z,y,x), and d4(x,y,z)=z. In meet-and-join notation the middle three functions are x∧(y∨z), x∧z, and z∧(y∨x). Every formula is legal using b alone, with the projections supplied by variables.

The terms have different roles. The first middle term starts from x and can move down towards the meet of x and z. The central term supplies that common meeting value. The third can move from the meeting value towards z. This order description is useful for this particular construction; the general definition of a Jónsson chain does not require an underlying lattice order.

Check the common endpoint identity first. Substituting z=x into d1 gives x∧(y∨x)=x. For d2 it gives x∧x=x. For d3 it gives x∧(y∨x)=x again. The projections also return x. Thus all five terms satisfy di(x,y,x)=x.

Notice the direction of the calculation. We are checking a proposed certificate, not deriving its correctness from its name. A list of five ternary formulas is not automatically a Jónsson chain. The endpoint equations, the common repeated-endpoint equations and all four adjacent links must hold together. Keeping these families separate makes it easier to find the exact failure if a formula is altered. It also prevents a successful check of d1 from being mistaken for a successful check of the whole list.

Contents · Previous chapter · Next chapter

At the first link, i=0 is even. Substituting x,x,z into d0 gives x, and into d1 gives x∧(x∨z)=x. The two values agree. This link establishes how the chain leaves the first projection while retaining its required left endpoint.

At i=1 use the right pattern x,z,z. The value of d1 is x∧(z∨z)=x∧z. The value of d2 is also x∧z. At i=2 return to the left pattern x,x,z. Here d2 gives x∧z, while d3 gives z∧(x∨x)=z∧x, the same value.

At i=3 use the right pattern again. The value of d3(x,z,z) is z∧(z∨x)=z. This agrees with d4(x,z,z). The four checks complete the certificate. They use lattice absorption, idempotence and commutativity of meet, all valid for our Boolean minimum and maximum.

Do not substitute the wrong endpoint pattern merely because the resulting expression is familiar. For example, d0 and d1 need not agree at x,z,z: with x=1,z=0 their values are one and zero. That disagreement does not invalidate the first link, because the first link requires agreement at x,x,z. It shows why the alternating specification matters. An audit should record the index, its parity, the substitution pattern and the two resulting expressions. Those four pieces of information distinguish a genuine failure from a test of an equation that was never required.

Contents · Previous chapter · Next chapter

Suppose a chain had only d0=x, d1=m and d2=z under the same convention. Its first adjacent equation would say m(x,x,z)=x. Its second would say m(x,z,z)=z. The common endpoint equation would say m(x,y,x)=x. Renaming variables in the second equation supplies m(y,x,x)=x. These are precisely the three majority identities.

Thus a chain with one middle term combines all three repeated-input jobs in that one operation. A longer chain distributes the endpoint connections among several operations. It is not legitimate to take any one middle operation from a longer certificate and assume it inherits the complete majority condition.

Our d1 already gives a direct warning. Although d1(x,x,z)=x and d1(x,y,x)=x, it fails the remaining majority equation. Indeed, d1(0,1,1)=0, whereas majority would have to return one. The first input can block the other two repeated values. The third middle term fails a different majority test because its controlling input is z.

This distinction concerns existence, not merely how a formula is written. A clever composition of b-terms might conceivably repair the failure of d1. To rule out majority entirely, we need an argument covering every possible term, including arbitrarily deep compositions. The next chapters supply both a structural obstruction and a complete finite calculation. Failure of the three displayed middle terms alone would not establish the stronger conclusion.

Contents · Previous chapter · Next chapter

For any b-term, follow the first child whenever you encounter a b-node in its expression tree. Eventually you reach a variable. Call this a bounding variable for that written term. The output of the term is always at most the value of that variable in our Boolean order.

Here is the induction. A variable term equals itself, so it is bounded by that variable. If a term is b(t1,t2,t3), its output is at most t1 because b(u,v,w)=u∧(v∨w)≤u. If t1 is already bounded by a particular variable, the whole term is bounded by that variable too. The argument continues through any finite expression tree.

For example, consider t=b(b(y,x,z),b(z,x,x),x). Following first children reaches y. Consequently t≤y on every assignment, even though x appears several times and z appears in both inner branches. Frequency of a symbol is irrelevant to this bound. Set y=0 and the output must be zero; no choices of x or z can override it.

A function may admit more than one bounding variable, and different expressions for the same function may expose different choices. We only need the existence of at least one. This is an invariant of what can be built: every legal construction leaves some input with veto power over an output of one. A candidate function having no such input cannot be represented by any b-term. This converts an endless search through formulas into a finite kind of obstruction.

Contents · Previous chapter · Next chapter

Assume a ternary b-term m were a majority operation. The preceding argument gives it a bounding input position. Assign zero to that position and one to the other two positions. The bound forces m to output zero. The majority identity for that exceptional position forces it to output one. The contradiction excludes every ternary b-term at once.

The same reasoning works for a near-unanimity term with any arity at least three. Such an operation must return one whenever all but one of its inputs are one. Place the single zero at a bounding position. The term bound still forces zero, contradicting the required recovery of the repeated value.

This is stronger than observing that the basic operation b is not majority. Composition cannot evade the bound because the bound was proved by induction over every composition. That logical step is essential whenever an algebraic property asks for a term rather than for a basic operation. Basic-operation tables alone may conceal capabilities that arise through composition; here we have proved that the particular capability never arises.

The argument uses the two distinct values zero and one and their order, so the one-element algebra is not a counterexample to it. On a one-element carrier all repeated-input requirements agree automatically. It also uses the declared operation language. Adding a new operation can break the induction, because a new kind of expression node needs its own bounding argument. We will exploit that controlled change later rather than transferring the obstruction to an expanded signature without proof.

Contents · Previous chapter · Next chapter

The Boolean example admits a second certificate. Every b-term is monotone in its inputs: increasing input values cannot decrease its output. This holds for b because minimum and maximum are monotone, and composition preserves the property. Every term is also idempotent and has a bounding variable. Together these restrictions give a short complete list of ternary functions.

Suppose x is a bounding variable for a function f. When x=0, f=0. When x=1, the remaining function of y,z is monotone and takes value one at y=z=1, by idempotence of f. Its possibilities are 1, y, z, y∧z and y∨z. These are the five nonzero monotone Boolean functions of two variables. Therefore f is x, x∧y, x∧z, x∧y∧z or x∧(y∨z).

Allowing y or z as a bounding variable and removing repetitions leaves ten functions: three projections; the three pairwise meets; the triple meet; and the three functions obtained by choosing the controlling variable in x∧(y∨z). Every member is constructible using b. Pairwise meet is b(x,y,y), triple meet is an iteration of that derived meet, and the other three are permutations of b.

This establishes completeness in both directions. The restrictions exclude any other function, while explicit terms produce every listed function. A restriction alone would give only an upper bound, and a list of formulas alone would give only a lower bound. The coincidence of the two is what makes this a complete enumeration, rather than a collection of plausible examples.

The short list of two-variable functions can itself be verified. Write the four outputs of a monotone function g in order 00,01,10,11. We require the last output to be one. If the first is one, monotonicity forces all four to be one. If the first is zero, the middle two outputs can be 00,01,10 or11. These choices give y∧z, y, z and y∨z, with the middle two projection names depending on the stated row order. That accounts for all five possibilities without appealing to an unlisted classification theorem.

The ten-function count removes duplicates deliberately. The function x∧y appears both when x is chosen as a bound and when y is chosen as a bound. The triple meet appears under all three choices. Counting five functions for each possible bounding variable would therefore overcount the same functions and produce fifteen rather than ten. The complete column representation is a simple way to detect these repeated descriptions.

Contents · Previous chapter · Next chapter

Fix assignment order 000,001,010,011,100,101,110,111. A ternary Boolean function is now an eight-entry column. The projection x has column 00001111. The basic operation b(x,y,z) has column 00000111: it becomes one at 101,110 and111, and nowhere else. Majority has column 00010111, differing from b at 011.

The small difference between those two columns is decisive. At 011 the first input is the exceptional zero, so b returns zero and majority returns one. A function comparison is an exact comparison of all entries, not a judgement about how many rows agree. Seven agreements do not establish the eighth.

For an exhaustive construction, start with the three projection columns. Repeatedly combine any three stored columns by b row by row. Retain a formula whenever a new column appears. Stop only when every ordered triple of stored columns produces a stored column. The result must be the ten functions proved in the previous chapter. At that point, absence of the majority column is a finite expressibility certificate.

A completed closure check has one thousand ordered triples of stored functions to test, because each of the three argument positions independently selects one of ten columns. Repeated choices must be included: they produce derived operations such as meet. Store a witness expression with every column so that the calculation certifies reachability as well as closure. Merely finding a closed ten-element collection containing the projections would establish an upper bound unless its members were also shown reachable.

There are 256 possible eight-bit columns in the full function space, but only ten are reachable in this signature. Keeping the full space separate from the generated collection prevents the assumption that every Boolean table is automatically a term. The exhaustive calculation supplements the bounding-variable proof; it does not replace the reason the obstruction survives arbitrary term depth. That reason remains useful when the carrier changes and complete enumeration becomes less convenient.

Contents · Previous chapter · Next chapter

Let α,β,γ be congruences of an algebra carrying a verified Jónsson chain. Suppose a and c are α-related and can be connected by a finite path whose steps are β-related or γ-related. Such a path witnesses membership in β∨γ. Its intermediate points need not belong to the α-class containing the two endpoints.

Write the path as a=u0,u1,…,ur=c. For each term di, transform the entire path into a row of values di(a,uj,c). Compatibility of a congruence with basic operations implies compatibility with terms, by induction through the term expression. Therefore each transformed step retains the original β or γ relation.

Every transformed value is also α-related to a. Indeed, replace the last argument c by a using a α c. Compatibility gives di(a,uj,c) α di(a,uj,a), and the common endpoint identity makes the latter value a. Thus every transformed row lies inside the chosen α-class, including its two endpoints.

The original problem has now become an endpoint-connection problem. Each row is a path made of α∩β and α∩γ steps, but different rows can begin and end at different elements. The alternating adjacent identities explain how to connect those rows without leaving the class. This is the extra mechanism beyond a single majority term: no one row must have both original endpoints, because neighbouring rows provide the necessary handoffs.

Contents · Previous chapter · Next chapter

Let Li=di(a,a,c) and Ri=di(a,c,c), the left and right ends of row i. The even-index equation says Li=L(i+1) when i is even. The odd-index equation says Ri=R(i+1) when i is odd. These equalities alternate between the two ends of the rows.

Start at a, which is every entry of row zero because d0 is the first projection. The first left-end equality reaches row one. Traverse that row from left to right. Its right endpoint agrees with row two's right endpoint, so traverse row two in reverse. The next left-end equality reaches row three, which can be traversed forwards. Continue this zigzag until reaching the last row, whose entries all equal c.

Reversing a row is legitimate because congruences are symmetric. It does not reverse the operation b or assume that β and γ commute. We are walking along a previously valid sequence of equivalence steps in the opposite direction. The distinction matters: a path reversal justified by symmetry is different from a theorem about rearranging the order of two different congruences.

Consequently a and c lie in (α∩β)∨(α∩γ). This proves the difficult containment in the distributive law α∩(β∨γ)=(α∩β)∨(α∩γ). The reverse containment follows because each of α∩β and α∩γ is contained in α and in β∨γ. The proof works in every algebra where the displayed term identities hold. A uniform chain throughout a variety therefore establishes congruence distributivity throughout that variety.

Contents · Previous chapter · Next chapter

For a concrete calculation, take triples of values in {0,1,2,3}×{0,1,2,3}×{0,1}. Apply b coordinatewise, using minimum and maximum in each coordinate. Let α mean equality of the third coordinate, β equality of the first, and γ equality of the second. These are kernels of coordinate projections, so they are congruences.

Choose a=(3,0,0), u=(3,3,1) and c=(0,3,0). The endpoints are α-related, while u is outside their α-class. Nevertheless a β u γ c: the first step preserves the first coordinate, and the second preserves the second. We want a replacement path staying in third coordinate zero.

Put q=(0,0,0). Under d1 the three input-path positions produce a,a,q. Under d2 all three produce q, because d2 ignores its middle input. Under d3 they produce q,c,c. Following the row connections yields a path from a to q to c, with harmless repeated points if we keep the full list.

The step a to q preserves the second coordinate and the third, so it belongs to α∩γ. The step q to c preserves the first coordinate and the third, so it belongs to α∩β. The intermediate point q stays inside the α-class. Here the resulting colour order happens to be reversed after repeated points are removed; that feature of this example is not a general permutability conclusion. What the chain guarantees is a finite path using the two restricted congruences. Keep the guarantee distinct from additional simplifications visible in one chosen calculation.

Check one nontrivial row entry component by component. For d1(a,u,c), the join of u and c is (3,3,1), and meeting with a gives (3,0,0)=a. At the right endpoint, d1(a,c,c)=a∧c=q. For d3(a,u,c), join u with a and meet the result with c; this gives (0,3,0)=c. The central row is constant q because its formula is the meet of the fixed outer arguments. These calculations explain why the transformed rows lose the unwanted third-coordinate value one.

The ambient product contains other elements, and these three coordinate congruences need not be the only congruences available. Nothing in the calculation requires a full classification of them. We need only verify that the named relations are kernels of preserving projections and that the specific labelled steps satisfy them. This keeps the finite example focused on the path certificate instead of attaching an unsupported completeness claim to a convenient choice of congruences.

Contents · Previous chapter · Next chapter

Expand the Boolean algebra by adding binary join as a basic operation while retaining b. Meet was already available as b(x,y,y). We can now form m(x,y,z)=(x∧y)∨(x∧z)∨(y∧z). If two inputs equal a, absorption and idempotence make this expression equal a. Thus the expanded signature has a majority term.

The earlier impossibility proof has not become inconsistent. Its induction covered expression trees whose internal nodes were all b. A join node can combine two branches without leaving either input as a bound for the whole output. For example, x∨y is not bounded by x or by y: the assignments 01 and10 defeat those respective bounds.

One can also see why the new operation was genuinely unavailable before expansion. Every binary b-term has a bounding variable, whereas join has none. This supplies an expressibility obstruction for join itself, not just for majority. The expansion adds a capability rather than merely giving a shorter name to an old term.

Adding operations can reduce the congruence collection because every congruence must preserve more operations. On the two-element carrier there are only equality and the universal relation anyway, so that particular collection does not visibly shrink. The term capabilities still change. This is a useful warning against trying to recover every feature of an algebra from its congruence lattice alone. Two signatures on one carrier may have the same congruences and different available terms. The precise operations remain part of the object being studied.

Contents · Previous chapter · Next chapter

Jónsson's characterization concerns a variety: congruence distributivity throughout the class is equivalent to the existence of a finite chain of terms satisfying the required identities throughout that class. Our proof developed the direction from an explicit chain to distributivity. The converse uses a free-algebra argument; it is not established merely by noticing a distributive congruence lattice on one small algebra.

In particular, a two-element algebra always has just equality and the universal congruence. That observation alone does not imply that its generated variety is congruence distributive. The verified term equations are the stronger evidence in our example. Identities pass to subalgebras, products and homomorphic images, so our chain supplies a uniform certificate in the variety generated by the Boolean b-algebra.

Our list contains five terms. Constructing it proves that such a list suffices; it does not by itself prove that no list of four terms suffices. The no-majority argument rules out the three-term arrangement described earlier, but a full minimal-length theorem needs additional evidence. We do not claim to prove the complete distributivity spectrum here.

Lipparini's research paper treats the broader lattice-reduct family associated with Baker and analyses sharper lengths. Its definition and discussion give context for our example. The calculations here have the narrower teaching task of checking a concrete certificate, proving the absence of majority, and explaining the row-handoff mechanism. Distinguishing an available bound from an optimal bound is part of reading a mathematical result accurately.

Reference: Lipparini, Section 1.3 and Remark 2.2.

Contents · Previous chapter · Next chapter

Replace the Boolean carrier by the ordered set {0,1,2}, retaining b(x,y,z)=min(x,max(y,z)) as the only basic operation. Decide whether the five-term certificate still works and whether majority has become available. The carrier is larger, but changing its size alone does not answer either question.

The certificate still works because all its identity checks used lattice laws valid for minimum and maximum on this chain. For example, d1(2,0,1)=1, d2(2,0,1)=1 and d3(2,0,1)=1. Agreement at that particular triple is incidental; verify the required repeated patterns separately. At (x,x,z), d0 and d1 agree, and d2 and d3 agree, for every x,z in the three-element carrier.

No majority term exists. The same first-child induction bounds each term by one of its inputs. Put zero in that position and two in the other two positions. The bound forces zero, whereas majority would require two. This is a changed-value proof, not an assumption that the ten-function Boolean enumeration remains complete on the larger set.

For a further check, repeat the product-path construction with a=(2,0,0), u=(2,2,1) and c=(0,2,0), using coordinatewise b. The middle point again leaves the third-coordinate class, and q=(0,0,0) again supplies the repaired route. Explain each congruence label. Finally add binary maximum and build majority explicitly. These changes test three separate conclusions: validity of the chain, failure of majority in the restricted language, and recovery of majority after a genuine expansion.

Contents · Previous chapter · Next chapter

Does every middle term have to depend on all three inputs? No. Our d2 ignores y, and the endpoint projections ignore two inputs. Being written with three input positions specifies the identities to test; it does not assert that every position is essential to the resulting function.

Does a long chain prove that a shorter chain is impossible? No. A displayed list proves existence at that length. A lower bound requires an obstruction covering all shorter candidates. Here we proved that no majority term exists, but did not prove every possible minimal-length statement about the lattice-reduct family.

Can I check only the even-index links? No. Both sets of links are needed to move between rows. Without the right-end agreements, reaching the end of one row would not justify entering the next. The common endpoint identity is equally necessary for the class-containment argument; adjacent agreements alone do not provide it.

Does row reversal assume congruence permutability? No. Symmetry permits walking backwards through one existing row. Permutability concerns replacing a two-relation composition by the opposite-order composition in general. Those are different assertions, even if one concrete example happens to simplify into a reversed two-step path.

Does adding constants automatically make majority possible? No such conclusion follows from this lesson. Our successful expansion added join, and the displayed majority formula used it. A different expansion requires its own term construction or impossibility proof. Finally, can finite tables replace the proof for every lattice? No. Tables certify their specified finite algebra. The lattice-law derivation is what establishes the chain uniformly in the wider minimum-and-maximum examples.

Contents · Previous chapter · Next chapter

Begin with the carrier and the exact basic operations. Write the proposed terms as actual expressions in that language, expanding any derived meet notation at least once. Then separate the endpoint equations, the common repeated-endpoint equations and the alternating adjacent equations. This prevents a familiar-looking formula from passing an incomplete test.

Next reconstruct the impossibility argument without enumerating expression depth. Identify the property inherited by variables and preserved at every operation node. For b it is the existence of a bounding input. Choose an assignment that every candidate majority operation must answer differently from that bound. The resulting contradiction certifies nonexistence across all terms.

Afterwards build the ten ternary Boolean functions and compare them with complete evaluation columns. Explain both why every listed function is constructible and why no others are possible. Check the five-term identities separately from the majority exclusion. These are related claims about one algebra, but neither should be used as an unexplained substitute for the other.

Finally reconstruct the row argument using a path whose intermediate points need not remain in the chosen class. Label each row endpoint, mark the alternating handoffs and justify every reversed traversal by symmetry. Work the three-value transfer and the join expansion to locate which assumptions support each conclusion. The capability to retain is recognising when several formulas collectively provide a property that no single formula provides. A useful certificate makes that cooperation explicit: legal terms, exact endpoint agreements, a visible path construction and clear boundaries on what has actually been proved.

Contents · Previous chapter · Continue to related reading