1
$\begingroup$

Say we have a proposition If P then Q, and let Q = A $\land$ B

If we do a proof by contradiction, we assume the negation of Q: $\lnot (A \land B) = \lnot A \lor \lnot B$

From here, can we continue our contradiction proof by starting with only $\lnot A$ or $\lnot B$? Or do we have to look at them both?

My intuition tells me we have to look at both, and on that line of thinking, can we say $P \Rightarrow A \land B$ is equivalent to $P \Rightarrow A \land P \Rightarrow B$, and therefore we have to look at both negations?

But the statement $\lnot A \lor \lnot B$ makes me think we need only look at one...

Sorry this is basic, I am just getting back into math...

$\endgroup$
2
  • $\begingroup$ Well if you assume $\lnot A$ and get a contradiction you are not done as it's perfectly possible for $A$ to be true (so long as $B$ is false). So you have to prove that $\lnot B$ also gives a contradiction. (In other words the only thing that won't give a contradiction is $A$ and $B$ both being true). $\endgroup$
    – fleablood
    Apr 20, 2020 at 15:31
  • $\begingroup$ You may prove $(\neg A\vee\neg B)\to\neg P$ using a Proof by Cases. Assume $\neg A$ and derive $\neg P$, and assume $\neg B$ and derive $\neg P$ also.$$(\neg A\to\neg P)\wedge(\neg B\to\neg P)~~\iff~~(\neg A\vee\neg B)\to\neg P\\(P\to A)\wedge(P\to B)~~\iff~~P\to(A\wedge B)$$ $\endgroup$ Apr 21, 2020 at 0:36

3 Answers 3

1
$\begingroup$

To do a contrapositive proof of $P \implies (A\land B)$ you must prove $(\lnot A \lor \lnot B) \implies \lnot P$ or in other words and assuming $(\lnot A\lor \lnot B)$ causes a contradiction to $P$.

In essence $\lnot A \lor \lnot B$ is still a simple $M \lor N$ statements with $M = \lnot A$ and $N =\lnot B$. It doesn't matter if the components are negations or postive, they are are still components. You are still trying to prove: $something$ or $somethingelse$ implies $a third thing$.

And remember how to do an OR prove.

$M \lor N \implies W$.

You must show, separately, that $M \implies W$. (If $M$ is true but $W$ is not, then $M\lor N$ is true but $W$ is not so $M\lor N\implies W$ is not true.)

But that alone is not enough. We could have $M$ but false but $M\lor N$ is true if $N$ is true and then we must have $W$ true but we didn't do anything about that case when we only considered $M$ being true.

So we must consider $M$ being true implies $W$ is true. As well as showing $N$ being true implies $W$ is true.

But they don't have to both be true always at the same time. We can have $M$ is false but $N$ true (and still $W$) or $M$ is true but $N$ is falswe (and still $W$).

.....

ANd that's an OR proof in general. Even if $M = \lnot A$ and $N =\lnot B$ and $W = \lnot P$ it's still the same.

$\endgroup$
0
$\begingroup$

You need to show that $\neg A \lor \neg B$ implies a contradiction. So, showing that $\neg A$ by itself implies a contradiction is not enough, since $\neg A$ is not implied by $\neg A \lor \neg B$.

So, you need to show that each of $\neg A$ and $\neg B$ lead to a contradiction.

Then you would have $\neg A \to \bot$ as well as $\neg B \to \bot$, which means that you have $(\neg A \to \bot) \land (\neg B \to \bot)$, which is equivalent to $(\neg A \lor \neg B) \to \bot$, which is what you need to show.

This makes sense from the following perspective as well: Typically, with a goal like $A \land B$, you would show two things: that $A$ is implied by premise $P$, and that $B$ is also implied by premise $P$. Now, to show that $A$ is implied by $P$, you can do a proof by contradiction: show that $\neg A$ leads to a contradiction. But clearly you then still need to prove $B$ as well ... and for that you could do its own proof by contradiction. So again, you need both.

Let me also point out that approaching the problem from the latter perspective (proving $A$ and $B$ separately) is really just the best way to approach this, because you may find that, for example, proving $A$ might work well using a proof by contradiction, but for proving $B$, a direct approach might work a lot better. So, this way you keep your options open. But if you assume the negation of the conclusion $Q$, you basically lock yourself into doing a proof by contradiction for both.

$\endgroup$
3
  • $\begingroup$ Thanks! Your breakdown of the statements on the third line definitely helps. $\endgroup$
    – luh2e54
    Apr 20, 2020 at 15:28
  • 1
    $\begingroup$ I thing the phrase "both $\lnot A$ and $\lnot B$ lead to a contradiction" leads to confusion for students. The student may interpret it as [$\lnot A$ and $\lnot B$] must both be true at the same time to lead to a contradiction; whereas what you actually mean is that each $\lnot A$ and $\lnot B$ will each lead to contradictions-- (i.e. it's not enough that one does and the other doesn't; or that the both together do; -- it must be that each one by itself does, and the other one, by itself does.) $\endgroup$
    – fleablood
    Apr 20, 2020 at 15:37
  • $\begingroup$ @fleablood Good suggestion, thanks! $\endgroup$
    – Bram28
    Apr 20, 2020 at 15:54
0
$\begingroup$

You may prove $(\neg A\vee\neg B)\to\neg P$ using a Proof by Cases. Assume $\neg A$ and derive $\neg P$, and assume $\neg B$ and derive $\neg P$ also.$$(\neg A\to\neg P)\wedge(\neg B\to\neg P)~~\iff~~(\neg A\vee\neg B)\to\neg P\\~\\(P\to A)\wedge(P\to B)~~\iff~~P\to(A\wedge B)$$

But the statement $¬A∨¬B$ makes me think we need only look at one...

You wish to show that having at least one from not-$A$ or not-$B$ is sufficient to have not-$P$.

If you do prove that having not-$A$ alone is sufficient, that does not prove that having not-$B$ alone is also sufficient.

You have to prove having each alone will suffice before you can say that having at least one will suffice.

$\endgroup$

You must log in to answer this question.

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