Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:


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.

share|cite|improve this question
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

15 Answers 15

up vote 42 down vote accepted

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"

share|cite|improve this answer
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:…. 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
@DonAntonio Put another way: If you were posting an answer to a question, you researched the question, and you were familiar with the content of the question very deeply, would you not want to be accepted over a one line answer? Alancalvitti has went above and beyond the standards present in all other answers here, and that is to be rewarded. May we exchange our five cents and benefit from the perspective of one another? :-) – 000 Jan 20 '13 at 19:42

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

share|cite|improve this answer
@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
I beautified your edit, I hope you don't mind. – Asaf Karagila Jan 4 '13 at 0:40

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

This is reflexive and symmetric, but not transitive.

share|cite|improve this answer
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.

share|cite|improve this answer
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 Jahn Jan 3 '13 at 13:10
This has nothing to do with math. -1 – user2345215 Aug 14 '14 at 18:45

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

share|cite|improve this answer

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

share|cite|improve this answer
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 had body contact with $y$.
  • $x$ and $y$ were once nationals of the same country.
share|cite|improve this answer
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

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

share|cite|improve this answer
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

What about

  • $\,xRy\Longleftrightarrow\,\,x\,,\,y\,$ are blood related?
share|cite|improve this answer
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).

share|cite|improve this answer
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

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.

share|cite|improve this answer

$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.

share|cite|improve this answer
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

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}
share|cite|improve this answer

Let xMy mean that x owes money to y or that y owes money to x.Let xPy mean that x and y have at least one parent in common.

share|cite|improve this answer

I remember this (I think) from a Martin Gardner article in Scientific American; but I could not find the article. Yes, it is mathematical, but it seems to have "real world" implications.

      a  b  c
t X | 8  3  4 |
e Y | 1  5  9 |
a Z | 6  7  2 |
m   +---------+

Each team, X, Y, and Z, consists of three players. The table above, which just happens to be a magic square, shows the relative strengths of each player. In a competition, the player with the higher strength will win. In each game, every player in one team competes against each player in the other team. The team with the most wins is the better team.

When team X plays team Y, the wins are

Xa Xb Xc total  Ya Yb Yc total
 2  1  1   4     0  2  3   5   So team Y is "better than" team X : Y > X

When team Y plays team Z, the wins are

Ya Yb Yc total  Za Zb Zc total
 0  1  3   4     2  2  1   5   So team Z is "better than" team Y : Z > Y

Finally, when team Z plays team X, the wins are

Za Zb Zc total  Xa Xb Xc total  
 2  2  0   4     3  1  1   5   So team X is "better than" team Z : X > Z

Hence, "better than" is not a transitive relation.

share|cite|improve this answer

protected by Marvis Jan 7 '13 at 2:45

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.