PROOF TECHNIQUES

An identity is a mathematical sentence that is always true.
For example,   [beautiful math coming... please be patient] $\,x+x=2x\,$   is an identity.

A contradiction is a mathematical sentence that is always false.
For example,   [beautiful math coming... please be patient] $\,x=1\text{ and }x\ne 1\,$   is a contradiction.

Given any mathematical statement $\,S\,$,
[beautiful math coming... please be patient] $S\text{ or } (\text{not }S)\,$   is an identity, and
$S\text{ and }(\text{not }S)\,$   is a contradiction,
as the truth table below shows:

[beautiful math coming... please be patient] $\,S\,$ $\,\text{not }S\,$ $\,S\text{ or }(\text{not }S)\,$ $\,S\text{ and }(\text{not }S)\,$
TFTF
FTTF

Here's the intuition for ‘$S\text{ or } (\text{not }S)\,$’:   you're either true, or you're not true.

Here's the intuition for ‘$S\text{ and }(\text{not }S)\,$’:   you can't be true and not true at the same time.

PROOF BY CONTRADICTION

The proof by contradiction technique can be applied to any type of mathematical sentence:

PROOF BY CONTRADICTION a widely-applicable proof technique
To prove that a sentence is true, you can assume that it is false, and then reach a contradiction.

This approach is justified by the truth table below, where it is shown that a statement $\,S\,$ is equivalent to:   $\,(\text{not }S)\Rightarrow \text{(a contradiction)}$

[beautiful math coming... please be patient] $S$ $\text{not }S$ a contradiction $(\text{not }S)\Rightarrow \text{(a contradiction)}$
TFFT
FTFF

THREE STANDARD APPROACHES FOR PROVING IMPLICATIONS

There are three standard approaches for proving an implication, $\,A\Rightarrow B\,$:

DIRECT PROOF a proof technique for implications
To prove that an implication [beautiful math coming... please be patient] $\,A\Rightarrow B\,$ is true,
we can assume that $\,A\,$ is true, and show that $\,B\,$ is also true.

Recall from ‘If... Then...’ Sentences that the only time an implication is false is when the hypothesis is true, and the conclusion is false.
In a direct proof, we show that this line of the truth table can never occur.

The next method is based on the fact that an implication is equivalent to its contrapositive.

PROOF BY CONTRAPOSITION a proof technique for implications
To prove that an implication $\,A\Rightarrow B\,$ is true,
we can alternately prove that its contrapositive [beautiful math coming... please be patient] $\,(\text{not }B)\Rightarrow (\text{not }A)\,$ is true:
Assume that $\,B\,$ is false, and show that $\,A\,$ is also false.

Observe that ‘proof by contraposition’ is just a direct proof of the contrapositive.

Applying ‘proof by contradiction’ to an implication leads to a proof technique that is called an ‘indirect proof’.
By the way, don't mix up ‘proof by contraposition’ and ‘proof by contradiction’.
The words sound similar, but they're different proof techniques.

INDIRECT PROOF a proof technique for implications
To prove that an implication [beautiful math coming... please be patient] $\,A\Rightarrow B\,$ is true,
we can assume that $\,A\,$ is true, but $\,B\,$ is false, and then reach a contradiction.

What's the only time than an implication ‘$\,A\Rightarrow B\,$’ is false?
When $\,A\,$ is true, and $\,B\,$ is false.
In an indirect proof, we assume these conditions, and then reach a contradiction.

In Introduction to the Two-Column Proof, you'll get lots of practice with direct and indirect proofs, and proof by contraposition.
However, there are some skills you'll probably want to develop first—so keep moving forward!

Master the ideas from this section
by practicing the exercise at the bottom of this page.

When you're done practicing, move on to:
Logical Equivalences


On this exercise, you will not key in your answer.
However, you can check to see if your answer is correct.
PROBLEM TYPES:
1 2 3 4 5 6 7 8 9 10 11 12 13
AVAILABLE MASTERED IN PROGRESS

(MAX is 13; there are 13 different problem types.)