1
$\begingroup$

Suppose R is a relation on A, and define a relation S on P(A) as follows:

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

If R is symmetric, must S be symmetric? Prove or provide a counterexample.

A counterexample provided is as follows:

$A=\{ 0,1,2\}$

$R=\{(0,1),(1,0)\}$

$P(A)=\{ \{0\},\{1\},\{1,2\},...\}$

$X=\{0\}$

$Y=\{1,2\}$

$(\{0\},\{1,2\}\in S$ because $(0,1)\in R$

$(\{1,2\},\{0\})\notin S$ because $(2,0)\notin R$

I am confused about two thing:

  1. What exactly should the conclusion we are supposed to show be? Is it $\forall y\in Y \exists x\in X (yRx)$? Or $\forall x\in X \exists y\in Y (yRx)$? And why? If it's the former, then indeed it seems that the proof does not work; but if it's the latter, I have actually worked out a proof, but what's wrong with it?

My proof is as follows.

Suppose R is symmetric, we need to assume $\forall x\in X \exists y\in Y (xRy)$ and prove $\forall x\in X \exists y\in Y (yRx)$. From the assumption we get $xRz$. But since R is symmetric, we can use it to derive $zRx$ from $xRz$. Then we can existential generalise $zRx$ to get $\exists y\in Y (yRx)$. Since $x$ is arbitrary, this completes the universal proof.

  1. What does the definition of S, $\forall x\in X \exists y\in Y (xRy)$ mean? Specifically, I am not sure what the $\exists$ means - I am having trouble understanding the last statement of the counterexample. (In fact I think my confusion is in part to blame for my 1st question for not knowing what the conclusion should be.)

Could anyone please help? (I understand that someone has always asked questions on exactly the same proof, but his concern seems to be different from mine)

$\endgroup$
  • 1
    $\begingroup$ An arguably simpler counterexample: Let $R$ be the identity relation (which is clearly symmetric); then $S$ is the subset relation on $\mathcal P(A)$, which we know well is not symmetric. $\endgroup$ – Henning Makholm Oct 15 '16 at 15:20
2
$\begingroup$

What's wrong with your proof is that you have unfolded the definition of $S$ wrong at a crucial step along the way. You want to prove

  1. For all $X$ and $Y$, if $X\mathrel S Y$ then $Y\mathrel S X$.

which unfolds to

  1. For all $X$ and $Y$, if $\forall x\in X\,\exists y\in Y\,(x \mathrel R y)$, then $\forall x\in Y\,\exists y\in X\,(x \mathrel R y)$.

but what you're actually proving is

  1. For all $X$ and $Y$, if $\forall x\in X\,\exists y\in Y\,(x \mathrel R y)$, then $\forall x\in X\,\exists y\in Y\,(y \mathrel R x)$.

The unfolding of $Y\mathrel S X$ is wrong here. When you unfold $Y\mathrel S X$ the universally quantified variable must be picked from $Y$, because that is what is to the left of the $S$.

(3) is actually true and your proof of it seems to be correct, if a bit terse. But it's not what you need to prove here.

To see that $Y\mathrel S X$ means $\forall y\in Y\,\exists x\in X(y\mathrel R x)$, it may be easier to do the renamings in two steps:

$X\mathrel S Y$ means $\forall x\in X\,\exists y\in Y\,(x \mathrel R y)$.

Since the $X$ and $Y$ in this definition are different from the $X$ and $Y$ in $Y\mathrel S X$, let's first temporarily rename the ones in the definition to $P$ and $Q$ -- $X$ becomes $P$ and $Y$ becomes $Q$:

$P\mathrel S Q$ means $\forall x\in P\,\exists y\in Q\,(x \mathrel R y)$.

Now we can plug in $Y$ for $P$ and $X$ for $Q$ to get the definition as it applies to $Y\mathrel S X$:

$Y\mathrel S X$ means $\forall x\in Y\,\exists y\in X\,(x \mathrel R y)$.

Finally, just for tidiness we can switch the names of the dummy variables $x$ and $y$ (this changes nothing) to produce

$Y\mathrel S X$ means $\forall y\in Y\,\exists x\in X\,(y \mathrel R x)$.

All of this has nothing in particular to do with the meaning of $\exists$ -- it's just a matter of substituting variable names in the expression.


For the last statement in the counterexample: In the penultimate line we have seen that $\{0\}\mathrel S\{1,2\}$. If $S$ were symmetric, we must therefore also have $\{1,2\}\mathrel S \{0\}$, and what this means is $$ \forall x\in\{1,2\}\,\exists y\in\{0\},(x\mathrel R y) $$ The example then implicitly argues: If this is true, then it must be true both for $x=1$ and $x=2$. But it is not true for $x=2$, because $$ \exists y\in\{0\}\,(2\mathrel R y)$$ is false. The only value we can choose for $y$ is $0$ and that does not make $(2\mathrel R y)$ true, because $(2,0)\notin R$.

$\endgroup$
  • $\begingroup$ Thank you so much! Your explanation is incredibly clear! $\endgroup$ – Daniel Mak Oct 17 '16 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.