4

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.

Marc
  • 1,198

3 Answers3

5

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.

Dietrich Burde
  • 130,978
5

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.

Jesse Meng
  • 1,310
  • 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? – Marc Mar 08 '18 at 20:43
  • @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. – Jesse Meng Mar 08 '18 at 20:51
  • 1
    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? – Marc Mar 08 '18 at 20:57
  • that is correct – Jesse Meng Mar 08 '18 at 20:58
  • @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. – Mario Carneiro Mar 09 '18 at 03:47
  • @JesseMeng B is either true or not true The constructivist community would like to have a word with you about your first sentence there ;) – Silvio Mayolo Mar 09 '18 at 04:13
0

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$

Dan Christensen
  • 14,529