Relations & Order

Equality must be an equivalence relation — reflexive, symmetric, transitive — and must stay stable while the key is stored. Equal keys must produce equal hashes; unequal keys are allowed to collide, and a collision never means equality.

Reflexivity, symmetry and transitivity. A rule with all three is an equivalence relation, and only then does it cut the rows into disjoint groups where every row lands in exactly one group, whichever row you start from.

Injective means no two distinct old identifiers are sent to the same new identifier. Lose it and two separate records land on one row in the target: one write overwrites the other, references converge, and no rollback can tell them apart.

Injectivity alone gives an inverse only on the identifiers the remap actually produced. To translate back any identifier the new store holds, the remap must also be surjective onto that set — together, a bijection onto it.

Happened-before relates only events that are causally linked. If neither event saw the other, they are incomparable, not equal. A partial order permits such incomparable pairs; a total order demands that every pair be comparable.

The intersection of the two exclusions: documents that are not draft AND not internal. De Morgan's law for sets says the complement of a union is the intersection of the complements, so negating the filter flips 'or' into 'and'.

Sorting assumes a total order. Reporting 'equal' for incomparable items breaks transitivity, so the comparator contradicts itself: the output can be genuinely unsorted rather than arbitrarily tied, and some sort routines detect the contradiction and fail outright.

A one-sided map gives only an inequality. An injection from old rows into new ones proves the old count is at most the new; a surjection proves it is at least. Only a bijection, both at once, gives equality.

A maximal version has nothing above it. A maximum version is above everything. A store can hold several maximal versions at once — concurrent heads — but a maximum, when one exists, is unique and dominates every other version.

Every query that depends on how often something occurred: totals, averages, and any ranking by popularity. Membership questions survive de-duplication untouched, because a set records only whether an element is present, while a multiset also records how many times.

There are 2^n of them — the power set of the label set, including the empty combination. Because the count doubles with every label added, precomputing or caching one entry per possible label-set filter is impossible past roughly twenty labels.

The rule is reflexive and symmetric but not transitive, so it has no equivalence classes. 'The group of a row' stops being a property of the data and becomes a property of the traversal order, and chains of near matches fuse distinct people.

The smallest transitive relation containing every reported pair: two rows are related when a chain of reported pairs links them. Closing reflexively and symmetrically too gives the smallest equivalence containing the pairs, which is the grouping the matcher implies.

Finite identifiers can be listed one after another, so they reach only countably many things. The infinite streams are uncountable: given any listing, flip the n-th symbol of the n-th stream and you have built a stream the listing missed.

The join is the least upper bound: the smallest level that dominates both, unique whenever it exists. A plain partial order may offer several incomparable upper bounds, or none at all, so 'combine these two' has no canonical answer there.

Because a complement is meaningless until its universe is fixed. 'Not tagged archived' names a set only relative to a chosen collection — the whole corpus, one tenant, one shard, or the current page — and two services that pick different universes implement different filters.

Keep two relations. Identity is defined so that it is an equivalence by construction — equality of a normalized key — and the near-match rule stays advisory, feeding review and search but never partitioning the data or naming anything other systems store.

Decide by who still holds the old identifiers and what must be answerable later. A merge is a one-way loss of injectivity: the inverse stops existing, and only preimages you deliberately store can answer lineage questions afterwards.

A linear extension is a total order that agrees with the partial one, and a partial order usually admits many. Choosing one buys a single replayable sequence; it also erases which events were concurrent, which is precisely what conflict detection needs.

The representative must be determined by the class's members alone — never by arrival order, worker or wall-clock time. Formally it is a function whose value is equal for two rows exactly when they are in the same class.

Only the first stage must be injective. The second may collide freely outside the first stage's image, because the composition never exercises it there — which is a live defect the moment anything else feeds the second stage directly.

The largest antichain is the order's width: the greatest number of tasks that are pairwise unordered, and therefore a ceiling on how many could ever be in flight together. Dilworth's theorem says that same number is the fewest chains needed to cover every task.

Coverage of every input rather than the sampled ones. Two sets are equal exactly when each contains the other, so arguing both directions over an arbitrary document rules out both failure modes — missing results and extra ones — while a spot-check only shows the cases you happened to pick.