Computation answers what; proof answers why it must be so.
Every answer you have computed so far — an integral, a determinant, a remainder — tells you what is true. Mathematics asks a harder question: why must it be true, for every case, forever? A single check, even a thousand checks, is not a proof. A proof is an unbreakable chain of reasoning that leaves no room for a counterexample to hide. In this lesson you meet the grammar of that reasoning — the conditional sentence "if p then q," the quantifiers ∀ and ∃ — and the three great styles of argument: knocking over dominoes (induction), cornering an assumption until it self-destructs (contradiction), and simply building the thing you claim exists. This is the bedrock under everything else.
A statement is a sentence that is definitely true or definitely false — not a question, not an opinion. "7 is prime" is a statement (and true). "Is 7 prime?" is not. The workhorse of proof is the conditional: if p then q, written p → q. Here p is the hypothesis (what you assume) and q is the conclusion (what you must then show).
When is p → q a lie? Only in one situation: when you were promised q (because p held) and q failed to arrive. So p → q is false in exactly one row — p true, q false — and true in all three others. (If p is false, no promise was made, so the implication holds "vacuously.")
Two close cousins are easy to confuse:
| name | form | same as p → q? |
|---|---|---|
| contrapositive | ¬q → ¬p | YES — equivalent |
| converse | q → p | NO — a different claim |
| inverse | ¬p → ¬q | NO — a different claim |
The contrapositive "if not q then not p" is true in exactly the same rows as the original — it is the same statement in disguise, which is why "to prove p → q, prove ¬q → ¬p instead" is a legal and often easier move. The converse flips the arrow and is a genuinely different claim.
"If n is a multiple of 4, then n is even." True. Its contrapositive: "if n is odd, then n is not a multiple of 4." Also true — same fact. But its converse "if n is even then n is a multiple of 4" is false (take n = 6). Two sentences that sound symmetric are not.
Switch the connective. p → q and its contrapositive match in every row; the converse does not.
Most theorems are not about a single number but about all of them, or about the existence of one. Two symbols carry that load:
The deepest rule is what negation does: it swaps the quantifiers and flips what comes after.
¬(∀x P(x)) ⇔ ∃x ¬P(x) ¬(∃x P(x)) ⇔ ∀x ¬P(x)
In words: the opposite of "everything works" is "something fails," and the opposite of "something works" is "everything fails." This is the engine behind counterexamples — to deny a "for all," you exhibit one "there exists" that breaks it.
Claim: "∀ primes p, p is odd." Its negation is "∃ a prime p that is not odd" — and p = 2 is exactly that witness. One number topples the whole "for all."
How do you prove a statement P(n) for every positive integer — infinitely many cases — in finite work? Induction is the answer, and dominoes are the picture. Line up a domino for each n. To be sure they all fall you need only two things:
If both hold, P(1) is true, so P(2) is true, so P(3) is true… and every domino falls. You have proved infinitely many statements with one base check and one general step.
Claim: 1 + 2 + ⋯ + n = n(n+1)2. Base: n = 1 gives 1 on the left and 1·2/2 = 1 on the right. ✓ Step: assume 1 + ⋯ + k = k(k+1)/2. Then 1 + ⋯ + k + (k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2)/2 — which is the formula at n = k+1. ✓ The chain is unbroken.
Step through the proven dominoes. The running sum 1 + 2 + ⋯ + n always equals n(n+1)/2 — the staircase below it.
Drop the base case and you can "prove" nonsense. The famous fake: "all horses are the same color." The step (any k horses share a color ⇒ any k+1 do) limps along, but with no honest base it never gets off the ground. Equally, a true base with a broken step proves nothing. Induction stands on two legs.
Sometimes the cleanest road runs backwards. To prove a statement, assume it is false, follow the logic faithfully, and steer until you crash into an absurdity — something that cannot possibly hold. Since true reasoning never produces a falsehood, the only thing that could be wrong is your assumption. So the original statement is true.
Suppose, for contradiction, that √2 is rational: √2 = ab in lowest terms (no common factor). Square it: 2 = a²/b², so a² = 2b². Then a² is even, which forces a to be even, say a = 2c. Substitute: (2c)² = 2b² ⇒ 4c² = 2b² ⇒ b² = 2c², so b is even too. But then a and b both share the factor 2 — contradicting "lowest terms." The assumption explodes, so √2 is irrational. ∎
You have met this shape before — it is the same move as proof by contradiction in geometry, now aimed at the number line itself. A single irrational number, proved with one airtight argument, settled a question the Pythagoreans found genuinely unsettling.
Two short, sharp tools close the toolkit. To prove "∃x, P(x)" — that something exists — the most honest method is construction: build one explicitly and check it. "There is an even prime" — here is one, 2, and it is even and prime. Done.
And to refute a "for all" claim, you do not need a grand argument — a single counterexample is enough, because (from §37.4.2) ¬(∀x P) is exactly ∃x ¬P. The asymmetry is striking and worth memorizing:
| to do this… | you need… |
|---|---|
| prove ∃x P(x) (something exists) | one example ✓ |
| prove ∀x P(x) (everything works) | a full argument — examples never suffice |
| refute ∀x P(x) | one counterexample ✓ |
The polynomial n² + n + 41 is prime for n = 0, 1, 2, …, 39 — forty straight hits. Tempting to declare "∀n, n² + n + 41 is prime." But at n = 40 it equals 40² + 40 + 41 = 1681 = 41² — not prime. Forty confirmations did not make a proof; one counterexample ends the claim.
Pick a "for all" claim and step the value of n. The readout flags the first counterexample — or reports none in range.
These five ideas — the contrapositive, the quantifiers, induction, contradiction, construction — are the grammar of every proof you will ever read, from first-order logic to the frontiers of research. Computation tells you a thing happens; proof tells you it cannot do otherwise. That certainty is what mathematics is for.
| tool | the idea in one line |
|---|---|
| p → q | false only when p true and q false |
| contrapositive | ¬q → ¬p is equivalent; the converse q → p is not |
| quantifiers | ¬∀ ⇔ ∃¬ and ¬∃ ⇔ ∀¬ — negation swaps them |
| induction | base case and step ⇒ every domino falls; e.g. 1+⋯+n = n(n+1)/2 |
| contradiction | assume false, reach an absurdity; e.g. √2 is irrational |
| one counterexample | refutes a ∀; one example proves an ∃ |
Write the contrapositive and the converse of: "If a number is divisible by 6, then it is divisible by 3." Which one is logically equivalent to the original, and is the converse true?
Contrapositive: "If a number is not divisible by 3, then it is not divisible by 6" — equivalent to the original, and true. Converse: "If a number is divisible by 3, then it is divisible by 6" — a different claim, and false (9 is divisible by 3, not by 6).
In how many of the four rows (the combinations of p, q each true/false) is p → q true? Name the one row where it is false.
True in 3 of the 4 rows. It is false in exactly the row p = true, q = false (the promise made and broken).
Negate the statement: "∀ integers n, n² is greater than n." Then find a value of n that proves your negation.
Negation: "∃ an integer n with n² ≤ n." Witnesses: n = 0 (0 ≤ 0) or n = 1 (1 ≤ 1). The original "for all" is false.
Use induction to prove 1 + 3 + 5 + ⋯ + (2n − 1) = n² (the sum of the first n odd numbers).
Base: n = 1 gives 1 on the left and 1² = 1 on the right. ✓ Step: assume the first k odds sum to k². Add the next odd (2k+1): k² + (2k+1) = (k+1)². ✓ So it holds for all n.
Outline a proof by contradiction that there is no largest prime (there are infinitely many primes).
Assume there are finitely many primes p₁, …, pk. Form N = p₁·p₂·⋯·pk + 1. Dividing N by any pi leaves remainder 1, so no listed prime divides N — yet N greater than 1 has some prime factor. That factor is a prime not on the list: contradiction. So the primes are infinite. ∎
Disprove with one counterexample: "Every odd number greater than 1 is prime."
Take n = 9: it is odd and greater than 1, but 9 = 3 · 3 is not prime. One counterexample refutes the whole ∀. (Also works: 15, 21, 25, …)
Six questions to lock it in. Tap the answer you think is right.
This lesson is a first formal look at mathematical reasoning and proof, the spine of CCSS Mathematical Practice MP3 ("construct viable arguments and critique the reasoning of others") and HSA-REI.A.1 ("explain each step in solving an equation"). Students see that verification is not proof: forty examples do not establish a "for all," while a single counterexample refutes one. The contrapositive, the quantifier-negation rules, induction, and proof by contradiction are exactly the tools that carry into a college discrete-mathematics or introduction-to-proof course — and into rigorous calculus next door. For a gentler on-ramp, see for all & there exists, mathematical induction, and proof by contradiction.