Sets - Relations - proof involving transitivity

[eclayj]

I'm having trouble with the following:

Let R be a relation on A. Prove that if Dom(R) $\bigcap$ Range(R) = ø, then R is transitive.

I took the negation of the "R is transitive" to try proof by contrapositive (as the professor suggested), and have the following:

$\exists$ x,y,z $\in$ A s.t. (x,y) $\in$ R $\wedge$ (y,z)$\in$ R $\wedge$ (x,z) $\notin$ R.

Now I am stuck

 

[noowutah]

You are done. $$y\in{}\mbox{Dom}(R)\cap\mbox{Range}(R)$$

 

[economicsnerd]

To elaborate...
- If $xRy$, then $y\in\text{Range}(R)$.
- If $yRz$, then $y\in\text{Dom}(R)$.
- Therefore, if $xRyRz$, then $y\in\text{Dom}(R)\cap \text{Range}(R)$.

So you can argue as follows:
- $\nexists y$ with $y\in\text{Dom}(R)\cap \text{Range}(R)$.
- Therefore, $\nexists x,y,z$ with $y\in\text{Dom}(R)\cap \text{Range}(R)$.
- Therefore, $\nexists x,y,z$ with $xRyRz$.
- Therefore, $\nexists x,y,z$ with $xRyRz$ and $(x,z)\notin R$.
- Therefore, $R$ is transitive.

 

[eclayj]

So if I understand it right, I have the following:

Let R be a relation on A. Prove that if Dom(R) ⋂ Range(R) = ø, then R is transitive.

Taking the negation of the "R is transitive" to try proof by contrapositive gives the following:

1.) ∃ x,y,z ∈ A s.t. (x,y) ∈ R ∧ (y,z)∈ R ∧ (x,z) ∉ R (statement one is from $\neg$(R is transitive))
2.) Then (x,y) ∈ R (from statement 1)
3.) Then y ∈ Range(R) (from definition range)
4.) Then (y,z) ∈ R (from statement 1)
5.) Then y ∈ Dom(R) (from definition domain)
6.) Then y ∈ Dom(R) ⋂ Range(R) (from 3 and 5)
7.) Therefore $\neg$( Dom(R) ⋂ Range(R) = ø ) (from 6)

 

[PeroK]

I'm having trouble with the following:

Let R be a relation on A. Prove that if Dom(R) $\bigcap$ Range(R) = ø, then R is transitive.

I'd suggest an alternative approach. The statement itself is fairly non-sensensical, so why is it true? The answer is that R is vacuously transitive:

If dom(R) and range(R) have no elements in common, then you cannot have xRy and yRz. So, vacuously, for any such x, y, z anything is true, including xRz.

 

[economicsnerd]

... so why is it true? The answer is that R is vacuously transitive:

If dom(R) and range(R) have no elements in common, then you cannot have xRy and yRz. So, vacuously, for any such x, y, z anything is true, including xRz.

I think the solution I gave was a proof based on that exact idea.

I agree that there's no need to go by contradiction here.

 

[PeroK]

Yes, and I think it's useful and important to recognise when something is vacuously true, as you may get apparent absurdities that are true in this case. E.g.

If Dom(R) intersect Ran(R) = ø, then xRy and yRz => anything you like (e.g. x is a tree-frog)!