Randomly drawn identifiers make the copies in a multiset pairwise distinct, so set theory applies to it except with vanishing probability.
Multisets are sets if entropy exists
Symbols & Logic builds the number as copies of the empty set. As a set that collapses, , because a set is determined by membership alone. As a multiset it does not, and the usual way to turn a multiset into a set is structural: index the copies, or nest them so each one differs from the rest. This page conjectures a different way that uses no structure at all.
Conjecture
A multiset is a set if entropy exists. Pairwise distinctness need not be enforced by indices or nesting: it is upheld exclusively by giving each element an independently drawn random identifier, and every set operation on the identified elements agrees with the multiset operation, except on an event whose probability vanishes as the entropy grows.
In other words, randomness is a substitute for coordination. An index says “you are copy number 3”, which somebody had to decide. A random identifier says nothing, yet with enough entropy no two copies ever agree.
Entropy is not the size of the identifier space
Two quantities are easy to confuse here, and the conjecture is about the second one.
The identifier space is the set of identifiers that could be written down. Its cardinality , or bits, says how many elements could in principle be told apart. It is a property of the notation.
The entropy is a property of how identifiers are drawn. If an identifier is drawn from a distribution on , two independent draws agree with probability
which defines the collision entropy .1 Always , with equality exactly when the draw is uniform. So the identifier space is a capacity, and the entropy is how much of that capacity the draw actually uses.
The distinction matters in both directions. A 128-bit identifier space with identifiers produced by a counter that restarts from zero has , and every restart collides; a 128-bit space fed by a biased generator has less entropy than its width suggests. Conversely no draw can have more entropy than : a small identifier space caps the entropy no matter how good the randomness is. The hypothesis “entropy exists” asks for the second quantity, and a large identifier space is only the precondition that makes it possible.
What is proven
Fix a multiset of elements. Give every element an identifier drawn independently from the same distribution on , and form the set of pairs . It has members exactly when the identifiers are pairwise distinct.
Lemma (birthday bound). The probability that two identifiers collide is at most
For a uniform draw and the right-hand side is .
Proof. Any fixed pair of identifiers agrees with probability by the definition above, and there are pairs. The union bound finishes it.
For uniform draws the bound is tight up to a constant: the exact probability is , so entropy is also necessary. For a failure probability you need about
bits of entropy per identifier. An explicit index costs bits; the random identifier costs roughly twice that. That factor of two is the price of not coordinating.
Operations. On the no-collision event the identified collection is a genuine set, and set theory applies to it literally:
- Cardinality is the number of members, which equals the multiset’s count.
- The union of two independently identified collections is the multiset sum, , once the lemma is applied to the identifiers together.
- The Cartesian product needs no new randomness: pairs of distinct and distinct are distinct, so . This is the “set with elements for each of elements” picture of multiplication.
So any finite sequence of unions, products and counts on identified multisets yields the multiset answer with probability at least , where is the total number of elements ever identified.
Try it. The widget draws uniformly, so its entropy equals the bit width of the identifier space. With 8 bits and 16 elements a collision appears about every other draw. Raise the bits and watch the multiset become a set.
What is not proven
The lemma covers finitely many elements and the operations above. The conjecture claims more, and these parts are open:
- Exclusivity. That randomness is the only structure-free way to make copies distinct. Any deterministic rule that distinguishes the copies is an index in disguise, but that has not been made precise, for instance as a statement about the information an identification scheme must share across elements.
- Every operation. Operations that read the identifiers, such as sorting by identifier, do not correspond to any multiset operation. The conjecture needs a definition of which operations count, probably those invariant under permuting the identifiers.
- Infinite multisets. With infinitely many copies and a finite identifier space a collision is certain. Whether a countable identifier space with enough entropy per element recovers the infinite case, in the sense that the identified collection is a set almost surely, is not settled here.
- The constant. Whether the factor of two over explicit indices is necessary, or whether some scheme with shared randomness can approach bits per element while staying coordination free.
Why it matters
This is how distributed systems already behave. A UUID has a 128-bit identifier space of which 122 bits are drawn at random, and services treat records with fresh UUIDs as a set without ever agreeing on a numbering. A nonce makes otherwise identical messages distinct. A content hash is an identifier drawn from the data rather than from a coin, and collision resistance is the same birthday bound with the hash width standing in for the entropy. In each case a multiset of indistinguishable things is operated on as a set, and the only thing making that correct is entropy.
-
The collision entropy is at most the Shannon entropy and at least the min-entropy, so a bound in terms of either of those is also valid, with the min-entropy giving the safer one. ↩