The Gold Standard of Universal Algebra | Testing Compatible Tolerances Before Treating Them as Congruences

A binary relation T on a carrier A is a collection of ordered pairs. Writing a T b means that the pair (a,b) belongs to that collection. Reflexivity requires a T a for every a. Symmetry requires b T a whenever a T b. Transitivity requires a T c whenever a T b and b T c.

Compatibility is a different requirement. For each basic n-ary operation f, related inputs in every coordinate must give related outputs: if aᵢ T bᵢ for all input positions, then f(a₁,…,aₙ) T f(b₁,…,bₙ). Constants simply require their values to be related to themselves, which reflexivity already supplies.

In universal algebra, a tolerance is a reflexive, symmetric, compatible relation. A congruence is a compatible equivalence relation, so it also has transitivity. Every congruence is therefore a tolerance, but a tolerance need not be a congruence. The definitions make the missing obligation explicit.

Keep a separate line for each property in an audit. A successful operation-table check does not automatically establish transitivity. Likewise, proving an equivalence relation does not establish compatibility with the signature. Different failures need different witnesses and different repairs.

For example, a transitivity failure needs three elements a,b,c with two present pairs and one absent pair. A binary compatibility failure needs two related input pairs whose operation outputs are unrelated. Writing these witness shapes before calculating helps prevent a correct test of one property from being reported as evidence for another.

Contents · Next chapter

Take A={0,1,2}, ordered in the usual way. Its two basic operations are minimum and maximum. For example, min(0,2)=0 and max(0,2)=2. These operations make A a three-element chain lattice. There is no addition in the signature of this example.

Define a T b when |a−b|≤1. The relation contains (0,0), (1,1), (2,2), (0,1), (1,0), (1,2) and (2,1). It excludes exactly (0,2) and (2,0). Listing all nine possible positions gives a complete relation table.

Reflexivity follows because each element has distance zero from itself. Symmetry follows because |a−b|=|b−a|. Transitivity fails because 0 T 1 and 1 T 2 hold, while 0 T 2 does not. This witness remains visible even before compatibility is checked.

The phrase “one step apart” is a convenient description of this labelled finite chain. It is not a universal definition of tolerance. A different relation or different operations could fail compatibility, and arbitrary numerical closeness should not be called an algebraic tolerance without that check.

We have now established three facts: the relation is reflexive, it is symmetric, and it is not transitive. We have not yet earned the word tolerance, because the two lattice operations still need testing. Keeping this intermediate state honest is part of learning to build a proof in the correct order.

Contents · Previous chapter · Next chapter

Assume a T a′ and b T b′. Then a−1≤a′≤a+1 and b−1≤b′≤b+1. Taking the minimum of the lower bounds and of the upper bounds gives min(a,b)−1≤min(a′,b′)≤min(a,b)+1.

Therefore the two minimum values differ by at most one, so min(a,b) T min(a′,b′). The inequalities may mention numbers outside the carrier as bounds, but the actual inputs and operation outputs remain in {0,1,2}. No extra algebra elements have been introduced.

Check a mixed example: 0 T 1 and 2 T 1. The minima are min(0,2)=0 and min(1,1)=1, which are related. Another example uses 1 T 2 and 0 T 1; the minima are zero and one. These calculations illustrate the general bound rather than replacing it.

The proof uses simultaneous bounds on both coordinates. It would not be enough to say that minimum always chooses an input and therefore must preserve every relation. The chosen input position can change between the two tuples. Without an argument controlling that change, the shortcut is incomplete.

For a finite verification, the relation has seven ordered pairs, so there are forty-nine pairs of related input pairs to inspect for a binary operation. Exhaustive checking is feasible here. The inequality proof is more informative because it explains why the check succeeds and transfers to longer finite numerical chains with the same distance-one relation.

Contents · Previous chapter · Next chapter

The same bounds give max(a,b)−1≤max(a′,b′)≤max(a,b)+1. Hence maximum also sends coordinatewise T-related inputs to T-related outputs. With reflexivity and symmetry already established, T is a tolerance of the chain lattice.

It remains nontransitive. Compatibility with minimum and maximum has not added the missing pair (0,2) to the definition. We have proved that the relation satisfies the tolerance requirements while failing a separate congruence requirement. There is no contradiction between those conclusions.

Use a concrete maximum calculation beside the minimum one. For related pairs 0 T 1 and 2 T 1, the maxima are two and one, again related. Both operations respect the local one-step relation even though taking two relation steps can carry us from zero to two.

The distinction is between combining related inputs by the permitted operations and chaining relation links through an intermediate element. Neither minimum nor maximum automatically supplies the transitive step demanded by an equivalence relation. The relation can be stable under the operations while retaining its local, overlapping character.

This is a useful counterexample because every claim can be checked without a large theory. It disproves the universal statement that reflexive, symmetric compatibility always implies congruence. To disprove such a statement, one complete verified algebra and relation suffice; adding more examples would not strengthen the logical refutation, although changed examples can deepen understanding.

Contents · Previous chapter · Next chapter

For an element a, define its T-neighbourhood N(a)={b:a T b}. In our example, N(0)={0,1}, N(1)={0,1,2}, and N(2)={1,2}. These sets overlap, and related elements can have different neighbourhoods.

For an equivalence relation, related elements have identical equivalence classes. Here zero and one are related, yet N(0) differs from N(1). The familiar class notation [a] can therefore mislead if it suggests a partition that the relation does not provide.

There is a second warning: the neighbourhood of one contains zero and two, which are not related to each other. Being related to a shared central element does not imply mutual relatedness. N(1) is a star-shaped collection in the relation graph, not a set whose every pair belongs to T.

Imagine a record that groups every value related to one under the label “same as one.” It would place all three values into that group. If the record then treats group membership as proof that zero is related to two, it has silently imposed transitivity and changed the original relation.

This problem appears before any quotient operation is attempted. The proposed groups do not form disjoint equivalence classes. A careful report can still list neighbourhoods, but it should name them as neighbourhoods and retain their defining relation. The notation should communicate the evidence available rather than importing properties from a more restrictive mathematical object.

Contents · Previous chapter · Next chapter

A block of a tolerance is a maximal subset B of the carrier such that every two elements of B are T-related. Maximal means that no strictly larger subset has that property. It does not mean a block must have the largest possible size among all such subsets.

In the three-element example, the blocks are P={0,1} and Q={1,2}. Each has all its pairs in T. Adding the remaining element to either block would include both zero and two, violating the condition. Singletons are not maximal because each lies inside one of these larger sets.

The blocks overlap at one. They cannot be the fibres of a function from A onto the two-block set {P,Q}, because a function assigns one output to each input and disjoint fibres result. Assigning one to both blocks would require a relation-valued assignment rather than an ordinary function.

Notice also that N(1) is not a block: its two endpoints are unrelated. A neighbourhood asks which elements are related to one chosen centre. A block asks whether every pair inside the set is related. Confusing those two questions is an easy way to construct an incorrect tolerance-block list.

For a finite relation, one can find blocks as maximal cliques in the undirected graph obtained from its symmetric pairs, with reflexive loops understood. That is a method for identifying mutually related subsets. It does not turn the graph into an equivalence partition or prove that any proposed operation on those blocks is well-defined.

Contents · Previous chapter · Next chapter

An ordinary quotient algebra A/θ has one element for each equivalence class of a congruence θ. The canonical projection sends a to its unique class. Compatibility ensures that operations computed from different representatives yield the same output class.

For T, uniqueness of the class assignment already fails if we use maximal blocks. The element one lies in both P and Q. If we instead use neighbourhoods, related elements may receive different neighbourhoods, and the neighbourhoods do not form a partition. Neither substitution reproduces the ordinary quotient construction.

Suppose we choose to assign one to P, leaving zero in P and two in Q. The resulting partition is {0,1},{2}. It happens to be a congruence of the chain lattice, but its equivalence relation is not T: it no longer relates one to two.

Choosing one for Q instead gives {0},{1,2}, another congruence that loses the other adjacent relation. Merging P and Q gives the universal partition, which preserves both adjacent identifications but adds zero related to two. These are three distinct decisions, not three descriptions of the original tolerance.

Specialised tolerance-factor constructions exist in lattice theory; the research references discuss them. Their existence does not license treating overlapping blocks as ordinary congruence classes. The construction and its rules must be stated. In this lesson, the immediate task is to identify exactly why the familiar projection-and-class recipe does not apply unchanged.

Contents · Previous chapter · Next chapter

The transitive closure T* relates two elements when there is a finite T-path between them. Reflexivity allows a path of length zero, and symmetry allows paths to be reversed. Concatenating paths proves transitivity. Thus T* is an equivalence relation.

For our example, zero reaches two through one. Every pair of elements is therefore connected, so T* is the universal relation on {0,1,2}. The two missing ordered pairs have been added. The resulting ordinary quotient has one element, not two overlapping block elements.

This operation answers a specific question: what is the least equivalence relation containing all the original T-pairs? It does not preserve the original meaning of “at most one step apart.” It replaces that local condition by finite-path connectedness, which can relate endpoints arbitrarily far apart on a longer chain.

Consider the chain {0,1,2,3,4}. Its distance-one relation still has only neighbouring links, but its transitive closure relates zero and four through four steps. Reporting the closure as though it were the original proximity test would be false, even though the closure is mathematically well-defined.

When a procedure repairs nontransitivity by merging connected components, record that repair explicitly. It may be appropriate if every original related pair must become an identification. It may be inappropriate if the relation was intended to preserve a strict local distinction. The closure solves one requirement by deliberately weakening another.

Contents · Previous chapter · Next chapter

For a tolerance on a finitary algebra, T* is not only an equivalence relation; it is compatible. Suppose each pair of corresponding inputs aᵢ,bᵢ is connected by a finite T-path. We must connect the two operation outputs by such a path.

Because the operation has finitely many input positions, the finitely many path lengths have a maximum m. Extend every shorter path to length m by repeating its endpoint. Reflexivity makes each repeated step a valid T-step. We now have aligned input tuples at stages zero through m.

At each stage, consecutive tuples are coordinatewise T-related. Compatibility of T sends their operation values to T-related outputs. Reading those outputs in order gives a finite T-path from f(a₁,…,aₙ) to f(b₁,…,bₙ). Hence the output pair belongs to T*.

This proves compatibility for every positive finite arity. Constants are covered by reflexivity. Therefore T* is a congruence. Moreover, any congruence containing T contains every finite T-path by transitivity, so it contains T*. The closure is exactly the least congruence containing the tolerance.

The word finitary matters in this proof. With infinitely many input positions, path lengths might have no common finite bound, and the padding argument would not apply as written. Our stated setting avoids that issue. A proof's small technical assumptions often identify precisely where a tempting unrestricted generalisation would need new work.

Contents · Previous chapter · Next chapter

Let K be the four-element chain {0,1,2,3}, again with minimum and maximum. Define a surjective map h:K→A by h(0)=0, h(1)=1, h(2)=1 and h(3)=2. The map is order-preserving, so on these chains it preserves minimum and maximum.

On K, let α have the two classes {0,1} and {2,3}. This is a congruence. One way to verify it is to map those intervals to the two-element chain; the monotone class map preserves minimum and maximum, and α is its kernel equivalence.

Now take the direct image relation h(α): a pair (u,v) belongs to it when some α-related x,y satisfy h(x)=u and h(y)=v. The first α-class contributes all pairs from {0,1}². The second contributes all pairs from {1,2}².

Their union is exactly our seven-pair tolerance T. In particular, (0,1) comes from the first class and (1,2) from the second, while (0,2) comes from neither. A genuine congruence has therefore become a nontransitive tolerance after taking its relational image through a homomorphism.

The duplicated image value one explains the mechanism. Its preimage includes elements one and two from different α-classes. Two image relation steps can use different preimage witnesses for that shared middle value. Nothing guarantees those witnesses are α-related, so transitivity in the source does not combine the two image steps.

Write the two witness pairs explicitly: (0,1) in K maps to (0,1) in A, while (2,3) in K maps to (1,2) in A. The image steps meet at one, but their source steps end at one and start at two. These are different source elements, separated by α. If we additionally identify them, the source chain of identifications becomes 0 related to 1 related to 2 related to 3. Its equivalence closure is universal, and its image is universal too. That is the concrete extra merge required to restore a transitive descent in this example.

Contents · Previous chapter · Next chapter

The preceding example may seem to challenge the familiar statement that homomorphisms interact well with congruences. The resolution is to distinguish direct image from inverse image, and to state any kernel-containment hypothesis needed for a quotient correspondence.

An inverse image relation pulls a target congruence θ back by declaring x related to y when h(x) θ h(y). Reflexivity, symmetry and transitivity transfer immediately through the images, and homomorphism preservation transfers compatibility. This construction always gives a source congruence.

A direct image uses existential witnesses in the source, as h(α) did. Those witnesses need not match when two image pairs are chained. Surjectivity gives reflexivity throughout the target, and symmetry and compatibility transfer, but transitivity can fail. The four-element chain demonstrates that failure completely.

For an onto homomorphism, the standard congruence correspondence uses source congruences containing the kernel of h. Here the kernel has blocks {0},{1,2},{3}. Our α does not contain it because one and two lie in different α-classes. The example therefore falls outside that correspondence's hypothesis.

Keep the direction of the map beside the relation operation in your notes. “Transport a congruence through a homomorphism” is too vague to determine which theorem applies. The companion quotient-correspondence lesson develops the kernel condition; the present example shows what can happen when an unrestricted direct image is mistaken for that controlled descent.

Contents · Previous chapter · Next chapter

Suppose an algebra has a ternary term p satisfying p(x,y,y)=x and p(x,x,y)=y. Such a term is called a Malcev term. Compatibility with basic operations implies compatibility with term operations by induction through the expression, so a tolerance respects p.

Assume a T b and b T c. Compare the triples (a,b,b) and (b,b,c). Their first coordinates are T-related by the first assumption, their second coordinates agree, and their third coordinates are T-related by the second assumption. Compatibility gives p(a,b,b) T p(b,b,c).

The two identities simplify this to a T c. Thus T is transitive, and every tolerance of this algebra is a congruence. The proof has constructed the missing transitive step using one compatible term. It does not need a separate enumeration of all possible relation chains.

For a group, p(x,y,z)=xy⁻¹z is a term with these identities. Hence every tolerance compatible with the group operations is a congruence. Our nontransitive chain tolerance therefore cannot remain compatible with a group structure on the same carrier if that structure supplies the term.

This complements the existing Malcev-path lesson without replacing its reader job. There the term reverses the order of two congruence steps. Here it forces transitivity of one reflexive compatible relation that was not initially assumed to be a congruence. The similar formula is serving a different missing property, which the displayed triples make explicit.

Contents · Previous chapter · Next chapter

Keep the three-element chain and its relation T, but add the ternary operation p(x,y,z)=x−y+z modulo three. This operation satisfies the Malcev identities on the carrier {0,1,2}. The expanded signature includes minimum, maximum and p.

Our old T cannot be compatible with p, because it is not transitive and the previous proof would force transitivity. We can locate the failure directly instead of relying only on that general argument. Use the related coordinate pairs 0 T 1, 1 T 1 and 1 T 2.

The corresponding triples are (0,1,1) and (1,1,2). Their p-values are zero and two, respectively. Those outputs are not T-related. This single witness shows exactly which new operation invalidates the old tolerance status.

The relation itself has not changed. It is still reflexive and symmetric and still compatible with minimum and maximum. It is a tolerance of the lattice reduct but not of the expanded algebra. Adding operations increases the compatibility obligations and can remove previously permitted relations.

This is a useful way to test understanding of signatures. A learner who says “T was a tolerance, so it remains one” has treated tolerance as a property of the carrier alone. A complete answer names the operations, records the failed output pair and explains why the earlier successful lattice checks remain correct within their original scope.

Contents · Previous chapter · Next chapter

Outside algebra, tolerance may refer to an allowed measurement deviation. A condition such as |x−y|≤ε is reflexive and symmetric when ε≥0, but it need not be transitive. It also need not be compatible with whatever operations an application uses.

For a simple exact example on the integers, let ε=1 and consider addition. We have 0 T 1 in both input positions, but 0+0=0 and 1+1=2 are not related. Thus distance-one closeness is not a tolerance of the additive group of integers.

The same relation is compatible with minimum and maximum on a numerical chain, as our bound proofs showed. The difference is the operation, not a change in the numerical threshold. Calling the relation “within tolerance” in ordinary language does not establish the universal-algebra property.

If a real measurement model is intended, further questions arise: units, uncertainty, correlations and the meaning of the threshold. Our exact integer examples establish none of those empirical facts. They illustrate a logical test that can be applied once the actual model and its operations have been specified.

For practical transfer, write the proposed relation and the downstream calculation before deciding whether closeness is preserved. Two individually small changes can combine into a larger change under addition. A minimum or maximum calculation has a different bound. This operation-sensitive reasoning is more useful than assuming that every reasonable-looking similarity rule defines interchangeable values.

Contents · Previous chapter · Next chapter

Start with a complete carrier and operation tables. Record the relation as an explicit pair set or a membership rule. Verify reflexivity across the diagonal and symmetry across reversed pairs. If either fails, it is not a tolerance under the definition used here.

Then test compatibility for each basic operation. For a binary operation, inspect pairs of related input pairs and record any unrelated outputs. For a finite relation containing r ordered pairs, this direct check has r² combinations per binary operation. Constants and unary operations have their own simpler checks.

Test transitivity separately over triples of carrier elements. Whenever a T b and b T c hold, ask whether a T c holds. A single failed triple suffices to rule out congruence. Passing the compatibility checks does not reduce the need for this test unless an applicable theorem supplies it.

If the relation is a nontransitive tolerance, identify what the intended next step requires. Neighbourhood reporting, maximal-block reporting, an ordinary quotient and transitive closure are distinct tasks. Choose one explicitly, and record which pairs or distinctions it adds or removes.

Finally retain small certificates rather than only a final label. For our chain, the relation table, the min/max bound proof and the triple (0,1,2) explain the classification. If the signature is expanded, append the p-operation witness. A reviewable record lets another learner reproduce the conclusion and recognise when a changed assumption invalidates it.

Contents · Previous chapter · Next chapter

Use the chain {0,1,2,3,4} with minimum and maximum. Define S by |a−b|≤2. Decide whether S is a tolerance, whether it is a congruence, what its maximal blocks are, and what ordinary quotient results after taking transitive closure.

The same bound argument works with two in place of one, so S is compatible with minimum and maximum. It is reflexive and symmetric. It is not transitive: 0 S 2 and 2 S 4 hold, while 0 S 4 does not. Thus it is a tolerance but not a congruence.

Its maximal mutually related subsets are {0,1,2}, {1,2,3}, and {2,3,4}. Each has diameter two, and adding any other carrier element makes its diameter exceed two. Every smaller mutually related set can be extended into one of these, so the block list is complete.

The neighbourhood of two is the whole carrier, but it is not a block because zero and four are unrelated. The transitive closure is universal, since neighbouring elements are S-related and connect the chain. Hence the ordinary quotient obtained by closure has one class, even though the tolerance has three overlapping maximal blocks.

Now change the operation by adding addition modulo five. The input pairs 0 S 2 and 0 S 2 give outputs zero and four, which are not S-related. S ceases to be a tolerance of the expansion. This final change checks whether the learner carries the signature requirement along with the relation rather than memorising a classification from the earlier chain.

Contents · Previous chapter · Next chapter

Is every symmetric relation a tolerance? No. It must also be reflexive and compatible with every basic operation. Symmetry alone only says that the direction of a related pair can be reversed. It says nothing about diagonal pairs, operation outputs or transitivity.

Why do tolerance blocks overlap? Without transitivity, two mutually related sets may share an element while their remaining members are unrelated. In the three-element chain, both {0,1} and {1,2} are maximal, but zero and two cannot join one block. Their overlap reflects the original relation rather than a counting error.

Does taking transitive closure always give the least congruence? For a tolerance on the finitary algebras considered here, yes, by the aligned-path compatibility proof. For an arbitrary relation that is not already compatible, equivalence closure alone need not be compatible. Additional operation-forced pairs may be necessary.

Can a homomorphism turn a congruence into a noncongruence? Its unrestricted direct image can, as the four-element chain demonstrates. Its inverse image of a target congruence is a congruence. The usual onto-map congruence correspondence adds a kernel-containment condition to direct descent, so these statements do not conflict.

Are all tolerances in groups congruences? Yes, when compatibility is with the group signature. The term xy⁻¹z forces transitivity. This statement should not be transferred to an unrelated reduct or to a numerical closeness rule that has not passed the group-operation compatibility test.

Contents · Previous chapter · Next chapter

Rebuild the seven-pair relation on the three-element chain without looking at the table. Prove its three positive properties and give the exact triple that defeats transitivity. State why the maximum and minimum checks cannot replace that triple test.

Then list the three neighbourhoods and the two maximal blocks. Explain why the middle neighbourhood is not a block, why the blocks are not a partition, and why choosing one block for the shared element changes the represented relation. This distinguishes three objects that can look deceptively similar in a small diagram.

Next reconstruct the four-element source chain, its two-class congruence and the map with repeated middle image. Trace the witnesses for 0 T 1 and 1 T 2 back to the source. Identify precisely why they cannot be joined into an α-chain without an additional source identification.

Finally prove the Malcev-term transitivity argument and locate its failed compatibility witness in the expanded chain. Work the five-element transfer problem independently. A successful explanation should preserve the distinction between a relation's equivalence properties, its operation compatibility and the separate construction chosen for downstream use.

The capability to retain is knowing when related values may legitimately become quotient values. Compatibility alone does not supply transitivity. By keeping neighbourhoods, overlapping blocks and congruence classes distinct, you can use tolerances accurately, explain the cost of taking closure, and avoid silently turning local relationships into global identifications.

Contents · Previous chapter · Continue to related reading