5
$\begingroup$

Suppose you need to prove that $A\iff (B\implies C)$.

The two ways to prove this are:


(1a): Suppose $A$ and $B$ are true. Prove that $C$ is true.

(1b): Suppose $B$ and $C$ are true. Prove that $A$ is true.


(2a): Suppose $A$ and $B$ are true. Prove that $C$ is true.

(2B): Suppose $A$ is not true and B is true, prove that $C$ cannot be true.


Are these ways correct? I always get confused what you can assume and what you have to prove when there's multiple implications and such in one statement.

$\endgroup$

3 Answers 3

5
$\begingroup$

Prove both directions:

Forward: assume A, prove ($B \implies $C). This means "suppose A and B are true. Prove that C is true".

Reverse: Assume ($B \implies $C), prove A. So, you don't "Suppose B and C are true. Prove that A is true". Instead, "suppose the truth of B implies truth of C, then prove that A is true. $1b$ is incorrect. Now, reverse can also be interpreted as suppose A is not true, prove ($B \implies $C) is not true by the contrapostive. Which means prove $B$ is true and $C$ is false. So you don't "Suppose A is not true and B is true, prove that C cannot be true." Instead, "Suppose A is not true, prove B is true and prove that C cannot be true." $2b$ is incorrect.

$\endgroup$
6
  • $\begingroup$ I understand both corrections, the second one was a small difference which I understand. The first one I did on purpose; I know strictly speaking you must assume that ''If B, then C'', but when proving this is not a particularly useful mechanism. If you suppose B implies the truth of C, how do you use this when proving? $\endgroup$
    – Marc
    Mar 8, 2018 at 20:43
  • $\begingroup$ @Marc B is either true or not true. So if you want to use "if B, then C", to prove something, you'll need to prove that thing, when either B is false, or when B and C are both true. The assumption is useful in the sense that when B is true, C must also be true. $\endgroup$
    – Jesse Meng
    Mar 8, 2018 at 20:51
  • 1
    $\begingroup$ So in a sense, you can either assume both B and C are true, and prove A, or assume B is false and prove A. Or am I not getting correctly what you're trying to say? $\endgroup$
    – Marc
    Mar 8, 2018 at 20:57
  • $\begingroup$ that is correct $\endgroup$
    – Jesse Meng
    Mar 8, 2018 at 20:58
  • $\begingroup$ @Marc Almost; you have to prove both of those. The statement $(B\to C)\to A$ is equivalent to $(\neg B\lor C)\to A$, which is equivalent to $(\neg B\to A)\land (C\to A)$. Thus, you must prove that if $B$ is false then $A$ is true, and also if $C$ is true then $A$ is true. $\endgroup$ Mar 9, 2018 at 3:47
5
$\begingroup$

It helps to call $D$ the statement $B\implies C$. One has to prove $A\iff D$. So we need to show that $A$ implies $D$, and $D$ implies $A$. This means again, that, assuming $A$ it must follow $C$ if we assume $B$, and conversely, that whenever $C$ follows from $B$, then $A$ follows. Now check your $4$ statements according to this reasoning.

$\endgroup$
0
$\begingroup$

Hint 1: There are 6 ways to prove $P\implies Q$:

  1. Assume $P$, then prove $Q$
  2. Assume $\neg Q$, then prove $\neg P$
  3. Prove $\neg P$
  4. Prove $Q$
  5. Prove $\neg[P \land \neg Q]$
  6. Prove $\neg P \lor Q$

Hint 2: To prove $P\iff Q$, prove $P\implies Q$, then prove $Q\implies P$

$\endgroup$

You must log in to answer this question.

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