Skip to main content

Beginning Activity Beginning Activity 1: Proof by Contradiction
A4US

In a Definition in Section 2.1, we defined a tautology to be a compound statement \(S\) that is true for all possible combinations of truth values of the component statements that are part of \(S\text{.}\) We also defined contradiction to be a compound statement that is false for all possible combinations of truth values of the component statements that are part of \(S\text{.}\)

That is, a tautology is necessarily true in all circumstances, and a contradiction is necessarily false in all circumstances.

1.

Use truth tables to explain why \(\left( {P \vee \mynot P} \right)\) is a tautology and \(\left( {P \wedge \mynot P} \right)\) is a contradiction.

Another method of proof that is frequently used in mathematics is a proof by contradiction. This method is based on the fact that a statement \(X\) can only be true or false (and not both). The idea is to prove that the statement \(X\) is true by showing that it cannot be false. This is done by assuming that \(X\) is false and proving that this leads to a contradiction. (The contradiction often has the form \(\left( {R \wedge \mynot R} \right)\text{,}\) where \(R\) is some statement.) When this happens, we can conclude that the assumption that the statement \(X\) is false is incorrect and hence \(X\) cannot be false. Since it cannot be false, then \(X\) must be true.

A logical basis for the contradiction method of proof is the tautology

\begin{equation*} \left[ \mynot X \to C \right] \to X\text{,} \end{equation*}

where \(X\) is a statement and \(C\) is a contradiction. The following truth table establishes this tautology.

\(X\) \(C\) \(\mynot X\) \(\mynot X \to C\) \((\mynot X \to C) \to X\)
T F F T T
F F T F T
This tautology shows that if \(\mynot X\) leads to a contradiction, then \(X\) must be true. The previous truth table also shows that the statement \(\mynot X \to C\) is logically equivalent to \(X\text{.}\) This means that if we have proved that \(\mynot X\) leads to a contradiction, then we have proved statement \(X\text{.}\) So if we want to prove a statement \(X\) using a proof by contradiction, we assume that \(\mynot X\) is true and show that this leads to a contradiction.

When we try to prove the conditional statement, “If \(P\) then \(Q\)” using a proof by contradiction, we must assume that \(P \to Q\) is false and show that this leads to a contradiction.

2.

Use a truth table to show that \(\mynot \left( {P \to Q} \right)\) is logically equivalent to \(P \wedge \mynot Q\text{.}\)

The preceding logical equivalency shows that when we assume that \mbox{\(P \to Q\)} is false, we are assuming that \(P\) is true and \(Q\) is false. If we can prove that this leads to a contradiction, then we have shown that \(\mynot \left( {P \to Q} \right)\) is false and hence that \(P \to Q\) is true.

3.

Give a counterexample to show that the following statement is false.

For each real number \(x\text{,}\) \(\dfrac{1}{x(1 - x)} \geq 4\text{.}\)

4.

When a statement is false, it is sometimes possible to add an assumption that will yield a true statement. This is usually done by using a conditional statement. So instead of working with the statement in Exercise 3, we will work with a related statement that is obtained by adding an assumption (or assumptions) to the hypothesis.

For each real number \(x\text{,}\) if \(0 \lt x \lt 1\text{,}\) then \(\dfrac{1}{x(1 - x)} \geq 4\text{.}\)
To begin a proof by contradiction for this statement, we need to assume the negation of the statement. To do this, we need to negate the entire statement, including the quantifier. Recall that the negation of a statement with a universal quantifier is a statement that contains an existential quantifier. (See Theorem 2.24.) With this in mind, carefully write down all assumptions made at the beginning of a proof by contradiction for this statement.