The Gold Standard of Universal Algebra | Reconstructing Compatible Relations from Small Coordinate Projections

Imagine a list of allowed triples. You discard the triples and keep only the pairs appearing in each choice of two positions. Can you recover exactly which triples were allowed? Sometimes yes, sometimes no. Pairwise availability need not mean simultaneous availability, because a different original triple may witness each observed pair.

The short answer is that a compatible relation closed under a majority term is determined by its binary coordinate projections when the number of coordinates is finite. More generally, a relation closed under a near-unanimity operation with k+1 inputs is determined by its projections to k coordinates. The operation supplies a way to combine overlapping witnesses into one complete witness.

We will prove that mechanism explicitly. A four-input near-unanimity operation will then give a useful boundary example: its compatible relation can require three-coordinate information, so reducing everything to pairs would lose a real constraint. Finally, an infinite-coordinate example will show why the finite-coordinate qualification belongs to the statement.

This lesson concerns exact sets of allowed tuples and exact algebraic closure. It does not infer joint probabilities from marginal statistics, and it does not claim that sampled projections represent an unknown complete relation. Our Boolean tuples are teaching constructions whose membership and operation tables can be checked in full. The transferable task is to identify what evidence makes local observations sufficient for a global membership decision.

Contents · Next chapter

Let R be a subset of A³. Its projection to positions one and two contains a pair (a,b) exactly when some c makes (a,b,c) a member of R. The omitted coordinate is allowed to vary. Projection therefore records existence of a completion, not which completion supplied the evidence.

For a candidate tuple x=(a,b,c), passing all three pair tests means that (a,b) appears in the first-second projection, (a,c) appears in the first-third projection and (b,c) appears in the second-third projection. Each test can have a different witnessing triple. Nothing in the definition forces a common witness equal to x.

Every member of R passes these tests, so the reconstructed set formed by all tuples passing them contains R. The difficult direction is whether it contains anything extra. A lost constraint appears as a tuple outside R whose every small projection belongs to the corresponding projection of R.

Coordinate labels matter. The pair (0,1) in positions one and two describes a different observation from the same pair in positions two and three. Retain those labels when storing projections or comparing examples. Reordering coordinates can be legitimate, but it must reorder the tuple and the relation consistently. Much confusion about projection arguments comes from treating a list of observed values as if it also retained their original positions and their common source witness.

Contents · Previous chapter · Next chapter

A relation R contained in A raised to a finite power is compatible with an algebra on A when it is closed under every basic operation applied coordinatewise. For a binary operation f, take two tuples in R and apply f to their first entries, then their second entries, and so on. The resulting tuple must again belong to R.

For an operation with m inputs, arrange m member tuples as rows. Apply the operation down each coordinate column. Compatibility requires that the output row remain in R. The number of operation inputs and the number of relation coordinates are independent numbers; a four-input operation can preserve a relation of triples.

Closure under all basic operations implies closure under all term operations, by induction through a term. Projection variables select one input row, and each operation step combines rows already known to lie in R. Constants, if present in the signature, require their corresponding constant tuples to belong to R as well.

Our reconstruction proof needs only closure under the particular near-unanimity operation used in it. A compatible relation has that closure whenever the algebra possesses a near-unanimity term. Conversely, if a relation is supplied without compatibility, the existence of such a term somewhere on the carrier does not constrain it. Verify the connection between the relation and the operation; merely placing both objects on the same set is not enough to activate the theorem.

Contents · Previous chapter · Next chapter

A ternary majority operation m satisfies m(x,x,y)=m(x,y,x)=m(y,x,x)=x. Whenever two of its three inputs agree, it returns that repeated value. On a set with more than two elements, these identities leave freedom when all three inputs differ. The operation need not be described by voting on unrestricted lists.

A near-unanimity operation with k+1 inputs, where k is at least two, returns x whenever all but at most one input equal x. The exceptional value may occupy any input position. Every position needs its own identity. Setting the exceptional value equal to x also gives idempotence: an all-x input list returns x.

The identities provide a controlled repair mechanism. If several tuples agree with a desired candidate at a particular coordinate, and at most one tuple is wrong there, near unanimity restores the candidate's value in that coordinate. Applying the operation coordinatewise can therefore repair different exceptional coordinates in different rows at once.

This mechanism is different from the existing majority-term argument about congruence paths. There, a term keeps a path inside a congruence class. Here, it combines tuples agreeing on overlapping coordinate sets. The same identities support both results, but the objects, proof steps and reader tasks differ. Keeping the actual input rows visible helps explain the new conclusion without treating the name of a term condition as a substitute for the calculation.

Contents · Previous chapter · Next chapter

Suppose R is a relation of triples closed under a majority operation. Let x=(a,b,c) pass all three pair-projection tests. Because (a,b) is in the first-second projection, choose r12 in R whose first two entries are a,b. Its third entry may be wrong.

Likewise choose r13 in R matching a,c in positions one and three, and r23 in R matching b,c in positions two and three. Apply majority coordinatewise to these three rows. In position one, r12 and r13 both contain a. In position two, r12 and r23 both contain b. In position three, r13 and r23 both contain c.

The three majority identities therefore make the output exactly (a,b,c). Since R is closed under the operation, the output lies in R. This proves the difficult containment: every tuple passing all pair tests actually belongs. Combined with the automatic forward containment, it establishes exact reconstruction for triples.

Notice what the argument did not require. The three original witnesses did not have to agree everywhere, and none had to equal the candidate. Their disagreements were allowed, but each coordinate had at most one disagreement. Nor did we need a finite carrier A. We selected three witnesses and used three identities. The finite object at this stage was the coordinate list, which made it possible to cover the candidate by finitely many overlapping views.

Contents · Previous chapter · Next chapter

Use Boolean values zero and one, with their usual majority operation. Let R consist of triples (a,b,c) satisfying a≤b≤c. Its members are 000,001,011 and111. The first-second and second-third projections both contain 00,01 and11; the first-third projection has the same three pairs.

The relation is majority closed. If each of three rows satisfies a≤b, then whenever at least two first-coordinate values are one, the corresponding second-coordinate values are also one. Thus the majority output in the first coordinate cannot exceed that in the second. The same reasoning proves the second output does not exceed the third.

Test the candidate 010. Its first-second pair 01 is allowed, but its second-third pair 10 is forbidden. It fails the reconstruction test and indeed is absent from R. Candidate 001 passes all pair tests and belongs. The tests expose the direction of the order constraint rather than merely checking whether each individual value has appeared somewhere.

Unary projections alone would all be {0,1}, whose product contains every Boolean triple. They would falsely admit 010,100,101 and110. Thus majority closure gives a binary projection bound, not a promise that single-coordinate information suffices. The example displays both success at the justified level and failure after an unjustified further compression. When a theorem says small views suffice, keep its stated view size attached to the conclusion.

Contents · Previous chapter · Next chapter

For a relation with four or more coordinates, three pair witnesses cannot directly cover every required position. We need an induction that first builds witnesses agreeing on almost the whole candidate and then combines them. The finite-coordinate theorem becomes transparent when those two stages are kept separate.

Assume the result has been established for relations with r−1 coordinates, and consider a majority-closed relation R with r coordinates, where r is greater than three. Suppose candidate x passes every pair test. Project R onto all coordinates except one chosen position i. This projected relation is still majority closed, because coordinatewise operations commute with deleting a coordinate.

Every pair restriction of the shortened candidate occurs in that projected relation. By the induction hypothesis the entire shortened candidate occurs. Therefore there is a tuple ri in R agreeing with x everywhere except possibly at position i. Do this for three distinct omitted positions i,j,l.

Apply majority to ri,rj,rl. At every coordinate, at most one of these rows can differ from x: only the row associated with that omitted coordinate has permission to differ. The output is therefore x, and closure places it in R. The three-coordinate proof supplied the induction's first nontrivial step; relations of one or two coordinates are already known in full from projections of at most two coordinates. This explains how pair evidence can determine a relation of many coordinates without assuming one pair witness already solves the whole task.

Contents · Previous chapter · Next chapter

Let q have k+1 inputs and satisfy all near-unanimity identities, with k≥2. Let R have r finite coordinates and be closed under q applied coordinatewise. We claim that R is determined by its projections to at most k coordinates. When r≤k, that family includes the full coordinate set, so the claim is immediate.

For the induction step assume r>k. Suppose x passes every k-coordinate projection test. Delete any one coordinate i. All k-coordinate tests still pass for the shortened candidate in the corresponding projection of R. The induction hypothesis therefore supplies a member ri of R agreeing with x outside i.

Choose k+1 distinct omitted coordinates, which is possible because r>k. We obtain k+1 member tuples, each with at most one exceptional position. Apply q to those rows. At any fixed coordinate, at least k rows agree with x, since at most the one row omitting that coordinate can disagree. Near unanimity gives x in that position.

The output is x, and closure proves x belongs to R. This establishes the theorem by induction. The proof also works for a finite product of different algebras when one common term satisfies the required identities in each factor: the coordinate calculations use that factor's interpretation of the same term. The statement does not require finite factor carriers. It does require finitely many coordinates for this induction and actual closure under the operation that performs the repair.

Reference: Snow: the near-unanimity projection theorem.

Contents · Previous chapter · Next chapter

The standard result is associated with Baker and Pixley. John W. Snow's paper on relations compatible with near-unanimity operations states the finite-product projection theorem in its introduction and distinguishes it from the additional question of which proposed projection systems can actually arise from one relation.

Our proof above develops the reconstruction direction directly. We begin with a relation R that already exists, know its actual projections, and show that those projections determine R. This is an exact uniqueness statement together with a reconstruction formula: retain precisely the tuples whose small restrictions occur in all the appropriate projections.

That is different from being handed arbitrary small relations and assuming they are the projections of some larger relation. The small relations may contradict one another. Even when their intersection-of-constraints construction is nonempty, its projections can be smaller than the originally supplied relations because some locally listed pairs have no global completion.

The source treats consistency questions with additional conditions and operations. This lesson will use a small inconsistency example to keep the boundary visible, rather than claiming to teach the full classification in that paper. Separating the standard theorem from our worked construction makes attribution precise: the source establishes the established framework, while the finite witness argument and explicit Boolean examples explain the selected reader job step by step.

Reference: Snow, introduction and Section 3: reconstruction and consistency.

Contents · Previous chapter · Next chapter

On {0,1}, define q on four inputs to return one exactly when at least three inputs are one. Otherwise it returns zero. In particular a two-two split returns zero. This is a four-input near-unanimity operation: three zeros and one arbitrary value give zero, while three ones and one arbitrary value give one.

Now let R be the relation of Boolean triples containing at most two ones. It contains all eight triples except111. We will prove that R is closed under q even though every binary projection is the full set of four Boolean pairs. Consequently binary information will be insufficient to reconstruct R.

Take four rows from R. Each row has at most two ones, so the twelve entries contain at most eight ones altogether. For q to output111, each of the three coordinate columns would need at least three ones. That would require at least nine ones altogether, contradicting the upper bound eight.

Thus the output cannot be111 and remains in R. This counting proof covers every ordered choice of four member rows, including repeated rows. It also shows why the operation's threshold matters. An arbitrary four-input operation would not obey the required three-ones condition in each output column. We have verified the exact closure needed for the theorem, with a short argument that can be checked independently against the complete finite table.

Contents · Previous chapter · Next chapter

Every Boolean pair occurs in each binary projection of the seven-member relation R. Given any chosen pair, complete the remaining coordinate with zero. The resulting triple has at most two ones, so it lies in R. This supplies a witness for all four pairs in every pair of positions.

The tuple111 therefore passes every binary projection test: each observed pair is11, and each such pair has a completion in R. Yet111 itself is excluded. Different pairs are witnessed by110,101 and011. There is no common allowed completion containing all three ones.

This does not contradict the near-unanimity theorem. Our operation has four inputs, so k=3. The theorem guarantees reconstruction from three-coordinate projections, not from pairs. For a relation of triples that includes the whole relation as a projection and gives no smaller representation. A bound may be correct without compressing every instance.

The example also proves that the algebra with q as its only basic operation has no majority term. If it had one, R would be closed under that term by term induction. Applying majority coordinatewise to110,101 and011 would produce111, contradicting closure. This is a structural obstruction to every possible majority term, not just a failure of one guessed formula. The distinction between a four-input near-unanimity term and a ternary majority term is therefore substantive and visible in the relation's required projection size.

Contents · Previous chapter · Next chapter

Keep q and let S consist of Boolean quadruples with at most two ones. The same counting method proves closure. Four member rows contribute at most eight ones total. If the output had at least three one coordinates, those three columns would each need at least three ones, requiring at least nine. Therefore the output again has at most two ones.

Every projection of S to three coordinates is the earlier relation R: a projected triple has at most two ones, and every such triple can be completed by a zero in the omitted coordinate. These two containments establish the projection exactly, not merely an observed sample of it.

A quadruple passes all those ternary tests exactly when no three of its coordinates are simultaneously one. That is equivalent to having at most two ones. The reconstruction therefore returns S exactly. Candidate1110 fails the projection onto its first three positions. Candidate1010 passes every ternary projection and belongs to S.

Binary projections are still all full: any pair can be completed with two zeros. They would admit all sixteen quadruples, including1111, whereas S contains 1+4+6=11 members. The counts separate the levels of retained information. One-coordinate and two-coordinate records lose the threshold constraint; three-coordinate records recover it. This is a complete example in which the general theorem gives a useful reduction while the tempting stronger pairwise claim remains false.

We can also watch the four-input repair produce a concrete member. Choose candidate1000 and the four rows0000,1100,1010 and1001. Every row belongs to S. The first row agrees with the candidate outside position one; the second agrees outside position two; the third outside position three; and the fourth outside position four. None of these rows equals the candidate.

Down the first column there are three ones, so q returns one. Each other column contains only one one, so q returns zero there. The output is1000 exactly. This gives a visible instance of the induction's final step: four partial witnesses combine into a complete witness, with a different row responsible for the possible error at each position.

The example should not be read backwards as permission to choose arbitrary nearly matching rows. They must already belong to the relation. Projection membership or the induction supplies that membership; the repair operation then supplies the new tuple. If a proposed witness is outside the relation, closure cannot be invoked on it. A sound reconstruction keeps the source of every witness alongside the coordinate calculation.

Contents · Previous chapter · Next chapter

Consider three Boolean coordinates and suppose someone supplies these pair constraints: the first must equal the second, the second must equal the third, and the first must differ from the third. Each individual relation is nonempty. Each is also preserved by Boolean majority: equality is preserved coordinatewise, and complementing every input complements the majority output, so inequality on two Boolean values is preserved too.

Nevertheless no triple satisfies all three constraints. The first two force all coordinates equal, contradicting the third. There is no relation whose projections are exactly these three nonempty supplied relations, because any member would have to satisfy the impossible combination.

This example shows why separate compatibility of the small views is insufficient for existence of a common relation with those exact projections. The reconstruction theorem started from actual projections of an existing relation. That premise already guarantees consistency; it is not an incidental detail that can be dropped.

In practical work, distinguish an observed relation being compressed from a collection of proposed constraints being assembled. For the former, the theorem can certify lossless reconstruction under the stated closure. For the latter, compute the common solution relation and check whether projecting it back recovers every supplied view. A missing local pair means it had no global completion. This round-trip check is an evidence test, not a claim that the entire advanced consistency theory reduces to one convenient example.

Contents · Previous chapter · Next chapter

Let the coordinates be the positive integers rather than a finite list. Consider all Boolean sequences having only finitely many ones. This relation is closed under coordinatewise Boolean majority. The support of a majority output is contained in the union of the supports of its three input sequences, and a union of three finite sets is finite.

Every projection to finitely many coordinates is full. Given any assignment on that finite coordinate set, complete the sequence with zeros everywhere else. The completed sequence has finite support and belongs to the relation. Thus all finite views look identical to those of the full Boolean sequence space.

The all-ones sequence passes every finite projection test but has infinite support and is not in the relation. Consequently even all finite projections together do not reconstruct this infinite-coordinate relation. In particular its pair projections are insufficient despite majority closure.

The finite induction explains the failure of the earlier proof to extend. There is no final finite coordinate stage at which the candidate has been assembled everywhere. Near unanimity combines finitely many rows at a time, and every such combination remains finitely supported. Do not describe this as a failure of majority identities; those identities still hold. It is a failure of an unstated infinite extension of a theorem whose finite-coordinate hypothesis does real work.

Contents · Previous chapter · Next chapter

For a finite relation, first record the carrier, coordinate order and complete tuple set. Specify the candidate operation by a complete table or formula. Verify its near-unanimity identities in every exceptional position. Then verify that applying it coordinatewise to any permitted list of member rows returns a member.

Next calculate each required projection from the full tuple set. Reconstruct the candidate relation by accepting a tuple exactly when all its required small restrictions occur. Compare that reconstructed set with the original relation in both directions. The original is always contained; an extra tuple is the useful witness of lost information.

For our seven-triple example, there are seven to the fourth power, or2401, ordered choices of four input rows to a complete closure check. A script can exhaust those cases. The counting proof explains them more efficiently and identifies why111 cannot be produced. Retain both the complete result and the proof if using computation as a teaching check.

Do not confuse closure under one tested operation with compatibility under a larger signature. If another basic operation is added, it must also preserve the relation before the relation can be called compatible with the expanded algebra. For the reconstruction proof itself, closure under the particular near-unanimity term is enough. State which of those claims the check establishes. This keeps an adequate argument from being advertised as a stronger, untested property.

There is a further distinction when the tuple list is observational rather than complete. A sample might omit valid tuples, causing its computed projections to omit valid local combinations. Alternatively, its projections may look full even though a rare global exclusion remains unseen. The mathematical theorem applies to the specified relation and its exact closure property; it cannot certify an unknown relation merely because a sample resembles one of our small examples.

If a finite list is explicitly the complete allowed relation, exhaustive closure and projection checks are meaningful certificates. If the list is a sample, record that limitation and separate observed membership from the asserted rules defining the full relation. An explicit defining rule, such as at most two ones, can supply a complete proof even when the list is not manually enumerated. The key is coverage of the actual mathematical object, not whether the evidence happens to be written as a table or a formula.

Contents · Previous chapter · Next chapter

On Boolean values define p with five inputs to return one when at least four inputs are one, and zero otherwise. Verify near unanimity, then consider the relation T of Boolean quadruples with at most three ones. Decide whether T is preserved and whether ternary projections reconstruct it.

Four ones and one arbitrary value produce one; four zeros and one arbitrary value produce zero. Thus p is a five-input near-unanimity operation. Five member rows of T contain at most fifteen ones altogether. An output1111 would require four columns with at least four ones each, or at least sixteen. That is impossible, so T is closed.

Every ternary projection is full: complete any three chosen Boolean values with zero. Therefore1111 passes every ternary test while remaining outside T. The theorem's bound is now k=4, not three. The changed example repeats the mechanism with new numbers while requiring you to track which arity belongs to the operation and which belongs to the retained views.

For a useful reconstruction, extend the relation to five coordinates while still allowing at most three ones. The same fifteen-versus-sixteen count proves closure. Its four-coordinate projections forbid four simultaneous ones, and satisfying all those constraints is equivalent to having at most three ones globally. Thus four-coordinate views reconstruct this five-coordinate relation. A complete answer should give both the failed compression for quadruples and the successful reconstruction for the extended relation, rather than repeating only the phrase near unanimity.

Contents · Previous chapter · Next chapter

Does seeing every value in every coordinate imply every tuple exists? No. Unary projections retain individual availability only. The ordered-triple relation already shows that all values can appear while some combinations are forbidden.

Does a four-input near-unanimity operation guarantee pairwise reconstruction? No. It guarantees the three-coordinate bound. The seven-triple relation excludes111 despite having all pairs in every binary projection and being closed under the four-input threshold operation.

Must the carrier be finite? Not for the reconstruction proof given here. The number of coordinates must be finite, and the relation must be closed under the required operation. Finite carriers are useful for exhaustive table checks but were not used in the witness-gluing induction.

Must every factor in a product be identical? No. A common term satisfying the near-unanimity identities in each factor supports the coordinatewise proof. Arbitrary unrelated operations on different factors would need an explicitly compatible formulation rather than an assumed common term.

Can arbitrary compatible projections always be assembled? No. Equality, equality and inequality on the three pairs give an inconsistent example. Actual projections of a known relation come with an existence premise that separately supplied constraints may lack.

Does reconstruction promise a fast algorithm? It supplies a bounded projection description, not an unconditional performance guarantee. Computing all projections or enumerating all candidate tuples can still be expensive. The proof explains correctness; computational complexity requires additional choices about how the relation and operations are represented.

Does closure require the output to be one of the input rows? No. The majority proof deliberately constructs a new row from several witnesses. Closure requires membership in the relation, not selection of an already listed input. Confusing those requirements would hide the very mechanism that makes reconstruction possible.

Contents · Previous chapter · Next chapter

First write three rows witnessing the three pair projections of a candidate triple. Mark the coordinate each row is allowed to get wrong. Apply majority down the columns and explain why every output coordinate is forced. This small proof is the core of the whole lesson.

Next reproduce the finite-coordinate induction. Explain why projecting a closed relation preserves closure, why the shortened candidate passes the necessary tests, and how that supplies a row with only one possible exceptional coordinate. Then use k+1 such rows for a near-unanimity operation with k+1 inputs.

Afterwards rebuild the four-input threshold example. Count the maximum number of ones in four allowed input rows and the minimum required for a forbidden output. Compute the binary projections and retain111 as the lost-constraint witness. Extend to four coordinates and explain why ternary views now recover exactly the eleven allowed tuples.

Finally solve the five-input transfer and the infinite-support example. They test different boundaries: one changes the required projection size, while the other removes finite coordinate length. Identify the assumption that changes in each case and the explicit tuple that exposes the resulting loss.

The capability to retain is knowing when overlapping views determine a whole object. Near unanimity provides a precise repair operation for local witnesses, and compatibility ensures that the repaired result is still allowed. The conclusion is powerful because its mechanism is visible, and reliable because its limits remain attached: correct projection size, genuine closure, consistent source data and a finite coordinate list.

Contents · Previous chapter · Continue to related reading