The Gold Standard of Universal Algebra | Recognising Congruences That Mix Product Coordinates

Let C3 be the additive group of residues {0,1,2} modulo three. Form A=C3×C3. Its nine elements are ordered pairs (x,y), and its operations are coordinatewise addition, coordinatewise inverse and the zero pair (0,0). For instance, (2,1)+(2,2)=(1,0).

Coordinatewise means that the first output uses only the first inputs, and the second output uses only the second inputs. It does not say that every possible function from A to another algebra must inspect the coordinates separately. A map can combine them, provided it preserves the declared operations.

A congruence θ on A is an equivalence relation compatible with addition and inverse. The quotient A/θ has equivalence classes as elements. Its addition is defined by adding representatives and taking the resulting class. Compatibility is what makes the choice of representative irrelevant.

We will compare two ways a quotient can forget information. It may forget some first-coordinate distinctions and some second-coordinate distinctions independently. Or it may forget a coordinated change in both inputs while retaining a relationship between them. These are different partitions of the same nine-element carrier.

Do not decide which case holds merely from the fact that the carrier is a Cartesian product. The carrier and basic operations specify the starting algebra; the congruence specifies a further identification. The question is whether that extra identification respects the chosen coordinate separation, and that requires its own evidence.

Contents · Next chapter

Take a congruence α on the first C3 and a congruence β on the second C3. Define α×β on A by (x,y) related to (x′,y′) exactly when x α x′ and y β y′. The two coordinate tests are independent and both must pass.

This is a congruence of the product. Equivalence follows coordinatewise. For compatibility with addition, related first-coordinate inputs give α-related sums, while related second-coordinate inputs give β-related sums. Inverse and zero are handled in the same fashion. This constructs valid product congruences, but does not yet classify every congruence of A.

The class of (x,y) is [x]α×[y]β. It contains every combination of a first coordinate from the α-class and a second coordinate from the β-class. This rectangular form is a necessary feature of a product congruence relative to the given factors.

For C3, the only group congruences are equality and the universal relation. To see this, any identification of two distinct residues gives a nonzero difference, either one or two. Repeated addition of that difference generates all residues, forcing every element into the zero class.

There are therefore four product congruences on C3×C3: preserve both coordinates, preserve only the first, preserve only the second, or preserve neither. The coming example produces another valid congruence, showing why the four obvious coordinatewise choices do not exhaust the quotient possibilities.

Contents · Previous chapter · Next chapter

Define h:A→C3 by h(x,y)=x−y modulo three. This records the difference between the two coordinates. It is onto, because h(r,0)=r for every residue r. It also preserves addition: the difference of the coordinatewise sum is the sum of the two original differences.

Writing this out gives h((x,y)+(u,v))=(x+u)−(y+v)=(x−y)+(u−v), all modulo three. Inverse is preserved because h(−x,−y)=−(x−y), and h(0,0)=0. Thus h is a homomorphism in the full additive-group signature.

Its kernel congruence θ identifies two pairs exactly when their differences agree: x−y=x′−y′ modulo three. Since θ is a homomorphism kernel, it is compatible with the operations. We have not merely invented a partition that looks regular; we have supplied a preserving observation that defines it.

The zero class is D={(0,0),(1,1),(2,2)}. Moving both coordinates by the same residue leaves their difference unchanged. The other two classes consist of pairs with difference one or two. Each class contains three of the nine elements.

This is information loss with a clear meaning. The observation cannot recover either absolute coordinate, because simultaneous shifts are invisible. It can recover their difference exactly. Whether that is adequate depends on the later question. Algebraic validity guarantees a well-defined quotient operation, rather than guaranteeing that every original-coordinate question remains answerable.

Contents · Previous chapter · Next chapter

Let D0={(0,0),(1,1),(2,2)}, D1={(1,0),(2,1),(0,2)} and D2={(2,0),(0,1),(1,2)}. The subscript records the common difference modulo three. These three sets are disjoint, cover the nine-element carrier and are precisely the fibres of h.

Adding a representative from Di to one from Dj gives a representative with difference i+j modulo three. Therefore the quotient addition is Di+Dj=D(i+j mod 3). Its zero is D0 and its inverse sends Di to D(−i mod 3). The quotient is isomorphic to C3 through the class-difference map.

Check a calculation with different representatives. From D1 choose (1,0), and from D2 choose (0,1); their sum (1,1) belongs to D0. Alternatively choose (2,1) from D1 and (1,2) from D2; their sum is (0,0), again in D0.

The original output pairs differ, but the quotient output agrees. That is exactly the required representative independence. A quotient does not demand that every choice produce the same original element; it demands that every choice produce the same equivalence class.

This calculation is a useful safeguard against conflating a class with one chosen representative. Writing D1 as though it were only (1,0) can hide the identifications that need checking. Keep the complete class list available until the general difference calculation has established compatibility for all representative choices.

Contents · Previous chapter · Next chapter

Suppose, for contradiction, that θ=α×β for congruences on the given two factors. Since (0,0) θ (1,1), the product definition would require 0 α 1 and 0 β 1. It would then also relate (0,0) to (1,0), because the first coordinates are α-related and the second coordinates agree.

But h(0,0)=0 and h(1,0)=1. These pairs are not θ-related. The proposed product representation therefore contradicts the actual observation. The single diagonal identification has forced a missing rectangle corner that θ does not contain.

The same argument can be phrased through classes. D0 contains (0,0) and (1,1), but not (1,0) or (0,1). A Cartesian product of coordinate classes containing the two diagonal points would have to contain both cross-corners as well. D0 is not such a rectangle.

Consequently θ is a skew congruence relative to the displayed decomposition C3×C3. Its validity as a congruence and its failure to be a product congruence are separate conclusions, each supported by a separate argument. The homomorphism proves the first; the missing-corner contradiction proves the second.

This proof pattern is useful beyond this particular group. To refute a proposed independent-coordinate quotient, find related tuples whose coordinate mixing would be forced by that independence, then show the mixed tuple lies in another class. The witness is small enough to inspect, while its consequence rules out every possible factor-congruence choice in that coordinate system.

Contents · Previous chapter · Next chapter

Project D0 onto the first coordinate. The result is {0,1,2}. Project it onto the second coordinate and the result is again {0,1,2}. Each coordinate value occurs somewhere in the class. Yet D0 contains only three pairs, while the product of its projections contains nine.

The projections have discarded the constraint that the coordinates must agree. Recombining projected possibilities independently adds six pairs that were never present. For instance, first coordinate one is possible and second coordinate zero is possible, but the pair (1,0) is not possible in D0.

This is the same logical distinction as individually available choices versus jointly available combinations, now applied to a congruence class rather than to an algebra's image in a product. It must not be read as a claim of statistical independence. No probability distribution has been introduced.

Suppose a report retained only the two projected sets and attempted to reconstruct the original class as their Cartesian product. It would incorrectly identify every pair with zero. The resulting quotient would have one class instead of three and would lose the difference information that h was designed to retain.

A complete record of a coupled class therefore needs its membership relation, such as x=y or x−y=r, rather than only its coordinate ranges. Coordinate summaries can be useful, but they answer a weaker question. Before reconstructing a set or a quotient from them, prove the required rectangularity instead of assuming it.

Contents · Previous chapter · Next chapter

For an additive abelian group, a congruence is determined by the class N of zero. This class is a subgroup: it contains zero, is closed under addition by compatibility, and is closed under inverse. If a θ b, adding −b to both sides gives a−b θ 0, so a−b belongs to N.

Conversely, if a−b belongs to N, then a−b θ 0. Adding b gives a θ b. Thus the relation is exactly equality modulo N: two elements are related when their difference lies in N. This argument proves both directions rather than relying on a group-theory label alone.

For our product A, elements are pairs and subtraction is coordinatewise. The zero class D from the difference observation is the diagonal subgroup generated by (1,1). The associated equivalence classes are its cosets. Translating D by (1,0) gives D1, and translating by (2,0) gives D2.

This reduces the classification of congruences of A to the classification of its subgroups. The reduction uses the additive group operations, including inverse. An arbitrary algebra's congruence need not be determined by one distinguished class, and its signature may not even include a named zero.

Keep that boundary attached to the method. The universal-algebra question concerns congruences generally, while this worked family supplies a particularly transparent group calculation. The group-specific zero-class proof is what permits the shortcut here. Reusing it for an unrelated operation table without such a proof would be an unsupported transfer.

Contents · Previous chapter · Next chapter

Every nonzero pair in C3×C3 has additive order three. Its generated subgroup consists of zero, that pair and its double. There are eight nonzero pairs, and each three-element subgroup contains two of them. The resulting four lines are generated by (1,0), (0,1), (1,1) and (1,2).

These lines are distinct and account for every nonzero vector. If a subgroup contains nonzero vectors from two different lines, those vectors are linearly independent over the three-element field. Their nine linear combinations cover A, so the subgroup is the whole group. This can also be checked by enumerating the three possible coefficients on each vector.

Therefore the subgroup list is complete: the zero subgroup, four lines and the whole group. By the zero-class argument, A has exactly six congruences. The zero subgroup gives equality; the whole group gives the universal relation; each line gives a three-class quotient.

Two line congruences are product congruences. The horizontal line forgets the first coordinate while preserving the second, and the vertical line does the reverse. The two diagonal lines couple coordinates and are skew relative to the original coordinate axes.

This classification shows why counting only combinations of factor congruences misses valid quotients. Each C3 has two congruences, yielding four coordinatewise combinations, but the product has six congruences. The extra two are not errors or exotic exceptions to compatibility; they arise from legitimate homomorphisms that compare coordinates.

Contents · Previous chapter · Next chapter

The line generated by (1,2) is N={(0,0),(1,2),(2,1)}. It is the zero class of the sum observation s(x,y)=x+y modulo three. Like the difference observation, s is an onto homomorphism. Its kernel congruence preserves the sum while forgetting coordinated changes of the form (t,−t).

This congruence differs from the first diagonal one. The pair (1,1) has difference zero but sum two, so it belongs to the difference-zero class and not to the sum-zero class. Conversely, (1,2) has sum zero but difference two. Writing both tests prevents the two diagonals from being conflated.

The missing-corner proof works again. The sum-zero class contains (0,0) and (1,2), but not (1,0). If this congruence were a product α×β, the first identification would force the second. Thus it too cannot be represented by separate equivalence decisions on the original coordinates.

A quotient's size does not distinguish these cases. Both diagonal quotients have three classes and both are isomorphic to C3. What differs is the map from the original product and therefore which distinctions are forgotten. Equal-sized or isomorphic targets can represent different observations of one source.

For a practical comparison, test the same input pair under both observations. The outputs answer different questions: difference versus sum. Choosing a quotient should be tied to the information the next task needs, rather than only to the convenience of obtaining a small target algebra.

Contents · Previous chapter · Next chapter

The six congruences are ordered by inclusion. Equality lies below each of the four line congruences, and the universal relation lies above them. Two distinct line congruences are incomparable. Their meet is equality because the corresponding lines intersect only at the zero pair.

Their join is universal because two distinct lines generate the whole group. Thus any two different middle congruences have the same meet and join. The congruence lattice has four incomparable middle elements between its bottom and top, rather than the four-element square obtained from the factor congruence lattices alone.

Choose three different line congruences α,β,γ. Then β∨γ is universal, so α∧(β∨γ)=α. But α∧β and α∧γ are both equality, whose join is equality. Since α is not equality, the distributive law fails in this congruence lattice.

This gives a concrete structural contrast with the majority-term lesson. A majority term would force congruence distributivity. Our product's explicit failure therefore rules out a majority term in this additive-group signature. It does not rule out a Malcev term: x−y+z is available in every group.

The point is not to attach as many theorem names as possible to one small example. It is to understand what the complete classification can certify. The four obvious coordinatewise congruences would conceal the nondistributive pattern; including the diagonal congruences exposes it and supports a conclusion about which terms cannot exist.

Contents · Previous chapter · Next chapter

Define a new coordinate map T(x,y)=(x−y,y). It is an invertible group homomorphism on A. Its inverse sends (u,v) to (u+v,v). Both formulas use addition and inverse modulo three, and composing them in either order returns the original pair.

In the new coordinates, the difference observation is simply the first projection: h(x,y)=u when (u,v)=T(x,y). The diagonal zero class D becomes {(0,0),(0,1),(0,2)}, a coordinate-axis subgroup in the new representation. The quotient now looks like forgetting the second new coordinate.

Does that make the earlier skew conclusion wrong? No. It was explicitly relative to the original decomposition into the stored x and y coordinates. T mixes those coordinates before exposing u and v. A relation that is not coordinatewise for one selected factorization can become coordinatewise after a different factorization is chosen.

The map T is not a separate relabelling of each original factor. Its first output depends on both x and y. If only independent coordinate relabellings were allowed, they could not turn the diagonal membership constraint into a rectangle. The change in permitted representation is doing substantive work.

This is an important reporting habit: state the coordinates relative to which a congruence is called skew. The term is not a claim that no imaginable isomorphic representation can simplify the quotient. It describes the relation between a particular product decomposition and a particular congruence, both of which belong in the mathematical specification.

Contents · Previous chapter · Next chapter

Keep the additive product but expand its signature with the unary operation r(x,y)=(x,0). This operation resets the second coordinate while retaining the first. It is a total function on A. A congruence of the expanded algebra must now preserve r as well as addition, inverse and zero.

The diagonal congruence fails. It relates (0,0) to (1,1), but r sends them to (0,0) and (1,0), which have different differences. Thus the old quotient cannot support a representative-independent reset operation. The new requirement removes this congruence from the available list.

The other diagonal fails too: r sends the sum-zero pair (1,2) to (1,0), whose sum is one. The horizontal and vertical line congruences remain compatible, as do equality and the universal relation. Since adding operations cannot create new congruences, these four exhaust the expanded algebra's congruences.

We can also prove the separation directly using a zero-class subgroup N stable under r. If (a,b) belongs to N, then r(a,b)=(a,0) belongs to N. Subtracting gives (0,b) in N. Hence every retained pair splits into its coordinate components, and N is a product of its coordinate subgroups.

The same carrier and old arithmetic now permit fewer quotient designs because an additional operation must survive. This is a concrete reason to revisit abstractions when an interface gains an operation. A summary preserving sums and differences under addition may fail when asked to perform a coordinate reset after information has been discarded.

Contents · Previous chapter · Next chapter

Replace C3×C3 by the additive product C3×C5. Its carrier has fifteen pairs. This time every subgroup is a product of coordinate subgroups, so every group congruence is coordinatewise. The difference comes from the coprime factor orders, not from a general rule that products must have skew congruences.

To prove the claim, let N be any subgroup and take (a,b) in N. Adding this pair to itself ten times yields (a,0), because ten is one modulo three and zero modulo five. Adding it six times yields (0,b), because six is zero modulo three and one modulo five.

Both coordinate components therefore belong to N. Conversely, any two components belonging to N can be added to produce their pair. Thus N equals the product of its first-coordinate component subgroup and its second-coordinate component subgroup. This argument works for every N, completing the classification pattern.

Each prime-order factor has only a zero subgroup and a whole subgroup, so there are four subgroups and four congruences. They are the same four kinds of independent-coordinate forgetting listed earlier. The diagonal coupling available for equal order-three factors has no analogue of that subgroup form here.

This is a useful changed-context warning. Seeing a skew congruence in C3×C3 establishes a counterexample to a universal coordinatewise claim. It does not say that every direct product has one. The scalar multiples ten and six provide an explicit reason the coprime example behaves differently, which is more informative than relying on its larger size.

Contents · Previous chapter · Next chapter

One question asks whether an algebra embeds into a product of quotient observations. The criterion is that the observation kernels intersect in equality. Another asks whether the image fills the product or satisfies additional consistency constraints. A third asks whether a congruence on an already-given product separates into factor congruences.

This lesson concerns the third question. We began with the full nine-element product and then examined ways of identifying its pairs. The difference-zero class is a subset of that product, but it is an equivalence class inside a quotient construction, not itself the full source algebra being represented.

The companion lesson on recovering an algebra from quotient observations concerns the first two questions. There, multiple maps can jointly distinguish every element while their image occupies only part of the ambient product. The common appearance of pairs and coordinate projections does not make the reader jobs identical.

A pullback is another nearby construction. It selects pairs whose images under two maps agree, and then checks that those compatible pairs form an algebra with the required mapping property. A kernel relation can be described using such a construction, but that does not automatically classify it as a product congruence.

When choosing a calculation, write the object being studied: an image, a subalgebra of compatible pairs, one congruence class, or a relation on all pairs of source elements. Their carriers live at different levels. Distinguishing them prevents a correct rectangularity observation about one object from being misapplied to a different product-related question.

Contents · Previous chapter · Next chapter

First specify the original factors, common signature and product operations. Then specify the proposed congruence, either by a complete partition, a membership rule or a homomorphism kernel. Verify that it is genuinely compatible before asking whether it is a product congruence. An invalid equivalence cannot be rescued by a coordinate description.

For a proposed representation θ=α×β, check both directions of the defining equivalence. Every θ-related pair must pass the coordinate tests, and every pair passing the tests must be θ-related. One-way containment only proves an approximation, which may merge too much or retain too many distinctions.

A missing rectangle corner is a quick disproof certificate. Record two tuples in one class and a coordinate-mixed tuple excluded from that class. Explain why a product class would include it. This supplies a finite reason that no suitable factor congruences can give the claimed relation in those coordinates.

In the additive abelian examples, the zero-class method gives a stronger classification tool. List subgroups, prove the list complete, and decide which split as coordinate subgroup products. Do not assume that any collection of projected values forms the correct subgroup or that class projections retain all coupling information.

Finally state allowed representation changes. If a coordinate-mixing automorphism is permitted, record it and its inverse, as with T(x,y)=(x−y,y). If only independent coordinate relabelling is allowed, do not use that stronger transformation unnoticed. A clear audit records the original decomposition and the exact sense in which the quotient does or does not separate.

Contents · Previous chapter · Next chapter

Replace C3×C3 by C5×C5 and define h(x,y)=x−2y modulo five. Verify that h is an onto additive homomorphism, find its zero class, and decide whether its kernel congruence is coordinatewise in the original factors. Try to produce a missing-corner witness before listing every class.

The zero class consists of pairs (2t,t) as t runs through residues modulo five. Explicitly it is {(0,0),(2,1),(4,2),(1,3),(3,4)}. Every coordinate value occurs, but only five of the twenty-five possible pairs belong to the class.

It contains (0,0) and (2,1), while excluding (2,0), whose observation is two. A product congruence relating the first two pairs would have to relate (0,0) to (2,0). Therefore the kernel is skew. Its validity follows from h preserving the group operations, just as in the original example.

Now add the reset r(x,y)=(x,0). It sends the zero-class pair (2,1) to (2,0), outside that class, so the congruence fails compatibility with the expansion. The same small witness answers both the rectangularity and reset questions, but the logical explanations are different and should both be stated.

For a further change, use new coordinates (u,v)=(x−2y,y). The inverse is (u+2v,v), so the observation becomes the first new projection. This confirms that the general distinction transfers: skewness refers to the chosen coordinates, while a verified mixed change of coordinates may expose a simpler form of the same quotient.

Contents · Previous chapter · Next chapter

Does skew mean the quotient operation is malformed? No. The diagonal examples are kernels of verified homomorphisms and give well-defined quotient groups. Skew describes failure to split the congruence into independent factor congruences for the specified product decomposition. It is a structural distinction, not an error message.

Can a class project onto every coordinate without containing every tuple? Yes. The diagonal zero class projects onto both C3 factors while containing only three of nine tuples. Coordinate surjectivity establishes individual availability, not simultaneous availability. The missing-corner calculation makes the lost constraint explicit.

Does isomorphism of quotient targets imply the same information is lost? No. The sum and difference observations both have target C3 but identify different pairs in the source. To describe information loss, keep the homomorphism or kernel, not merely the target's name and size.

Is checking one class enough? In an additive group, the zero class determines the whole congruence through the difference criterion proved earlier. In a general algebra, that shortcut is unavailable without additional hypotheses. A class-level witness can disprove product form, but a claim about the entire relation still needs an appropriate complete argument.

Must I enumerate every congruence to disprove coordinatewise decomposition? No. One valid skew congruence suffices to refute the universal claim. Enumeration supplies further structural understanding and can support conclusions such as failure of distributivity, but it is not required for the basic missing-corner counterexample.

Contents · Previous chapter · Next chapter

Start with the difference observation on C3×C3. List its three classes, verify the homomorphism equations and calculate one quotient sum using two different pairs of representatives. Then produce the missing-corner contradiction without relying on a picture. These checks establish validity and skewness independently.

Next classify the four lines in the nine-element group and explain why no other proper nonzero subgroup exists. Identify which lines are coordinate axes and which couple the coordinates. Translate that list into six congruences, then compute one meet and join of distinct middle relations.

After that, make one controlled change at a time. Add the coordinate reset and see which congruences disappear. Change the factor orders to three and five and use scalar multiples to split every subgroup element. Change coordinates with T and verify both inverse equations before reinterpreting the quotient.

Finally compare the three nearby questions: representing an algebra through several observations, selecting compatible pairs, and quotienting an existing product. For each, identify the source, target and object whose membership is being tested. The distinctions make the surrounding reading routes useful rather than interchangeable.

The capability to retain is deciding when separate coordinate summaries are sufficient. Coordinatewise operations do not guarantee coordinatewise information loss. A quotient may preserve a relationship while forgetting the individual values that produced it. By checking complete classes, missing corners and the permitted coordinate transformations, you can describe that loss accurately and carry the conclusion into a changed model without assuming more than the operations justify.

Contents · Previous chapter · Continue to related reading