6
$\begingroup$

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.

  • 0
    One interesting kind of intransitive thing http://plato.stanford.edu/entries/nonwellfounded-set-theory/ satisfies `a>b>c>...>a`.2014-01-30

3 Answers 3

7

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.

  • 0
    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.2011-07-17
6

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.

2

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

  • 1
    @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.2011-07-17