2
$\begingroup$

I encountered earlier today a question "Is the proof by contradiction same as that $A \rightarrow B$ is true when $A$ is false?" continued by "Are they related, then? How?"

I think the answer is "no, they´re not the same thing", and demonstrates some confusion on the subject. However, as I am still more than a little confused about mathematical logic myself, too, I couldn't explain properly why this felt wrong to me. I pointed that proving statement $P$ by contradiction can be formulated symbolically as a $\neg P \rightarrow Q \wedge \neg Q$, and if $P = A \rightarrow B$ (because statements like that were the topic of discussion), we get something ...quite different. (I think I lost my trail of thought here.) However, it (the method of proof by contradiction) does feel like a different thing than the existence of a line in the truth table for $A \rightarrow B$ where $A$ is false and $B$ is true and thus the implication is true. Was I correct in this?

However, afterwards I remembered that $A \rightarrow B = \neg B \rightarrow \neg A$, where the right side is known as proof by contraposition. And the proof by contraposition is "in practice" usually done by assuming that $\neg B$ is true and then showing that $\neg A$ follows. (Because of the equality above, this is same as showing that "$A \rightarrow B$".)

Drawing the truth tables for both $A \rightarrow B$ and $\neg B \rightarrow \neg A$, this line (where $\neg B$ and $\neg A$ are true) does coincide with with $A$ being false and $B$ being true. So maybe one could say that $A \rightarrow B$ is true when $A$ is false is related to (or even "same thing as"?) the proof by contraposition.

Maybe we're both (or just me) confused about the relation of truth tables of statements like $A\rightarrow B$ to actually proving statements like "if A, then B".

Enlighten me, please.

$\endgroup$
2
$\begingroup$

A proof by contradiction is an argument of the form :

  • assume $A$ and infer $B$;

  • then, assume $A$ and infer $\lnot B$,

  • and conclude with $\lnot A$.

In words, showing that the assumption leads to a contradiction, licences us to infer the negation of the assumption.

We cam express it in symbolic form (in propositional logic) as :

$(A → B) → ((A → ¬B) → ¬A)$.

We can easily reconcile the two versions noting that, by a "standard" result of a proof system for propositional logic (the Deduction Theorem), we have that :

if $A \vdash B$, then $\vdash A \rightarrow B$

where we have used (as usual) the "turnstile" ($\vdash$) to denote the relation of derivability in a proof system.

Thus, the above argument can be foramlized as follows :

if $\vdash A \rightarrow B$ and $\vdash A \rightarrow \lnot B$, then $\vdash \lnot A$.


How to reconcile it with truth table ?

Having $\vdash A \rightarrow B$ means to have proved the conditional $A \rightarrow B$, and the same with $\vdash A \rightarrow \lnot B$.

Of course we assume that "our logic" is sound, i.e. it does not prove false formulae.

Thus, if both formulae are true, due to the fact that one of $B, \lnot B$ is false, we must conclude that - in order that both conditionals are true - $A$ is false.

$\endgroup$
  • 1
    $\begingroup$ What is an argument of the form "1. assume $\lnot$A, infer B. 2. assume $\lnot$A, infer $\not$B. 3. Conclude A"? Is that a proof by contradiction? $\endgroup$ – Doug Spoonwood Sep 15 '14 at 3:24
  • $\begingroup$ @DougSpoonwood - yes, it is. $\endgroup$ – Mauro ALLEGRANZA Sep 15 '14 at 7:36
1
$\begingroup$

There is a connection between proving $A \rightarrow B$ and proving "if $A$, then $B$". That's called the deduction theorem, which guarantees that one is true iff the other is. You may want to look that up.

As for your question, I'm a little confused by your wording. A proof by contradiction works by showing, generally, that "if $A$, then $B$" is true, and then showing that $B$ is false, whence $A$ is false. Assuming the deduction theorem, this is the same as showing that $A \rightarrow B$ is true and $B$ is false. So yes, this is related to the idea that $A \rightarrow B$ is true when $A$ is false: given the truth of $A \rightarrow B$ and the falsity of $B$, the only way to jointly maintain this is to assume that $A$ is false.

In case you're unsure, draw the truth table, and then cross-out the row which say that $A \rightarrow B$ is false and the rows which say that $B$ is true. The remaining row will give you that $A$ is false.

$\endgroup$
  • 3
    $\begingroup$ I think that's modus tollens or proof by contrapositive, not proof by contradiction. $\endgroup$ – WimC Sep 14 '14 at 19:36
  • $\begingroup$ @WimC - They are connected. In a proof by contradiction, you assume the hypothesis and show it implies a contradiction. You can then apply modus tollens to negate the hypothesis. $\endgroup$ – Nagase Sep 14 '14 at 19:42
0
$\begingroup$

Suppose you want to prove statement $X$. If, assuming that $X$ is false leads to a contradiction of the form $Y\land \neg Y$, then, of course, $X$ must be true (by contradiction).

That is certainly the mainstream (i.e. non-instuitionst) view anyway.

$\endgroup$
0
$\begingroup$

A proof by contradiction consists of an argument where you hypothesize something, infer a conclusion which is a contradiction, and then discharge the hypothesis one way or another.

This means either that you infer either two propositions "A" and "$\lnot$A" which qualify as contradictory, or you infer a conjunction which has the form (A$\land$$\lnot$A), or more broadly you infer some formula which is known to consist of the negation of a tautology.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.