What is the explicit reasoning behind proof by contradiction?

Question

From my understanding, proof by contradiction consists of the following steps.
1. Show that p -> q, where "->" is the conditional.
2. Show that q is false.
3. Deduce from a truth table that p must be false.

My problems with this are the following:

A. If we base the truth of the conditional off the truth of p and q, how can we know that the conditional is true before knowing whether both p and q are true?

B. Assuming we can know that the conditional is true before knowing the truth values of p and q, then proof by contradiction deduces the truth value of p by knowing that q is false while the conditional is true. The only scenario that produces this is result is the one where p is also false. I've never been satisfied with the argument that two false propositions create a true implication however. What good justifications are there for agreeing with this?

Answer 1

There seem to be several overlapping concerns in your issue with proof by contradiction.

1. You have an objection to the truth table for material implication:

I've never been satisfied with the argument that two false propositions create a true implication however. What good justifications are there for agreeing with this?

2. You seem to misunderstand proof by contradiction:

1. Show that p -> q, where "->" is the conditional. 2. Show that q is false. 3. Deduce from a truth table that p must be false.

I will start with the second issue. I'd say a better definition of proof by contradiction is as follows:

1. Given P, A
2. Given P, not A
3. Ergo, given P, A & not A
4. Thus, not P due to contradiction when P

This is somewhat related to material implication as you rightly note. But this is not really about proving A false -- it's about proving A & not A simultaneously true. But since this is impossible on standard logics, then we must have erred in accepting P, therefore not P.

Returning to the topic of standard logics, we can partially address your concerns about material implication. There's three fundamental rules that classical logic follows:

1. Law of Identity - we need to mean the same thing by the same thing every time. (we cannot change the meaning of variables and terms mid argument).
2. Law of Excluded Middle - every proposition we address must be either true or false (and just one of the two on this meaning of or).
3. Law of Non-Contradiction - we can not accept that both A and its opposite (not A) are true at the same time.

We can also express this succinctly:

1. A = A
2. For any A, true or false
3. not (A and not A)

Material implication is a logical operator that operates on two terms and lives in this world. Its purpose is to work with conditions, i.e. places where the value of one variable depends on another. Given that we have 2 variables which (per rule 2 can each have two values), we have four possibilities.

For A -> B,

1. A is true and B is true
2. A is true and B is false
3. A is false and B is true
4. A is false and B is false

What implication does is test whether the implication holds. Thus, we accept that it holds (see the entire implication as true) when A is true and B is true. We also should be able to see that the implication is false when A is true but B is false.

The situation is a bit more complicated and confusing when A is false (if we are thinking "if, then" rather than just accepting it as an operator). Most recently, the explanation I've been giving in my classes is as follows,

When A is false, we don't have a chance to check whether or not the implication holds directly. But given the three laws (particularly 2), we must declare this to be either true or false. Given that, we have not disproved the implication, it remains true for our purposes.

But the thing is, we don't specifically need this for proof by contradiction, because in proof by contradiction what we've done is show that some assumption P leads to a contradiction. And contradictions are unacceptable based on the third rule. Ergo, the assumption itself must be rejected.

Answer 2

Proof by contradiction in general, is not limited to the use of conditional.

In logic, proof by contradiction is a form of proof, and more specifically a form of indirect proof, that establishes the truth or validity of a proposition by showing that the proposition's being false would imply a contradiction.

What is needed is the concept of logical implication or logical consequence.

This concept is the core of all logic. It was firstly clearly identified by Aristolte:

All Aristotle’s logic revolves around one notion: the deduction (sullogismos). [...] What, then, is a deduction? Aristotle says:

A deduction is speech (logos) in which, certain things having been supposed, something different from those supposed results of necessity because of their being so. (Prior Analytics I.2, 24b18–20)

Each of the “things supposed” is a premise (protasis) of the argument, and what “results of necessity” is the conclusion (sumperasma).

The core of this definition is the notion of “resulting of necessity”. This corresponds to a modern notion of logical consequence: X results of necessity from Y and Z if it would be impossible for X to be false when Y and Z are true. We could therefore take this to be a general definition of “valid argument”.

Thus, a valid argument is an argument that, from true premises derives a true conclusion.

If we, from the set of premises Γ ∪ {A} derive something false, like a contradiciton by means of the rules of logic, we have to conclude that at least one of the premises if false, because, by the definition of logical consequance:

if all the premises are true, then necessarily also the conclusion is.

Thus, we conclude that the statement A is "responsible" for the contradiction and that the remaing set of premises Γ implies the negation of A, i.e. ¬ A.

---

In your example, if we have proved

P → Q,

then we proceed as follows:

1) assume P

2) derive ¬ Q;

by modus ponens, we derive from P → Q and 1) also:

3) Q

Now we have the contradiction and thus we have to conclude that our initial assumption P is false, i.e.

4) ¬ P.

Put in another form, if P → Q and P → ¬ Q, using the tautology: (P → Q) → ((P → ¬ Q) → ¬P), by two application of modus ponens we conclude with ¬ P, that amounts to saying:

¬ P is logical concequence of P → Q and P → ¬ Q.

In symbols:

P → Q, P → ¬ Q ⊨ ¬ P

Answer 3

The explicit reasoning behind a proof by contradiction are the two laws

"non (non A) = A" and "If A => B and B false, then A false"

These laws holds in propositional logic. The truthtable method proves the second law.

A proof by contradiction applies these laws in the following way : In order to prove that a proposition "A" is true, one assumes on the contrary that "A" is false. i.e. "non A" true. From this assumption one derives in one or more steps a certain statement "B", which one shows to be false. Now "non A => B" and "B" false implies "non A" false, hence "A" true.

Answer 4

The method you are describing is not "proof by contradiction", it is called "proving the contrapositive" - expressed symbolically as ¬q ⇒ ¬p. This statement is logically equivalent to p ⇒ q. It is important to understand that both of these methods are concerned with proving the material implication p ⇒ q, not (repeat not) the truth of p or q, as you assume in your comments.

How does this work? The statement p ⇒ q is true unless p can be true while q is false. [1]

In the method of proving the contrapositive which you describe one proceeds by assuming q is false and show that this implies that p must be false. This means that we can never have p be true and q false, so one can conclude that p ⇒ q as per [1].

In the method of proof by contradiction one assumes that p ⇒ q is false, i.e. p true and q false (contrary to [1]) and show that this assumption leads to a contradiction, enabling us to conclude that we can never have p true and q false. This is equivalent to saying p ⇒ q since the only time a material implication is false is when it is possible to p true and q false.

Your comments concerning these strategies assumes that we know that p ⇒ q is true and we then derive the truth values of p and q. This is not correct in either of the proof methods - by contradiction or by contraposition. The point of these methods is to prove the truth of p ⇒ q.

---

EDIT

Concerning your comments (below):

1. How can we prove the material implication without first establishing what the truth values of p and q must be?

Both of these methods work by assuming the relevant truth values. In the case of proving the contrapositive, we assume that q is false and show that this forces us to accept that p must also be false. Here is an example of a proving the contrapositive :

(note: I shall give an example of an informal argument since it will be easier to follow how the methods work.)

EXAMPLE : Suppose n is a positive integer and that we wish to prove that :

• If n² is even then n is even.

To use the method of proving the contrapositive, we would assume that the statement q (= n is even) is false and show that a necessary consequence of this assumption is that p (= n² is even) must also be false.

To do this, assume n is not even. Then we can write n as 2k+1, for some positive integer k. Therefore n² = (2k+1)². Expanding this expression and grouping the terms we can write this as n² = 4(k²+k)+1. Since 4(k²+k)+1 is not even (since it is not divisible by 2), we have shown that the assumption that n is not even forces us to conclude that n² is not even. Thus, we have proven "If n is odd then n² is odd", or equivalently “If n² is even then n is even.” I.e., ¬ q ⇒ ¬p, which is equivalent to p ⇒ q.

To use the method of proof by contradiction, we would assume that p ⇒ q is false and derive a contradiction. If p ⇒ q is false then there is a positive integer n such that n² is even, but n is odd. But if n is odd, then by the same argument used in our example of proving the contrapositive, we must have n² also odd. This contradict our assumption that p ⇒ q is false and we can therefore conclude that p ⇒ q must be true.

2. Using the method of proving the contrapositive,can you explain the reasoning behind how we are able to show that p is false by assuming q is false without use of the truth table? Or is that what is being used to establish this?

I believe that my comments on question 1 also answer this question. The example I have given is obviously an informal argument, but one which is easily formalised.

Answer 5

From my understanding, proof by contradiction consists of the following steps. 1. Show that p -> q, where "->" is the conditional. 2. Show that q is false. 3. Deduce from a truth table that p must be false.

You are describing modus tollens, not proof by contradiction.

If we base the truth of the conditional off the truth of p and q, how can we know that the conditional is true before knowing whether both p and q are true?

The assumption in symbolic logic is that we know/believe the conditional (or another premise) is true for some reason outside of symbolic logic. Maybe you believe the implication is self-evident, or is well established by scientific evidence. It is certainly not because you know the truth value of p and q.

The only scenario that produces this is result is the one where p is also false. I've never been satisfied with the argument that two false propositions create a true implication however. What good justifications are there for agreeing with this?

Firstly, this does not actually change the reasoning for modus tollens. If false -> false were either false or indeterminate it would still be the case that true -> false is false. Given that q is false, the only remaining option is that p is false.

The way I see it, you shouldn't think of the material conditional as being equivalent to our natural language concept of implication. Our natural language notion of implication is more like the concept from predicate logic:

(x)(Ax -> Bx)

This says that for all x, if Ax is true, Bx is true. It is trivially true when Ax is false, but if Ax is true, then Bx must also be true.

Consider the proposition: If I'm the president, you're the Pope. Neither proposition is true, but it seems wrong to claim the implication is true because me being president wouldn't make you the pope. But what we really mean is something like, in all possible worlds where I'm the president, you are the pope.

Answer 6

First-order logic is kind of neat in that there are several ways to think about it that all turn out to give identical results.

When Γ is a set of formulas and P is a formula, the notation

Γ ⊢ P

called syntactic entailment, is the assertion that there is a deductive proof of P using the formulas in Γ as hypotheses. e.g. conjunction introduction is the axiom

P, Q ⊢ P ∧ Q

One formulation of proof by contradiction is

Γ, P ⊢ Q
Γ, P ⊢ ¬Q
therefore
Γ ⊢ ¬P

Some versions of logic have a symbol ⊥ that means "contradiction", in which case we would likely instead formulate this as

Γ, P ⊢ ⊥
therefore
Γ ⊢ ¬P

such proof forms may often use of

P, ¬P ⊢ ⊥

---

The conditional can be thought of as a means of converting the notion of entailment into propositional form; specifically

Γ, P ⊢ Q      if and only if      Γ ⊢ P → Q

Then, rather than working with the notion of entailment, one instead manipulates propositions. e.g. modus ponens

P, P → Q ⊢ Q

but we might instead see it given as the tautology

⊢ (P ∧ (P → Q)) → Q

Similarly, we can rephrase proof by contradiction as

(P → Q), (P → ¬Q) ⊢ ¬P

or as the tautology

⊢ ((P → Q) ∧ (P → ¬Q)) → ¬P

Using the contradiction symbol, we could also put this as

⊢ (P → ⊥) → ¬P

---

There's another notation

Γ ⊨ P

called semantic entailment. Since we're talking propositional logic, one ways to define this is that it is the assertion that every truth valuation that makes every statement in Γ true also makes P true.

(a truth valuation is simply a choice of truth value for each atomic proposition and computing the truth of more complex propositions by using the corresponding boolean operators on truth values)

For example, we can prove

P ⊨ P ∨ Q

by truth tables -- that is, by checking that each row of the truth table where P = true also has P ∨ Q = true.

We want implication to behave the same way: for example,

Γ, P ⊨ Q      if and only if      Γ ⊨ P → Q

Observe that the assertion P⊨Q is identical to

it's impossible to assign truth values in a way that makes P true and Q false

Consequently, the rows in the truth table that are false for P→Q must be exactly the rows where P is true and Q is false — no more, no less.

Then, the magical thing about propositional logic (and of first-order logic) are the completeness theorem and the soundness theorem, which together say

Γ ⊢ P      if and only if      Γ ⊨ P

So that's what we're doing when we look at truth values — we are doing calculations and tabulations of truth values to work out semantic entailment, and using this theorem to determine syntactic entailment.

Answer 7

Proof by contradiction is an INDIRECT proof method: you add the negation of what you want to prove conditionally to your premisses in a subproof and show it leads to a contradiction with a prior step of your proof. So you may classically conclude that what you wanted to prove must be true. Not all logics support this form of reasoning - i for instance, intuitionistic logics do not, for they don't accept the unqualified logical equivalence between a statement being true and the negation of that statement being false.

Answer 8

If I ran at high speed into a lamp post, my nose would be bleeding. My nose is not bleeding. Therefore, I didn't run into a lamp post.

You asked: "If we base the truth of the conditional off the truth of p and q, how can we know that the conditional is true before knowing whether both p and q are true?"

In the example, p and q are both false. I didn't run into the lamp post, my nose isn't bleeding. But the conditional is true. p -> q is true in three out of four cases: If p and q are both false, if they are both true, and if p is false but q is true. It is only false if p is true and q is false.