3

Has anyone ever used the size of the symmetric difference of two sets $X,Y$ as a metric on finite sets?

Is there any literature on this? Where could this be used?

Garmekain
  • 3,124
  • 13
  • 26
  • 5
    Related to the Hamming distance for binary strings. You can even find https://www.researchgate.net/post/How_to_calculate_the_Hamming_Distance_between_two_sets where it is explicitly the distance between two sets. – GEdgar Nov 05 '18 at 13:03
  • Indeed, if you write the set as a serie of $0$'s and $1$'s this is exactly the Hamming distance of the string-representation of the sets. – Henno Brandsma Nov 05 '18 at 17:20

1 Answers1

3

This is the standard $\mu$-metric on a measure space, specialised to the counting measure on a finite set:

If $(X,\mathcal{S},\mu)$ is a measure space, with $\mathcal{S}$ a $\sigma$-algebra on $X$, and $\mu: \mathcal{S} \to \mathbb{R}$ a finite measure, we define $d_\mu(A,B) = \mu(A \Delta B)$ as a metric on $\mathcal{S}$, where to make it a true metric we take equivalence classes of sets in $\mathcal{S}$, under the induced equivalence $A \sim B$ iff $d_\mu(A,B)=0$. The set of classes then has the induced metric from $d_\mu$ as well. This metric is often introduced when talking about separable measures ($\mu$ is separable iff the classes of $\mathcal{S}$ in this metric are a separable metric space), but I don't think there's a lot of separate study of this construction.

So if $X$ is finite, and $\mathcal{S} = \mathscr{P}(X)$ and $\mu(A) = |A|$ (the cardinality of $A$) we get your metric as a special case. Every subset is only equivalent to itself, so we don't need classes here.

Henno Brandsma
  • 242,131