Working on the book: Daniel J. Velleman. "HOW TO PROVE IT: A Structured Approach, Second Edition" (p. 201)
∗20. Suppose $R$ is a relation on $A$. Let $B = \{X \in P (A) \colon X\neq\emptyset \}$, and define a relation $S$ on $B$ as follows: $S = \{(X,Y) \in B \times B \colon \forall x \in X, \forall y \in Y(xRy)\}$.
Prove that if $R$ is transitive, then so is $S$. Why did the empty set have to be excluded from the set $B$ to make this proof work?
I am trying to find a counterexample to justify the exclusion of the empty set from this proof. So, I define:
- $R = \{(1,2), (2,1), (1,1), (2,2)\}$
- $A = \{1,2\}$
- $B = \{X \in P (A)\} = \{\emptyset, \{1\}, \{2\}, \{1,2\}\}$
Can I find a suitable counterexample with these sets? Why does $S$ lose transitivity property if the empty set is not excluded ?
The problem is that if $X=\varnothing$, then $\forall x\in X\,\forall y\in Y\,(xRy)$ is vacuously true for every $Y\subseteq A$. What could make it false? There would have to be some $x\in X$ and some $y\in Y$ such that $x\not Ry$. But if $X=\varnothing$, there isn’t any $x\in X$ at all, so it’s impossible for such a pair of $x$ and $y$ to exist.
Now take $X$ and $Y$ to be two subsets of $A$ such that $X\not S Y$. Then $XS\varnothing$ and $\varnothing SY$, but $X\not SY$, so $S$ is not transitive. Your example won’t work, because all subsets of your $A$ are related by $S$, but it could be changed easily enough; try $R=\{\langle 1,1\rangle,\langle 1,2\rangle,\langle 2,2\rangle\}$, the $\le$ relation on $A$, and $X=\{2\}$. (I’ll let you find a $Y$ such that $X\not SY$.)