Thread: Equivalence relations on R intersection R^-1

1. Equivalence relations on R intersection R^-1

Let R be a reflexive and transitive relation on X. Show that R intersection R^-1 is an equivalence relation on X.

My proof:
Let R be reflexive and transitive, therefore R (x,x) (y,y) (z,z) (x,y) (y,z)
and R^-1 (x,x) (y,y) (z,z) (y,x) (z,y).
By the intersection rule we have R intersection R^-1 (x,x) (y,y) (z,z).

Is this correct?

How can I show that R intersection R^-1 is an equivalence relation on X?
Thank you.

2. Re: Equivalence relations on R intersection R^-1

Originally Posted by mathproblems
Let R be a reflexive and transitive relation on X. Show that R intersection R^-1 is an equivalence relation on X.
How can I show that R intersection R^-1 is an equivalence relation on X?
What you have posted is an example.
But it is not a proof.

You may have shown the elsewhere. But:
If a relation $\mathbf{R}$ is transitive then so is $\mathbf{R}^{-1}{}$ .
If a relation $\mathbf{R}$ is reflexive then so is $\mathbf{R}^{-1}{}$.

For any relation $\mathbf{R}$ relation $\mathbf{R}\cap\mathbf{R}^{-1}{}$ is symmetric.

3. Re: Equivalence relations on R intersection R^-1

relation is transitive R then (x,z) (x,y) (y,z)
R^-1 is also transitive (z,x) (y,x) (z,y)
relation is reflexive R then (x,x) (y,y) (z,z)
relation is reflexive R^-1 then (x,x) (y,y) (z,z)
Then R (x,z) (x,y) (y,z) (x,x) (y,y) (z,z)
and R^-1 (z,x) (y,x) (z,y) (x,x) (y,y) (z,z)
How is R intersection R^-1 is an equivalence relation?

4. Re: Equivalence relations on R intersection R^-1

Originally Posted by mathproblems
relation is transitive R then (x,z) (x,y) (y,z)
R^-1 is also transitive (z,x) (y,x) (z,y)
relation is reflexive R then (x,x) (y,y) (z,z)
relation is reflexive R^-1 then (x,x) (y,y) (z,z)
Then R (x,z) (x,y) (y,z) (x,x) (y,y) (z,z)
and R^-1 (z,x) (y,x) (z,y) (x,x) (y,y) (z,z)
How is R intersection R^-1 is an equivalence relation?
relation is transitive R then (x,z) (x,y) (y,z)
R^-1 is also transitive (z,x) (y,x) (z,y)
relation is reflexive R then (z,x) (y,x) (y,z)
relation is reflexive R^-1 then (x,z) (y,x) (y,z)
Then R intersection R^-1 is an equivalence relation
and include {(x,z) (x,y) (y,z) (z,x) (y,x) (y,z)}

5. Re: Equivalence relations on R intersection R^-1

Then R intersection R^-1 is an equivalence relation
and include {(x,z) (x,y) (y,z) (z,x) (y,x) (z,y)}
is this correct?
Thank you!

6. Re: Equivalence relations on R intersection R^-1

Originally Posted by mathproblems
Then R intersection R^-1 is an equivalence relation
and include {(x,z) (x,y) (y,z) (z,x) (y,x) (y,z)}
You can't use a name without first saying what it refers to. If I said that Jim likes Jane, is it true or not? This depends on who I mean by Jim and Jane.

Every variable you use must be introduced, for example, by "for all x," "there exists x," "let x be such that," etc.

7. Re: Equivalence relations on R intersection R^-1

Is this good ?
relation is transitive R then (x,z) (x,y) (y,z)
R^-1 is also transitive (z,x) (y,x) (z,y)
relation is reflexive R then (z,x) (y,x) (z,y)
relation is reflexive R^-1 then (x,z) (y,x) (y,z)

Then R intersection R^-1 is an equivalence relation
and include {(x,z) (x,y) (y,z) (z,x) (y,x) (y,z)}

8. Re: Equivalence relations on R intersection R^-1

Originally Posted by mathproblems
Is this good ?
relation is transitive R then (x,z) (x,y) (y,z)
No, you used x, y and z without introducing them.

Note, for example, the definition of reflexivity: R is reflexive if for all x we have R(x,x).

Also, "(x,z) (x,y) (y,z)" does not make sense. The fact that some x and y are related by a relation R is usually denoted by R(x,y), xRy, or (x, y) ∈ R.

9. Re: Equivalence relations on R intersection R^-1

Let R be transitive (x,y) (y,z) then (x, z).
R^-1 transitive will be opposite as (y,x) (z,y) then (z,x)

and then R is reflexive and transitive: (x,y) (y,z) (x, z) (y,x) (z,y) (z,x).
and R^-1 is reflexive and transitive: (y,x) (z,y) (z,x) (x,y) (y,z) (x,z).
Therefore R intersection R^-1 is also symmetric and R intersection R^-1 is an equivalence relation.

10. Re: Equivalence relations on R intersection R^-1

Originally Posted by tinabaker
Let R be transitive (x,y) (y,z) then (x, z).
R^-1 transitive will be opposite as (y,x) (z,y) then (z,x)
and then R is reflexive and transitive: (x,y) (y,z) (x, z) (y,x) (z,y) (z,x).
and R^-1 is reflexive and transitive: (y,x) (z,y) (z,x) (x,y) (y,z) (x,z).
Therefore R intersection R^-1 is also symmetric and R intersection R^-1 is an equivalence relation.
Suppose that $\mathbf{R}$ is transitive and $(x,y)\in\mathbf{R}^{-1}\text{ and }(y,z)\in\mathbf{R}^{-1}$.
We know that $(y,x)\in\mathbf{R}\text{ and }(z,y)\in\mathbf{R}$
Because $\mathbf{R}$ is transitive we know that $(z,x)\in\mathbf{R}$.
This means that $(x,z)\in\mathbf{R}^{-1}$ which shows that $\mathbf{R}^{-1}$ is transitive.

Now that is a proper proof.

11. Re: Equivalence relations on R intersection R^-1

Originally Posted by tinabaker
Let R be transitive (x,y) (y,z) then (x, z).
R^-1 transitive will be opposite as (y,x) (z,y) then (z,x)
No, since R is transitive, we have that for all x y and z, if R(x, y) and R(y, z), then R(x, z). Just renaming the variables, we get that for all x, y, z, if R(z, y) and R(y, x), then R(z, x). Now, for all x, y and z, $R(z, y)$ iff $R^{-1}(y,z)$, $R(y, x)$ iff $R^{-1}(x, y)$ and $R(z, x)$ iff $R^{-1}(x,z)$. Therefore, the previous statement means that for all x, y, z, if $R^{-1}(x, y)$ and $R^{-1}(y, z)$, then $R^{-1}(x, z)$, i.e., $R^{-1}$ is transitive, as Plato wrote above. This is a lemma that is useful in proving that $R\cap R^{-1}$ is transitive.

Originally Posted by tinabaker
and then R is reflexive and transitive: (x,y) (y,z) (x, z) (y,x) (z,y) (z,x).
This is not clear.

12. Re: Equivalence relations on R intersection R^-1

Let R be reflexive, then we have a relation R on a set X that is reflexive if (x,x) elements of R for every x element of X. So we get (x,x), (y,y) (z,z).
What is reflexive of R^-1? the same as R?

13. Re: Equivalence relations on R intersection R^-1

Originally Posted by mathproblems
Let R be reflexive, then we have a relation R on a set X that is reflexive if (x,x) elements of R for every x element of X.
The blue part is not needed.
Originally Posted by mathproblems
So we get (x,x), (y,y) (z,z).
This is not clear. Why not continue it to (t,t), (u,u), etc? What does (x,x) mean? It's nether true or false, but R(x,x) is true or false. So, R is reflexive means by definition that for every x, R(x,x), or (x,x) ∈ R.
Originally Posted by mathproblems
What is reflexive of R^-1?
I am not sure what you mean by "reflexive of R^-1." The fact is, if R is reflexive, then so it R^-1, which has to be proved, but which is easy. Remember only that the definition of reflexivity starts with "for all x ∈ X, ...", so a proof of such statement must start with "Consider an arbitrary x ∈ X."

14. Re: Equivalence relations on R intersection R^-1

Originally Posted by mathproblems
If $\left( {\forall x} \right)\left[ {(x,x) \in\mathbf{R}} \right]$
then by definition $\left( {\forall x} \right)\left[ {(x,x) \in\mathbf{R}^{-1}} \right]$.