1
$\begingroup$

Let's say we have a finite metric space $(S,d)$. I need to prove that $P(S)$ (the power set of $S$) is a metric space with the metric $\bar d:P(S)\times P(S)\to[0,\infty)$ defined as

$$\bar d(X,Y)=\sum_{x,y\in X\cup Y}d(x,y)-\sum_{x,y\in X\cap Y}d(x,y)$$

Non-negativity, identity of discernibles and symmetry are almost obvious, but what about the triangle inequality? I'm not able to prove that. I cannot find a value between $\bar d(X,Z)$ and $\bar d(X,Y)+\bar d(Y,Z)$ that sends me in the right track. Thanks.

$\endgroup$
1
$\begingroup$

There is a quite nice visual answer to this question.

Note that for all $A,B\subseteq S$,

\begin{align*} \bar d(A,B)&=\sum_{x,y\in A\cup B}d(x,y)-\sum_{x,y\in A\cap B}d(x,y)\\ &= \sum_{x,y\in A\Delta B}d(x,y)+2\sum_{x\in A\Delta B}\sum_{y\in A\cap B}d(x,y) \\ &= \sum_{x,y\in A-B}d(x,y)+\sum_{x,y\in B-A}d(x,y)+2\sum_{x\in A-B}\sum_{y\in B-A}d(x,y)\\ &\quad+2\sum_{x\in A-B}\sum_{y\in A\cap B}d(x,y)+2\sum_{x\in B-A}\sum_{y\in A\cap B}d(x,y) \end{align*}

Because $A-B$, $A\cap B$ and $B-A$ are all disjoint, every $\bar d(A,B)$ can be expressed as a sum of distances between disjoint sets. This lets us define the distance between $A$ and $B$ as a graph.

Suppose we treat the venn diagram of $A$, $B$ and $C$-in OP's example, $X$, $Y$ and $Z$ respectively- as an unordered graph $G$ where each vertex is a portion of the venn diagram with no intersection with the rest, and an edge between two portions corresponds to the sum of the distances between the points of each set, so $d(a,b)=\sum_{x,y\in a\cup b}d(x,y)$ for any distinct nodes $a,b\in V(G)$-where $V(G)$ is the set of vertices of $G$- because $a\cap b=\emptyset$ for all $a,b\in V(G)$. We will enumerate the nodes like so

enter image description here

This will be useful later.

For example, assuming wether the definition of $d$ is over $S$ or $P(S)$(where $P(S)$ is the power set of $S$), is given by context, so we don't need the bar to distinguish them, and $^c$ is the complement of a set, then $d(A\cap B^c\cap C^c,A\cap B\cap C^c)$ could be defined with the following graph:

enter image description here

meaning that $$d(A\cap B^c\cap C^c,A\cap B\cap C^c)=\sum_{x,y\in A\cap B^c\cap C^c}d(x,y)+\sum_{x,y\in A\cap B\cap C^c}d(x,y)+{\sum_{x\in A\cap B^c\cap C^c}\sum_{y\in A\cap B\cap C^c}d(x,y)}+{\sum_{x\in A\cap B\cap C^c}\sum_{y\in A\cap B^c\cap C^c}d(x,y)}$$

(the terms involving the intersection gets cancelled because there is no intersection between these two sets).

Knowing that edges correspond to sums, and that adding an edge just adds to the sum, then $d(A,B)$ could be defined with the following one:

enter image description here

and $d(B,C)$ with

enter image description here

Knowing that unioning the graphs of $d(A,B)$ and $d(B,C)$ gives a number less than their sum, because we are only counting once even the sum appears more than once, we will prove that the union of these graphs is indeed larger than the graph of $d(A,C)$. If we union those graphs together we get the graph

enter image description here

comparing with the graph of $d(A,C)$, which is

enter image description here

we can see that the only edge of the graph of $d(A,C)$ which is not contained in the graph of the union is the edge between the nodes $3$ and $5$, so if there is a way to compensate that edge in the graph of the union we are done, and there is.

We have a lot of unused edges going from the node $1$, and two of those edges are from $3$ to $1$, and from $1$ to $5$. This means that for every sum of the graph of $d(x,z)$ where $x\in\text{Region 5}$ and $z\in\text{Region 3}$ there is a sum in the graph of the union where for some $y\in\text{Region 1}$ we have that $d(x,z)\leq d(x,y)+d(y,z)$, meaning that we have compensated that missing edge on the graph of the union, meaning that the union of the graphs $d(A,B)$ and $d(B,C)$ are indeed bigger than $d(A,C)$, so $d(A,B)+d(B,C)$ must be bigger than $d(A,C)$, proving that OP's $\bar d$ is in fact a metric.

$\endgroup$
0
$\begingroup$

The 8 sets $$ A_{xyz}=X\cap Y \cap Z,\,\, A_{xyz'}=X\cap Y \cap Z^c,\,\, A_{xy'z}=X\cap Y^c \cap Z,\,\, A_{xy'z'}=X\cap Y^c \cap Z^c,\\ A_{x'yz}=X^c\cap Y \cap Z,\,\, A_{x'yz'}=X\cap Y \cap Z^c,\,\, A_{x'y'z}=X^c\cap Y^c \cap Z,\,\, A_{x'y'z'}=X^c\cap Y^c \cap Z^c, $$ are mutually disjoint, and their union is $X\cup Y\cup Z$.

To see this draw the Venn diagram.

Then $$ \overline{d}(X,Y)=\sum_{x,y\in X\cup Y}- \sum_{x,y\in X\cap Y}=\sum_{x,y\in A_{xy'z'}}+\sum_{x,y\in A_{xy'z}}+ \sum_{x,y\in A_{x'yz'}}+\sum_{x,y\in A_{x'yz}} $$ and $$ \overline{d}(Y,Z)=\sum_{x,y\in Y\cup Z}- \sum_{x,y\in Y\cap Z}=\sum_{x,y\in A_{xyz'}}+\sum_{x,y\in A_{x'yz'}} +\sum_{x,y\in A_{xy'z}}+\sum_{x,y\in A_{x'y'z}} $$ and hence $$ \overline{d}(X,Y)+\overline{d}(Y,Z)\ge\sum_{x,y\in A_{xyz'}}+\sum_{x,y\in A_{x'yz'}}+\sum_{x,y\in A_{xy'z}}+\sum_{x,y\in A_{x'y'z}}=\overline{d}(X,Z) $$

$\endgroup$
  • 1
    $\begingroup$ there is a mistake in some of the equations: you forget terms of the form $d(x,y)$ where $x,y$ are not in the same $A_{\dots}$-set. $\endgroup$ – supinf Nov 19 '18 at 13:46
  • $\begingroup$ Drawing a venn diagram helped me out. Thanks. $\endgroup$ – Garmekain Nov 19 '18 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.