The Gold Standard of Universal Algebra | Recovering an Algebra from Several Quotient Observations

Begin with an algebra A: a nonempty carrier equipped with specified total operations. An observation h:A→B is useful algebraically when it preserves those operations. For a binary operation m, the requirement is h(m(a,b))=m(h(a),h(b)), with the right-hand operation interpreted in the observation algebra B.

The requirement says that observing after a calculation agrees with calculating on the observations. It does not require h to preserve all original distinctions. Two different elements may have the same observation. That information loss is exactly what makes a quotient smaller than the original algebra.

For a concrete starting point, let A be the chain a<b<c<d, with minimum and maximum as its two operations. Think of a,b,c,d as four ordered levels in a teaching model. A yes-or-no observation might ask whether a level is at least c. Its values are 0,0,1,1 on a,b,c,d.

Equip the observation carrier {0,1} with minimum and maximum too. The threshold observation preserves both operations. The smaller of two original levels is at least c exactly when both are at least c; the larger is at least c exactly when at least one is. These are the corresponding minimum and maximum rules on bits.

The order interpretation makes preservation transparent, but it must still be stated. An arbitrary classification of levels into two colours may fail. For instance, assigning 1 only to b and d does not behave like a threshold. The later calculation must use verified observation maps, not merely attractive labels.

Contents · Next chapter

Every map groups original elements that receive the same output. For a homomorphism, this grouping is a congruence, often called its kernel congruence. It is a relation on pairs: a and b are related when h(a)=h(b). Do not confuse it with only one special output fibre in a group example.

For the threshold at c, the two fibres are {a,b} and {c,d}. The observation distinguishes the lower two levels from the upper two. It does not distinguish a from b or c from d. Those failures are mathematical properties of the map, independent of how the two output labels are displayed.

The quotient A/θ consists of the congruence classes themselves. The threshold map can be viewed as taking a class and then naming it 0 or 1. Because the map is onto this two-element target, the quotient and the target observation algebra have the same structure.

Suppose the task is to recover the exact original level. This one observation is inadequate: receiving 0 leaves two candidates. If the task is only to decide whether the level is at least c, the observation is completely adequate. Information loss is judged relative to the later question, not merely the size of the output set.

Write the unresolved pairs down. In this case they are a,b and c,d, together with their reversals and the unavoidable identical pairs. This list gives a concrete design target for additional observations: at least one new view must distinguish each unresolved pair if full recovery is required.

Contents · Previous chapter · Next chapter

Let h1:A→B1 and h2:A→B2 be homomorphisms of the same signature. Define H(a)=(h1(a),h2(a)). The product B1×B2 applies every operation coordinatewise. Consequently H is a homomorphism: its first coordinate preserves each operation because h1 does, and its second coordinate does so because h2 does.

For a binary operation, H(m(a,b)) has coordinates h1(m(a,b)) and h2(m(a,b)). Replacing each with its preservation equation gives m(h1(a),h1(b)) and m(h2(a),h2(b)). Together these are exactly the coordinatewise product operation applied to H(a) and H(b).

The same argument works for any finite list of observations, and more generally for an indexed family. Constants are sent to the tuple of target constants, and unary or higher-arity operations are handled in the same coordinatewise fashion. No special property of numerical addition is needed.

There is an important prerequisite: the target algebras must interpret the common signature. Combining one map that preserves minimum with another map that only records an unrelated statistic does not automatically produce a homomorphism for minimum and maximum. Each coordinate must meet every required preservation obligation.

This construction separates two questions. Is the tuple map operation-preserving? That follows from the component maps. Is it injective? That depends on which pairs the components distinguish. Keeping those questions separate makes it easier to locate a failed representation instead of treating every problem as a vague loss of structure.

Contents · Previous chapter · Next chapter

The tuple outputs H(a) and H(b) are equal exactly when every coordinate agrees: hi(a)=hi(b) for each i. Therefore the kernel congruence of H is the intersection of the kernel congruences of its component maps. A pair survives as indistinguishable only if every observation loses it.

Injectivity means that equal tuple outputs force a=b. Thus H is injective precisely when the intersection is the equality relation Δ={(a,a):a∈A}. Equivalently, for every distinct pair a,b, at least one component must give different outputs. These are two descriptions of the same condition.

Notice the order of the quantifiers. Each pair needs some separating observation, but the observation can depend on the pair. We do not require one component to distinguish every pair by itself. If that were required, a single injective component would already carry the whole representation.

For a small finite algebra, build a pair checklist. A four-element carrier has six unordered distinct pairs. Mark which observations separate each pair. All six rows must receive at least one mark. Missing a row gives an explicit collision, rather than merely a failed global assertion.

This criterion also explains why an intersection, rather than a union, is the relevant relation. Two elements collide in the combined observation only when they collide in every coordinate simultaneously. A union would instead record pairs lost by at least one view, and could wrongly declare a successful combined representation uninformative.

Contents · Previous chapter · Next chapter

Return to a<b<c<d with minimum and maximum. Use three bit-valued homomorphisms. Let q1 ask whether the input is at least b, q2 whether it is at least c, and q3 whether it is at least d. Their output lists are respectively 0111, 0011 and 0001.

The combined map Q=(q1,q2,q3) gives Q(a)=000, Q(b)=100, Q(c)=110 and Q(d)=111. Each original level receives a distinct three-bit tuple. Every component loses several distinctions, but together the components recover all four levels.

Check the adjacent pairs first. Only q1 distinguishes a from b. Only q2 distinguishes b from c. Only q3 distinguishes c from d. Any nonadjacent pair crosses at least one of those thresholds, so it is separated as well. This supplies a structural proof of injectivity rather than relying solely on noticing four different strings.

Each threshold map is onto {0,1}, because there are levels on both sides of its cut. Thus the image of Q projects onto every coordinate factor. This is a subdirect representation: all coordinate values are individually obtainable, while the image remains a subalgebra of the product.

Use the tuple labels as an encoding, not as ordinary binary numerals. The bit order records the three specified questions. Reading 100 as the integer four contributes nothing to the algebraic argument and can conceal which threshold each coordinate means. The meaning of the coordinates is what makes the representation explainable.

Contents · Previous chapter · Next chapter

The full product of three two-element carriers has eight tuples. Our image contains only 000,100,110,111. The other four tuples are absent. For example, 010 would report that the level is at least c but not at least b, which is impossible in the declared order.

Every valid tuple satisfies first bit ≥ second bit ≥ third bit. Conversely, every three-bit tuple satisfying those inequalities is one of the four listed images. We have therefore given an exact membership rule for the represented subalgebra, not just a list of examples that happen to occur.

The full product permits the three bits to vary independently. The chain representation imposes consistency conditions between them. Surjectivity of each coordinate projection does not remove those conditions. One can find an input producing either value in any selected coordinate without being able to realise every simultaneous combination.

This is why multiplying factor sizes gives the size of the ambient product, not automatically the size of the represented algebra. Here 2×2×2=8 counts all bit triples; only four satisfy the consistency rule. Injectivity tells us that those four valid triples correspond one-to-one with the four original levels.

A practical decoder should reject an impossible tuple rather than invent a level for it. On the image, decoding is well-defined and reverses Q. Extending a decoder to the entire product is an additional design choice and need not preserve the original operations or the intended interpretation of the observations.

Contents · Previous chapter · Next chapter

Take b and c in the chain. Their images are 100 and 110. Coordinatewise minimum gives 100, which decodes to b, exactly the minimum of b and c. Coordinatewise maximum gives 110, which decodes to c, exactly their maximum. This is a direct instance of the homomorphism equation.

Now combine a and d. Minimum of 000 and 111 is 000; maximum is 111. The endpoints behave as expected. More generally, taking coordinatewise minimum or maximum of two nonincreasing bit triples again gives a nonincreasing triple, so the image is closed under both operations.

The inverse map from the image back to A also preserves operations. If u=Q(a) and v=Q(b), then the image operation yields Q(m(a,b)); decoding returns m(a,b). Injectivity ensures that a and b are uniquely determined. This proves an isomorphism between A and its image.

Do not extend that conclusion to an inverse defined on all eight tuples. Four tuples have no original preimage. A bijection between A and the full product is impossible because their sizes differ. The precise statement is that an injective homomorphism identifies A with a subalgebra of the target product.

This distinction matters even when no finite count is available. The algebraic proof of inverse preservation works on the image. Surjectivity onto the declared target is a separate property. Writing the image explicitly prevents an otherwise correct representation argument from silently acquiring a stronger, unsupported conclusion.

Contents · Previous chapter · Next chapter

Delete q2, the threshold at c. The remaining observations are q1 and q3. Their tuples on a,b,c,d are 00,10,10,11. Levels b and c now collide. The other distinctions remain visible, but the representation is no longer faithful on the whole carrier.

The pair checklist explains exactly why. The deleted coordinate was the only one separating b from c. It was therefore essential for this chosen family. Deleting q1 instead merges a with b; deleting q3 merges c with d. Each threshold carries a distinction that the others cannot replace.

Could some different choice of two onto bit-valued homomorphisms encode the four-element chain faithfully? Any order-preserving map from a chain to {0,1} can change from 0 to 1 at most once. A nonconstant such map is a threshold. Each threshold separates only one of the three adjacent pairs at its change point.

Two thresholds therefore cannot separate all three adjacent pairs. At least three are needed when the target factors are two-element chains with minimum and maximum. The ordinary information-count bound would only say that two bits have room for four states. Algebraic preservation imposes a stronger restriction than capacity alone.

This is a useful design lesson: enough possible output strings do not guarantee the existence of an allowed encoding. The encoding must also preserve the operations. State the permitted observation type before using a counting argument to claim that a certain number of coordinates will suffice.

Contents · Previous chapter · Next chapter

The three-coordinate minimum depends on restricting each observation to a two-element chain. If larger quotient factors are allowed, the design changes. Consider p with output list 0,0,1,2 on a,b,c,d, and r with output list 0,1,2,2. Each maps onto a three-element chain.

Both maps are order-preserving, so they preserve minimum and maximum on these chains. Their kernel partitions are {a,b},{c},{d} and {a},{b},{c,d}. The only nontrivial pair lost by p is a,b; the only nontrivial pair lost by r is c,d. No distinct pair is lost by both.

The combined outputs are (0,0),(0,1),(1,2),(2,2). They are distinct, so two larger quotient observations recover the original four levels. The ambient product now has nine elements, of which only four are used. Fewer coordinates did not mean a smaller unrestricted product.

There is no contradiction with the previous chapter. The allowed target algebras changed. Three binary thresholds were necessary under one restriction; two three-valued quotients work under another. A claim of minimality must always specify what may vary: the number of maps, the size of factors, the signature or the available class of quotients.

For a comparison notebook, record both the factor sizes and the image size. Also record which distinctions each map forgets. These three pieces of information expose trade-offs that a single phrase such as “more compact representation” would leave ambiguous. Mathematical faithfulness and an application-specific storage cost are related but different assessments.

Contents · Previous chapter · Next chapter

Use a different algebra: the four bit pairs {00,01,10,11} under coordinatewise addition modulo 2, with zero 00. Let p return the first bit and q return the second bit. Both are onto group homomorphisms to the two-element additive group.

The combined observation H=(p,q) is simply the original pair. Every possible two-bit tuple occurs. Here the image is the full product, so the representation is an isomorphism onto that product rather than merely onto a proper subalgebra of it.

Compare the mechanism with the chain. In the group example, the two coordinates are independent in the precise sense that each pair of desired bit values is realised by an element of A. In the chain, nested threshold conditions prohibit some combinations. The word “independent” should be tied to that realisability statement, not used as an unexplained statistical claim.

Add a third homomorphism s(x,y)=x+y modulo 2. The new image consists of triples satisfying third bit = first bit + second bit modulo 2. It contains four triples inside an eight-element product. All three coordinate projections remain onto, but the third observation supplies no new ability to distinguish original elements.

This contrast gives two separate questions for any added observation. Does it distinguish a pair previously unresolved? Does it introduce a consistency relation among output coordinates? A redundant observation can still be useful for a specified checking task, but the algebraic representation alone does not imply any particular reliability benefit in a noisy system.

Contents · Previous chapter · Next chapter

An observation is redundant for injectivity if removing it leaves the intersection of the remaining kernels equal to equality. More generally, it adds no new distinctions when every pair that all existing maps fail to separate is also identified by the new map. The exact criterion concerns pairs, not whether the new formula looks different.

In the two-bit group, the first two projections already have equality as their kernel intersection. Adding their sum cannot improve injectivity. It does give a derived coordinate, but any element's third value can be computed from the first two. The representation contains a visible algebraic dependency.

By contrast, repeat the threshold at c twice while omitting the threshold at d. The duplicated coordinates may make the output tuple longer, but c and d remain indistinguishable. Repeating the same partition does not make its intersection finer. More coordinates are not automatically more information.

For a finite audit, delete one coordinate at a time and look for collisions. If a collision appears, keep a witness pair as evidence that the coordinate was needed in that family. If no collision appears, the coordinate is unnecessary for injectivity, although other requirements might still justify keeping it.

This deletion test establishes irredundancy of a particular family, not global minimality among every possible family. Another set of larger or differently structured quotient maps may use fewer components, as our three-valued chain example showed. Distinguish “none of these maps can be removed” from “no better design exists.”

Contents · Previous chapter · Next chapter

Consider the additive group of residues modulo 9, with addition, negation and zero. Its subgroups are {0}, {0,3,6} and the whole group. Congruences correspond to these subgroups through equality modulo their cosets. Thus the only proper nontrivial quotient has three elements; the other proper quotient has one.

Every proper quotient identifies 0 with 3. The three-element quotient does so because their difference belongs to {0,3,6}. The one-element quotient identifies everything. Consequently, any family consisting only of proper quotients still loses the pair 0,3 in every coordinate.

Their kernel intersection cannot be equality, so their combined map cannot be injective. Adding more copies of those quotient views does not help. The obstruction is not an insufficient search for clever output labels; it is a distinction that every allowed proper quotient necessarily forgets.

For completeness, the subgroup list follows from the cyclic group structure. The order of a subgroup divides 9, leaving sizes 1,3 and 9, and the unique subgroup of size 3 consists of the multiples of 3. This argument uses a group fact; it should not be transferred to arbitrary algebras without an analogous analysis of their congruences.

This example introduces the idea behind subdirect irreducibility. A nontrivial algebra with a least non-equality congruence has a pair that every nontrivial quotient collapse shares. Any faithful subdirect representation must therefore retain an isomorphic factor somewhere. The example demonstrates that obstruction without claiming that every algebra has the same congruence pattern.

Contents · Previous chapter · Next chapter

There are two different construction jobs nearby. If you insist that certain pairs be identified, you generate the least congruence containing those requests. That process adds consequences. If you combine observations and ask what remains indistinguishable, you intersect their kernel congruences. That process retains only the pairs lost by all views.

In the chain example, the threshold-at-b kernel has blocks {a},{b,c,d}. The threshold-at-d kernel has blocks {a,b,c},{d}. Their intersection has blocks {a},{b,c},{d}. Adding the threshold at c refines the intersection to four singleton classes.

No congruence-generation algorithm is needed to repair that intersection. Intersections of congruences are already congruences: equivalence properties and operation compatibility hold in every constituent relation, so they hold simultaneously in the intersection. The combined observation map supplies another direct explanation.

If instead you take a union of two congruence relations, transitivity may fail and closure may be needed. That is a different question. Using a union when designing a faithful product representation would reverse the intended information test, recording pairs lost somewhere rather than pairs lost everywhere.

The existing guide on computing forced congruences supplies the complementary closure lesson. Here the central task is to preserve enough separating observations. A helpful note labels each calculation by its purpose: “merge these pairs” or “recover distinctions from these views.” That purpose makes the correct operation on relations easier to choose.

Contents · Previous chapter · Next chapter

Our two-bit group admitted the sum observation s(x,y)=x+y modulo 2. Now keep the same four bit pairs but change the algebraic operations to coordinatewise minimum and maximum. The coordinate projections still preserve both operations. Does the old sum observation also remain a homomorphism to the two-element chain?

Take u=10 and v=01. Their coordinatewise minimum is 00, whose sum bit is 0. But s(u)=1 and s(v)=1, whose minimum is 1. Thus s(min(u,v)) differs from min(s(u),s(v)). One allowed pair proves that the old observation fails in the new signature.

The table defining s has not changed, and it is still a perfectly valid set function. What changed was the preservation requirement. Calling it a quotient observation of the new algebra would now be false. The first two projections still give a faithful product representation, but adding s no longer gives a homomorphism into the proposed three-factor lattice product.

This is why an extra coordinate can be harmless for set-theoretic injectivity yet invalid for an algebraic representation. Adding any function to an already injective tuple keeps the tuple injective. It does not ensure that the enlarged tuple preserves operations. Information recovery and structural preservation remain separate obligations.

When an application changes its combination rule, revisit every observation equation. A representation designed for one rule cannot inherit correctness merely because the stored labels are unchanged. The exact failed equation identifies what must be repaired: the observation, the target operation or the intended source structure.

Contents · Previous chapter · Next chapter

Start with complete operation tables for the source and each target. Verify that every operation is total on its declared carrier. For each proposed observation map, check preservation of each basic operation, including constants. A binary table on n source elements requires all n² input pairs for a direct exhaustive test.

Next construct the tuple output for every source element. Group equal tuples and inspect the resulting collision classes. If any class contains two distinct elements, record that pair and identify which maps failed to separate it. This is an explicit certificate of noninjectivity.

Then enumerate the image and compare it with the full target product. If they differ, give an exact consistency rule when possible, as with the nonincreasing threshold bits. Verify image closure independently on a small example. A faithful map can still have a proper image, and that fact should appear in the report.

Finally, test coordinate removal if minimality or redundancy matters. Keep witness pairs for essential coordinates. State the allowed target sizes and signatures before claiming a minimum number of observations. An irredundant collection is not automatically globally optimal, and raw bit capacity need not capture the preservation restrictions.

The finished record should include the source, target algebras, maps, kernels, image, decoder domain and evidence. A successful program run is easier to trust when its mathematical obligations can be checked separately. The aim is a reconstructible argument, rather than a large output table whose meaning depends on the original author's memory.

Contents · Previous chapter · Next chapter

Replace the four-level chain by five levels a<b<c<d<e, still using minimum and maximum. You are offered the three thresholds “at least b,” “at least d,” and “at least e.” Decide whether they recover every level. If not, identify a collision and supply a repair using another bit-valued threshold.

The three-coordinate outputs are 000,100,100,110,111. Levels b and c collide because no selected threshold lies between them. Add the threshold “at least c.” Ordering the four coordinates by thresholds b,c,d,e gives 0000,1000,1100,1110,1111, which are all distinct.

The full four-bit product has sixteen tuples, but the image has only five. Its exact rule is again that the bits never increase as you move from the lower threshold to the higher threshold. A tuple such as 1010 violates that rule and must not be decoded as an original chain element.

Now ask whether three different bit-valued lattice homomorphisms could do better. There are four adjacent pairs to separate. Each nonconstant map to the two-element chain has only one threshold change and therefore separates only one adjacent pair at that change. At least four are required under this restriction.

For a further check, replace the factor restriction by allowing three-element chain quotients. The previous lower bound no longer applies. You would need a new construction or impossibility argument for that new design space. A correct transfer answer retains the preservation principle while recalculating the consequences of the changed carrier and permitted observations.

Contents · Previous chapter · Next chapter

Does every collection of quotients recover the original algebra? No. Their congruences must intersect in equality. Repeating the same quotient usually repeats the same information loss. The modulo-9 example shows that even every proper quotient together can fail to separate a particular pair.

Does onto in every coordinate mean onto the product? No. The threshold image reaches both bit values in every coordinate while excluding combinations that violate the threshold order. Coordinatewise surjectivity and simultaneous realisability are different requirements. Listing the image or giving its consistency rule makes the distinction concrete.

Can an embedding be useful without filling the product? Yes. It gives a faithful operation-preserving representation, with an inverse defined on its image. The image constraints are part of the representation. They should be preserved during calculations rather than discarded because the surrounding product is easier to describe.

Can I combine arbitrary functions instead of quotient maps? Their tuple may be injective as a set map. To obtain an algebraic embedding, each coordinate must also preserve the declared operations into a suitable target algebra. A successful encoding does not automatically supply compatible target operations of the kind you want.

Is a smaller factor always better? That depends on the problem. Smaller factors may require more coordinates, and the image may carry complicated consistency conditions. This guide proves faithfulness and structural preservation. Storage cost, computation time and robustness require additional models and evidence rather than following automatically from the word quotient.

Contents · Previous chapter · Next chapter

First reproduce the four-level threshold construction. Write all three maps, their kernel partitions and the four image tuples. Explain injectivity using pair separation, then explain why the image is proper using one impossible tuple. These are complementary checks, not alternative ways to say the same thing.

Next remove each coordinate and produce its collision witness. Compare the result with the two larger quotient views. State which restriction changed and why the old coordinate-count lower bound no longer applies. This trains you to attach a minimality claim to its actual design conditions.

Then move to the two-bit additive group. Verify the two coordinate projections, add the sum coordinate, and describe the resulting consistency equation. Change the operation to coordinatewise minimum and find the explicit failure of the sum observation. The same labels now support a different preservation problem.

Finally, explain the modulo-9 obstruction in your own words. Name a pair that every proper quotient loses and connect it to the kernel-intersection criterion. A failed representation can be as informative as a successful one when the failure identifies a distinction that the permitted observations cannot recover.

The durable skill is to account for information one pair at a time while checking operations one symbol at a time. Several lossy views can jointly become faithful, but only when their losses do not overlap on a distinct pair. Their outputs can still be constrained, so recovery of the original algebra should always be stated as an isomorphism with the actual image.

Contents · Previous chapter · Continue to related reading