# Are there real-life relations which are symmetric and reflexive but not transitive?

Inspired by Halmos (Naive Set Theory) . . .

For each of these three possible properties [reflexivity, symmetry, and transitivity], find a relation that does not have that property but does have the other two.

One can construct each of these relations and, in particular, a relation that is

## symmetric and reflexive but not transitive:

$$R=\{(a,a),(a,b),(b,a),(b,b),(c,c),(b,c),(c,b)\}.$$

It is clearly not transitive since $$(a,b)\in R$$ and $$(b,c)\in R$$ whilst $$(a,c)\notin R$$. On the other hand, it is reflexive since $$(x,x)\in R$$ for all cases of $$x$$: $$x=a$$, $$x=b$$, and $$x=c$$. Likewise, it is symmetric since $$(a,b)\in R$$ and $$(b,a)\in R$$ and $$(b,c)\in R$$ and $$(c,b)\in R$$. However, this doesn't satisfy me.

## Are there real-life examples of $$R$$?

In this question, I am asking if there are tangible and not directly mathematical examples of $$R$$: a relation that is reflexive and symmetric, but not transitive. For example, when dealing with relations which are symmetric, we could say that $$R$$ is equivalent to being married. Another common example is ancestry. If $$xRy$$ means $$x$$ is an ancestor of $$y$$, $$R$$ is transitive but neither symmetric nor reflexive.

I would like to see an example along these lines within the answer. Thank you.

• To me a more interesting question is whether there are relations that are symmetric and transitive but not reflexive. That question made me realize that "reflexive" means reflexive on some set. Every relation that is symmetric and transitive is reflexive on some set, and is therefore an equivalence relation on some set, but "$x$ got a Ph.D. from the same university from which $y$ got a Ph.D." is an equivalence relation only on the set of persons with Ph.D.s, not on any larger set of people. – Michael Hardy Jan 1 '13 at 19:12
• I think this big-list question has run its course. I've cast the final vote to close. – Zev Chonoles Jan 3 '13 at 6:38
• Limitless - I suspect the closure correlates to my answer. @Zev I really don't think the question should be "penalized" (aka closed) because of my answer (which - in all honestly - was posted with the literal interpretation in mind!) Protecting it makes sense, but this was, and is, a legitimate question. – amWhy Jan 4 '13 at 15:40
• @ZevChonoles I agree with Asaf and amWhy. I am fine with it being closed, but I do not feel that 'not constructive' is an appropriate portrayal of why it is closed. (I am actually confused as to why it was closed: Is it bad if there are multiple answers to a question? Can you clarify? I have seen questions with a lot of answers before . . .) Of course, anyone interested could read your most recent comment. So, this seems to be a minimal (but relevant) issue. – 000 Jan 5 '13 at 19:47
• @amWhy: is it necessary to bump this thread to the front page without really changing anything of substance for at least the sixth time now? I think the thread has run its course and ceased to be useful long ago. – Martin Feb 3 '13 at 15:46

My favorite example is synonymy: certainly any word is synonymous with itself, and if you squint you can imagine that if a word appears in the thesaurus entry for another, then the latter will symmetrically appear in the thesaurus entry for the former. But synonymy is not transitive.

However this and many other examples are special cases of vertices joined by edges in graphs which is a canonical example of Tolerance:

Tolerance relations are binary reflexive, symmetric but generally not transitive relations historically introduced by Poincare', who distinguished the mathematical continuum from the physical continuum, then studied by Halpern, and most notably the topologist Zeeman.

Recent surveys include:

Peters & Wasilewski's "Tolerance spaces: origins, theoretical aspects and applications" Info Sci 2012, and Sossinsky's "Tolerance Space Theory" Acta App Math 1986, which mentions these examples:

• Metric space with distance between points less than $\epsilon$

• Topological space with a fixed covering and 2 points both contained in one element of the cover

• Vertices in the same simples of a simplicial complex

• Vertices joined by an edge in an undirected graph

• Sequences that differ by 1 (or 2, or 3) binary digits

• Cosets in a group with nonempty intersection

An intersting textbook that discusses tolerances is Pirlot & Vincke's Semiorders, 1997.

Sossinsky's paper goes on to mention:

(i) tolerance spaces appear quite naturally in the most varied branches of mathematics;

(ii) the tolerance setting is very convenient for the use of many existing powerful mathematical tools;

(iii) only results 'within tolerance' are usually required in practical applications.

and that "tolerance, in a way, is a trick for avoiding the specific hazards of infinite-dimensional-function spaces, eg their local noncompactness; moreover, in a certain sense, in tolerance spaces, you can't have large finite dimensions"

• This seems to be an extremely researched and detailed answer. You have given me an ample amount of resources to further my understanding of this question. Consequently, +1 and accept. – 000 Jan 12 '13 at 14:59
• @Limitless, thanks- you may be interested in this Q that I asked but so far got no replies: math.stackexchange.com/questions/270678/…. Also, if symmetry is removed, it would be interesting to develop a theory of directed tolerances to handle neighborhood digraphs in finite metric spaces. – alancalvitti Jan 12 '13 at 20:31
• @Limitless, I guess everybody's free to do whatever (s)he likes, but it seems slightly exaggerated, and even a little rude if you don't mind my saying so, to change your chosen question after more than 10-11 days you chose another question, not to mention that amWhy's answer has 126 upvotes (!) . You can always upvote received answers, but to "flip" chosen ones after so many days...well, perhaps it's only me but I don't think it is...uh, say... appropiate. Only my 5 cents – DonAntonio Jan 20 '13 at 16:43
• @DonAntonio It is in no way an attempt to be inappropriate. It is quite the opposite. Alancalvitti has clearly put a lot of effort into this answer. amWhy also put effort into her answer. I like both answers. However, I feel that this answer deserves just as much praise as amWhy's. It is unique, it is insightful, and it is very in depth. – 000 Jan 20 '13 at 19:39
• @RahulNarain, so be it, though I'd be a lawyer or a medicine doctor if I were to pay too much attention to consensus. Some of the answers in your link provide what I think is the best strategy: to wait a good while before accepting an answer as the best one. After all, upvoting is always fine. Just my opinion, anyway. – DonAntonio Jan 25 '13 at 18:10

$\quad\quad x\;$ has slept with $\;y$ ${}{}{}{}{}$

• @amWhy You read my mind in your edit. I'll be sure to remember this exercise. – 000 Jan 1 '13 at 18:32
• In certain circles this is transitive – Andrea Mori Jan 1 '13 at 23:53
• Surely this relation is not reflexive for newborns... – akkkk Jan 2 '13 at 11:17
• The discussion of religion on this answer seemed to me to be taking a turn for the worse, so I have deleted several comments. Sorry to spoil everyone's fun. – Zev Chonoles Jan 2 '13 at 23:42
• my favourite answer on MSE so far (+1) – tired Jan 3 '17 at 10:39

$x$ lives within one mile of $y$.

This is reflexive and symmetric, but not transitive.

• A classic example is the notion of just noticeable difference in psychophysics. – Brian M. Scott Jan 1 '13 at 18:26
• Or perhaps $|x-y|\le 1$. Or does this fail "real life"? – MJD Jan 2 '13 at 2:18
• @MJD : The original poster said "not directly mathematical", so I think that probably makes that a bad way of putting it. – Michael Hardy Jan 2 '13 at 4:06
• @MJD That is essentially the usual way of modeling just noticeable differences. – Michael Greinecker Jan 4 '13 at 0:49

$x$ is indistinguishable from $y$.

The non-transitivity of this relation is my favorite way to account for the non-intuitiveness of the theory of evolution.

• See also "ring species". – Douglas S. Stones Jan 1 '13 at 21:59
• @DouglasS.Stones How odd. I've been looking for that term for a couple days (the Larus gulls specifically), only to find it on math.SE? (o_0) – Izkata Jan 2 '13 at 20:44
• Nice example! (And link to the theory of evolution) (+1) – Dahn Jan 3 '13 at 13:10
• This has nothing to do with math. -1 – user2345215 Aug 14 '14 at 18:45
• @user2345215, a lot of these examples have nothing to do with math. Isn't that the point? OP was "asking if there are tangible and not directly mathematical examples." – user307169 Dec 21 '16 at 14:15

On the set of countries: $x$ and $y$ share a border.

There exists a question on math.SE that both $x$ and $y$ have answered.

• I'd venture to add: There exists a question on math.SE that both $x$ and $y$ have asked :-/ – amWhy Jan 2 '13 at 0:48
• amWhy, and then the obvious follow up: there is a question that $x$ and $y$ voted to close. :-) – Asaf Karagila Jan 2 '13 at 7:01

$x$ has the same number of legs and/or the same number of teeth as $y$.

• So the disjunction of two equivalence relations is always reflexive and symmetric, but usually not transitive. – Michael Hardy Jan 1 '13 at 19:06
• Actually, several other exmaples here are also of this disjunctive type, e.g. "lived together once" is "live together today or lived together yesterday or ... " – Hagen von Eitzen Jan 6 '13 at 11:19
• In fact every symmetric reflexive relation is a union of equivalence relations (if nothing else, then one equivalence relation for each distinct related pair). – hmakholm left over Monica Sep 5 '18 at 1:21
• $x$ has had body contact with $y$.
• $x$ and $y$ were once nationals of the same country.
• For that matter "are nationals of the same country" works because of dual nationality (and higher numbers). – Steve Jessop Mar 31 '15 at 17:40

• $\,xRy\Longleftrightarrow\,\,x\,,\,y\,$ are blood related?
• This defines the full relation amongst living humans, no? Hence, transitive. – Did Jan 6 '13 at 18:09
• You think? Prove it...:) As far as I know, I am not related to my wife's sister, say. If someone can prove otherwise please do be my guest. – DonAntonio Jan 6 '13 at 18:18
• You are most certainly related to your wife's sister, only your most recent common ancestor did not live two or three generations ago but slightly many more. Current estimates of the identical ancestor point for Homo sapiens are between 15,000 and 5,000 years ago. This takes into account isolated human groups (living mainly in central Africa, in Australia and in some Pacific islands) hence, assuming you do not descend from one of these groups, the identical ancestor point of your wife's sister and yourself is probably much later, at most of the order of 3,000 BC and probably still later. – Did Jan 6 '13 at 19:02
• You seem to negate the existence of, for example, what many biologists call mitochondrial Eve (as opposed to datation problems). I thought this was more or less consensual. Any reference to substantiate your claim? – Did Jan 6 '13 at 19:48
• Looked at the links, saw nothing in them related to my comments nor to my question to you. – Did Jan 6 '13 at 20:44

$x$ and $y$ are foods that go well together (with respect to a fixed person's palate, I suppose).

• I wonder if adding a quantifier there will reduce the relation to being trivial. That is whether or not the relation "$x$ and $y$ are foods that there is someone which find them very [palatally] compatible." is just all pairs of edible things, or reasonable "food". :-) – Asaf Karagila Feb 3 '13 at 14:14

Equality of numbers in Mathematica is symmetric and reflexive but not transitive:

eps = 50*$MachineEpsilon; a = 1; b = a + eps; c = b + eps; {a == a, b == b, c == c, a == b, b == a, b == c, c == b, a == c} (* Out: {True, True, True, True, True, True, True, False} *)  • This is cute :-) – Jyrki Lahtonen May 9 '18 at 17:43 • @JyrkiLahtonen Thanks! I actually like it, in part, because I think it's worth knowing this can happen when you use the computer. – Mark McClure May 9 '18 at 17:47 Several of the examples given have in common some similarity between things (if I resemble John and John resembles Mike, I do not necessarily resemble Mike: I and J. might have some common features different from those J. has in common with M.). And, sure enough, a reflexive, symmetric, non-transitive relation has been called a “similarity relation”; see for instance this search, and several other hits in (especially fuzzy) set theory.$x$has lived with$y$at some point (whether in the same building or same location on the streets). Alternately,$x$and$y$have at least one biological parent in common. • might not be reflexive for people born homeless. – Hagen von Eitzen Jan 1 '13 at 18:21 • True. I'll fix that. – Cameron Buie Jan 1 '13 at 18:22 Actors$x$and$y$have appear in the same movie at least once.$x$~$y$:$x$is the classmate of$y\$.

I hope this example work.