Binary relations, closures and equivalences

Question

Let $R$ be the relation on $Z$ such that $xRy \iff x-y=c$.

Well, what I have so far is $R=\{ 0,-1,1,0,-1,1,0 \cdots\}$

Is $R^* $ and equivalence relation? Why not?

This is where problems start: I don't know what the definition of $R^* $. In fact, I cannot seem to find anything related to this in my notes. First off, is my relation $R$ correct at this point?

Unless $;c=0; $ the relation has no chance whatsoever to be reflexive and, thus, not an equivalence relation...But then you see what you get if $;c=0;$ , right? :) — DonAntonio, Nov 23 '13 at 02:02
@Dimitri : your question has several issues. You never defined what $R^$ is (an apparent typo). Your "$R$" (which maybe was supposed to be $R^$"?) should be a set of ordered pairs, and it isn't. — Stefan Smith, Nov 23 '13 at 02:06
@DonAntonio: The question was not whether $R$ is an equivalence relation, but whether $R^*$ is -- I suppose this notation means the reflexive transitive closure of $R$. — hmakholm left over Monica, Nov 23 '13 at 02:07
@HenningMakholm I have never seen this notation before and it has been causing me some problems. — Dimitri, Nov 23 '13 at 02:09
$R^*$ for reflexive transitive closure is commonly encountered at least in connection with rewrite systems (such as the $\lambda$-calculus). Since this is tagged "discrete math" which is usually a support course for computer science, I think it is likely that this is the relevant meaning here. — hmakholm left over Monica, Nov 23 '13 at 02:10
@HenningMakholm I see now. And you're right, it is a Computer Science course. So this is just plain notation for a transitive closure? — Dimitri, Nov 23 '13 at 02:11
If $;R^;$ is only* the reflexive/transitive closure then we still have issues here with symmetry, don't we? — DonAntonio, Nov 23 '13 at 02:12
Dimitri: Transitive and reflexive closure, I would assume. The pure transitive closure would usually be $R^+$ (by analogy with regular expressions, for example). @DonAntonio: Yes, there are still symmetry issues. — hmakholm left over Monica, Nov 23 '13 at 02:13
In fact, when $c=1$ the resulting $R^*$ is a well-known relation on $\mathbb Z$... — hmakholm left over Monica, Nov 23 '13 at 02:15
With $;c=0;$ we get an even more well-known relation, me thinks...and way more boring, too. — DonAntonio, Nov 23 '13 at 02:18
If $R \subseteq \Bbb Z X \Bbb Z$, then the only time $c=1$ is when $x>y$, no ? — Dimitri, Nov 23 '13 at 02:19
@Dimitri: Right. Or when $x=y$, since the star (called the Kleene star) is the reflexive transitive closure. — hmakholm left over Monica, Nov 23 '13 at 02:27
@Dimitri: One possibility would be "the intersection of all relations that contain $R$ and are reflexive and transitive". — hmakholm left over Monica, Nov 23 '13 at 13:01
You might want to look at this question about the same relation. — Brian M. Scott, Nov 29 '13 at 20:41

score 0 · Accepted Answer · answered Nov 23 '13 at 02:07

0

Your relation is not correct. A relation is defined to be a set of ordered pairs where the ordered pair (x,y) is included if xRy.

answered Nov 23 '13 at 02:07

Alex Chandler

86

Binary relations, closures and equivalences

1 Answers1