1
$\begingroup$

R is a partial order relation on some set A. Which of the following statements are correct?

a) $R\cup R^{-1}$ is an equivalence relation

b) $R^{2}$ is a partial order relation

c) $R\cap R^{-1}$ is an equivalence relation

I've tried solving this. For (a), I think this is true, but the answer I got say false. My logic was:

for every x, $xRx$ since R is reflexive. R is also ant-symmetric, so for every pair $xRy$, we will have $yRx$ because of the union, and so $R\cup R^{-1}$ is symmetric. Now I tried thinking on transitive, I took an example:

$R={(1,1),(2,2),(3,3),(1,2),(2,3),)(1,3)}$

If you do $R\cup R^{-1}$ you get a transitive relation. I can't find an example to break it.

What am I doing wrong ?

For (b) I tried a similar example and go $R^{2}=R$ which shows it's true, but it must have been a private case. How can you explain the fact that (b) is true ? (I am not looking for a formal proof).

For (c), if I use intersection, I get only "reflexive" couples, so this is true. Am I correct on this one at least ?

Thank you.

$\endgroup$
  • 1
    $\begingroup$ Counter example to the transitivity claim in part (a): (1, 2), (3, 2). $\endgroup$ – Bob Krueger Jun 7 '17 at 19:53
  • $\begingroup$ What, exactly, is your definition of "partial order relation"? I have never seen a requirement that it be reflexive. $\endgroup$ – user247327 Jun 7 '17 at 19:53
  • $\begingroup$ @user247327, I'd assume they are using the standard reflexive, antisymmetric, and transitive definition (en.wikipedia.org/wiki/Partially_ordered_set). Something like $\leq$. $\endgroup$ – Bob Krueger Jun 7 '17 at 19:55
  • $\begingroup$ @user3275222, you may also want to be more specific about what you mean by $R^2$. Is it partial order on $A^2$? Is it an extension of $R$? $\endgroup$ – Bob Krueger Jun 7 '17 at 20:03
  • $\begingroup$ Sorry, I'll be more specific. 1. Partial order is indeed reflexive, ant-symmetric and transitive. As for R^2, I mean the composite relation R on R. Thanks. $\endgroup$ – user3275222 Jun 7 '17 at 20:07
1
$\begingroup$

b) If aRRb, bRRa, then some x,y with aRx, xRb, bRy, yRa. Thus...

If aRRb, bRRc, then some x,y with aRx, xRb, bRy, yRc. Thus...

$\endgroup$
  • $\begingroup$ I'm not sure whether you are saying (b) is correct or incorrect. Of course it may be helpful to unroll the relation $R^2$ as you outline, but you omit to draw a conclusion one way or the other. $\endgroup$ – hardmath Jun 8 '17 at 2:25
  • $\begingroup$ William, I don't get what you mean by that. Your first line implies that RR can't be symmetric. But I need it to be anti-symmetric, it's not the same thing. What am I missing ? $\endgroup$ – user3275222 Jun 8 '17 at 4:11
  • $\begingroup$ @hardmath User didnot want a proof so I gave him a hint. $\endgroup$ – William Elliot Jun 9 '17 at 3:38
  • $\begingroup$ @user3275222. To continue, aRb and bRa. Hence a = b. How are you defining anti-symmetric? $\endgroup$ – William Elliot Jun 9 '17 at 3:44

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.