4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you for your useful comment and edits. Unfortunately, I am having a hard time seeing why $(1)$ is not equivalent to $(2)$ and $(3)$. Do you mean that $(2)$ and $(3)$ should respectively be re-written as “$(\exists y\in Y:y\in B,y\notin C)\Rightarrow (x\notin A)$” and “$(\exists y\in Y:y\notin B)\Rightarrow (x\notin A)$”? Any help in correctly re-writing $(2)$ and $(3)$ will be much appreciated. P.S: I can use any method I want; but I thought that given the nature of my statement, contraposition was the best. $\endgroup$
    – EoDmnFOr3q
    Commented Jan 10, 2022 at 9:55
  • 1
    $\begingroup$ I edited the question. $\endgroup$
    – EoDmnFOr3q
    Commented Jan 10, 2022 at 10:39

2 Answers 2

1
$\begingroup$

$$(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).$
$\endgroup$
0
1
$\begingroup$

Let $\overline{B}$ be the complement of $B$ in $Y$, and a similar definition for $\overline{C}$. Then the statements \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} are equivalent to \begin{gather} \forall y\in Y,((y\in \overline{C})\Rightarrow(x\notin A))\tag2\\ \forall y\in Y,((y\in \overline{B})\Rightarrow(x\notin A))\tag3 \end{gather} which can be combined into \begin{gather} \forall y\in Y,\left(\left[y\in \left( \overline{B} \cup \overline{C}\right)\right]\Rightarrow(x\notin A)\right).\tag{2 and 3}\\ \end{gather} and De Morgan's law gives \begin{gather} \forall y\in Y,\left(\left[y\notin {\left( B \cap C\right)}\right]\Rightarrow(x\notin A)\right)\tag{2 and 3}\\ \end{gather}

From statement (1), we can apply the rule that $\lnot\exists$ is equivalent to $\forall\lnot$: \begin{gather} \left[\forall y\in Y, y\notin (B\cap C)\right]\Rightarrow(x\notin A).\tag1 \end{gather}

Compare the last two statements, which are versions of (1) and (2 and 3). Note that they are similar but not the same, because the parentheses are in different places. Statement (1) says "if $B$ and $C$ are disjoint, then $x\notin A$". Statement (2 and 3) says "for all $y$, if $y$ is outside the intersection of $B$ and $C$, then $x\notin A$".

Therefore, (1) is not equivalent to (2 and 3). The following is a counterexample: $$x=1,\qquad A=\{1\}, \qquad B=\{1,2\}, \qquad C=\{2,3\}$$ With these values,

  • your original statement evaluates to $\textrm{true} \Rightarrow \textrm{true}$, which is true
  • statement (1) evaluates to $\textrm{false} \Rightarrow \textrm{false}$, which is true
  • statement (2 and 3) is false, because for $y=3$, we get $\textrm{true} \Rightarrow \textrm{false}$, which is false
  • statement (2) is true for $y=3$
  • statement (3) is false for $y=3$.
$\endgroup$
3
  • $\begingroup$ Thank you for your answer. If I am understanding it right, I should re-write $(1)$ and $(2)$ in my original question to be $(\forall y\in Y,y\notin B)\Rightarrow(x\notin A)$ and $(\forall y\in Y,y\notin C)\Rightarrow(x\notin A)$. Correct? $\endgroup$
    – EoDmnFOr3q
    Commented Jan 10, 2022 at 12:12
  • 1
    $\begingroup$ @Héctor unfortunately, that does not seem to work, because your new (2) and (3) mean $(B=\emptyset) \Rightarrow (x\notin A)$ and $(C=\emptyset) \Rightarrow (x\notin A)$, which is not the same as (1). I think, however, that your original (2 and 3) imply (1), but not the other way round: (1) does not imply (2 and 3). $\endgroup$
    – wimi
    Commented Jan 10, 2022 at 13:48
  • $\begingroup$ Thank you for your comment. Unfortunately, I am a bit lost right now… I can’t figure out whether showing $(2)$ and $(3)$ in my original question implies that I have shown $(1)$. Some clarification would be appreciated. $\endgroup$
    – EoDmnFOr3q
    Commented Jan 10, 2022 at 13:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .