Is the approach to showing $(x\in A)\Rightarrow(\exists y\in B\cap C)$ correct

elementary-set-theorylogicproof-writingpropositional-calculussolution-verification

I wish to prove the converse of the statement in my previous question:

Let $X$ and $Y$ be arbitrary sets. Further, let $A$ be a subset of $X,$ and let $B,C$ be subsets of $Y.$ I am currently trying to prove a statement of the form
\begin{gather}
(x\in A)\Rightarrow(\exists y\in B\cap C).
\end{gather}
My approach is to prove the (equivalent) contrapositive statement
\begin{gather}
(\nexists y\in B\cap C)\Rightarrow(x\notin A).\tag1
\end{gather}
In order to show this last statement, I show two things:
\begin{gather}
\forall y\in Y,((y\notin C)\Rightarrow(x\notin A))\tag2\\
\forall y\in Y,((y\notin B)\Rightarrow(x\notin A))\tag3
\end{gather}

Unfortunately, I’m not sure whether my approach to the problem is legit.

Best Answer

$$(x\in A)\Rightarrow(\exists y\in B\cap C).\tag1$$

Grammatical correction (duplicating the $y):$ $$x\in A\Rightarrow\exists y\;y\in B\cap C.$$

These are all equivalent to $(1):$ \begin{gather} \exists y\;\big(x\in A\Rightarrow y\in B\cap C\big)\\\exists y\;\big(x\not\in A\lor y\in B\cap C\big)\\\exists y\;\big(x\not\in A\lor (y\in B\land y\in C)\big).\tag#\end{gather}

My approach is to prove the (equivalent) contrapositive statement \begin{gather} (\nexists y\in B\cap C)\Rightarrow(x\notin A).\end{gather}

Grammatical correction (the parentheses here are only for disambiguation though): $$\big(\nexists y\;y\in B\cap C\big)\Rightarrow x\notin A.\tag1$$

Note that this is equivalent to (here, the parentheses are required) $$\exists y \;\big(y\not\in B\cap C\Rightarrow x\notin A\big).$$

All the above formulae are equivalent to one another; taking contrapositive doesn't appear to offer any advantage.

In order to show this last statement, I show two things: \begin{gather} \forall y\in Y,((y\notin C)\Rightarrow(x\notin A))\tag2\\ \forall y\in Y,((y\notin B)\Rightarrow(x\notin A))\tag3 \end{gather}

\begin{gather} \exists y{\in}Y\;\big(y\notin C\Rightarrow x\notin A\big)\tag4\\ \exists y{\in}Y\;\big(y\notin B\Rightarrow x\notin A\big)\tag5 \end{gather}

Ignoring all quantifiers: $$\big(y\not\in B\cap C\Rightarrow x\notin A\big)$$ and $$\big(y\notin B\Rightarrow x\notin A\big)\land\big(y\notin C\Rightarrow x\notin A\big)$$ are indeed equivalent. However, with quantifiers, things get more complicated:

  • $\left[(2)\land(3)\right]$ implies $(1)$
  • $(1)$ does not imply $\left[(2)\land(3)\right]$
  • $(1)$ implies $\left[(4)\land(5)\right]$
  • $\left[(4)\land(5)\right]$ does not imply $(1)$
  • $(\#)$ is equivalent to $(1).$
Related Question