Proofs by contradiction, if P then Q, what if Q is equivalent to A and B?

Question

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

Answer 1

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.

Answer 2

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.

Answer 3

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.