Back to the on-screen lesson ·
The four moves of a direct proof, why every step has to name the definition or result it uses, and how the shape of a claim chooses the technique.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to write a direct proof in its four moves — take arbitrary objects, unfold the definitions, do the algebra, fold the definition back up — and name the definition, axiom or earlier line that licenses each step. You will also be able to choose a technique from the shape of a claim rather than from its subject, and read somebody else's sketch to say which statement it actually established, which is where a proof of the converse hides.
Unit 1 gave you the tools to say precisely what a claim asserts: the connectives, the arrow and its rearrangements, the quantifiers and their order, and how to negate any of it. None of that proved anything. This unit is where the statements get established, and the first line of every proof in it is read off the shape you already know how to see.
A theorem is a statement with a proof. A definition fixes what a word means and is the thing a proof unfolds. A lemma is a small theorem proved on the way to a bigger one; a corollary is one that falls out afterwards. An axiom is assumed without proof. A proof is a finite list of statements, each following from the definitions, the axioms or the statements above it, ending in the theorem.
A proof of $P \Rightarrow Q$ has to establish one thing: that the forbidden row cannot occur — $P$ holding while $Q$ fails. The direct route does it by assuming $P$ and reaching $Q$, and it has four moves and no others.
Every step cites something: a definition, an axiom, an earlier line, or a theorem already proved. Cites is the operative word — a step nobody can name a reason for is not a step, however obvious it looks, and the discipline of naming the reason is most of what separates a proof from a persuasive paragraph.
Checking $n = 1, 2, 3$ establishes the claim for $1$, $2$ and $3$. It is evidence for a conjecture and it is not an argument about every $n$; the whole of induction is the step that turns one case into the next.
Another way: steps
Before writing anything:
Another way: example
Claim: if $a \mid b$ and $b \mid c$ then $a \mid c$. First line: 'let $a, b, c$ be integers with $a \mid b$ and $b \mid c$'. Unfolded: $b = ak$ and $c = b\ell$. Last line wanted: $c = a \times$ (an integer). Substituting, $c = ak\ell$ — and the gap is closed by one substitution, because the two definitions were written out.
| The claim looks like | Try | Because |
|---|---|---|
| $P \Rightarrow Q$ with a usable $P$ | direct | unfolding $P$ gives you something to write |
| $P \Rightarrow Q$ with an awkward $P$ | contrapositive | $\neg Q$ may be the concrete one |
| there is no ..., $x$ is irrational | contradiction | a non-existence claim has nothing to construct |
| for every natural number $n$ | induction | each case can be built from the one before |
| a hypothesis that splits | cases | the split covers everything and each part is easy |
None of these is forced. Almost every statement provable one way is provable another, and the technique to choose is the one that makes the first line easy to write. If assuming the hypothesis leaves you staring at a blank page, assume the negation of the conclusion instead and see whether that gives you an equation.
Proving the converse. A proof of the converse looks exactly like a proof of the statement until you check which way the assumption ran. Before writing a line, say out loud what you are assuming and what you are trying to reach.
Assuming what is to be proved. Starting 'suppose $ab$ is odd' in a proof that $ab$ is odd is circular, however much correct work follows it.
Never unfolding a definition. A proof that uses the word even four times and the equation $a = 2m$ never has not begun.
Stopping at the algebra. $2(2mn + m + n) + 1$ is not a conclusion until somebody says that this is what odd means.
Checking a claim at $n = 1, 2, 3$ tells you the claim is worth trying to prove. It is not an argument about every $n$, and the gap is not a matter of degree: $n^2 + n + 41$ is prime for the first forty values of $n$ and composite at $n = 41$, and the first forty were never evidence of anything about the forty-first. The only universal claim a list of cases settles is one with finitely many cases, all of them checked.
Claim: the sum of two even integers is even. Let $a$ and $b$ be even integers — arbitrary, so nothing beyond evenness may be used.
Move 1: take arbitrary objects.
By definition, $a = 2m$ and $b = 2n$ for some integers $m, n$.
Move 2: unfold the definition.
Then $a + b = 2m + 2n = 2(m + n)$, and $m + n$ is an integer because the integers are closed under addition.
Move 3: algebra, aimed at the shape $2 \times {}$.
So $a + b$ is twice an integer, which is the definition of even. Since $a$ and $b$ were arbitrary, the claim holds for every pair.
Move 4: fold the definition back up.
'To show $P \Rightarrow Q$: assume $Q$, and derive $P$.' Strip the subject matter and look at the arrows.
What was assumed, and what was reached?
$Q$ was assumed and $P$ was reached, so what has been established is $Q \Rightarrow P$ — the converse.
The direction is the whole question.
It may happen that the converse is also true. That is a separate theorem needing a separate proof, and this page is not it.
A true conclusion does not rescue a wrong direction.
The hypothesis is usable, so go direct. Let $n$ be an even integer — arbitrary.
Move 1.
Unfold: $n = 2m$ for some integer $m$. Then $n^2 = 4m^2$.
Moves 2 and 3.
$m^2$ is an integer, so $n^2$ is four times an integer, which is the definition of divisible by four. Notice how little the proof did: the whole argument was the definition, written out, and one squaring.
Build the direct proof that the product of two odd integers is odd.
This task has no paper form; do it on a device.
Here are the four lines of a direct proof that the square of an odd integer is odd. Put them in order.
Number the steps in order (write the number in the box):
A step of a direct proof has reached $(4m + 1)(2n + 1)$. Multiply it out.
Answer:
Which technique fits: if $3n + 2$ is odd then $n$ is odd?
To show $P$: assume $P$, and derive something true. What does this establish?
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A step of a direct proof has reached $(4m + 1)(8n + 1)$. Multiply it out.
Answer:
You can write a direct proof with every step named and say which technique a claim's shape asks for. Say in your own words why a list of checked examples is not a proof, and what the last line of a direct proof has to do. Next: the claims whose hypothesis gives you nothing to write, and the rearrangement that rescues them.
10. Your turn: prove that if $n$ is even then $n^2$ is divisible by four, step 3