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)!