Suppose R is a relation on A, and S is a relation on P(A) (the power set of A) such that S = {(X,Y) ∈ P(A)×P(A)|(∃x∈X)(∃y∈Y)((x,y)∈R)}.
Thm: If R is transitive, then S is transitive.
Proof: Assume R is transitive. Let (x,y)∈R and (y,z)∈R be arbitrary. Since R is transitive, it follows that (x,z)∈R. Since (x,y),(y,z),(x,z)∈R, it follows that (X,Y),(Y,Z),(X,Z)∈S. Since (x,y),(y,z) were arbitrary, it is true for all such, and therefore we can conclude that S is transitive. □
Where is my reasoning going wrong?
$(X,Y)\in S$ requires that there exists some elements of $X$ and $Y$ that are $R$-related. $$(X,Y)\in S \iff (\exists x\in X\,\exists y_1\in Y: (x,y_1)\in R)$$
$(Y,Z)\in S$ requires that there exists some elements of $Y$ and $Z$ that are $R$-related. $$(Y,Z)\in S \iff (\exists y_2\in Y\,\exists z\in Z: (y_2,z)\in R)$$
It is possible that no single element of $Y$ serves as a common witness for both $S$-relations.
Thus the transitivity of $R$ does not guarantee the transitivity of $S$.
Suppose $X=\{1\}, Y=\{1,2\}, Z=\{2\}, R=\{(1,1),(2,2)\}$ . $R$ is transitive.
$(X,Y)\in S$ since $(1,1)\in R$ and $(Y,Z)\in S$ since $(2,2)\in R$.
However, $(X,Z)\notin S$ since $(1,2)\notin R$.
Thus we have an $R$ that is transitive yet the $S$ defined by it is not.