Is the Triangle Inequality Necessary?

Below, I am going to distill a proof that in the source is embedded in a story. The question is about the necessity of the triangle inequality in the definition of the distance function. To remind, a nonnegative real-valued function $f(x, y)$ defined on some set $S$ is a distance function, provided it satisfies three conditions:

  1. $f(x, y) = 0$ only if $x = y$.
  2. $f(x,y) = f(y,x)$.
  3. $f(x,y) \le f(x,z)+f(z,y)$.

The three conditions must be understood as preceded by the quantifiers "for all": $\forall x\forall y$ for the first two conditions, and $\forall x\forall y\forall z$, for the third one, the triangle inequality. Following E. Semyenov, I am going to show that the latter is not necessary (as a distance axiom) in the sense that it is being implied by the first two.

So assume the first two conditions and attempt to derive the third. To this end, suppose on the contrary that it does not hold, meaning that for all $x$, $y$, and $z$, $f(x,y) \gt f(x,z)+f(z,y)$. We arrive at a contradiction by letting $y = z$ and $x \ne y$. For this choice of three points we then get $f(x,y) \gt f(x,z)+0 \gt f(x,y)$. This is certainly a contradiction, because no quantity, $f(x,y)$ in particular, can be greater than itself.

It follows that our assumption of the reverse of the triangle inequality led to a contradiction, implying that the assumption was wrong and thus proving the triangle inequality.

Do you agree with the above?

References

  1. E. Semyenov, Can prove, cannot prove, Kvant, 1978, #1, 38-41 (in Russian)

|Contact| |Front page| |Contents| |Algebra| |Up| |Store|

Copyright © 1996-2017 Alexander Bogomolny

First, let's show "indirectly" that the "proof" is indeed faulty. What is claimed was that any function that satisfies the first to conditions necessarily satisfies the third. This could be proved wrong by simply exhibiting a set and a function defined on that set that satisfy 1 and 2 but not 3.

The set in the example will consist of just three points $x$, $y$, and $z$. We define a function $f$ thus:

$f(x,x)=f(y,y)=f(z,z)=0,$
$f(x,z)=f(z,x)=1$,
$f(y,z)=f(z,y)=1$,
$f(x,z)=f(z,x)=3$.

For so defined function $f$, the triangle inequality does not hold, for $f(x,y) \gt f(x,z) + f(z,y)$. On the other hand, the function clearly satisfies the first two conditions.

Why would anyone define such a distance function? A simple answer is, "To give a counterexample." A student may then complain that the example is artificial and is far from reality. In that case consider this example."

Let x, y, z be the capitals of three countries X, Y, Z, joined by the highways. Along the highways, the capitals are 1 hour drive from each other. However, between $y$ and its neighbors there is a trade agreement and no visa is required to enter or exit $y$. However, the relations between $x$ and $z$ are strained and custom checkups take a long time - at least extra 2 hours. If the distance is measured in time units - the time required to get from one capital to another then the function $f$ defined above gives a realistic reflection of the effort involved.

Returning to our "proof", so we now know that an error has been committed. The question is, Where?

There was a slight of hand in passing from the triangle inequality to its converse. Formally, I should have written

  1. $\forall x\forall y\forall z f(x,y) \le f(x,z)+f(z,y)$.

The negation of which is

$ \neg \forall x\forall y\forall z [f(x,y) \le f(x,z)+f(z,y)]$

$\iff \exists x \neg\forall y\forall z [f(x,y) \le f(x,z)+f(z,y)]$

$\iff \exists x \exists y \neg \forall z [f(x,y) \le f(x,z)+f(z,y)]$

$\iff \exists x \exists y \exists z \neg [f(x,y) \le f(x,z)+f(z,y)]$

$\iff \exists x \exists y \exists z [f(x,y) \gt f(x,z)+f(z,y)].$

This is obviously different from $ \forall x\forall y\forall z [f(x,y) \gt f(x,z)+f(z,y)]$ that we have proved wrong. I had to say "Assume that for some $x$, $y$, and $z$, $f(x,y) \gt f(x,z)+f(z,y)$" instead of "Assume that for all $x$, $y$, and $z$, $f(x,y) \gt f(x,z)+f(z,y)$", as I did. With the right formulation, I would not be at liberty to choose $y=z$, and the "proof" would not go through.

|Contact| |Front page| |Contents| |Algebra| |Up| |Store|

Copyright © 1996-2017 Alexander Bogomolny

 62040775

Search by google: