Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
12  
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
1  
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
2  
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
2  
@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
5  
@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

12 Answers 12

up vote 21 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|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: 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
    
@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|improve this answer
24  
(+1): Works literally and euphemistically! –  Cameron Buie Jan 1 '13 at 18:27
1  
@amWhy You read my mind in your edit. I'll be sure to remember this exercise. –  000 Jan 1 '13 at 18:32
20  
In certain circles this is transitive –  Andrea Mori Jan 1 '13 at 23:53
11  
Surely this relation is not reflexive for newborns... –  akkkk Jan 2 '13 at 11:17
10  
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

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

This is reflexive and symmetric, but not transitive.

share|improve this answer
7  
A classic example is the notion of just noticeable difference in psychophysics. –  Brian M. Scott Jan 1 '13 at 18:26
3  
Or perhaps $|x-y|\le 1$. Or does this fail "real life"? –  MJD Jan 2 '13 at 2:18
2  
@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|improve this answer
16  
See also "ring species". –  Douglas S. Stones Jan 1 '13 at 21:59
3  
@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

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

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

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

share|improve this answer
  • $x$ has had body contact with $y$.
  • $x$ and $y$ were once nationals of the same country.
share|improve this answer

What about

  • $\,xRy\Longleftrightarrow\,\,x\,,\,y\,$ are blood related?
share|improve this answer
1  
This defines the full relation amongst living humans, no? Hence, transitive. –  Did Jan 6 '13 at 18:09
2  
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
3  
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
1  
Yeah, well: that still isn't a proof, as it hasn't yet been proved there's one single ancestor for human beings that we can point at. I happen to be a very well educated mathematician in anthropology and, fortunately enough for us all who love deeply this subject, there're still more open than closed questions in all this. So no: no proof...yet. –  DonAntonio Jan 6 '13 at 19:23
5  
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$ has the same number of legs and/or the same number of teeth as $y$.

share|improve this answer
27  
So the disjunction of two equivalence relations is always reflexive and symmetric, but usually not transitive. –  Michael Hardy Jan 1 '13 at 19:06
2  
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

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

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

share|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

$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|improve this answer
1  
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

protected by Marvis Jan 7 '13 at 2:45

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

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.