Every fact this course states — a matrix is invertible, a set of vectors spans a plane, a transformation preserves length — gets stated as a proof, not as a rule to memorize. That only pays off if you can tell a valid proof from a plausible-looking argument that secretly checked three examples and called it done. This section is not new mathematics; it's the reading and writing habits that make every theorem from here on actually land.
Think of a direct proof as a chain of dominoes you build yourself, not one you're handed already toppled. Each domino, each line of the proof, has to physically touch the one before it. You can't place domino 5 floating in midair and claim it falls because dominoes 1 through 4 fell. "Check a few examples" is like tipping over three dominoes by hand and declaring the chain works. A real proof shows that any domino you place in that chain topples the next one. So the whole infinite row falls, no matter how long it is or which row you built.
Reading a proof well means checking that every line follows validly from the lines before it, each for a stated reason — not skimming for the conclusion. A direct proof of a universal claim \forall x \in S,\ P(x) \implies Q(x) starts by fixing an arbitrary x \in S satisfying P(x) — not a specific number, a generic one — and chains a sequence of implications, each justified by a definition or an already-established fact, until Q(x) is reached. Because x was never specialized, the argument holds for every element of S at once. Two habits separate a real proof from an imitation: every line must follow from the lines before it by a stated reason, and the opening line must quantify over the whole set, never substitute a number.
A second, equally common shape flips the goal entirely: instead of building forward to the conclusion, you assume the conclusion is false and hunt for a contradiction.
This is the alibi defense in reverse. To convict a suspect, meaning "the claim is true," you don't have to walk the jury through everything the suspect actually did. Instead you can say "suppose the suspect is innocent," then show that assumption forces something impossible, like the suspect being in two cities at once. The impossibility doesn't prove where the suspect was. It just proves the "innocent" story can't be true, and that's enough to force the opposite. The trap is the same one lawyers fall into: negate the claim sloppily. Swap "everyone" for "someone" by accident, and the whole argument collapses even though every later step was valid.
A proof by contradiction of a claim C begins by assuming \neg C — the negation of the claim — and derives, through valid steps, a statement that is impossible: something of the form R \wedge \neg R, or a numerical falsehood like 0 = 1. Since every step from \neg C was logically valid, the only thing that could be false is the assumption itself, so C must hold. Negating a quantified claim correctly is essential here: \neg(\forall x,\ P(x)) becomes \exists x,\ \neg P(x), and \neg(\exists x,\ P(x)) becomes \forall x,\ \neg P(x) — the quantifier flips every time the \neg moves past it.
Dragging two vectors around won't prove anything by itself, but it's the right first move: build the evidence, then ask whether the pattern you're seeing has to be true for every vector, or just the ones you happened to drag.
Testing a claim before proving it
Drag vector u or vector v and watch the grey sum arrow u+v — the diagonal of the parallelogram they form. Try to drag u and v so that the sum arrow reaches farther from the origin than u's arrow and v's arrow laid end to end would allow.
Loading interactive…
No matter how you drag them, the sum never reaches past that combined tip-to-tail length — that's the triangle inequality, and dragging examples is evidence for it, not a proof of it. The worked example below proves a close cousin of that fact algebraically, for every real number at once.
Recipe Write a direct proof of a universal claim Use when: the claim has the form "for every x in some set, P(x) implies Q(x)" (or just "for every x, Q(x)") and a forward chain from hypothesis to conclusion is at least plausible Goal: an unbroken chain of justified steps from an arbitrary element satisfying the hypothesis to the conclusion, valid for every such element at once
Quick recipe
-
1
Open with "let x be an arbitrary element of S" (or, when there's a hypothesis P(x), "let x be arbitrary with P(x)"). Whatever gets derived next must never depend on x being any particular value.
Example
For the claim \forall a,b\in\mathbb R,\ (a+b)^2\le2(a^2+b^2): "fix arbitrary real numbers a and b" — not, say, a=5 and b=-1.
Why: the entire payoff of a direct proof — that it covers every element of S at once — depends on x never having been specialized; substituting a number here only proves the claim for that one number.
-
2
Restate the goal in a form where the property you need becomes visible: for an inequality, often as a difference (show it's \ge0); for an equation, by substituting a definition; for a set claim, by unfolding what membership means.
Example
Rewrite the inequality as the difference of its two sides and expand: 2(a^2+b^2)-(a+b)^2 = 2a^2+2b^2-a^2-2ab-b^2 = a^2-2ab+b^2
Why: the claim in its original form rarely reveals why it's true; restating the goal as "show this expression is \ge0" turns it into something concretely checkable.
-
3
Write each line as a consequence of the line before it, and name the definition, identity, or already-established fact that licenses the step.
Example
Recognize a^2-2ab+b^2 as the perfect square (a-b)^2 — an algebraic identity, not a guess — and note (a-b)^2\ge0 because a real number squared is never negative.
- the chain reaches the target statement directly — the proof is done; move to Step 4 and write the conclusion.
- the chain stalls, with no obvious next justified step — go back to Step 2 and try a different rewriting of the claim.
Why: every line needs a stated reason precisely so a reader can check each link, instead of taking the chain on faith.
-
4
Confirm the final line is exactly the conclusion you set out to prove, phrased in terms of the same arbitrary object from Step 1 — then say explicitly that, because that object was arbitrary, the result holds for every element of S.
Example
(a-b)^2\ge0 rearranges to (a+b)^2\le2(a^2+b^2); because a and b were arbitrary real numbers, this holds for every pair of real numbers.
Why: this is the actual logical move that upgrades "true for this a,b" into "true for all a,b" — skipping it leaves even flawless algebra short of being a proof.
-
5
Substitute one concrete choice satisfying the hypothesis and confirm the conclusion holds numerically.
Example
At a=5,\ b=-1: left side (4)^2=16, right side 2(25+1)=52, and 16\le52 ✓.
Why: this catches an algebra slip from Steps 2–3 before you trust the argument, but one example — or a thousand — never proves a claim about infinitely many elements; that's exactly what Steps 1–4 were for.
Common mistakes
- Substituting a specific number for the "arbitrary" element in Step 1, which only proves the claim for that one number.
- Writing a line that doesn't follow from the line before it, or giving no reason at all for a step.
- Stopping once the algebra "looks finished" without restating the conclusion in the exact form the claim asked for, and invoking arbitrariness explicitly.
- Treating the numeric check in Step 5 as if it were the proof, rather than a check on one.
Recipe Prove a claim by contradiction Use when: a direct forward chain from hypothesis to conclusion isn't obvious — especially when the claim asserts that something does NOT exist or CANNOT happen Goal: a valid chain of steps from the claim's negation to an outright logical impossibility, which forces the original claim to be true
Quick recipe
-
1
Write the exact negation of the claim. A quantifier flips every time the negation moves past it: \neg(\forall x,\ P(x)) becomes \exists x,\ \neg P(x), and \neg(\exists x,\ P(x)) becomes \forall x,\ \neg P(x).
Example
The claim "no smallest positive rational number exists" is \neg\big(\exists\, r\in\mathbb Q,\ r>0 \text{ and } r \text{ is smallest}\big) on its face, so its negation flips right back to the existence statement: "there exists a positive rational r that IS the smallest positive rational."
- the claim is a "for all" statement — its negation becomes a "there exists" statement.
- the claim already has the form "there is no X" (itself a negation) — negating it produces the plain existence statement "there is an X."
Why: a sloppy negation — swapping "everyone" for "someone" by accident — aims every later step at the wrong target, even if each one is individually valid.
-
2
Take the negated statement as a working hypothesis. If it asserts something exists, give it a name — a symbol standing for an unknown object, not a specific number.
Example
Assume: there exists r\in\mathbb Q with r>0 such that r is the smallest positive rational.
Why: naming the hypothetical object is what lets the next steps reason about it concretely, the same role Step 1 of a direct proof plays by fixing an arbitrary element.
-
3
Chain valid, justified steps from the assumption until you reach a statement of the form R \wedge \neg R, or a plain falsehood like 0=1.
Example
\dfrac r2 is rational (half a rational is rational) and positive (half a positive number is positive), and since r>0, \dfrac r2 < r — so \dfrac r2 is a positive rational strictly smaller than r.
Why: only an actual logical impossibility forces the blame onto the assumption; a merely surprising or unlikely consequence doesn't finish the proof.
-
4
State explicitly which two statements contradict each other, conclude the Step 2 assumption must be false, and then state the conclusion in terms of the ORIGINAL claim, not just "the assumption is false."
Example
"r is the smallest positive rational" and "\dfrac r2 is a smaller positive rational" can't both hold — that's the impossibility. So the assumption is false, and no smallest positive rational number exists, exactly the original claim.
Why: this is the step that actually finishes the logical move: since every step from the assumption was valid, the only thing that could be false is the assumption itself — but only if the final line explicitly returns to what was originally claimed.
Common mistakes
- Negating a quantified claim incorrectly, forgetting that \forall flips to \exists and vice versa.
- Deriving something merely surprising, not an actual logical impossibility, and calling it a contradiction.
- Losing track of which two statements are contradicting each other, so the R\wedge\neg R is never stated explicitly.
- Ending with "the assumption is false" and stopping there, instead of translating that back into the original claim.
Check your understanding (counts toward your progress)
In a direct proof that (a+b)^2 ≤ 2(a^2+b^2) for all real a, b, the key step rewrites the difference 2(a^2+b^2) − (a+b)^2 in fully expanded then factored form as a single squared expression. Write that squared expression.
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.
Any equivalent form counts — 2x+3, 3 + 2·x, … Use the keypad below the field for fractions, roots, and other symbols.
Why
Expanding gives 2a^2+2b^2 − (a^2+2ab+b^2) = a^2 − 2ab + b^2, which factors as (a−b)^2 — a square is never negative, which is exactly what forces the inequality for every real a and b.
Correct answer
Also accepted:
Why
Expand (a+b)^2 and 2(a^2+b^2) fully, subtract, then look for a familiar squared binomial pattern in what's left.
You want to prove the universal claim "for every real number x, if x > 5 then x^2 > 25." What should the very first line of a direct proof do?
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.
Checking x = 6 only shows the claim holds for one number — a direct proof needs an argument that works no matter which x > 5 was chosen.
That opening move starts a proof by contradiction, not a direct proof of the implication.
Squaring is a valid step, but only after x has been introduced as an arbitrary number satisfying the hypothesis.
Why
A direct proof of ∀x, P(x) ⇒ Q(x) opens by fixing a generic x with P(x) true, so every later step applies to all such x at once, not just one chosen value.
To prove "if n^2 is odd, then n is odd" for integers n, a student instead proves "if n is even, then n^2 is even." Is this a valid strategy?
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.
Contrapositives are always logically equivalent to the original conditional — that's precisely why proving one proves the other. Check what the contrapositive of "if n^2 odd then n odd" actually is.
The converse of "if n^2 is odd, then n is odd" would be "if n is odd, then n^2 is odd" — that's not what the student proved. Negating both sides (not swapping them) of the original gives "if n is even, then n^2 is even," which is the contrapositive.
Equivalence between a conditional and its contrapositive is a logical guarantee, true for every statement of that form, not a coincidence tied to these particular hypotheses being true.
Why
The contrapositive of "if n^2 is odd, then n is odd" negates and swaps both parts: "if n is not odd (even), then n^2 is not odd (even)." That is exactly "if n is even, then n^2 is even," and a conditional is always logically equivalent to its contrapositive, so proving it proves the original.
Recall how the contrapositive of a conditional statement relates logically to the original statement.
Worked example
Prove: for all real a and b, (a+b)² ≤ 2(a²+b²)
-
1
This is the direct-proof recipe above, Steps 1–4, run start to finish. Claim. \forall a, b \in \mathbb{R},\ (a+b)^2 \le 2(a^2+b^2). Fix arbitrary real numbers a and b — not specific values, so whatever we derive holds for every pair at once.
-
2
Work with the difference between the right side and the left side; showing it's never negative proves the inequality: 2(a^2+b^2) - (a+b)^2 = 2a^2 + 2b^2 - a^2 - 2ab - b^2 = a^2 - 2ab + b^2
-
3
Recognize the right side as a perfect square: a^2 - 2ab + b^2 = \textcolor{#4f46e5}{(a-b)^2}
-
4
A real number squared is never negative, so \textcolor{#4f46e5}{(a-b)^2} \ge 0 for every choice of a and b — this is where fixing a,b as arbitrary real numbers earlier makes the argument apply to all of them.
-
5
Since 2(a^2+b^2) - (a+b)^2 = (a-b)^2 \ge 0, rearranging gives \boxed{(a+b)^2 \le 2(a^2+b^2)} \quad \forall a, b \in \mathbb{R} Check at a=5, b=-1: left side (4)^2=16, right side 2(25+1)=52, and 16 \le 52 ✓ — but the proof above is what guarantees it for every pair, not just this one.
Loading interactive…
Worked example
Prove by contradiction: no smallest positive rational number exists
-
1
This is the proof-by-contradiction recipe above, Steps 1–4, run start to finish. Claim. There is no smallest positive rational number. Assume, for contradiction, the negation: \exists\, r \in \mathbb{Q} with r > 0 such that r is the smallest positive rational.
-
2
Consider \dfrac{r}{2}. Since r is a positive rational, \dfrac{r}{2} is also a rational number, and \dfrac{r}{2} > 0 because r > 0.
-
3
Compare \dfrac{r}{2} to r: since r > 0, we have \textcolor{#b91c1c}{\dfrac{r}{2} < r} so \dfrac r2 is a positive rational number strictly smaller than r.
-
4
This contradicts the assumption that r was the smallest positive rational — we just produced a smaller one, of the form R \wedge \neg R (both "r is smallest" and "r is not smallest" hold).
-
5
The assumption must be false, so \boxed{\text{no smallest positive rational number exists}} Notice the whole proof needed only one arbitrary object, r — the contradiction came from a property of any claimed smallest element, not from checking specific fractions like \tfrac12 or \tfrac13.
Loading interactive…
A proof-reading habit worth carrying forward: before trusting any argument in this course, find the line where a variable was fixed ("let x be arbitrary," "suppose r is the smallest such rational") and the line where the conclusion actually gets reached — everything between those two lines has to be an unbroken chain, or the proof isn't finished yet.
Where this goes next
Linear Algebra
Nearly every theorem later in this course is a universal claim proved the same two ways you just practiced. "Every invertible matrix has exactly one inverse" is a direct proof: assume A has two inverses B and C, then chain B = BI = B(AC) = (BA)C = IC = C to force B=C — the whole argument is one implication chain from an arbitrary pair of inverses to their equality. "A set of more vectors than the dimension of the space must be linearly dependent" is usually proved by contradiction: assume such a set were independent, and that assumption collides with a counting argument about how many equations a matrix can pin down. When Chapter 3 hands you a boxed theorem with a proof underneath it, that proof will use exactly the two moves from this section — fix an arbitrary object, or assume the opposite and force a contradiction — so recognizing which move is being made, and where the arbitrary object gets fixed, is what turns "I read the theorem" into "I could defend it."
Practice: Reading and writing a proof, start to finish (6 problems · doesn’t affect your progress)
You want to prove the universal claim "for every real number x, if x > 5 then x^2 > 25." What should the very first line of a direct proof do? (For reference, the choices given are: Fix an arbitrary real number x satisfying x > 5, and treat it as a generic, unspecified value.; Pick a convenient number, such as x = 6, and verify the claim for it.; Assume x^2 > 25 is false and search for a contradiction.; Skip straight to squaring both sides of x > 5..)
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.
Checking x = 6 only shows the claim holds for one number — a direct proof needs an argument that works no matter which x > 5 was chosen.
That opening move starts a proof by contradiction, not a direct proof of the implication.
Squaring is a valid step, but only after x has been introduced as an arbitrary number satisfying the hypothesis.
Why
A direct proof of ∀x, P(x) ⇒ Q(x) opens by fixing a generic x with P(x) true, so every later step applies to all such x at once, not just one chosen value.
Fix an arbitrary real number x satisfying x > 5, and treat it as a generic, unspecified value.
A student checks the claim "n^2 + n is even for every integer n" at n = 1, n = 2, and n = 3, finds it true each time, and declares the claim proved. What's wrong? (For reference, the choices given are: Three true examples don't rule out a counterexample at some integer never checked, such as n = 4 or a negative integer.; Nothing — three examples of a pattern that consistent is always enough to prove a universal claim.; The student should have checked n = 0 instead, since 0 is the only integer that matters.; The claim is actually false, so no number of examples could ever prove it..)
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.
This is the flaw itself, not a diagnosis of it — three examples are never enough to prove a claim about every integer.
n = 0 is just one more example; no single extra check turns finite evidence into a proof for every integer.
The claim itself is true (n^2+n = n(n+1) is always a product of consecutive integers, hence even) — the problem is the method, not the conclusion.
Why
A universal claim ranges over infinitely many integers; checking finitely many, however many, never rules out a counterexample among the ones left unchecked. Only a general argument that fixes an arbitrary n closes that gap.
Three true examples don't rule out a counterexample at some integer never checked, such as n = 4 or a negative integer.
Which statement is the correct negation of ∀x ∈ ℝ, P(x)? (For reference, the choices given are: ∃x ∈ ℝ such that ¬P(x); ∀x ∈ ℝ, ¬P(x); ∃x ∈ ℝ such that P(x); ¬∃x ∈ ℝ, P(x).)
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.
This keeps the universal quantifier instead of flipping it to existential — negating ∀ always produces ∃.
This drops the negation on P(x) entirely, so it isn't a negation of the original claim at all.
This is logically equivalent to the original statement ∀x, P(x), not its negation.
Why
Negating a ∀ quantifier flips it to ∃ and pushes the negation onto the inner statement: ¬(∀x, P(x)) ≡ ∃x, ¬P(x).
Negating a \forall statement flips it to \exists, and negates the statement inside -- recall that rule before writing the negation out.
∃x ∈ ℝ such that ¬P(x)
To prove "there is no largest even integer" by contradiction, what should the opening assumption be? (For reference, the choices given are: Assume some even integer N exists such that N is greater than or equal to every other even integer.; Assume every even integer is less than some fixed number.; Assume N + 2 is odd for some even integer N.; Assume 2 is the largest even integer, since it's the smallest positive one..)
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.
That restates part of what 'largest' would imply, but it isn't the negation of the claim — it doesn't assert that a largest even integer exists.
N + 2 being odd is false by definition whenever N is even, so this assumption doesn't correspond to negating the claim at all.
Assuming a specific number like 2 is largest only tests one case; contradiction needs the general assumption that some largest even integer N exists, whichever one it is.
Why
Negating "there is no largest even integer" (i.e., ¬∃ largest) gives ∃ an even integer N that is ≥ every even integer — the general existence claim, not a specific candidate.
A proof by contradiction starts by assuming the opposite of what you want to prove -- so assume a largest even integer DOES exist.
Assume some even integer N exists such that N is greater than or equal to every other even integer.
The claim "for every real number x, x^2 ≥ x" is false. Give a value of x strictly between 0 and 1 that disproves it. (Answer for this specific instance.)
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
At x = 0.5, x^2 = 0.25, and 0.25 ≥ 0.5 is false, so x = 0.5 (or any value strictly between 0 and 1) is a counterexample — one counterexample is enough to disprove a universal claim.
Correct answer
Also accepted:
Why
To prove "if n^2 is odd, then n is odd" for integers n, a student instead proves "if n is even, then n^2 is even." Is this a valid strategy? (For reference, the choices given are: Yes — "if n is even, then n^2 is even" is the contrapositive of the original claim, and a statement is always logically equivalent to its contrapositive.; No — the contrapositive of a statement is never logically equivalent to the original statement.; No — the student actually proved the converse, "if n is odd, then n^2 is odd," which does not establish the original claim.; Yes, but only because both statements happen to be true for these particular hypotheses; in general contrapositives can differ in truth value from the original..)
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.
Contrapositives are always logically equivalent to the original conditional — that's precisely why proving one proves the other. Check what the contrapositive of "if n^2 odd then n odd" actually is.
The converse of "if n^2 is odd, then n is odd" would be "if n is odd, then n^2 is odd" — that's not what the student proved. Negating both sides (not swapping them) of the original gives "if n is even, then n^2 is even," which is the contrapositive.
Equivalence between a conditional and its contrapositive is a logical guarantee, true for every statement of that form, not a coincidence tied to these particular hypotheses being true.
Why
The contrapositive of "if n^2 is odd, then n is odd" negates and swaps both parts: "if n is not odd (even), then n^2 is not odd (even)." That is exactly "if n is even, then n^2 is even," and a conditional is always logically equivalent to its contrapositive, so proving it proves the original.
Recall how the contrapositive of a conditional statement relates logically to the original statement.
Yes — "if n is even, then n^2 is even" is the contrapositive of the original claim, and a statement is always logically equivalent to its contrapositive.