Starting with chapter 1's group axioms, almost nothing in this course is taken on faith. Closure, the subgroup test, Lagrange's theorem, and the isomorphism theorems are all short chains built from exactly the three proof techniques reviewed here. None of that machinery is new. What changes going forward is only the subject matter the techniques get pointed at.
Direct proof follows a trail of footprints forward, from where you started to where you ended up. Contrapositive proof walks the same trail backward. Suppose the destination was never reached. Then something at the start must have gone differently. You argue from "not there" back to "not here." Contradiction works differently. Instead of following any trail, you assume the walker reached somewhere impossible. Then you show the whole situation falls apart before a single step could happen. Reach for contradiction first when the claim itself says "no such path exists." You cannot walk forward along a trail that was never supposed to exist.
A direct proof assumes the hypothesis and chains forward, step by justified step, to the conclusion. A proof by contrapositive proves an equivalent statement instead: "not-conclusion implies not-hypothesis." This is useful exactly when the negated conclusion unfolds into something more useful than the original hypothesis does. A proof by contradiction assumes the entire claim is false. It then derives an impossible result. This is always the right first move for a claim that says something is impossible, or that no object of some kind exists. "No such object exists" has no starting point to reason forward from. Choosing between direct and contrapositive comes down to which side gives you more to work with: what you're given, or its negation.
Negate a universal claim as the first move of a contradiction proof
Push the negation through 'for every x, P(x)' and simplify to its standard form.
Loading interactive…
Direct or contrapositive?
Answer each question about the claim to see which approach the negated conclusion makes easier.
Loading interactive…
Test a claim before trusting it
The claim: for every integer n >= 1, n squared plus n is divisible by 4. Find the n that breaks it.
Loading interactive…
Worked example
Direct proof: the sum of two even integers is even
-
1
Prove that if m and n are even integers, then m+n is even.
-
2
By definition of even, m = 2j and n = 2k for some integers j,k.
-
3
Add: m+n = 2j+2k = 2(j+k).
-
4\boxed{m+n \text{ is even, since } j+k \text{ is an integer}}
Worked example
Contradiction: the integers under addition have no largest element
-
1
Prove that \mathbb{Z} has no largest element under its usual order.
-
2
Assume for contradiction that some integer M is the largest integer that exists.
-
3
Then M+1 is also an integer, and M+1 > M — a larger integer than the one assumed to be largest.
-
4\boxed{\text{Contradiction} — \text{no largest integer can exist}}
Chapter 2 leans on exactly this fact when it distinguishes finite from infinite groups. (\mathbb{Z}, +) is infinite precisely because this same idea rules out a largest element for it to stop at.
Where this goes next
Chapter 1: Foundations and the idea of a group
Testing whether a candidate structure is a group is a sequence of direct proofs. Show closure holds by computing. Show associativity holds by expanding both sides. Showing a structure fails to be a group usually takes just one counterexample — the same disproof-by-example move as the widget above. Take a fact like "a group's identity element is unique." That is a one-line proof by contradiction. Assume two different identities exist, then show they would have to be equal after all.
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics I — Logic, Proof, and Structure
A student proves 'every even integer squared is even' by checking n=4. Is this a valid direct proof?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
n=4 is one specific value, not a stand-in for every even integer -- the same evidence-versus-proof issue from Chapter 0.
From Discrete Mathematics I — Logic, Proof, and Structure
A direct proof of p implies q begins by...
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Direct proof fixes an arbitrary object satisfying the hypothesis, then reasons forward to the conclusion.
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics I — Logic, Proof, and Structure
To prove 'if n squared is even, then n is even' by contrapositive, what should be assumed first?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Contrapositive assumes the negated conclusion (n odd) and derives the negated hypothesis (n squared odd).
From Discrete Mathematics I — Logic, Proof, and Structure
Why is n odd easier to unfold than n squared is even, for this particular claim?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
The negated conclusion's unfolding directly hands you n's form, while the original hypothesis's unfolding does not.
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics I — Logic, Proof, and Structure
Which famous results are typically proved by contradiction?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
These are two of the most celebrated contradiction proofs in mathematics, both featured later in this course.
From Discrete Mathematics I — Logic, Proof, and Structure
To prove 'no integer is both even and odd' by contradiction, what should be assumed?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
The negation of 'no integer has property X' is 'some integer has property X' -- exactly this.