Prove that if $R$ is reflexive so is $S$, given the following following relations

271 Views Asked by At

Suppose $R$ is a relation on $A$, and define $S$ on $\mathcal{P}(A)$

$S=\left\{ (X,Y)\in \mathcal{P}(A)\times \mathcal{P}(A)\vert \forall x \in X\exists y \in Y(xRy) \right\}$

The following is what I have

Suppose $R$ is symmetric, Let $X$ be an arbitrary element in $\mathcal{P}(A)$. We have to prove that $(X,X) \in S$. Let $x$ be an arbitrary element in $X$. From $x \in X$ and $X \in \mathcal{P}(A)$, it follows that $x \in A$. Since $R$ is symmetric the $(x,x) \in R$ and since $x$ is arbitrary it follows that $\forall x \in X(x,y) \in R$ . By applying universal and existential instantiation $\forall x \in X \exists y \in X(x,y) \in R$ therefore $S$ is reflexive.

Not quite sure if this is an adequate proof, my professor mentioned to me that I need to take into consideration what if $X$ is the empty set, it made sense when he told me that but know I am struggling to understand what he meant.

1

There are 1 best solutions below

0
On

"Suppose $R$ is reflexive, then..." the rest of your proof will at least hold for non-empty $X$.

But the empty set is also a subset of $A$, so you'll need to verify whether it works for that too.

So for any $x$ in the empty set, does there exist a $y$ also in the emptyset, such that $x\operatorname Ry~$?

$$\forall x\in \emptyset ~\exists y\in\emptyset~(x\operatorname R y)\quad\text{(true/false)}$$

Think carefully on this.