The Gold Standard of Universal Algebra | Verifying Term Equivalence Between Different Operation Sets

An algebra consists of a carrier and specified operations. A signature records the operation names and their arities. A binary operation accepts two inputs, a unary operation accepts one, and a nullary operation supplies a designated element without an input. These choices determine which formal expressions may be built.

For a group, one familiar signature contains multiplication, inverse and the identity constant. Another description might contain only right division and the identity constant. Both descriptions can act on the same group elements. The question is whether the shorter instruction list retains all the calculations available through the longer one.

Do not answer by counting symbols. One binary operation may encode information that several other operations expose separately. Conversely, a long list can contain operations that contribute nothing new because they are already definable from the others. The relevant comparison concerns the resulting functions, not the number of names on the instruction sheet.

Consider a calculator with a multiplication button and an inverse button. Replacing these with a right-division button changes the immediate actions the user sees. If a fixed sequence of the new actions reproduces each old action on every allowed input, the replacement may preserve expressive power. We still need the reverse construction before calling the descriptions equivalent.

Record the two signatures side by side, including their constants. Under each proposed definition, identify which symbols belong to the destination language. This simple check catches circular translations, where the supposedly eliminated operation has quietly remained inside the formula used to define it.

Contents · Next chapter

A term is a finite expression made from variables and the declared operation symbols. Evaluating a term in an algebra produces a term operation. Different expressions may induce the same function. Term equivalence concerns these functions, rather than literal equality between the expressions that describe them.

Suppose a proposed translation replaces an old binary operation m by a new-language term t(x,y). The obligation is m(a,b)=t(a,b) for every pair of carrier elements a,b. A successful calculation at a=0 and b=0 establishes one instance. It does not certify the entire binary operation unless additional reasoning connects that instance to every possible input.

For a finite carrier with n elements, a complete binary comparison checks n² ordered pairs. A ternary comparison checks n³ triples. Such a test proves agreement for the particular operation tables supplied. It does not establish a uniform formula for an infinite family of algebras whose tables vary with a parameter.

For an infinite carrier, a symbolic derivation is usually more useful. Keep the inputs arbitrary and use only laws known to hold in the algebra. If a step commutes two factors, mark the commutativity assumption. A calculation intended for all groups must remain valid when the group is not commutative.

There are therefore two separate questions: is the proposed expression a term in the permitted language, and does its evaluation equal the operation being replaced? A syntactically valid term can compute the wrong function. A correct numerical formula can use forbidden symbols. Both checks must pass.

Contents · Previous chapter · Next chapter

Let G be any group with multiplication written by juxtaposition, inverse x⁻¹ and identity e. Define d(x,y)=xy⁻¹. This is right division under our convention: its value multiplied on the right by y returns x. Indeed, d(x,y)y=(xy⁻¹)y=x(y⁻¹y)=xe=x.

The formula is a permitted term of the usual group signature. Its only ingredients are the two variables, inverse and multiplication. No extra carrier element has been chosen as a parameter. We can therefore interpret a new binary symbol d by that term and keep the same designated identity e.

This proves one direction of definability. Any calculation using d and e can be expanded into a calculation using multiplication, inverse and e. Replace each occurrence of d(u,v) with uv⁻¹, continuing until every d has disappeared. Nested expressions cause no conceptual difficulty because the replacement applies to their construction trees.

For example, d(d(x,y),z) expands to (xy⁻¹)z⁻¹. The expression d(x,d(y,z)) instead expands to x(yz⁻¹)⁻¹, which simplifies to xzy⁻¹. These are not generally equal. Introducing a division-like symbol does not make it associative, and a translation must preserve the actual order of operations.

In the additive group of integers, the same definition becomes d(x,y)=x−y. At x=11, y=4 and z=2, the first nesting gives 5 while the second gives 9. This numerical check makes the bracketing issue visible before we use the new operation to reconstruct the old language.

Contents · Previous chapter · Next chapter

Now suppose d and e are available, interpreted as above. The inverse of x can be recovered as d(e,x), because ex⁻¹=x⁻¹. Multiplication can then be recovered as d(x,d(e,y)). The inner expression gives y⁻¹, and right division by y⁻¹ gives x(y⁻¹)⁻¹=xy.

Both recovery formulas use only d, e and the variables. They do not use a multiplication symbol hidden inside a definition. Together with d(x,y)=xy⁻¹ in the other direction, they give a complete two-way translation between the two operation lists. The identity constant is retained directly in both signatures.

Try the recovery in the additive group of integers. With d(x,y)=x−y and e=0, the inverse formula gives d(0,7)=−7. The multiplication-symbol analogue is addition, recovered by d(8,d(0,5))=8−(−5)=13. The nested subtraction reproduces addition without assuming subtraction itself is associative.

The symbolic argument works in noncommutative groups too. It uses associativity, the inverse laws and the fact that the inverse of an inverse is the original element. It never exchanges x with y. That is why the formula can be transferred from numerical addition to permutation composition or matrix groups within their declared domains.

A useful verification record contains three lines: the definition of d, the recovered inverse, and the recovered product. Check each with arbitrary inputs. If only the first line is supplied, you have established a term-defined reduct or expansion, but have not yet established that the old operations can all be recovered.

Contents · Previous chapter · Next chapter

Take the group expression w(x,y,z)=x(y⁻¹z). A translation into d and e can be constructed from the inside outward. First represent y⁻¹ by d(e,y). Next represent its product with z by d(d(e,y),d(e,z)). Finally multiply x by that result using the same recovered-product formula.

The resulting term is d(x,d(e,d(d(e,y),d(e,z)))). It looks longer than the original, but every symbol belongs to the new language. Evaluating the innermost inverse expressions, then the reconstructed inner product, then the outer product returns x(y⁻¹z). The length of the expression is separate from its correctness.

Use the additive group modulo 7 for a concrete check. Let x=5, y=3 and z=6. The original calculation is 5+(−3+6)=8, giving residue 1. With d(a,b)=a−b modulo 7, the inner d(e,y) is 4 and d(e,z) is 1. Their reconstructed sum is d(4,1)=3.

The remaining expression is d(5,d(0,3)). Since d(0,3)=4 modulo 7, the result is d(5,4)=1. Every intermediate value stays inside the declared carrier. We have checked the translation tree, rather than assuming that a familiar-looking subtraction expression can be regrouped freely.

This example also shows why equivalent languages can have different practical conveniences. One gives a short expression where the other gives a nested construction. Term equivalence certifies availability of the function. It does not assert equal expression length, equal human readability or equal cost in a particular implementation.

Contents · Previous chapter · Next chapter

There are infinitely many formal terms even in a small finite signature. Fortunately, proving term equivalence does not require listing all of them. Once every basic operation has a valid definition in the other language, any larger term can be translated recursively by replacing its operation nodes.

The proof follows the way terms are built. A variable translates to itself. A designated constant translates to its chosen variable-free defining term. If an expression is formed by applying a basic operation to already constructed subterms, translate those subterms and insert them into the defining term for that operation.

Induction on the finite expression tree shows that the translated term has the same value on every assignment. Each replacement is correct for every possible value of its inputs, so it remains correct when those inputs are themselves the values of complicated subexpressions. That is the compositional reason the method scales.

Carry out this argument in both directions. It shows that every term operation available through the first signature is available through the second, and conversely. These opposite inclusions establish equality of expressive power at every arity under the stated convention for constants.

Notice what the proof does not require: the translated expression need not return to exactly the same written string after translating back. Different strings can evaluate to the same function. The round trip must preserve interpretation, not typography. Confusing those two requirements would incorrectly reject ordinary simplifications such as inserting or removing an identity operation.

Contents · Previous chapter · Next chapter

For a second family, use the two-element Boolean algebra {0,1}. Its familiar operations are AND, OR, NOT, and constants 0 and 1. Define N(x,y)=NOT(x AND y), the NAND operation. It is already a term of the familiar Boolean language, so one translation direction is immediate.

Choose the alternative signature containing N and the constant 0. Recover NOT(x) as N(x,x). Recover AND(x,y) as N(N(x,y),N(x,y)). Recover OR(x,y) as N(N(x,x),N(y,y)). Finally recover the missing constant 1 as N(0,0). These formulas use no unnamed parameters.

Check the binary formulas on all four ordered inputs. NAND produces outputs 1,1,1,0 on 00,01,10,11. Applying NAND to two copies of that output reverses it, giving 0,0,0,1, which is AND. Applying NAND to the two individual negations gives 0,1,1,1, which is OR.

The point is not merely that NAND is a useful circuit gate. We have supplied a complete mutual translation of specified algebraic operations on the same carrier, including the constants. The construction also makes sense in any Boolean algebra, with NAND defined by complement of meet and the corresponding Boolean identities.

Before extending a two-entry truth-table argument to every Boolean algebra, identify that additional justification. The general statement follows from the Boolean laws, including De Morgan's laws. The small table is a transparent finite check; the laws explain the broader scope of the same formulas.

Contents · Previous chapter · Next chapter

Suppose the alternative Boolean signature contains only AND, together with constants 0 and 1. AND is certainly available in the full Boolean language. But can the restricted language recover NOT? Every operation built using AND and these constants is order-preserving on 0<1, whereas NOT reverses that order.

To justify the invariant, variables are order-preserving, constants are order-preserving, and applying AND to order-preserving functions gives another order-preserving function. Induction over the term construction preserves the property. NOT sends 0 to 1 and 1 to 0, so it cannot be one of those term operations.

There is also a direct obstruction to recovering OR in this restricted language. A binary AND-term simplifies to one of 0,1,x,y,x AND y. Repetition of an input changes nothing, combining with 1 changes nothing, and combining with 0 gives 0. This exhausts the possible variable subsets in two inputs.

OR differs from each listed function. It is not constant; at inputs 01 it differs from x and from AND, while at 10 it differs from y. Thus the restricted signature cannot express OR either. Having access to the same two carrier elements does not compensate for the missing operations.

This counterexample gives a reliable way to disprove term equivalence. Find a property preserved by all permitted term constructions, then show that a required operation violates it. A failed search for a formula is weak evidence; a preserved invariant rules out every formula at once.

Contents · Previous chapter · Next chapter

Different authors and applications handle zero-arity operations differently when discussing clones of term functions. Our comparison explicitly includes designated constants and asks for variable-free definitions of them. This prevents a positive-arity constant function from silently standing in for a nullary symbol.

Remove the constant 0 from the NAND signature and leave only the binary operation N. With a variable x available, the term N(x,N(x,x)) always evaluates to 1 in the two-element Boolean algebra. Applying N to two copies of that term always gives 0. Thus positive-arity constant functions remain constructible.

However, there is no variable-free term at all in a language containing only a binary operation and no constants. Every finite construction tree needs leaves. Without variables or nullary symbols, there is nothing from which to begin. The existence of a unary expression that ignores its input does not create a ground term.

Accordingly, NAND alone has the familiar positive-arity expressive completeness, but it does not meet our stronger constant-inclusive translation requirement for the bounded Boolean signature. Adding one designated Boolean constant fixes that issue, as the formulas in Chapter 7 demonstrate. This is a convention boundary, not a contradiction.

When comparing two sources, check whether their definition of term equivalence includes nullary operations, only positive arities, or an explicit convention about constant functions. State the choice once, then use it consistently. Otherwise two correct claims using different conventions can appear to disagree about an example that both actually understand.

Contents · Previous chapter · Next chapter

Isomorphic algebras and term-equivalent algebras answer related but different questions. An isomorphism normally compares algebras of the same signature through a bijection of their carriers. Term equivalence, as used here, compares operation languages on the same fixed carrier through mutual term definitions.

Take A={0,1} with addition modulo 2, additive inverse and designated zero 0. Define another group structure B on that same set by x*y=x+y+1 modulo 2. Its identity is 1, and every element is its own inverse. The bijection h(x)=x+1 is an isomorphism from A to B.

Check the product equation: h(x+y)=x+y+1, while h(x)*h(y)=(x+1)+(y+1)+1=x+y+1 modulo 2. The designated identity also travels correctly, since h(0)=1. So the two group structures are isomorphic after relabelling.

They are not term-equivalent on the fixed labelled carrier under our convention. Every variable-free term of A evaluates to 0, because its only constant is 0 and its operations keep 0 at 0. It cannot define B's identity constant 1. The obstruction concerns the fixed interpretation of elements, not their abstract group type.

The repair is to say precisely what may change. If relabelling is allowed, transport one structure along a bijection before comparing languages. If the carrier labels must stay fixed, test mutual definability directly. Saying that two descriptions are “the same” without specifying this permission leaves the central mathematical question unanswered.

Contents · Previous chapter · Next chapter

A term definition must use the permitted variables and operation symbols. A polynomial operation in universal algebra may additionally use fixed carrier elements as parameters. Allowing those parameters can make a failed term translation appear to work, but it has changed the requirement.

In the additive group modulo 5 with its usual zero constant, the unary function x↦x+1 can be written using addition and the fixed element 1. It is a polynomial operation. It is not a term operation of the original signature, because every original unary term sends 0 to 0, whereas this function sends 0 to 1.

If a proposed translation uses such a shift, ask where the element 1 came from. Is it a declared constant, a variable that must remain free, or a supplied parameter? These roles cannot be exchanged merely because the same numeral appears in an informal calculation.

Naming the parameter explicitly creates an expanded algebra. That can be an appropriate modelling choice, but the equivalence claim must then name the expansion. It should not be presented as a proof about the original operation list. The earlier guide on term and polynomial operations develops this distinction in detail.

This matters for structural consequences. A subset closed under the original operations need not contain an external parameter. A map preserving the original signature need not send that parameter to the element chosen in its target. Parameter-free translations avoid those extra obligations; parameter-dependent translations require them to be stated and checked.

Contents · Previous chapter · Next chapter

Suppose two operation sets are term-equivalent on A. A nonempty subset closed under the first set of operations is closed under every term built from them. Since each operation of the second set is one of those term operations, the subset is also closed under the second set, including its required constants.

The reverse translation gives the converse. Thus the two descriptions have exactly the same subalgebras on the fixed carrier. This is a consequence of mutual definability, not an additional assumption. For the group example, closure under multiplication, inverse and identity agrees with closure under right division and identity.

Congruences are preserved for a similar reason. A congruence compatible with basic operations is compatible with every term operation, by induction through the expression. Therefore it is compatible with all the translated basic operations. Applying the reverse argument shows that the congruence collections coincide.

These facts give useful rejection tests. If one proposed description has a subalgebra that the other does not, they cannot be term-equivalent under the stated constant convention. Likewise, a compatible partition for one that fails for the other rules out mutual term definability.

Do not use these tests backwards without a theorem. Two algebras can share selected substructures or congruences while having different term operations. Structural agreement supplies necessary evidence, but the actual two-way formulas remain the direct certificate of equivalence. A short list of matching invariants is not automatically a complete description of an algebra's expressive power.

Contents · Previous chapter · Next chapter

Term evaluation commutes with homomorphisms. If h preserves the basic operations, then applying h after a term calculation equals evaluating the same term on the images of its inputs. This follows from the same expression-tree induction used to extend a translation from basic operations to all terms.

Consequently, if a whole class is re-described using the same defining terms in every source and target algebra, its homomorphisms are preserved by the translation. A group homomorphism automatically preserves d(x,y)=xy⁻¹. Conversely, a map preserving d and e preserves inverse and multiplication through their recovery formulas.

The phrase “the same defining terms” is important. Suppose each individual finite algebra admits some convenient formula, but the formula changes unpredictably between algebras. That gives pointwise facts about those algebras. It does not immediately supply a uniform translation of maps between them.

For example, in the additive group modulo 7, negation can be written as six repeated copies of x. In the additive group modulo 5, four copies give negation instead. A single fixed count of copies cannot represent negation across all cyclic groups of arbitrary order, and certainly cannot do so in the additive integers using only addition and zero.

When making a claim about a family, write the defining term independently of the chosen member and prove its equation throughout the family. When making a claim about one finite table, say so. This distinction protects a correct local shortcut from becoming an unsupported universal conclusion.

Contents · Previous chapter · Next chapter

Consider two descriptions of the additive group modulo 7. One has addition, negation and zero; the other has only addition and zero. The omitted negation is recoverable as x+x+x+x+x+x, because 6x=−x modulo 7. The reverse direction merely retains operations already present, so these particular algebras are term-equivalent.

Now make the same comparison on the integers. Every unary term built from addition and zero has the form nx for a nonnegative integer n. The variable supplies coefficient 1, zero supplies coefficient 0, and combining terms adds their coefficients. This inductive description excludes negative coefficients.

The function −x cannot equal nx on every integer for any nonnegative n. At x=1, it would require −1=n. Therefore the addition-and-zero reduct of the integers cannot recover negation by a term. The same written operation lists have a different equivalence outcome because their interpretations have changed.

This is a useful changed-domain diagnostic. Finite wraparound allows repeated addition to simulate an inverse in the modulo-7 example. Ordinary integer addition has no such wraparound. A learner who memorises “inverse can be omitted” without carrying the carrier and exponent assumption will transfer the shortcut incorrectly.

The comparison also distinguishes definability from a practical algorithm using extra control operations. A program might search for an integer's inverse or use a subtraction instruction elsewhere. That does not create a term in the restricted algebraic signature. The available mathematical operations must remain the ones specified in the question.

Contents · Previous chapter · Next chapter

Begin with two complete operation lists on a stated carrier. Record every arity and constant. If the carrier is being relabelled, separate that preliminary step from the comparison of term languages. Decide explicitly whether nullary operations are included, as they are throughout this guide.

Next write one defining term for each basic operation in each direction. Check that the terms contain only symbols from the intended language and no unnamed fixed parameters. A formula that invokes the operation it was supposed to eliminate is circular, even if it produces correct numerical answers when evaluated by hand.

Then prove equality of the resulting functions. Use complete tables for small finite cases and symbolic laws for general families. State whether the proof covers a particular algebra, every algebra in a named class, or only positive arities. Keep counterexamples beside failed directions rather than deleting them from the record.

Finally, derive the consequences you need. Perhaps you want identical subalgebras, congruences or homomorphisms under a uniform re-description. Explain why term preservation gives that consequence. Do not add claims about efficiency, implementation behaviour or numerical stability that the algebraic proof does not address.

A compact certificate contains the carrier, both signatures, both translation lists, the verification method and the scope statement. Another reader should be able to reconstruct the result without guessing what a numeral means or which inverse convention was used. That is a stronger outcome than a bare declaration of equivalence.

Contents · Previous chapter · Next chapter

Work on the two-element Boolean carrier. Compare the familiar signature AND, OR, NOT, 0, 1 with an alternative containing NAND and the constant 1, rather than the constant 0 used earlier. Find definitions in both directions. Then remove the constant 1 as well and explain exactly which part of your conclusion changes.

With NAND and 1, recover 0 as N(1,1). Negation, conjunction and disjunction use the same formulas as before. The original constant 1 is already present, and the recovered 0 is a variable-free term. Thus both directions satisfy our constant-inclusive definition of term equivalence.

After removing the last constant, all positive-arity Boolean functions remain expressible through NAND, including constant-valued functions that use a dummy input. However, there is still no variable-free term. The stronger comparison with the bounded Boolean signature therefore fails at nullary arity, not at the binary truth tables.

For a second change, replace NAND by AND while retaining both constants. The missing negation cannot be recovered because every available term is order-preserving. This failure concerns positive arity and survives even after the constant issue has been repaired. The two failures have different causes.

A successful answer identifies those causes separately. Adding constants repairs an absent ground-term starting point. It does not make an order-preserving operation set express an order-reversing function. The exercise tests whether you can diagnose the actual obstruction instead of applying a single remembered slogan about functional completeness.

Contents · Previous chapter · Next chapter

Does term equivalence mean the signatures must match? No. Different signatures are the point of the comparison. The operations must be mutually definable by terms on the fixed carrier, with the constant convention stated. An ordinary isomorphism instead compares corresponding operations in a specified common signature through a bijection.

Is adding an operation always a genuine expansion of expressive power? No. If the added operation is already term-definable from the old ones, it supplies a convenient name without adding new term functions. If it needs a previously unnamed parameter or violates an invariant of old terms, more careful analysis is required.

Can a successful translation be impractically long? Yes. Algebraic availability does not impose an efficient representation. Even recursive replacement of a short expression may repeat large subexpressions. Questions about sharing intermediate results, program size and evaluation cost belong to a further analysis with an explicit computational model.

Can agreement on subalgebras prove term equivalence? It can rule equivalence out when the subalgebras differ, but agreement alone is not the certificate used here. Mutual definitions establish the whole collection of term operations directly. Avoid promoting a useful necessary check into an unproved converse.

Why insist on no hidden parameters? Because the task concerns what the declared language can construct. Parameters add permitted elements and can change which subsets or maps behave correctly. They are legitimate when explicitly allowed, but they answer a different definability question. Keeping the distinction visible makes later structural arguments dependable.

Contents · Previous chapter · Next chapter

Start with the group division example. Write the three translation formulas from memory and check them with arbitrary symbols. Then evaluate a nested expression in a small cyclic group, recording each intermediate result. This combines a general proof with a concrete calculation that exposes bracketing mistakes.

Next reconstruct the Boolean NAND translations and verify the four binary input pairs. Explain the role of the designated constant separately from the role of the binary gate. Change which constant is named, then remove constants entirely, and state the resulting nullary limitation without denying positive-arity completeness.

For a proof of impossibility, use the AND-only language. Show by induction that every term is order-preserving and use NOT as the forbidden target. This practice develops a different skill from finding a clever formula: identifying a property that no permitted construction can escape.

Finally, compare the modulo-7 additive example with the integers. Explain why a finite identity permits one recovery formula and why a coefficient invariant defeats the analogous infinite claim. The changed carrier should alter your conclusion for a stated reason, rather than merely making the arithmetic look less convenient.

The capability to retain is precise translation with an honest scope. A shorter operation list may preserve an entire algebraic language, or it may lose a single crucial function. Mutual definitions, constant bookkeeping and explicit counterexamples let you tell those situations apart and carry the result into the next structural question.

Contents · Previous chapter · Continue to related reading