Question

Let \(R\) be a reflexive and transitive relation on a set \(S\). Let \(R^*\) be the dual relation, \((a,b) \in R^*\) if and only if \((b,a) \in R\). Show that \(R \cap R^*\) and \(R \cup R^*\) are equivalence relations.

Answer 1

My attempt: By definition 6.2.3

R is reflexive if \((\forall x \in S)(b,b) \in R]\)

R is transitive if \((\forall x, y, z \in S)[((b,a) \in R \land (a,c) \in R) \rightarrow (b,c) \in R]\).

At first I wanted to disprove the statement. I thought that R wouldn't be an equivalence relation because it was only reflexive and transitive, not symmetric. And by set intersection definition for \(R \cap R^*\) I thought that \(R\) and \(R^*\) must both be an equivalence relation . However for set union definition, \(R\) or \(R^*\) can be equivalence relation. It turns out that it's possible to prove.

I was given this massive hint during the lecture:




\((a,b) \in R^* \leftrightarrow (b,a) \in R\).

Set \(T = R \cap R^*\). Show that \(T\) is an equivalence relation.

1. \((a,a) \in R\) and \( (a,a) \in R^* \rightarrow (a,a) \in R \cap R^*\)

2. Suppose \((a,b) \in R \cap R^* \rightarrow (a,b) \in R\) and \((b,a) \in R \rightarrow (b,a) \in R \cap R^*\)

3. Suppose \((a,b) \in R \cap R^*\) and \((b,c) \in R \cap R^*\) then \((a,b) \in R\) and \((b,a) \in R\). \((b,c) \in R)\) and \((c,b) \in R\). So \((a,c) \in R \) and \((c,a) \in R\). So \((a,c) \in R\) and \((a,c) \in R^*\) and \((a,c) \in R \cap R^*\)

Is \(R \cup R^*\) and equivalence relation?

\((a,b) \in R \cup R^*\) if \((a,b) \in R\) or \((b,a) \in R\).

\((a,b) \in R \cap R^*\) if \((a,b) \in R\) and \((b,a) \in R\)

The first two work, but the last one won't match. give a counter example

I'm thinking that the last one won't match because we have the extra element c, but how do I show it. Do I let a,b,c be sets in \(R\) and \(R^*\) like let \(A =[1,2],B = [1,2]\) and \(C=[1,2,3]\)? And then use the dual relation to see that something doesn't match due to the \(3\) in \(C\)?

Answer 2

@UnkleRhaukus

Answer 3

@miracrown @ParthKohli

Answer 4

For it to be an equivalence relation, we need to show that it is reflexive, symmetric, and transitive.

Answer 5

yeah but the problem is that R is just reflexive and transitive..

Answer 6

so how can there be an equivalence relation when there is no symmetry in R?

Answer 7

Well, consider \(R\cap R^*\) for a moment. Is it possible that \((a,b) \in R\cap R^{*}\) and yet \((b,a)\notin R\cap R^*\)

Answer 8

If \((a,b)\in R\cap R^*\), then that means \((a,b)\in R\) and \((a,b)\in R^*\).

Answer 9

If \((a,b)\in R\) then \((b,a)\in R^{*}\) by nature of being a dual relation.

Answer 10

oh so for R* then (b,a) is in R* and (a,b) is in R* because it's a dual relation.. could be one or the other

Answer 11

more like both

Answer 12

If \((a,b)\in R^{*}\) then \((b,a) \in R\), otherwise why would it be in \(R^*\)?

Answer 13

It is clear that \(R\cap R^{*}\) is symmetric. It isn't clear whether or not it reflexive or transitive.

Answer 14

D: what!!!

Answer 15

If \((a,b)\notin R\) then \((b,a)\notin R^*\) so there can't be any case where \( (a,b)\notin R\cap R^{*}\) and yet \((b,a)\notin R\cap R^{*}\)

Answer 16

Well, it is easy to prove that \(R\cap R^{*}\) is reflexive, but you shouldn't just assume it.

Answer 17

If \(R\) is reflexive, then \(\forall x\quad (x,x)\in R \implies (x,x)\in R^{*}\) and so \(R^{*}\) is reflexive.

Answer 18

So \(\forall x\quad (x,x)\in R\cap R^{*}\).

Answer 19

I think we can also show that the dual relation is transitive.

Answer 20

\[
\forall x,y,z \quad (x,y)\in R\land (y,z)\in R\implies (x,z)\in R
\]This means \[
\forall x,y,z \quad (y,x)\in R^{*}\land (z,y)\in R^*\implies (z,x)\in R
\]If we reorder those first two pairs:\[
\forall x,y,z \quad (z,y)\in R^* \land (y,x)\in R^{*}\implies (z,x)\in R
\]This is the transitive property.

Answer 21

ahhh so wait.. if R* is a dual relation, could it be that it's reflexive and transitive as well?

Answer 22

Oh, those two \(R\) should be \(R^*\).

Answer 23

Yeah.

Answer 24

ok ^^

Answer 25

That doesn't mean the intersection of them is transitive though.

Answer 26

It still has to be proven.

Answer 27

so what about for \[R \cup R^* \]? doesn't .. oh I see like suppose R is reflexive and transitive... and R* is dual relation then that means that R* is transitive and reflexive... by set union definition either R or R* must be an equivalence relation

Answer 28

teh transitive for \[R \cap R^* \] was super massive it had (a,b) with c's.. it's #3

Answer 29

but for set union #3 doesn't work because something doesn't match

Answer 30

\[
\forall x,y,z\quad (x,y) \in R\cap R^{*}\land (y,z) \in R\cap R^{*}
\]Start here.

Answer 31

We know that \((x,y)\in R\cap R^{*}\implies (y,x) \in R\cap R^*\), since we have shown this is symmetric. Same can be said for \((z,y)\).

Answer 32

Since \((x,y) \in R \land (y,z)\in R\), we can use transitive property to show that \((x,z) \in R\).

Answer 33

Since \((z,y) \in R^*\) and \((y,x) \in R^*\), we can use transtive property of \(R^*\) to show that \((x,z)\in R^*\). So since \((x,z)\) is in both, we can say \((x,z)\in R\cap R^*\). This proves that \(R\cap R^*\) is transitive.

Answer 34

Finally, I'll do a more formal proof of symmetry.
Suppose \[
\forall x,y\quad (x,y) \in R\cap R^{*}
\] The fact that \((x,y)\in R\) tells us \((y,x)\in R^*\).
The fact that \((x,y)\in R^*\) tells use \((y,x)\in R\). So \((y,x)\in R\cap R^*\).

Answer 35

but what about for R union R*.. . if the 3rd part doesn't work then suppose it's not transitive?

Answer 36

You want a proof for transitive for the union?

Answer 37

Suppose \[
\forall x,y,z\quad (x,y)\in R\cup R^*\land (y,z)\in R\cup R^*
\]

Answer 38

So \((x,y)\) is either in \(R\) or \(R^*\). Regardless of which one it is in, \((y,x)\) is in the other.

Answer 39

This shows that \(R\cup R^*\) is symmetric.

Answer 40

okkk?! but something has to break ... right? because the first two for R U R* worked but the last one doesn't because it simply doesn't match.

Answer 41

We can disprove it with a counter example.

Answer 42

the one with suppose a, b , c it was really long.

Answer 43

errr yes we have to provide a counter example I know that. maybe we can have a set [1,2,3]

Answer 44

Let \(R = \{(1,2), (1,1), (2,2)\}\) This is transitive, I believe.

Answer 45

So \(R^*=\{(2,1), (1,1), (2,2)\}\)

Answer 46

Actually in this case \(R\cup R^*\) is transitive.

Answer 47

Okay let \[
R = \{(1,1),(2,2),(3,3), (1,2),(3,2)\}
\]Then \[
R^* = \{(1,1),(2,2),(3,3), (2,1),(2,3)\}
\]
We can see \((1,2) \in R\) and \((2,3)\in R^*\) But \((1,3)\) is not in either one of them. Thus it isn't transitive.

Answer 48

So \(R\cup R^*\) is not equivalence relation.

Answer 49

argh how do I prove reflexivity for \[R \cup R^*\] would it just be \[(a,a) \in R \lor (a,a) \in R^* \leftrightarrow (a,a) \in R \cup R^*\]?

Answer 50

I kinda just showed that it isn't an equivalence relation.

Answer 51

the transitivity fails, but the symmetry and reflexivity lives on .. but how for the reflexivity part... I mean by definition we are just dealing with one element here .. \[(\forall x \in S ) [(x,x) \in R\]

Answer 52

what I'm trying to do is proving reflexivity for \[(a,a) \in R \lor (a,a) \in R^* \leftrightarrow (a,a) \in R \cup R^*\]

Answer 53

*bangs head*

Answer 54

ok ok.. there's reflexivity for \[R \cap R^* \] but what about for \[R \cup R^*\]?

Answer 55

Well, yeah, \(R\cup R^*\) is reflexive and symmetric.

Answer 56

ok so how do I prove the reflexive part.. won't that be just\[(a,a) \in R \lor (a,a) \in R^* \leftrightarrow (a,a) \in R \cup R^*\] ?????

Answer 57

\[
\forall x\quad (x,x)\in R \implies (x,x)\in R^*
\]

Answer 58

\[
\forall x\quad (x,x)\in R \implies (x,x)\in R\cup R^*
\]

Answer 59

only instead of x it would be a right?

Answer 60

It is a dummy variable, it doesn't matter.

Answer 61

got it ^^

Answer 62

now I just got to gather all the info for the set algebraic proof and I'm done with these corrections... these questions are longer than the first exam.. I highly doubt that the whole exam would be done in 15 minutes x0x