Prove with relational algebra

• Mar 10th 2009, 01:17 AM
thehollow89
Prove with relational algebra
If R and S are both reflexive, then RS is reflexive, too. I need to prove this with relational algebra or disprove by giving a counterexample. Any help? (Rock)
• Mar 10th 2009, 03:51 AM
Plato
Quote:

Originally Posted by thehollow89
If R and S are both reflexive, then RS is reflexive, too. I need to prove this with relational algebra or disprove by giving a counterexample.

Any reflexive relation on a set contains the diagonal of the cross product of the set with itself. So does it follow that the intersection of two reflective relations must be reflexive?
• Mar 10th 2009, 09:04 AM
thehollow89
Quote:

Originally Posted by Plato
Any reflexive relation on a set contains the diagonal of the cross product of the set with itself. So does it follow that the intersection of two reflective relations must be reflexive?

Oh I know it's reflexive, but how exactly am I supposed to show that? (Rock)
• Mar 10th 2009, 09:37 AM
Plato
Quote:

Originally Posted by thehollow89
Oh I know it's reflexive, but how exactly am I supposed to show that?

Suppose that each of $R\;\&\;S$ is a reflexive relation on $A$.
That means $\Delta _A \subseteq R\;\& \;\Delta _A \subseteq S\; \Rightarrow \;\Delta _A \subseteq R \cap S$.
That is the whole proof that $R \cap S$ is reflexive.
• Mar 10th 2009, 12:13 PM
thehollow89
Quote:

Originally Posted by Plato
Suppose that each of $R\;\&\;S$ is a reflexive relation on $A$.
That means $\Delta _A \subseteq R\;\& \;\Delta _A \subseteq S\; \Rightarrow \;\Delta _A \subseteq R \cap S$.
That is the whole proof that $R \cap S$ is reflexive.

Oh thanks. I really do assume that proofs are harder than they actually are. (Rock)