Lesson · Logic and Proof · Proof

Direct Proof

The default technique: to prove p → q, assume p and reason forward to q. Most of the difficulty is not logical but expository — a proof is a piece of writing whose job is to convince a careful reader.

Open the interactive lesson Practice

To prove ∀x (P(x) → Q(x)): 1. Let x be arbitrary with P(x). 2. ... reasoning, each step justified ... 3. Therefore Q(x). Since x was arbitrary, the claim holds for all x.

The shape of a direct proof

Core ideas

What this lesson establishes

Three things make a direct proof work: the right starting assumption, justified steps, and a reader who can follow them.

Start by assuming the hypothesis

You are not proving q. You are proving that q follows from p, so p is yours to use from the first line.

Unfold the definitions

"n is even" is not a fact to be contemplated but a statement to be replaced: n = 2k for some integer k. Most direct proofs are definition unfolding plus algebra.

Arbitrary means arbitrary

"Let n be an even integer" licenses a conclusion about every even integer. "Let n = 4" does not.

The material

How a direct proof is built and written

The method, then the standards a written proof is held to.

Almost every theorem is a universally quantified conditional: ∀x (P(x) → Q(x)). A direct proof takes an arbitrary x satisfying P, and derives Q(x) by a chain of justified steps.

Definition · Direct proof

To prove p → q, assume p and derive q through a sequence of steps, each justified by a definition, a previously proved result, or a rule of inference.

Theorem · The sum of two odd integers is even

For all integers m and n, if m and n are odd then m + n is even.

Let m and n be arbitrary odd integers. By definition of odd, there are integers j and k with m = 2j + 1 and n = 2k + 1.

Then m + n = (2j + 1) + (2k + 1) = 2j + 2k + 2 = 2(j + k + 1).

Since j + k + 1 is an integer, m + n is twice an integer, which is the definition of even. As m and n were arbitrary odd integers, the claim holds for all of them.

□

Notice how much of that is definition management. "Odd" was replaced by 2j + 1 immediately, the algebra was routine, and the final step recognised 2(j + k + 1) as matching the definition of even. Two different letters j and k were used because m and n are different numbers — reusing one letter for both would have proved only the case m = n.

What a written proof owes the reader

State what is being proved, in full, before starting.
Introduce every variable as it appears: "let n be an arbitrary integer", "there exists k such that".
Justify each step by name: by definition, by hypothesis, by the theorem just proved. A step whose justification you cannot state is a step you have not made.
Say when you are done and what has been established. The reader should never have to guess whether the argument has finished.

Two conventions worth adopting. Write in complete sentences — a proof is prose containing symbols, not a column of formulas. And distinguish the assumption you made from the conclusion you reached; confusing the two is how a proof silently becomes circular.

Example · A proof that assumes what it proves

"Claim: if n² is even then n is even. Proof: n is even, so n = 2k, so n² = 4k² is even." This proves the converse, having assumed the conclusion. It is the most common flawed proof in this course, and “Contraposition and Contradiction” gives the technique that handles the real claim.

When a direct proof stalls, that is information. Being unable to get from p to q forwards often means the natural route is backwards — through the contrapositive — which is “Contraposition and Contradiction”.

Interactive

Check P(n), then notice checking is not proving

Two of these statements are false

Check a claim before you try to prove it

n³ − n is divisible by 6 for every n the slider reaches, and the table is evidence about those n and nothing more. Try the direct proof after this lesson: n³ − n = (n − 1) n (n + 1), and the attempt stalls at "one of three consecutive integers is a multiple of 3", which needs a split into cases. A stall like that is diagnostic — “Contraposition and Contradiction” is about reading it — and “Cases, Counterexamples, and Writing a Proof” finishes this claim. Ignore the "inductive step" line under the table for now: it is Induction and Recursion's vocabulary.

Statement

Check up to n =10

Checked—

Held—

First failure—

Method

Writing a direct proof

The first two steps are where proofs are won or lost.

Write the statement in full

Including quantifiers and domain. If you cannot state it precisely you cannot prove it, and half of all failed attempts end here.

Assume the hypothesis and unfold every definition

Replace "even", "divides", "rational" by what they mean. Symbols can be manipulated; adjectives cannot.

Work forward to the conclusion

Keep the target in view. If a step is not moving toward it, it is probably not the step to take.

Recognise the conclusion in the form you need it

The last line must match the definition of the conclusion. 2(j + k + 1) is even because it is twice an integer — say so.

Direct proof

Score 0 / 0

Choose the answer you can justify.

If a | b and b | c then a | c

a | b means "a divides b": there is an integer k with b = ak.

Let a, b, c be integers with a | b and b | c. By definition of divisibility: a | b ⟹ b = a·j for some integer j b | c ⟹ c = b·k for some integer k Substituting the first into the second: c = b·k = (a·j)·k = a·(j·k) j·k is an integer, so c = a·(integer), i.e. a | c. ∎

Two separate letters j and k are essential: the two factors have no reason to be equal. Using k twice would prove only the special case b = aj and c = bj, which is a different and much weaker theorem.

Common mistakes

Assuming the conclusionStarting from q and deriving something true proves nothing: true statements follow from false ones. Start from p.

Proving one case and claiming all"Let n = 4" proves a fact about 4. The word that makes a proof general is "arbitrary", and it has to be earned.

Leaving a step unjustified because it is obviousIf it is obvious, the justification is one clause long. If you cannot write that clause, it was not obvious — it was unexamined.

Check your understanding

✓

Finish when you can write a proof another person could check line by line.

Prove: if n is an odd integer then n² is odd. Then hand it to someone and watch for the place they hesitate. That place is where a justification is missing, whether or not the mathematics is right.

Note: Every proof in this course is written in prose, because that is how mathematics is actually communicated. A formal derivation is a different object with a different purpose, and neither replaces the other.