Relational proof

**thehollow89** · March 12th 2009, 07:27 PM

If R is reflexive and transitive, then R U R^U is an equivalence. I need to prove this using algebraic-relation calculations or disprove by counter example. I'm really not understanding this stuff.

**Plato** · March 13th 2009, 02:42 AM

Originally Posted by thehollow89

If R is reflexive and transitive, then R U R^U is an equivalence. I need to prove this using algebraic-relation calculations or disprove by counter example. I'm really not understanding this stuff.

What is the meaning of $R^U$ ?

**thehollow89** · March 13th 2009, 06:50 AM

R converse I believe.

**Grandad** · March 13th 2009, 11:25 PM

Hello thehollow89

$R^U$ is the converse, or the inverse, of $R$ , means that if the element $(x, y)$ in R, the element $(y,x)$ is in $R^U$ - because that's what the inverse relation is: the relation you get by switching the order of the elements in the relation. (It's usually denoted by $R^{-1}$ , as you might expect).

So, if $R$ is reflexive and transitive, all you'll need to prove in order for $R\cup R^U$ to be an equivalence relation is:

$R^U$ is also reflexive and transitive, and therefore $R \cup R^U$ is reflexive and transitive
$R \cup R^U$ is symmetric; in other words, $(x, y) \in R \cup R^U \Rightarrow (y,x) \in R \cup R^U$

Can you do that, or do you need further help?

Grandad

**thehollow89** · March 14th 2009, 11:43 AM

Originally Posted by Grandad

Hello thehollow89

$R^U$ is the converse, or the inverse, of $R$ , means that if the element $(x, y)$ in R, the element $(y,x)$ is in $R^U$ - because that's what the inverse relation is: the relation you get by switching the order of the elements in the relation. (It's usually denoted by $R^{-1}$ , as you might expect).

So, if $R$ is reflexive and transitive, all you'll need to prove in order for $R\cup R^U$ to be an equivalence relation is:

$R^U$ is also reflexive and transitive, and therefore $R \cup R^U$ is reflexive and transitive
$R \cup R^U$ is symmetric; in other words, $(x, y) \in R \cup R^U \Rightarrow (y,x) \in R \cup R^U$

Can you do that, or do you need further help?

Grandad

I mean I understand the question and what I need to prove, I'm just not sure how I go about proving it. The prof isn't really all that clear. He'll just teach us about the kinds of relations and then ask us to prove something and most kids end up stumped on what method of proof writing he wants...

**Grandad** · March 14th 2009, 03:32 PM

Originally Posted by Grandad

So, if $R$ is reflexive and transitive, all you'll need to prove in order for $R\cup R^U$ to be an equivalence relation is:

$R^U$ is also reflexive and transitive, and therefore $R \cup R^U$ is reflexive and transitive
$R \cup R^U$ is symmetric; in other words, $(x, y) \in R \cup R^U \Rightarrow (y,x) \in R \cup R^U$

First we prove that $R^U$ is reflexive.

Assume that $R$ and $R^U$ are defined on the set $S$ .

Then $R^U$ is reflexive $\iff (x, x) \in R^U, \forall x \in S$ .

Now $(x, y) \in R^U \Rightarrow (y, x) \in R$ . Therefore $(x, x) \in R^U, \forall x\in S$ , since $(x,x) \in R$ , because $R$ is reflexive.

$\Rightarrow R^U$ is reflexive.

Next, we prove that $R^U$ is transitive.

$R^U$ is transitive $\iff ((x,y) \in R^U \wedge (y,z) \in R^U) \Rightarrow (x,z) \in R^U$

Now $(x,y) \in R^U \Rightarrow (y,x) \in R$ , and $(y,z) \in R^U \Rightarrow (z,y) \in R$

$\Rightarrow (z, x) \in R$ , since $R$ is transitive

$\Rightarrow (x, z) \in R^U$

$\Rightarrow R^U$ is transitive

Finally, we prove that $R \cup R^U$ is symmetric.

$(x,y) \in R \cup R^U \Rightarrow (x,y) \in R$ or $(x,y) \in R^U$

Now if $(x,y) \in R$ , then $(y,x) \in R^U$ , and if $(x,y) \in R^U$ , then $(y,x) \in R$ .

Either way, $(x,y) \in R\cup R^U \Rightarrow (y,x) \in R\cup R^U$

So $R\cup R^U$ is symmetric.

Finally, then, $R$ and $R^U$ are both reflexive and transitive, and $R\cup R^U$ is symmetric. So $R\cup R^U$ is an equivalence relation.

Grandad

**thehollow89** · March 14th 2009, 04:59 PM

Originally Posted by Grandad

First we prove that $R^U$ is reflexive.

Assume that $R$ and $R^U$ are defined on the set $S$ .

Then $R^U$ is reflexive $\iff (x, x) \in R^U, \forall x \in S$ .

Now $(x, y) \in R^U \Rightarrow (y, x) \in R$ . Therefore $(x, x) \in R^U, \forall x\in S$ , since $(x,x) \in R$ , because $R$ is reflexive.

$\Rightarrow R^U$ is reflexive.

Next, we prove that $R^U$ is transitive.

$R^U$ is transitive $\iff ((x,y) \in R^U \wedge (y,z) \in R^U) \Rightarrow (x,z) \in R^U$

Now $(x,y) \in R^U \Rightarrow (y,x) \in R$ , and $(y,z) \in R^U \Rightarrow (z,y) \in R$

$\Rightarrow (z, x) \in R$ , since $R$ is transitive

$\Rightarrow (x, z) \in R^U$

$\Rightarrow R^U$ is transitive

Finally, we prove that $R \cup R^U$ is symmetric.

$(x,y) \in R \cup R^U \Rightarrow (x,y) \in R$ or $(x,y) \in R^U$

Now if $(x,y) \in R$ , then $(y,x) \in R^U$ , and if $(x,y) \in R^U$ , then $(y,x) \in R$ .

Either way, $(x,y) \in R\cup R^U \Rightarrow (y,x) \in R\cup R^U$

So $R\cup R^U$ is symmetric.

Finally, then, $R$ and $R^U$ are both reflexive and transitive, and $R\cup R^U$ is symmetric. So $R\cup R^U$ is an equivalence relation.

Grandad

So basically for these proofs I use implication to show that if R has a certain property, these other things hold? I don't get proofs, sometimes it seems like they're just making statements rather than prove in the sense of what I think proving means.

**Plato** · March 16th 2009, 12:38 PM

The is a counter example to the statement in this problem.
Please see: http://www.mathhelpforum.com/math-he...roof-help.html

Thread: Relational proof

LinkBack

Thread Tools

Display

Relational proof

Equivalence Relation

Equivalence Relation

Similar Math Help Forum Discussions

relational expression, zermelo definition, proper divisor...

relational algebra

Prove with relational algebra

(Discrete Mathmatics) Defining a relational set

Relational Composition Problem - Please help!

Search Tags