12
$\begingroup$

I need an example of a relation which is simultaneously not reflexive, not symmetric, and not transitive. Any accessible examples? Thanks in advance.

$\endgroup$
  • 10
    $\begingroup$ $a,b\in \mathbb{Z}$, $a\sim b$ iff $b=a+1$. $\endgroup$ – Dario Jul 1 '14 at 11:59
  • 36
    $\begingroup$ For any people $x, y$, try "$x$ loves $y$" :) $\endgroup$ – Shaun Jul 1 '14 at 12:22
  • 4
    $\begingroup$ Not all people are narcissists, @anorton $\ddot\smile$ $\endgroup$ – Shaun Jul 1 '14 at 15:37
  • 2
    $\begingroup$ @Shaun whoops. I was getting "not reflexive" confused with "irreflexive" $\endgroup$ – apnorton Jul 1 '14 at 15:38
  • 3
    $\begingroup$ A fun follow-on to your question is: what is the size of the smallest set on which you can define such a relation? $\endgroup$ – Eric Lippert Jul 1 '14 at 19:56

10 Answers 10

56
$\begingroup$

Here's a non-mathematical one: "is the father of".
You are not your own father. You are not your father's father. Your father's father is not your father.

$\endgroup$
  • 13
    $\begingroup$ It's actually stronger than "not reflexive, symmetric or transitive", it's irreflexive ($\forall x, x \not\sim x$), asymmetric ($x \sim y \Rightarrow y \not\sim x$), and antitransitive ($(x \sim y \wedge y \sim z) \Rightarrow x \not\sim z$). $\endgroup$ – M. Vinay Jul 1 '14 at 12:36
  • 11
    $\begingroup$ Note: does not work for grandfathers. $\endgroup$ – Emily Jul 1 '14 at 15:57
  • 4
    $\begingroup$ “Luke, I am your ….” :) $\endgroup$ – Scott Jul 1 '14 at 17:33
  • 7
    $\begingroup$ I'm not complaining, just observing: this is in some sense the same answer as Dario's comment to the question. $\endgroup$ – Steve Jessop Jul 1 '14 at 18:11
  • 2
    $\begingroup$ @SteveJessop Ah, I see "$a$ is the predecessor of $b$". Good observation. $\endgroup$ – M. Vinay Jul 2 '14 at 2:37
15
$\begingroup$

Think of three points $u, v, w$ with relation $R = \{(u, v), (v, w) \}$. So $u$ is related to $v$ and $v$ is related to $w$. This is not reflexive since $(u,u) \notin R$, not symmetric because $(v, u) \notin R$ and not transitive because $(u, w) \notin R$.

$\endgroup$
10
$\begingroup$

What beats what in Roshambo or "Rock, Paper, Scissors" is such a relation.

  1. not reflexive: rock does not beat rock.

  2. not symmetric: rock beats scissors, but scissors does not beat rock.

  3. not transitive: rock beats scissors and scissors beats paper, but rock does not beat paper.

The same is true of "Rock, Paper, Scissors, Lizard, Spock".

$\endgroup$
7
$\begingroup$

A simple one is : Define $R$ on $\mathbb{Z}$ by $(x,y)\in R$ if and only if $x-y=10$.

$\endgroup$
6
$\begingroup$

On $\mathbb{N}$, consider $$a \sim b \iff a +2b = 5,$$ then

  • $1\nsim 1$,

  • $3\sim 1$ but $1 \nsim 3$,

  • $3\sim 1, 1 \sim 2$ but $3 \nsim 2$.

$\endgroup$
  • $\begingroup$ Please don't use a symbol that's a variant of "$=$" for a relation that has none of the properties of equality! $\endgroup$ – David Richerby Jul 1 '14 at 15:33
  • $\begingroup$ @DavidRicherby It has been edited. $\endgroup$ – Surb Jul 1 '14 at 15:55
6
$\begingroup$

How about: "is the square of", defined on the set of positive integers? In other words, $$a \sim b \iff a=b^2$$

This relation is not reflexive (most numbers are not their own square), not symmetric (if $a$ is the square of $b$ then in most cases $b$ is not the square of $a$) and not transitive (if $a$ is the square of $b$ and $b$ is the square of $c$ then in general $a$ will not be the square of $c$).

$\endgroup$
6
$\begingroup$

Minimal example:

$X = \{0,1,2\}$

$R = \{(0,1),(1,2)\}$

$\endgroup$
4
$\begingroup$

Less than, but close: $$a \sim b \iff a < b \ \ \text{ but } \ \ a > (b-1)$$

So

  • $1\nsim 1$,

  • $0.5\sim 1$ but $1 \nsim 0.5$,

  • $0\sim 0.5$, $0.5 \sim 1$, but $0 \nsim 1$.

$\endgroup$
3
$\begingroup$

Why not $a\sim b$ if and only if either $a=3$ and $b=4$ or $a=4$ and $b=5$?

$\endgroup$
  • $\begingroup$ Whoops, right you are! I’ll add another point. $\endgroup$ – Lubin Jul 2 '14 at 12:37
3
$\begingroup$

Take any directed acyclic graph amd the arcs form an irreflexive, asymmetric antitransitive relation of its nodes. Then add some loops (not to all nodes), back-arcs (not to all of them) and some skip-forward arcs (not to all directed paths) and you have a more general relation with your restrictions.

Ex: 1) Strong version: a->b, b->c, c->d, a->e 2) Then add: a->a, b->a,a->d

$\endgroup$
  • $\begingroup$ Velcome to our site! $\endgroup$ – kjetil b halvorsen Jul 3 '14 at 7:50

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.