Index Mathematics Conjectures nbv lettuce Widgets

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 n as n 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 I is the set of identifiers that could be written down. Its cardinality N=|I|, or λ=log2⁡N 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 p on I, two independent draws agree with probability

Pr⁡[two draws agree]=∑i∈Ipi2=2−H2(p),

which defines the collision entropy H2(p).1 Always H2(p)≤log2⁡N, 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 H2=0, 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 log2⁡N: 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 M of n elements. Give every element an identifier drawn independently from the same distribution p on I, and form the set of pairs {(ιi,mi)}. It has n members exactly when the identifiers are pairwise distinct.

Lemma (birthday bound). The probability that two identifiers collide is at most

Pr⁡[collision]≤(n2)2−H2(p)=n(n−1)2H2(p)+1.

For a uniform draw H2(p)=λ and the right-hand side is n(n−1)/2λ+1.

Proof. Any fixed pair of identifiers agrees with probability 2−H2(p) by the definition above, and there are (n2) pairs. The union bound finishes it. □

For uniform draws the bound is tight up to a constant: the exact probability is 1−∏i<n(1−i/N)≥1−e−n(n−1)/2N, so entropy is also necessary. For a failure probability ε you need about

H2≥2log2⁡n+log2⁡1ε

bits of entropy per identifier. An explicit index costs log2⁡n 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:

So any finite sequence of unions, products and counts on identified multisets yields the multiset answer with probability at least 1−n(n−1)/2H2+1, where n 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:

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.

  1. 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. ↩