Given the usual set-theoretic definition of a binary relation[1], along with the usual notions of

  • reflexivity
  • symmetry
  • transitivity

Do there exist any interesting (i.e. surprising, yielding novel results, worth studying etc.) binary relations (across the various fields of study) satisfying reflexivity and symmetry, but not transitivity? If so, could you provide a non-trivial[2] example?

In my (limited) experience (< 1 year of undergraduate study) I've not come across an example satisfying this constraint, but I'm also relatively new to studying Mathematics.

[1] A binary relation on sets $A$ and $B$ is defined as a subset of the cartesian product $A \times B$, that is, a collection of ordered pairs

[2] A really simple example would be the relation over sets of people encoding had a conversation with. That is, we've all debated with ourselves granting reflexivity, and the symmetry is similarly obvious, while transitivity is not guaranteed.

  • 4
    $\begingroup$ Here is one you met before first year. Let $A$ be the set of points on the edges of a certain triangle. Define a relation $R$ on $A$ by $(x,y)\in R$ if $x$ and $y$ are on the same edge of the triangle. $\endgroup$ – André Nicolas Jul 16 '11 at 23:29
  • $\begingroup$ is friends with $\endgroup$ – isomorphismes Jan 28 '14 at 21:12
  • $\begingroup$ The three axioms put together form an equivalence relation; here are some examples of relaxing at least one of the three conditions. $\endgroup$ – isomorphismes Jan 30 '14 at 3:15
  • $\begingroup$ One interesting kind of intransitive thing plato.stanford.edu/entries/nonwellfounded-set-theory satisfies a>b>c>...>a. $\endgroup$ – isomorphismes Jan 30 '14 at 3:18

Such a thing is (more or less) the same as an undirected graph, if you adhere to the convention that a vertex is adjacent to itself. I daresay people find graph theory interesting and worth studying.

  • $\begingroup$ A bit less than more, it seems to me, at least for a question at this level, since for an exact match you must disallow multiple edges and require a loop at each vertex. I’d have said that undirected simple graphs are essentially symmetric, irreflexive binary relations, though I grant you that in some sense the difference between reflexive and irreflexive is more formal than essential. $\endgroup$ – Brian M. Scott Jul 16 '11 at 23:36
  • 2
    $\begingroup$ @Brian: well, there are many many categories of graphs that one might be interested in with endless little tweaks as to the exact types of graphs and morphisms one wants to admit, and this is one of them. A loop at each vertex isn't so strange: if one is studying random walks, it corresponds to allowing the random walker to not move, for example. $\endgroup$ – Qiaochu Yuan Jul 16 '11 at 23:38
  • $\begingroup$ Thanks! This was the clarification I was more or less looking for; I'd initially thought that the relation might represent those directed graphs with an identity edge at each vertex and two (opposing) edges between each vertex where the relation holds; your representation is much cleaner. $\endgroup$ – Raeez Jul 17 '11 at 10:22

Many natural examples of this arise from "having something in common"; for instance, lines having points in common, numbers having divisors in common, sets having elements in common, algebraic structures having isomorphic substructures in common, statements having models in common, etc. In real life, a corresponding example is having a parent in common.


For $x, y \in \mathbb{R}$, put $(x,y)$ in the relation if $|x-y|<1$. Or do the same thing in $\mathbb{R}^2$. Or else replace $1$ by some $\epsilon>0$.

  • $\begingroup$ These are well-known graphs with some very interesting open problems. But your post doesn't even mention why anyone should care about these graphs! $\endgroup$ – François G. Dorais Jul 17 '11 at 5:16
  • 1
    $\begingroup$ @François G. Dorais: Graph theory was already taken. I was thinking geometry/analysis. The colouring problem for $|x-y|=1$ in $\mathbb{R}^2$, and its relatives, are not directly connected to inequalities. $\endgroup$ – André Nicolas Jul 17 '11 at 5:57

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.