4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ The statement $\exists x \in \mathcal X'(\neg B(x) \not \Rightarrow x \not \in \mathcal X')$ can be rewritten as $\exists x \in \mathcal X'(\neg B(x) \land A(x))$. Does this help you? $\endgroup$ – Git Gud Sep 29 '16 at 22:02
  • $\begingroup$ @GitGud greatly! Then it holds that $B(x)$ is not true if $A(x)$ is true. $\endgroup$ – Benjamin Lindqvist Sep 29 '16 at 22:07
  • 1
    $\begingroup$ For some $x$, yes. $\endgroup$ – Git Gud Sep 29 '16 at 22:08
  • $\begingroup$ There exists x such that A(x) and not B(x), if A(x) for some x...? $\endgroup$ – Benjamin Lindqvist Sep 29 '16 at 22:12
  • $\begingroup$ No, "for some" is another way of saying "exists". One suffices. $\endgroup$ – Git Gud Sep 29 '16 at 22:19
1
$\begingroup$

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)$$

$\endgroup$
4
$\begingroup$

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)$.

$\endgroup$

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.