$S=\{(X,Y) \in \mathcal{P}(A) \times \mathcal{P}(A) \mid \forall x \in X \exists y \in Y(xRy)\}.$ Si R es simétrica, debe S ser simétrica?

Question

Estoy trabajando en un ejercicio de Cómo demostrarlo por Velleman, y estoy teniendo un momento difícil.

Supongamos $R$ es una relación en $A$ y definir una relación S $\mathcal{P}(A)$ como sigue: $$S=\{(X,Y) \in \mathcal{P}(A) \times \mathcal{P}(A) \mid \forall x \in X \exists y \in Y(xRy)\}.$$ (b) If $R$ es simétrica, debe S ser simétrica?

(Las partes (a) y (c) pedir a la misma para la reflexividad y transitividad, pero yo sólo estoy teniendo problemas con la parte (b) en el minuto).

Yo he probado un par de ejemplos y todo lo que he probado parece ser simétrico, pero tal vez no estoy teniendo en cuenta el derecho de los ejemplos.

He empezado por intentar demostrar que si $(X,Y) \in S$$(Y,X) \in S$. Así que supongamos $(X,Y) \in S$. Tenemos que mostrar que $(Y,X) \in S$, lo que significa $\forall y \in Y \exists x\in X(yRx)$. Así que supongamos $y \in Y$.

Estoy teniendo problemas para encontrar algunos $x \in X$ tal que $yRx$. Sé que si me puede encontrar toda la $x \in X$, de inmediato me puede inferir $xRy'$ algunos $y' \in Y$ debido a $(X,Y) \in S$, y a partir de ahí se puede inferir $y'Rx$ desde $R$ es simétrica. El único problema que veo con esto es que sin mostrar que $y'=y$, yo no puedo inferir $(Y,X) \in S$ porque $y'$ es sólo un elemento específico de $Y$. Yo no puedo pensar en ninguna manera obvia de hacerlo.

También traté de considerar los casos al $X= \varnothing$, e $X \neq \varnothing$. A mí me parece que $X=\varnothing$ no tiene ningún sentido para $S$, porque nunca vamos a tener todos los elementos de la $X$ a considerar la posibilidad de encontrar un correspondiente valor de $y$ tal que $xRy$. Al menos con $X \neq \varnothing$ tendría $x \in X$ a trabajar. Creo que este método sufre desde el último método de la misma manera como antes, solo podemos considerar un elemento específico $y' \in Y$ donde $xRy'$ a partir de la declaración de $(X,Y) \in S$.

Todo esto me lleva a creer que hay algún contraejemplo que me falta. Me siento completamente perdido, cualquier ayuda con esto sería muy apreciada!

Answer 1

Su intuición era buena; esto no tiene que ser verdadero. Aquí una muestra de una gran clase de los contraejemplos: Vamos a $A=\{1,2,3,4\}$$R = \{ (1,3), (2,3), ~~ (3,1), (3,2) \}$.

Ahora $R$ es simétrica, pero si $X=\{1,2\}$$Y=\{3,4\}$, $(X,Y)\in S$ pero $(Y,X)\notin S$.

Answer 2

Así, por $X=\emptyset$, la condición vacuously tiene, porque cada vez que el enemigo te da un $x\in X$ (que nunca puede suceder), usted sería capaz de encontrar una $y$.

Esto significa que, por ejemplo, para $Y=\{a\}$$a\in A$,$(\emptyset,\{a\})\in S$, pero $(\{a\},\emptyset)\notin S$.

Si lo prefiere, podemos tener otros contraejemplos: vamos a $R={id}_A$. Luego tenemos a $(X,Y)\in S\iff X\subseteq Y$.