The Gold Standard of Universal Algebra | Computing Subalgebra Joins Without Mistaking Them for Unions

Fix an algebra A with a carrier set and specified basic operations. A subuniverse is a subset closed under every operation, including the requirement to contain every designated constant. A nonempty subuniverse carries the restricted operations and gives a subalgebra. We compare these subsets by inclusion.

Now take two subuniverses B and C. An upper bound is another subuniverse containing both. Their join is the least such upper bound: it is contained in every other subuniverse that contains B and C. The word least refers to inclusion, not merely to having a small number of elements.

Their union is the smallest subset containing both, but the order we are studying contains only closed subsets. A union that fails closure is not even a candidate upper bound in that order. The join must include any extra outputs forced by mixing elements from the two inputs.

For comparison, a lower bound is a subuniverse contained in both B and C. Their meet is the greatest lower bound. Intersection will work because applying an operation to inputs in both subsets keeps the output in both. The two constructions behave asymmetrically for a structural reason.

Write the ambient algebra before using a join symbol. The same carrier can have different closed subsets when its operations change. Even the phrase “join of two subsets” is incomplete unless the order, the allowed subsets and the closure requirements have been specified. These choices determine what the calculation means.

Contents · Next chapter

Suppose x₁ through xₙ all belong to B∩C. They belong to B, so the output of any n-ary basic operation belongs to B. They also belong to C, so the same output belongs to C. Hence the output lies in the intersection. Every designated constant lies in both subsets as well.

This proves closure of B∩C. Any subset contained in both B and C is contained in their intersection. Therefore the intersection is the greatest lower bound, with no extra operation-generated elements needed. The proof works for arbitrary families of subuniverses, not only two.

For the empty family, the intersection is understood as the whole carrier A, which is closed. For a nonempty family, the intersection may be empty when the signature has no constants. That is why it helps to state whether the objects being ordered are subuniverses including the empty one, or only nonempty subalgebras.

In groups, the identity constant belongs to every subgroup, so intersections are always nonempty. Our main residue examples therefore avoid this convention problem. Later we will inspect a constant-free example where it becomes essential rather than treating the group behaviour as universal.

The proof also explains why an elementwise overlap calculation is enough for meet. Closure follows from the hypotheses already established for B and C. For join, the inputs can come from different subsets, so neither closure hypothesis alone controls their combined output. That is the gap the next example exposes.

Contents · Previous chapter · Next chapter

Let A be the additive group C30, represented by the residues 0 through 29. The signature contains addition modulo 30, additive negation and constant zero. Let B be the subgroup generated by 6, and C the subgroup generated by 10. We use letters for subsets and C30 for the ambient group.

The five elements of B are 0,6,12,18,24. Adding another 6 returns from 24 to 0 modulo 30. Negation reverses this cycle, and zero is present. The three elements of C are 0,10,20. Adding another 10 returns to zero, and negation exchanges 10 and 20.

Both lists are closed under all group operations. One way to verify addition is to observe that sums of multiples of 6 remain multiples of 6 modulo 30, and likewise for multiples of 10. Because 6 and 10 divide 30, reduction modulo 30 preserves the respective divisibility descriptions.

Their intersection is {0}. Their union is {0,6,10,12,18,20,24}, containing seven elements. These are ordinary set calculations at this stage. We have not yet decided whether the seven-element union is closed, and therefore have not identified the join.

Keep the source of each number visible. Elements 6 and 10 belong to different subgroups. Once we allow both as inputs to the same ambient addition, new sums become possible. The join calculation concerns precisely those mixed computations that neither separate subgroup had to contain on its own.

Contents · Previous chapter · Next chapter

Add 6 from B to 10 from C. The result is 16 modulo 30. It belongs to neither displayed subgroup and is absent from the seven-element union. Therefore B∪C is not closed under addition. It cannot be their join in the inclusion order of subalgebras.

This single failed pair is enough to reject the union. There is no need to test every pair after a valid counterexample has been found. However, finding one missing output does not finish the join construction. Adding 16 may enable further outputs, so a repaired list still needs closure verification.

For instance, the combined operations also allow 6+6−10=2. Any subalgebra containing B and C must contain 2, since it must contain both initial numbers, their sum and the negative of 10. Once 2 is present, repeated addition produces every even residue modulo 30.

The important evidence is the expression producing 2. It is a membership certificate: a finite calculation using only admitted inputs and permitted operations. Merely noticing that 2 would make a convenient generator would not prove that every common upper bound must contain it.

The root guide's single-generator closure example establishes the basic generation idea. Here the new reader job is to compare two already closed systems, locate the mixed-operation failure and prove the least common closed extension. That distinction becomes increasingly useful when many subalgebras must be combined or compared.

Contents · Previous chapter · Next chapter

Let E be the set of all even residues modulo 30: 0,2,4 and so on through 28. It has fifteen elements. It contains B and C. It is closed under addition and negation modulo 30, because subtracting a multiple of 30 does not change parity, and it contains zero.

Thus E is a common upper bound, so the join cannot require anything outside E. Conversely, every common upper bound contains 6 and 10, hence contains 6+6−10=2. Closure under addition then forces all fifteen even residues. Therefore every common upper bound contains E.

These arguments point in opposite directions and meet exactly. E is an allowed common upper bound, and E is contained in every allowed common upper bound. Consequently B∨C=E. The join has fifteen elements even though the union had only seven and the intersection only one.

This is a reliable proof pattern for generated objects. An invariant such as evenness gives an upper bound on what can be produced. Explicit expressions give a lower bound by showing what must be produced. When the two descriptions coincide, the answer is certified without an enormous operation table.

Do not confuse a closed superset with the least closed superset. The whole thirty-element group is also closed and contains both inputs, but it is too large. The proof of minimality is the part that excludes arbitrary additions. A complete answer explains both why the candidate works and why no smaller candidate can work.

Contents · Previous chapter · Next chapter

Start with X₀=B∪C and all required constants. Form X₁ by adding every basic-operation output whose inputs lie in X₀. Continue with X₂ using all inputs in X₁, and repeat. Each step retains everything already present, so the sets increase rather than replacing earlier outputs.

In a finite carrier, a strict increase adds at least one new element. Eventually a stage repeats: Xₖ₊₁=Xₖ. At that point every operation applied to inputs in Xₖ returns an element of Xₖ, so the set is closed. Its construction used only operations forced by the initial union.

Inductively, every subuniverse containing X₀ contains each stage. It therefore contains the final set. This proves minimality. Termination plus a closure check gives sufficiency, while the stage-by-stage containment argument establishes that no unnecessary elements were introduced. Both are required for a trustworthy algorithm.

For C30, a simple implementation can store residues in a set, add all pairwise sums modulo 30 and all negatives, and stop when the set does not change. Retaining an expression for each newly discovered residue turns the output into an auditable collection of membership witnesses.

The algorithm's finite termination depends on the carrier being finite. The definition of generated closure remains meaningful on an infinite carrier, but a program may keep discovering new elements forever. Do not infer a finite runtime merely from the fact that each individual operation accepts finitely many inputs.

There is also a practical difference between a round and a discovery. A round should use a clearly specified current set, while an implementation may immediately reuse newly discovered elements. Either approach can reach the same least closed set if it eventually checks every required tuple. Their intermediate stages and operation counts can differ. Compare final closure and witness validity rather than assuming that an identical number of rounds is part of the mathematical answer.

Contents · Previous chapter · Next chapter

For any subset X of A, write Sg_A(X) for the smallest subuniverse containing X. One definition takes the intersection of all subuniverses containing X. This family is nonempty because A itself belongs to it. Intersection closure ensures that the resulting set is a subuniverse.

The join formula is B∨C=Sg_A(B∪C). Every common upper bound contains the union and therefore its generated closure. Conversely, that closure is itself a subuniverse containing both B and C. These two facts prove the least-upper-bound property directly.

For a whole family of subuniverses, take the generated closure of their union in the same way. The construction does not depend on grouping the family into pairs. The least-upper-bound property ensures that repeated binary joins and the join of a finite family agree when they concern the same ambient order.

Generation has three basic checks. It contains X; enlarging X cannot shrink the generated set; generating again from an already generated set changes nothing. In symbols these are extensivity, monotonicity and idempotence. Each follows from the minimal-closed-superset definition rather than from a special feature of residues.

Use these properties to inspect a computed result. If an alleged closure drops an input, shrinks when new inputs are admitted, or grows after being closed again under the same operations, something is wrong. These are necessary consistency checks, although they do not by themselves establish that an arbitrary procedure implements the intended algebraic closure.

Contents · Previous chapter · Next chapter

If B⊆C, then B∪C=C, which is already closed. Their join is C. More generally, a union works whenever every mixed operation output remains in the union. There is no need to enlarge a set that already satisfies all the closure obligations.

For two subgroups, the union is a subgroup exactly when one contains the other. To see the nontrivial direction, suppose neither contains the other. Choose b in B but not C and c in C but not B. If b+c belongs to B, subtract b to force c into B, a contradiction.

If b+c instead belongs to C, subtract c to force b into C, another contradiction. Hence the sum lies outside the union. This proof uses additive group operations; in a noncommutative group the corresponding product and inverse argument works with the appropriate order retained.

The nestedness conclusion should not be exported to arbitrary algebras. With only unary operations, a union of nonempty closed subsets is closed: an operation sees one input at a time, and that input belongs to some member whose closure supplies the output. Designated constants already belong to every member.

Thus the reason unions can fail is not simply that algebra is abstract. Multi-input operations can combine elements that previously lived in separate closed subsets. Removing those operations changes the closure problem. A useful explanation identifies the operation responsible for a failure instead of memorising union as always wrong.

Contents · Previous chapter · Next chapter

Return to residues modulo 30, but retain only unary negation and constant zero. Remove binary addition from the signature. The earlier subsets B and C remain closed, since both contain zero and are stable under negation. Their seven-element union is now also closed.

In this reduced algebra, the join is exactly the union. The calculation 6+6−10=2 is no longer a permitted construction because addition is not available. Although we can still write ordinary arithmetic outside the model, it cannot certify membership in a subuniverse generated using the reduced signature.

This is the same carrier with a different answer to the join question. No residue changed its identity. What changed was the list of operations that a closed subset must support. A displayed set alone does not determine its subalgebra structure or its generated extensions.

Restore addition and the join returns to the fifteen even residues. Now add a designated constant interpreted as 1. The original B and C cease to be subuniverses at all because they omit the new constant. Asking for their join as subalgebras of this expanded algebra is therefore ill-posed until the inputs are repaired.

One can instead ask for the generated closure of the same two underlying subsets in the expanded signature. The new constant supplies 1, whose repeated addition generates all thirty residues. That is a legitimate but different question. Distinguish changing the join of valid subalgebras from changing which subsets qualify as subalgebras in the first place.

Contents · Previous chapter · Next chapter

Let V be the two-dimensional vector space over the field F2. Its four elements are 00,10,01,11, with coordinatewise addition modulo 2. Regard it as an algebra with addition, zero and scalar multiplication. The one-dimensional subspaces H={00,10}, K={00,01} and L={00,11} are subalgebras.

Any two different lines intersect only at 00 and jointly generate V. For example, 10+01=11, so H∨K=V. Their union has three elements and misses 11. This is another mixed-output failure, now small enough to inspect in one glance.

Compare H∩(K∨L) with (H∩K)∨(H∩L). Since K∨L=V, the first expression is H. Both intersections on the right are {00}, so their join remains {00}. The two sides differ. The lattice of subalgebras need not satisfy the distributive law.

This result concerns the order of closed subsets, not distributivity of scalar multiplication over vector addition inside V. The vector space satisfies its usual algebraic laws. Its subspace lattice has a different pair of operations, meet and join, whose laws need their own proof.

The example also separates this topic from congruence-lattice results. A theorem about congruences produced by a special term does not automatically become a theorem about subalgebras ordered by inclusion. Name the objects being ordered and calculate the relevant operations before borrowing a lattice identity from another setting.

Contents · Previous chapter · Next chapter

A nonempty family of subuniverses is directed by inclusion when any two members are contained together in some member of that family. Unlike a chain, it need not compare every pair directly. The condition merely ensures that their information can be accommodated in another member already present.

Take finitely many inputs from the union of a directed family. Each input lies in some member. Directedness can be applied repeatedly to find one family member containing all those finitely many inputs. Closure of that member then supplies the operation output inside the union.

This proves that a directed union is a subuniverse for finitary operations. Constants lie in every family member. Hence the join of a directed family is simply its union; no further closure step is needed. Chains are a special case because the larger of two members contains both.

The finite arity matters. Directedness combines any finite list of witnesses, but need not combine infinitely many into a single member. A hypothetical operation taking infinitely many inputs could draw those inputs from endlessly larger members without all of them belonging to one member at once.

For a concrete infinite example, take an infinite-dimensional vector space whose vectors have finite support on basis symbols e₁,e₂,… . The span of the first n basis symbols forms an increasing chain of subspaces. Their union is the entire finite-support space. Each vector belongs to some finite stage even though no single stage is the whole space.

Contents · Previous chapter · Next chapter

Consider a two-element carrier {a,b} with one unary operation that fixes both elements and no constants. Every subset is a subuniverse, including the empty set. The nonempty singleton subalgebras {a} and {b} have empty intersection. Under a convention excluding empty algebras, their intersection is not a subalgebra.

Thus the poset of nonempty subalgebras need not have a meet for every pair in a constant-free setting. If one works with all subuniverses, including the empty one, intersection and generated-union formulas supply a complete lattice. Terminology and conventions determine which statement is correct.

Add a constant interpreted as a. Every subuniverse must now contain a, so the empty set and {b} are excluded. The smallest subuniverse is {a}. The intersection issue disappears because every allowed subset shares the constant. Adding a constant can therefore change the order's bottom element and its members.

Our group examples contain zero as a designated constant, so all their subuniverses are nonempty. It is safe there to speak of the subgroup lattice without repeatedly qualifying emptiness. The safety comes from a stated operation in the signature, not from a general rule that intersections of nonempty sets remain nonempty.

When checking a source or a software package, look for its convention on empty carriers and nullary operations. If its Sub(A) includes empty subuniverses while another author's term subalgebra excludes them, apparently conflicting statements may be using different collections. Translate the convention before judging the mathematics.

Contents · Previous chapter · Next chapter

Let f:A→D be a homomorphism and B,C subalgebras of A. Their direct images are subalgebras of D: applying an operation to images gives the image of the corresponding source operation. Constants are preserved. We can therefore compare f(B∨C) with f(B)∨f(C).

They are equal. Every element generated from B∪C is a finite term value on elements of that union, including constants where required. Applying f transports that calculation to the same term in image elements. This proves f(B∨C) is contained in the join of the two images.

Conversely, every term calculation using elements of f(B)∪f(C) can choose source representatives in B∪C. Evaluate the term upstairs and apply f. This supplies the desired image element from B∨C. The two inclusions prove equality without requiring f to be injective or onto all of D.

For a worked check, reduce C30 modulo 6. The subgroup B generated by 6 maps to {0}. The subgroup C generated by 10 maps to {0,2,4}. Their join downstairs is {0,2,4}. The fifteen even residues forming B∨C map to exactly that same three-element set.

The image equality is useful because it lets a generated calculation be transported through a homomorphism. But do not infer that all lattice operations are preserved by direct image. The next example shows that intersections can behave differently when the map merges distinct source elements.

Contents · Previous chapter · Next chapter

Use V=F2² again and project onto the first coordinate p:V→F2. Let H={00,10} and L={00,11}. Their intersection is {00}, whose image is {0}. But both H and L project onto all of F2, so p(H)∩p(L)=F2. Direct image has enlarged the apparent overlap.

The reason is that two different source witnesses can produce the same target value. The target value 1 comes from 10 in H and 11 in L, but no element of H∩L maps to 1. Joining information and identifying information are separate operations, and their interaction needs explicit witnesses.

Inverse image always preserves intersections as sets. For joins of subalgebras, however, equality can fail. Include the diagonal line L into V. Let H and K be the horizontal and vertical lines. The inverse image of each of H and K is just {00} in L.

Their join upstairs is still {00}. Yet H∨K=V, whose inverse image under the diagonal inclusion is the whole L. Thus taking an inverse image after a join can produce more than joining the separate inverse images. The mixed sum 10+01=11 exists downstairs even though neither summand lies in the diagonal image.

These comparisons give a compact map checklist: direct images preserve generated joins; direct images need not preserve meets; inverse images preserve meets; inverse images need not preserve joins. In settings without constants, an inverse image can also be empty, so use subuniverses or check nonemptiness before calling it a subalgebra.

Contents · Previous chapter · Next chapter

For a proposed finite join J, first check that both input subalgebras lie inside it. Then check every basic operation on J, including constants. This proves that J is a common upper bound. It does not yet prove that J is the least common upper bound.

For minimality, attach a term expression to each element of J using inputs from the original union. Alternatively, give a generating argument such as the expression for 2 in the C30 example. Any closed common upper bound must contain those expressions' values, so it must contain J.

An invariant can help keep the construction small. In the residue example, evenness prevents odd values from appearing. In a vector example, a linear equation may define a closed containing subspace. The invariant must be preserved by every operation in the actual signature, not merely by the operation most visible in the calculation.

Counting is useful after these structural checks. Fifteen elements in the C30 join is consistent with the exhibited even residues, but the number alone does not identify the subset or prove closure. Two sets of equal size can contain different elements and obey different operation requirements.

If using software, keep the carrier, operation tables, starting subsets and stopping condition in the evidence. Test the known failing mixed pair and retain witness expressions for newly added elements. A printed final set is less informative than a result whose membership and minimality can be checked independently of the program.

Contents · Previous chapter · Next chapter

Replace C30 by C18. Let B be generated by 6 and C be generated by 9. Find their intersection, union and join. Then remove addition from the signature, retaining only negation and zero, and explain which answers change. Work through the mixed calculation before reading the solution.

The first subgroup is B={0,6,12}; the second is C={0,9}. Their intersection is {0}, and their union is {0,6,9,12}. Adding 6 and 9 gives 15, which is missing from the union, so the union is not a subgroup of the original additive group.

Any common subgroup contains 9−6=3. Repeated addition forces {0,3,6,9,12,15}. This set is closed under addition and negation modulo 18 and contains both inputs. Hence it is exactly the join. The proof again supplies a necessary generator and a matching closed upper bound.

After removing addition, negation exchanges 6 and 12 and fixes 0 and 9. The four-element union is therefore closed in the reduced signature, so it becomes the join. The intersection remains {0}. The changed answer follows from losing mixed addition, not from changing the underlying residues.

For a further check, project C18 modulo 3. Both input subgroups and their join map to {0}. This is consistent with direct-image preservation of joins, although the map discards the distinction between the four-element union and six-element generated subgroup. Agreement after a quotient does not prove those source subsets were equal.

Contents · Previous chapter · Next chapter

Why is union not automatically a subalgebra? Separate closure controls calculations whose inputs all belong to one subset. A multi-input operation may mix elements from different subsets and leave their union. The pair 6,10 in C30 provides an explicit failure.

Does join mean add every possible element? No. It means include exactly the elements forced by the allowed operations, equivalently the least closed common upper bound. The whole carrier is an upper bound, but it can be much larger than the join.

Can two different subalgebras have a union that is already closed? Yes. Nested ones always do. With only unary operations, nonempty unions of subuniverses are closed even without nestedness. The subgroup criterion depends on the additional group operations and should not be treated as a universal algebra theorem.

Is the join symbol an operation on the original elements? Here it is an operation on closed subsets ordered by inclusion. In a lattice algebra there may also be a basic operation called join on carrier elements. Those are different levels of description, even when similar symbols are used.

Do subalgebras always form a distributive lattice? No. The three lines in F2² explicitly violate distributivity. Does every nonempty-subalgebra poset even have all meets? Without constants and with empty algebras excluded, not necessarily. Stating the empty-subuniverse convention keeps the general lattice claim accurate.

Contents · Previous chapter · Next chapter

Begin with the C30 example and reconstruct the two subgroups without looking at their lists. Find one mixed output outside the union, then produce 2 from 6 and 10. Explain both directions of the minimality proof. The goal is an answer supported by a mechanism, not a remembered fifteen-element count.

Next run the same reasoning in the reduced unary signature. Say precisely which earlier expression is no longer permitted. This tests whether you regard an algebra as a carrier equipped with operations rather than as a set of numbers whose familiar arithmetic can always be used.

Then draw or list the five subspaces of F2²: zero, the three lines and the whole space. Compute the particular distributivity failure and both mapping counterexamples. These small complete examples make it possible to inspect every witness instead of relying on a broad verbal rule about preserving structure.

Finally, write the directed-union proof in your own words. Identify where finite arity allows finitely many inputs to be placed in one family member. Compare this proof with finite closure iteration: one concerns an already directed collection of closed sets, while the other constructs closure from a possibly unclosed union.

A successful explanation names the ambient operations, distinguishes set union from generated join, and supplies closure plus minimality evidence. When the signature, map or carrier changes, revisit those checks. That habit makes subalgebra calculations dependable and prepares the same style of reasoning for more complicated generated structures.

Contents · Previous chapter · Continue to related reading