$S=\{(X,Y) \in \mathcal{P}(A) \times \mathcal{P}(A) \mid \forall x \in X \exists y \in Y(xRy)\}.$ If R is symmetric, must S be symmetric?

Question

I'm working on an exercise from How To Prove It by Velleman, and I'm having a hard time.

Suppose $R$ is a relation on $A$ and define a relation S on $\mathcal{P}(A)$ as follows: $$S=\{(X,Y) \in \mathcal{P}(A) \times \mathcal{P}(A) \mid \forall x \in X \exists y \in Y(xRy)\}.$$ (b) If $R$ is symmetric, must S be symmetric?

(Parts (a) and (c) ask the same for reflexivity and transitivity, but I'm only having trouble with part (b) at the minute.)

I've tried a few examples and everything I've tried appears to be symmetric, but perhaps I'm not considering the right examples.

I've started by trying to show that if $(X,Y) \in S$ then $(Y,X) \in S$. So suppose $(X,Y) \in S$. We need to show that $(Y,X) \in S$ which means $\forall y \in Y \exists x\in X(yRx)$. So assume $y \in Y$.

I'm having trouble finding some $x \in X$ such that $yRx$. I know if I can find any $x \in X$, I can immediately infer $xRy'$ for some $y' \in Y$ due to $(X,Y) \in S$, and from there can infer $y'Rx$ since $R$ is symmetric. The only problem I see with this is that without showing that $y'=y$, I can't infer $(Y,X) \in S$ because $y'$ is a only a specific element of $Y$. I can't think of any obvious ways of doing this.

I also tried considering cases when $X= \varnothing$, and $X \neq \varnothing$. It seems to me that $X=\varnothing$ makes no sense at all for $S$, because we'll never have any elements of $X$ to consider finding a corresponding value of $y$ such that $xRy$. At least with $X \neq \varnothing$ I would have some $x \in X$ to work with. I think this method suffers from the last method in the same way as before, as we can only consider a specific element $y' \in Y$ where $xRy'$ from the statement $(X,Y) \in S$.

All of this leads me to believe there is some counterexample I am missing. I feel completely lost, any help with this would be greatly appreciated!

Answer 1

Your intuition was good; this need not be true. Here's a sample from a large class of counterexamples: Let $A=\{1,2,3,4\}$ and $R = \{ (1,3), (2,3), ~~ (3,1), (3,2) \}$.

Now $R$ is symmetric, but if $X=\{1,2\}$ and $Y=\{3,4\}$, then $(X,Y)\in S$ but $(Y,X)\notin S$.

Answer 2

Well, for $X=\emptyset$, the condition vacuously holds, because whenever the enemy gives you an $x\in X$ (which can never happen), you 'would be' able to find an $y$.

It means, that, for example for $Y=\{a\}$ for an $a\in A$, we have $(\emptyset,\{a\})\in S$, but $(\{a\},\emptyset)\notin S$.

If you prefer, we can have other counterexamples: let $R={id}_A$. Then we have $(X,Y)\in S\iff X\subseteq Y$.