Logic and Proof

A proof is an argument that covers every case at once, including the cases nobody will ever check. Checking a thousand cases is evidence. A proof settles the question. The methods below are the shapes that argument can take.

What are the pieces of a mathematical argument?

A definition fixes what a word means. It is a choice, so it cannot be true or false. A proposition is a claim, and a claim can be true or false. A theorem is a proposition that has been proved. A lemma is a small theorem proved on the way to a bigger one, and a corollary follows from a theorem in one step.

This is why arguing about whether 1 is prime goes nowhere. The definition leaves 1 out so that every whole number has exactly one prime factorization. That is a choice, not a discovery.

Statements are joined by and, or and not, and a truth table lists every combination of true and false so that each connective is pinned down. In mathematics or is inclusive: P or Q is true when both hold.

The negation of a statement is true exactly when the statement is false, and it must deny no more than that. The negation of x > 5 is $x\le 5$x ≤ 5, not x < 5, because x = 5 was never ruled out. Under a negation and becomes or, and or becomes and. These are De Morgan's laws.

See Definitions, Propositions and Theorems, Logical Connectives and Truth Tables and Negating a Statement.

Why is the contrapositive true and the converse not?

Because the contrapositive says the same thing as the original in different words, and the converse makes a new claim.

A conditional statement is "if P then Q", written $P\Rightarrow Q$P ⇒ Q. P is the hypothesis and Q is the conclusion. Only one case breaks it: P true and Q false. When P is false the conditional promises nothing, so it cannot be broken.

The converse swaps the two parts: $Q\Rightarrow P$Q ⇒ P. The contrapositive swaps them and negates both: not $Q\Rightarrow$Q ⇒ not P. Take "if n is a multiple of 4 then n is even". Its converse, "if n is even then n is a multiple of 4", is false, and n = 6 is the counterexample. Its contrapositive, "if n is not even then n is not a multiple of 4", is true.

A truth table settles it in four rows. The columns for $P\Rightarrow Q$P ⇒ Q and not $Q\Rightarrow$Q ⇒ not P agree in every row, so the two statements are logically equivalent. The converse pairs off with the inverse, not $P\Rightarrow$P ⇒ not Q, in the same way.

P is sufficient for Q when P guarantees Q, and P is necessary for Q when Q cannot happen without P. When a condition is both, the statement reads "P if and only if Q", and proving it means proving $P\Rightarrow Q$P ⇒ Q and $Q\Rightarrow P$Q ⇒ P. Leaving out one direction leaves the claim unproved.

See Conditional Statements, The Converse and the Inverse, The Contrapositive, Necessary and Sufficient Conditions and If and Only If.

How do quantifiers change a statement?

A quantifier says how many objects a claim is about. "For all", written ∀, claims something of every object in a set. "There exists", written ∃, claims that at least one can be found. A for-all claim is proved by an argument that covers every case and disproved by one exception. A there-exists claim is proved by one example and disproved only by ruling out every case.

The order of two quantifiers changes the meaning. "Every person has a mother" and "there is a person who is the mother of everyone" use the same quantifiers in opposite orders, and only the first is true.

To negate a quantified statement, swap the quantifier and negate what follows it. The negation of "every swan is white" is "some swan is not white", not "no swan is white", which claims far more. This is why one counterexample disproves a general claim: the negation of a for-all statement is a there-exists statement, and one example proves it.

See For All and There Exists and Negating a Quantified Statement.

What are the standard ways to prove something?

Most proofs use one of six methods.

A direct proof assumes the hypothesis and takes forced steps to the conclusion. To show that the sum of two even numbers is even, write them as 2a and 2b. The sum is 2(a + b), which is 2 times a whole number, so it is even.

Proof by the contrapositive proves not $Q\Rightarrow$Q ⇒ not P instead, and it is the right choice when the negated statements are easier to work with. To prove that if $n^2$n² is even then n is even, start from "n is odd": n = 2k + 1, so $n^2=4k^2+4k+1$n² = 4k² + 4k + 1, which is odd. That proves the claim, with no extra step.

Proof by exhaustion splits the claim into a finite list of cases and proves each one. Check first that the cases leave nothing out. "n is even or odd" covers every whole number. "n is prime or composite" does not, because 1 is neither.

Disproof by counterexample ends a general claim with one case where it fails. $n^2+n+41$n² + n + 41 is prime for every n from 0 to 39, and that proves nothing.

A claim that exactly one object exists needs two arguments: produce one object that works, then take any two that work and show they are equal. Proof by induction shows a statement holds at n = 1 and that each case forces the next; it is taught in the sequences and series guide.

See Direct Proof, Proof by the Contrapositive, Proof by Exhaustion, Disproof by Counterexample, Proving Existence and Uniqueness and Proof by Induction.

Two counting arguments with their own names

The pigeonhole principle says that when more objects than boxes are placed into the boxes, some box holds at least two. It proves that a pair exists without saying which pair, and often that is all a proof needs.

Counting by a bijection matches two collections one to one, with nothing left over, to prove they have the same size. A set of n elements has $2^n$2ⁿ subsets, because each subset matches exactly one string of n yes-or-no choices.

See The Pigeonhole Principle and Counting by a Bijection.

Which inequalities are worth knowing by name?

Four. They do the work when a quantity has to be bounded rather than computed.

The triangle inequality says that in any triangle with sides a, b and c, $a+b\ge c$a + b ≥ c. Written as $|a+b|\le |a|+|b|$|a + b| ≤ |a| + |b|, it holds for numbers, vectors and complex numbers.

The arithmetic mean–geometric mean inequality says that for nonnegative a and b, $\frac{\left(a+b\right)}{2}\ge \sqrt{ab}$(a + b)/2 ≥ √(ab), with equality only when a = b. The proof is one square: ${\left(\sqrt{a}-\sqrt{b}\right)}^2\ge 0$(√a − √b)² ≥ 0, so $a-2\sqrt{ab}+b\ge 0$a − 2√(ab) + b ≥ 0. Rearrange to $a+b\ge 2\sqrt{ab}$a + b ≥ 2√(ab) and halve both sides. It finds a minimum without calculus: among rectangles of a fixed area, the square has the smallest perimeter.

The Cauchy–Schwarz inequality says that the dot product of two vectors is at most the product of their lengths, $|a\cdot b|\le |a||b|$|a · b| ≤ |a| |b|, because $a\cdot b=|a||b|\cos \theta$a · b = |a| |b| cos θ and a cosine never exceeds 1.

The growth ordering says that in the long run an exponential outgrows every polynomial, and a polynomial outgrows every logarithm. A large power delays the crossing point but does not remove it.

See The Triangle Inequality, The Arithmetic Mean–Geometric Mean Inequality, The Cauchy–Schwarz Inequality and Polynomial, Exponential and Logarithmic Growth.

How do you find a proof when you are stuck?

Use a heuristic: a method for finding a proof rather than for writing one out.

Working backward from the goal starts at the conclusion and asks what would produce it, then what would produce that, until the requirement is something already known. The proof is then written forward.

Solving a simpler problem first shrinks the problem until it can be done by hand, and the small cases show the rule. Check the rule on a case you counted, then use it on the case you could not.

Going from a special case to every case needs a general argument. Adding the odd numbers in order gives 1, 4, 9, 16, and that is a conjecture until an argument covers every n. Check also that the special case used nothing the general case lacks. A proof that quietly assumes a right angle, or positive numbers, has proved a narrower theorem than it claims.

Finding the flaw in an argument is the reverse skill. In the classic proofs that 1 = 2, the false conclusion means one step is unjustified, and it is usually a division by a − b when a = b, which is division by 0.

See Working Backwards from the Goal, Solving a Simpler Problem First, From a Special Case to Every Case and Finding the Flaw in an Argument.

The mistakes worth naming

• Proving the converse. Check which statement you assumed and which one you reached.
• Assuming what is to be proved. Starting from the conclusion proves nothing unless every step can be reversed.
• Negating a quantifier without swapping it. The negation of "all are" is "at least one is not", never "none are".
• Treating examples as proof. Fermat's conjecture that $2^{2^n}+1$2^(2^n) + 1 is always prime fails at n = 5.
• Cases that do not cover everything. A proof by exhaustion is only as good as the check that the cases are complete.
• Losing a case at a square root or a modulus. $x^2=9$x² = 9 has two solutions, 3 and −3. Dividing an inequality by a negative number reverses it.

Where this leads next

The geometry proofs in the lines, angles and Pythagoras guide are direct proofs with diagrams, and the circle theorems in the congruence and circle theorems guide are a chain of them. Induction is developed with the sequences and series it proves. The pigeonhole principle and bijections are used again in the sets and counting guide.

Learn this properly in the app

Math Challenge teaches each lesson above as an illustrated argument, line by line, with practice questions that explain the step you missed. The catalog runs from first counting to university-entrance mathematics.