Can I prove this set relation using associativity?

36 Views Asked by At

Suppose I have some set $R \subseteq X \times Y$ and $P \subseteq Y$ for sets $X$ and $Y$. I want to show that $\forall y \in Y$

$$[(\exists x \in X. xRy) \implies y \in P] \iff [\forall x \in X . (xRy \implies y \in P)]$$

To see the difference, they lie in where the brackets are being placed and a change in existence $\exists$ to $\forall$

I'm not entirely sure how to prove this, but intuitively I would argue like so:

$$[(\exists x \in X. xRy) \implies y \in P]$$ $$ \iff [(\exists x \in X. xRy) \land y \in P]$$

$$\iff [\forall x \in X. (xRy \land y \in P)]$$

$$\iff [\forall x \in X . (xRy \implies y \in P)]$$

Since it seems like the change to $\forall$ already refers to those $x \in X$ which already satisfies $xRy$ and leads the $y \in P$.

Is this proof sound? Is there a more rigorous one?

1

There are 1 best solutions below

0
On

To answer your first question: sorry, but your "proof" definitely isn't sound. To see that, we can even ignore the specific content of the problem, because you made a purely logical mistake at the very first step. Let's give names to the following two statements: $$S_1=(\exists x\in X \, . \, xRy) \quad \text{and} \quad S_2=(y \in P).$$ Then your very first step says that $S_1\implies S_2$ is equivalent to $S_1\land S_2$. But implication and conjunction are not equivalent to each other.

An idea for how to prove this equivalence: it may be easier to prove that their negations are equivalent to each other.