(I've asked the same question at the MSE, so far with no answers, so I thought I'd try it here as well. If there's some clash with any site rules, please let me know and I'll abide.)

Let $A$ be a set equipped with a binary reflexive and symmetric relation $\smile$ (such relations have been called tolerances and similarities in the past). I'm interested in meaningful mathematical instances of the following property for an element $a \in A$: $$ \forall_{b,b' \in A} (b \smile a \land a \smile b' \rightarrow b \smile b') \quad (\star)\ . $$ We may think of $a$ as a "transitive" element, a "transition go-between" for the otherwise not necessarily transitive relation $\smile$. Depending on the choice of carrier and relation, there may be many such elements, just one, or maybe none.

My questions: Is the property $(\star)$ known and studied? Is there a name for it? Are there natural examples of it?

I've personally thought of a couple (I've even elaborated on a simple one in MSE) but I'd rather not influence any possible answers here --- let alone, I'm not sure I'm satisfied with what I've found.

  • $\begingroup$ For future reference: flag on MSE, and a moderator will look at it and migrate it if it looks a good fit for MO. This way you don't leave two open questions dangling at two sites at the same time. $\endgroup$ – Willie Wong Jun 12 '14 at 11:43
  • $\begingroup$ Do you think it makes sense to do it now anyway?... $\endgroup$ – Basil Jun 12 '14 at 11:44
  • 1
    $\begingroup$ Nah. But you should add a link to the MSE version indicating that you have cross posted. $\endgroup$ – Willie Wong Jun 12 '14 at 11:46
  • 7
    $\begingroup$ Is it true that "a set equipped with a binary reflexive and symmetric relation" is also known as a "graph"? $\endgroup$ – Gerald Edgar Jun 12 '14 at 14:48
  • 5
    $\begingroup$ Graphs mean different things to different people, so it's right to specify "set equipped with a binary reflexive and symmetric relation". $\endgroup$ – Todd Trimble Jun 12 '14 at 17:26

Let $A$ be the integers bigger than $1$ and let $a$ be related to $b$ if and only if $\gcd(a,b)>1$. Then $x$ has property $(\star)$ exactly when $x$ is a prime power.

  • 4
    $\begingroup$ In the same vein: $A$ is some arbitrary collection of sets, and $a \smile b$ if $a \cap b \neq \emptyset$. Then singleton sets have the property (*). $\endgroup$ – Terry Tao Jun 12 '14 at 18:16

Let us use the language of graph theory and speak of the graph with vertex set $A$ and edges defined by $\smile$. Then, if $a$ has property ($*$), all its direct neighbours are connected by an edge. Therefore, $a$ has the property $(*)$ iff $a$ and its neighbours form a clique.

So we might speak of $a$ as a "vertex of a clique without outside connection".

  • $\begingroup$ Right. I'm pretty sure that Ramiro de la Vega wrote a comment to the question mentioning this translation, but it's not there anymore. $\endgroup$ – Basil Jun 12 '14 at 22:57

Interesting feedback, thanks.

It seems to me that the property I'm talking about is indeed meaningful in various settings, but apparently doesn't come up so often, or rather, in an interesting or useful enough fashion, to warrant special attention.

In any case, here are some further elementary examples that I'm aware of.

  1. The one I've already written in my MSE question: for the standard tolerance relation on the euclidean plane, namely $x \smile y$ if and only if their distance is bounded by some fixed constant, there are no such points. But if we restrict the plane to some cone $A$ which is narrow enough (angle at most $60^o$), then the apex of the cone is "transitive".

  2. Again on the euclidean plane, take $A$ to be the complement of a disc, boundary included (a non-convex set) and say that $x \smile y$ if and only if they are joined by a line segment entirely within $A$. The "transitive" elements here are the points of the circle (everything related to them has to be above the corresponding tangent).

  3. Take $A$ to be the set of all sequences in the interval $[0,1]$; say that $(x_n) \smile (y_n)$ when $(x_n)$ and $(y_n)$ share an accumulation point. Then the converging sequences are the "transitive" ones.


An example from model theory:

For $\mathcal{S}$ a structure in a finite relational language $\Sigma$, let $Age(\mathcal{S})$ be the set of all finite $\Sigma$-structures with domain $\subseteq\omega$ which are isomoprhic to a substructure of $\mathcal{S}$. Now define the relation $\smile$ on $Age(\mathcal{S})$, "admits amalgamation," as:

  • $A\smile B$ if, for every $C\in Age(\mathcal{S})$ and pair of embeddings $f_0: C\rightarrow A$, $f_1: C\rightarrow B$ satisfying $$f_0\upharpoonright (f_0^{-1}(\vert A\vert\cap \vert B\vert))=f_1\upharpoonright (f_1^{-1}(\vert A\vert\cap \vert B\vert))$$ (this condition just says that when $A$ and $B$ overlap, $f_0$ and $f_1$ look the same; it's necessary for reflexivity to hold) there is a $D\in Age(\mathcal{S})$ and embeddings $g_0: A\rightarrow D$, $g_1: B\rightarrow D$ such that $g_0\circ f_0=g_1\circ f_1$.

Saying that $\smile$ always holds is the same as saying that $Age(\mathcal{S})$ has the amalgamation property (see http://en.wikipedia.org/wiki/Age_(model_theory)); however, for lots of $\mathcal{S}$, this fails - for example, taking $\mathcal{S}$ to be the successor graph on $\mathbb{Z}$ (see “Fraïssé limits” without amalgamation).

So what can we say about $(\star)$ in this context? Well, for one thing, the one-element structure is trivially $\smile$-related to everything, so it has $(\star)$ iff $Age(\mathcal{S})$ has the amalgamation property. Another essentially trivial observation, in the $\mathbb{Z}$-chains example any connected subgraph of size $>2$ satisfies $(\star)$.

Beyond this, I don't really know anything about $\smile$, but it seems like it could be interesting.


Here's another simple example. Let $A=\mathbb{R}$ and let $x$ be related to $y$ if and only if $xy \geq 0$. Then $a$ satisfies $(\star)$ if and only if $a \neq 0$.


Consider graphs (I have seen these been called "corollas"), which consists of a central vertex, and connected to several other vertices, with no further edges. The relation $a \sim b$ defined is "there is a path from $a$ to $b$". The central vertex in this graph has this property.

Graphs which is the union of such corollas all have the central vertices as transitivity elements.

  • $\begingroup$ You mean something like this, right? Then every vertex would have the property (via the central vertex); path-connectedness is transitive. $\endgroup$ – Basil Jun 12 '14 at 22:52
  • $\begingroup$ Yes, exactly, a star. $\endgroup$ – Per Alexandersson Jun 13 '14 at 6:06

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.