48
$\begingroup$

Given a metric space $(X,d)$ and three points $x,y,z$ in $X$, say that $y$ is between $x$ and $z$ if $d(x,z) = d(x,y) + d(y,z)$, and write $[x,z]$ for the set of points between $x$ and $z$.

Obviously, we have

  1. $x,z\in[x,z]$;
  2. $[x,z]=[z,x]$;
  3. $y \in [x,z]$ implies $[x,y] \subseteq [x,z]$;
  4. $w,y \in [x,z]$ implies: $w\in [x,y]$ iff $y \in [w,z]$.

My question:

Has the family of objects with such an axiomatic “interval structure” $[\bullet,\bullet]:X \times X \to \mathcal{P}(X)$ satisfying approximately the above conditions been studied somewhere?

$\endgroup$
  • 4
    $\begingroup$ There is a bit of that in Busemann's Geometry of Geodesics because of its relation to inverse problems: determine all metrics which have the same geodesics (or same "between" structure: set of triplets $(x,y,z) \in X \times X \times X$ such $y$ is between $x$ and $z$). If you allow more structure (manifolds, foliations, etc.) this is basically the study of path geometries. $\endgroup$ – alvarezpaiva Mar 31 at 13:39
  • 7
    $\begingroup$ You might find Knuth's Axioms and Hulls of interest. Not only betweenness on an interval but also cyclic order as well. For betweenness the main idea is ordered geometry. $\endgroup$ – Somos Mar 31 at 18:18
  • 3
    $\begingroup$ I don't think this is exactly what you are looking for but this reminds me a lot of median spaces/median algebra. You might be interested in looking at Notes on coarse median spaces by Bowditch $\endgroup$ – Paul Plummer Apr 1 at 0:38
  • 1
    $\begingroup$ Since Bowditch has been mentioned you may well be aware of this, but a special case of these axioms is given by pretrees. These can be defined by the axioms: (a) $[x,y]=[y,x]$; (b) $y\in[x,z]$ and $z\in[x,y]$ implies $y=z$; and (c) $[x,z]\subseteq[x,y]\cup[y,z]$. The last axiom ensures the structure is treelike, and is of course not shared by most metric spaces. See Bowditch's Memoir of the AMS Treelike structures arising from continua and convergence groups and Adeleke and Neumann's Memoir Relations related to Betweenness. $\endgroup$ – shane.orourke Apr 6 at 8:50
  • 2
    $\begingroup$ @user148575 Pretrees aren't necessarily metrisable, at least not if the distances are required to be real numbers. Any linearly ordered set admits a natural pretree structure, so sufficiently large losets are counterexamples. If you are prepared to generalise the definition of metric space to allow distances in a pre-assigned linearly ordered abelian group, then every pretree admits a metric where each $[x,y]$ consists of the points between $x$ and $y$ in the sense of the question. $\endgroup$ – shane.orourke Apr 6 at 16:25
42
$\begingroup$

There is a wide body of work on this in connection with the classic De Bruijn–Erdős theorem.

De Bruijn–Erdős Theorem. Every set of $n$ points in the plane (not all lying on the same line) determine at least $n$ lines.

There is a beautiful conjecture of Chen and Chvátal that the De Bruijn–Erdős theorem actually holds in every metric space, where lines are defined using the notion of betweenness that you describe. That is, given a metric space $M$ and two points $a,b \in M$, the line determined by $a$ and $b$ is the set of points $c$ such that $c$ is between $a$ and $b$, or $a$ is between $c$ and $b$, or $b$ is between $a$ and $c$. Note that this definition reduces to the usual notion of lines if we use the Euclidean distance.

Chen-Chvátal Conjecture. Every set of $n$ points in a metric space (not all of which lie on the same line) determine at least $n$ lines.

If you Google 'Chen-Chvátal Conjecture' you will find many results, including some that focus on the combinatorial aspects of betweenness.

| cite | improve this answer | |
$\endgroup$
18
$\begingroup$

I'm reminded of W.A. Coppel's book which looks at these kinds of structures from a slightly different vantage point, namely closure systems. I can't actually find the book right now, but here's a quick synopsis of what's going on.

Given a set $X$ together with an arbitrary function $[\bullet,\bullet] : X^2 \rightarrow \mathcal{P}(X),$ let's call $A \subseteq X$ closed if and only if for all $a,b \in A$, we have that $[a,b] \subseteq A$. It's easy to show that an arbitrary intersection of closed sets is closed, or in other words the collection of closed sets forms a Moore family. This gives us a closure operator on $\mathcal{P}(X)$, which makes $(X,\mathcal{P}(X))$ into a closure system. This means that the collection of closed sets forms a complete lattice given by $$\bigwedge_{i \in I} C_i := \bigcap_{i \in I} C_i, \qquad \bigvee_{i \in I} C_i := \mathrm{cl}\left(\bigcup_{i \in I} C_i\right).$$

If we furthermore assume that $[a,a] = \{a\},$ which is true in an arbitrary metric space (though I'm not sure whether this follows from your axioms), then we can prove that singletons are closed sets. Thus we're allowed to consider the expression $\{a\} \vee \{b\}$ in the aforementioned lattice. This set clearly includes $[a,b]$, and I think your axioms probably imply that these sets are equal. Ergo the Moore family alone allows us to recover the original between-relation.

I think that if you take the first three axioms you've written down, and add in the axiom $[a,a] = \{a\},$ the resulting axiom list should provide a complete characterization of closure systems $X$ in which firstly, every singleton is closed, and secondly, for all $A \subseteq X$, we have that $A$ is closed if and only if for all $a,b \in A$, we have $\{a\} \vee \{b\} \subseteq A$. But you should check this explicitly rather than taking my word for it, because right now this is just a hunch.

I'll also remark that you might learn interesting things by looking at partially ordered sets and defining $[a,b] := \{x \in X : a \leq x \leq b\} \cup \{x \in X : b \leq x \leq a\}.$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Ah, this seems actually closer to what I had in mind, thank you! The axiom $[a,a] = {a}$ is indeed natural and, combined with my third one, implies the first, so should probably be used instead. $\endgroup$ – user148575 Apr 1 at 5:58
  • 4
    $\begingroup$ @user148575, glad I was able to help. These are exactly the kinds of questions I love by the way; looking at old structures (e.g. metric spaces) via new categories (e.g. between-relation spaces), fresh points of view on familiar ideas, and the axiomatic method at its simplest and most appealing. This is how things get better. $\endgroup$ – goblin Apr 1 at 6:01
9
$\begingroup$

This is more of an extended remark than a full answer. My message is: The property $[x,x]=\{x\}$ does not necessarily hold, but you can always make it hold by taking a natural quotient.

Your axioms don't imply $[x,x]=\{x\}$, so you have to add it if you want it. A pseudometric (e.g. a seminorm) will satisfy your axioms, and $[x,x]$ is the set of points distance zero from $x$, and this set can have any size.

In a pseudometric space you can take the quotient by the relation $x\sim y\iff d(x,y)=0$ and you get a metric space. It turns out the same works with the interval systems.

We can define a relation $\sim$ on $X$ so that $x\sim y\iff x\in[y,y]$. This is an equivalence relation:

  • Reflexivity: Axiom 1.
  • Symmetry: By axioms 1 and 2 $x,y\in[y,x]$. Thus axiom 4 says $x\in[y,y]\iff y\in[x,x]$.
  • Transitivity: Suppose $x\sim y\sim z$. By axiom 3 $x\sim y$ and $y\sim z$ imply $[y,x]\subset [y,y]$ and $[z,y]\subset [z,z]$. By axioms 2 and 3 $[y,y]\subset[z,y]$. Thus $x\in[y,x]\subset[y,y]\subset[z,y]\subset[z,z]$.

Then we can take the quotient space $X/{\sim}$. To avoid confusion, let's denote by $(x)$ the quotient set of $x\in X$. (In fact, $(x)=[x,x]$, but I find it cleaner to keep the separate notation.) Then declaring $(x)\in[(y),(z)]\iff x\in[y,z]$ defines an interval structure on $X/{\sim}$. To see this, we need to check two things:

  1. $[x,y]\subset[x',y]$ when $x\sim x'$. (The reverse inclusion and varying both $x$ and $y$ follow easily.)

    Proof: Since $x\in[x',x']\subset[x',y]$, we have indeed $[x,y]\subset[x',y]$.

  2. $x\in[z,y]\implies[x,x]\subset[z,y]$.

    Proof: Since $x\in[z,y]$ and $x\in[x,y]$, applying axiom 3 twice gives $[x,x]\subset[x,y]\subset[z,y]$.

In the quotient structure we evidently have $[(x),(x)]=\{(x)\}$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Interesting, thanks for the remark! $\endgroup$ – user148575 Apr 2 at 15:51

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.