1

Take $f,g\in S_n$, the symmetric group on a set $X$ of size $n$. Define the function $$d(f, g) = n - |\{x\in X : f(x) = g(x)\}|$$

In words, this defines a distance on permutations by how many inputs they map to the same output. This is kind of a measure of how much of $X$ the permutations "agree" on.

Is this a metric on $S_n$? I suspect the answer is no but I haven't come up with a counterexample. It's clearly reflexive and symmetric, but proving or disproving the triangle inequality is stumping me.

pg1989
  • 293
  • By the way, wouldn't it be simpler and more natural to say that $d(f,g)=|{x\in X:f(x)\ne g(x)}|,$ the number of places where $f$ and $g$ disagree? – bof Oct 05 '17 at 03:30
  • Note that it is really the number of elements of $X$ that the permutations disagree on. Reading it that way makes it easier to see that the triangle inequality is true. – Ross Millikan Oct 05 '17 at 03:31

1 Answers1

2

$$d(f,h)=|\{x:f(x)\ne h(x)\}|\le|\{x:f(x)\ne g(x)\}|+|\{x:g(x)\ne h(x)\}|=d(f,g)+d(g,h)$$ because $$\{x:f(x)\ne h(x)\}\subseteq\{x: f(x)\ne g(x)\}\cup\{x:g(x)\ne h(x)\}$$

bof
  • 78,265
  • Thanks very much! It's much simpler to see the triangle inequality holds when you write the condition as $f(x) \ne g(x)$, as you suggested. – pg1989 Oct 05 '17 at 17:48