Difficutly recognising flaw in putative theorem

Question

I'm trying to answer a textbook question from page 188 of How To Prove It, second edition by Daniel J. Velleman, but I can't figure it out.

19. Consider the following putative theorem.

Theorem? Suppose $R$ is a relation on $A$, and define a relation $S$ on $\mathscr{P}(A)$ as follows:

$$ S = \lbrace (X,Y) \in \mathscr{P}(A) \times \mathscr{P}(A) : \exists x \in X \, \exists y \in Y (xRy) \rbrace$$

If $R$ is transitive, then so is $S$.

19. a) What's wrong with the proof for this theorem?

Proof: Suppose $R$ is transitive. Suppose $(X,Y) \in S$ and $(Y,Z) \in S$. Then by definition of $S$, $xRy$ and $yRz$, where $x \in X$, $y \in Y$, and $z \in Z$. Since $xRy$, $yRz$, and $R$ is transitive, $xRz$. But then since $x \in X$ and $z \in Z$, it follows from the definition of $S$ that $(X,Z) \in S$. Thus, $S$ is transitive. Q.E.D.

19. b) Is the theorem correct? Justify your answer with either a proof or a counterexample.

Any ideas?

Answer 1

a) From the definition of $S$, we can only conclude $xRy_1$ and $y_2Rz$, where $x \in X, y_1, y_2 \in Y, z \in Z$. Note that we do not neccessarily have $y_1=y_2$, so we are unable to conclude that $xRz$.

b) False. Counterexample: Consider $\mathbb{N}$ with $xRy \iff x \equiv y \pmod{2}$. Let $X=\{1\},Y=\{2,3\}, Z=\{4\}$. As $1R3$ and $2R4$, $(X,Y),(Y,Z) \in S$. Clearly we also have $(X,Z) \notin S$ as $1R4$ does not hold.

Answer 2

Let's start with a counterexample!

Thinking about the $R$-to-$S$ transition, the point that seems slippery is that the witness could change: that is, the $y_1\in Y$ to which is related some $x\in X$ might not be the same $y_2\in Y$ which is related to some $z\in Z$. (Pictorially, viewing $X$, $Y$, and $Z$ as "blobs," maybe there is a line from a point in $X$ to a point in $Y$ and a line from a point in $Y$ to a point in $Z$ but the lines don't meet up.) If this happens, it's not obvious that we can "connect" $X$ to $Z$.

Along these lines we quickly get a counterexample:

• Take $R$ to just be $=$.

• Let $X=\{1\}, Y=\{1,2\}, Z=\{2\}$.

---

And this is precisely the error in the "proof" - that we can't use the same $y$ for both "lines."