1
$\begingroup$

What is an example of a relation $\mathscr{R}$ on a set $S$ such that $\mathscr{R}$ is reflexive but not transitive?

Here is what I have come up with.

Let $S = \mathbb{Z}$. Then let $\mathscr{R} = \{(x,y) \in S\times S|(x > 0 \land y>0) \lor (x < 0 \land y < 0)\}$

Because $(2,2) \in \mathscr{R}$ (i.e reflexive). But if $(-2,0) \in \mathscr{R}$ and $(0,2) \in \mathscr{R}$ but $(-2,2) \notin \mathscr{R}$ (i.e. NOT transitive)

Can anyone verify whether I have answered the question correctly or provide a much simpler example for a relation that is reflexive but not transitive on $\mathbb{Z}$?

$\endgroup$
  • $\begingroup$ I can't understand why $(-2,0)$ and $(0,2)$ is in relation $R$ according to your definiton unless modifing it by $ab\geq0$ $\endgroup$ – Shuchang Sep 12 '13 at 5:42
  • $\begingroup$ If you used "both $\ge 0$ or both $\le 0$" then your example would work. Probably that's what you meant, but positive means greater than $0$. The example is more elaborate than necessary, but a nice idea. $\endgroup$ – André Nicolas Sep 12 '13 at 5:44
  • $\begingroup$ I meant that -2 and 0 are both negative which both negative (I think) and 2 and 0 are both positive $\endgroup$ – Sione Pouhi Jr Samate Sep 12 '13 at 5:49
  • $\begingroup$ Thanks Andre that was exactly what I meant and guess I have got the answer I was looking for. Thanks $\endgroup$ – Sione Pouhi Jr Samate Sep 12 '13 at 5:51
  • $\begingroup$ One problem with your choice (not a big deal in this case) is that to show it is reflexive, you must argue that for any $x$, $(x,x)$ is in the relation. It is not enough to say $(2,2)$ is in the relation. On the other hand, to show it is not transitive, a single numerical example is enough. $\endgroup$ – André Nicolas Sep 12 '13 at 5:57
1
$\begingroup$

The relation $R=\{(1,1),(1,2),(2,2),(2,3),(3,3)\}$ on the set $\{1,2,3\}$ is reflexive and not transitive.

If you want the relation to be on the set of integers, cheat as follows: consider the relation $R=\{(1,2),(2,3)\}\cup\{(n,n):n\in\mathbb Z\}$.

$\endgroup$
0
$\begingroup$

You’ve almost answered it correctly. The problem is that $0$ is neither positive nor negative, so $\langle -2,0\rangle$ and $\langle 0,2\rangle$ are not actually in the relation $R$ as you defined it. However, you can modify the definition just a little to get a relation that works fine.

You want $\langle m,n\rangle\in R$ if either $m\ge 0$ and $n\ge 0$, or $m\le 0$ and $n\le 0$. A slick way to say this is that $\langle m,n\rangle\in R$ if and only if $mn\ge 0$. Clearly $n^2\ge 0$ for all $n\in\Bbb Z$, so $R$ is reflexive. And since we’ve now included $0$ with both the positive and the negative integers, we now do have $\langle -2,0\rangle\in R$ and $\langle 0,2\rangle\in R$, and of course $\langle -2,2\rangle\notin R$.

$\endgroup$

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.