Lack of implication and logical quantifiers

Question

After some botched attempts at formulating my question correctly, I stopped trying to simplify it and just ask straight out.

Here's the situation. We have a statement that we're trying to prove:

For all $x \in \mathcal X$, $A(x) \Rightarrow B(x)$.

We attempt to do this by contradiction. Define $\mathcal X' := \{x \in \mathcal X: A(x)\}$ and then we're equivalently trying to prove

For all $x \in \mathcal X'$, $B(x)$.

We assume the negation $\exists x \in \mathcal X':\neg B(x)$ and try to come up with a contradiction. Suppose we end up instead showing that

$\exists x \in \mathcal X':\neg B(x) \not \Rightarrow x \not \in \mathcal X'$

In other words, if there exists an $x \in \mathcal X$ such that $A(x)$, then $\neg B(x)$ doesn't imply that $\neg A(x)$. In other other words, we prove that $A(x)$ can not be contradicted by assuming $B(x)$. What does this say about $x$ such that $A(x)$? Can $B(x)$ ever hold if $A(x)$ holds and conversely, can $A(x)$ hold if $B(x)$ holds?

I would guess it simply means $A(x)$ and $B(x)$ are mutually exclusive, but I don't know. The quantifiers make everything kind of complicated.

Answer 1

Looking at your derived statement: $$\exists x \in \mathcal X':\neg B(x) \not \Rightarrow x \not \in \mathcal X'$$ Let's write explicitly the negations in this formula: $$\exists x \in \mathcal X':\neg(\neg B(x) \Rightarrow \neg x \in \mathcal X')$$ Now $\neg B\Rightarrow\neg A$ is equivalent to $A\Rightarrow B$, therefore the statement can be further rewritten as $$\exists x \in \mathcal X':\neg(x \in \mathcal X'\Rightarrow B(x))$$ Also, $\exists x:\neg P(x)$ is equivalent to $\neg\forall x: P(x)$ ("there exists an $x$ for which $P$ does not hold" is the same as "$P$ does not hold for all $x$"). Thus the statement can be further rewritten as $$\neg\forall x \in \mathcal X':x \in \mathcal X'\Rightarrow B(x)$$ Now obviously, for all $x\in\mathcal X'$, we have $x\in\mathcal X'$,therefore we can further simplify this to $$\neg\forall x\in\mathcal X':B(x)$$ But that is a direct contradiction to the assumption $$\forall x\in\mathcal X':B(x)$$

Answer 2

You should not be afraid of quantifiers. Think of them simply as specifying a context. When you say "everyone likes candy", for example, you are restricting to the context where you are given any arbitrary person P, and in that context you claim that P likes candy. Conditional statements are also the same, where it asserts something under some condition (context).

In your example you want to prove:

Given any $x \in X$:

  If $A(x)$:

    $B(x)$.

From the viewpoint of natural deduction, there is actually a unique way to proceed. Before that, read this to make sure you really understand why exactly proof by contradiction is valid.

The proof will be as follows

Given any $x \in X$:

  If $A(x)$:

    ...

    $B(x)$.

Always. You will need to fill in the "..." with a deduction of "$B(x)$" in the context where both $x \in X$ and $A(x)$. If you can do it without using the proof-by-contradiction rule, then we might call it a direct subproof. If not, then the proof will look like:

Given any $x \in X$:

  If $A(x)$:

    If $\neg B(x)$:

      ...

      Contradiction.

    Therefore $B(x)$.

There is no other way necessary. Notice that what you wanted to do in your question is subsumed by this too, because your proof that from $\exists x \in X'\ ( \neg B(x) )$ deduces a contradiction can be inserted right in the "...", since in that context we do have $x \in X$ satisfying $A(x)$ such that $\neg B(x)$.