# Prove with relational algebra

• Mar 10th 2009, 12: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, 02: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, 08: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, 08: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 \$\displaystyle R\;\&\;S\$ is a reflexive relation on \$\displaystyle A\$.
That means \$\displaystyle \Delta _A \subseteq R\;\& \;\Delta _A \subseteq S\; \Rightarrow \;\Delta _A \subseteq R \cap S\$.
That is the whole proof that \$\displaystyle R \cap S\$ is reflexive.
• Mar 10th 2009, 11:13 AM
thehollow89
Quote:

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

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