Proving negation with multiple conditions

Question

Suppose that there is some condition A that is only true iff condition 1 and condition 2 are true. Now suppose that there is some result B and I'm trying to prove A ⇔ B. I can prove A ⇒ B, but to prove B ⇒ A I'm trying to show ¬A ⇒ ¬B. Now the problem is if I assume that condition 1 is false, and can show this implies B is false, is this enough to prove that ¬A ⇒ ¬B? Or do I also need to prove that if condition 2 is false then B is false?

Answer 1

No, you need the second as well. Consider the situation when

• Condition 1 is true
• Condition 2 is false
• B is false

I'm going to call condition 1 $P$ and condition 2 $Q$ for the sake of clarity.

You know the following (101) about $A$ .

$$ A \iff P \land Q \tag{101} $$

This means that (102) is true as well.

$$ (\lnot A) \iff (\lnot P) \lor (\lnot Q) \tag{102} $$ .

You are trying to prove (103) below, the contrapositive of $B \implies A$ .

$$ (\lnot A) \implies (\lnot B) \tag{103} $$

We can subsittute for $\lnot A$ using (102), yielding (104) below.

$$ ((\lnot P) \lor (\lnot Q)) \implies (\lnot B) \tag{104} $$

Let's replace $\implies$ with disjunction and a negated left argument, yielding (105).

$$ (P \land Q) \lor (\lnot B) \tag{105} $$

Based on the passage below, you are proving (106a-b) and asking if that entails (105).

if I assume that condition 1 is false, and can show this implies B is false, is this enough to prove that ¬A ⇒ ¬B?

$$ (\lnot P) \implies (\lnot B) \tag{106a} $$

or equivalently

$$ P \lor (\lnot B) \tag{106b} $$

(106b) does not entail (105) . For instance, if $P$ (condition 1) is true, $Q$ (condition 2) is false, and $B$ is false, then (106b) would be true, but (105) would be false.

However, if you also knew (107a-b), then you could infer (105).

$$ (\lnot Q) \implies \lnot B \tag{107a} $$

$$ Q \lor \lnot B \tag{107b} $$

Answer 2

If you want to show $\neg A \implies \neg B$ you have to show that whenever $A$ fails, $B$ fails also. There are two ways for $A$ to fail: condition $1$ doesn't hold, or condition $2$ doesn't hold. So, yes, you have to deal with both cases.

To put it another way, suppose condition $1$ holds, but condition $2$ doesn't. Your proof has to deal with this case.

Answer 3

Suppose that there is some condition A that is only true iff condition 1 and condition 2 are true.

I can prove A ⇒ B,

So you have proof that $\def\getsto{\leftrightarrow}A\getsto(C\wedge D)$ and $A\to B$.

but to prove B ⇒ A I'm trying to show ¬A ⇒ ¬B. Now the problem is if I assume that condition 1 is false, and can show this implies B is false, is this enough to prove that ¬A ⇒ ¬B?

No.

If $\lnot B$ is derivable from $\lnot C$, then $C$ must be derivable under an assumption of $B$.   However, a derivation of $C$ is insufficient to derive $C\land D$, and hence $A$ cannot be derived under an assumption of $B$ just with the given premise.

Or do I also need to prove that if condition 2 is false then B is false?

Yes. You also need $\lnot B$ to be derivable under an assumption of $\lnot D$.