Recently I found this problem, which made me realize I have some problems with relations that are vacuously transitive.
Problem:
Assume that $R$ is a relation on $A$ and define the relation $S$ as
$$ S : = \{ (X, Y) \in \wp(A) \times\wp(A) : \exists x \in X, \exists y \in Y ((x,y) \in R) \}.$$
Statement: If $R$ is transitive, then $S$ is transitive.
Is the statement true or false?
Solution:
I think that the statement is false, and working on a counterexample, I came up with the following relations, where the first picture represents the relation $R$,
while the second picture represents the relation $S$.
This should be a counterexample, because $R$ is transitive, while $S$ fails to be transitive. Indeed, the $(X,Z)$ fails to be in $S$, because $(x,z) \notin S$, while $(X,Y) \in S$ and $(Y,Z) \in S$, with $(x,y) \in R$ and $(x,y^\prime) \in R$.
QUESTION:
Is my line of reasoning sound?
More specifically, is $R$ transitive?
To me, $R$ looks transitive, but only vacuously, because it fails to have $(x,y)$ and $(y,z)$, thus the antecedent of the material implication is false, that makes the implication automatically true.
Am I right?
Any feedback will be greatly appreciated.
Thanks a lot!
I think you meant "..., with $(x,y)\in R$ and $(y',z)\in R$." but with that correction your reasoning seems fine to me. We have both that $R$ is vacuously transitive (because there are no elements $\alpha$ such that $(\alpha,\cdot)$ and $(\cdot,\alpha)$ are in $R$) and that $S$ is not transitive for the reason you gave.