Logic and Proof

Updated 7 October 2026

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 mathematical argument is built from a few kinds of statement. A definition fixes what a word means; it is a choice, so it is neither true nor false. A proposition is a claim that is either true or false. A theorem is a proposition that has been proved, a lemma is a smaller theorem proved on the way to a bigger one, and a corollary follows from a theorem in a step or two. Define a multiple of 3 as 3k for a whole number k. Then "the sum of two multiples of 3 is a multiple of 3" becomes a theorem once 3a + 3b = 3(a + b) is shown, and the same claim for three multiples is a corollary. The labels matter because a proof may use only definitions and statements already proved. A conjecture seems true but has no proof yet. An instance is not a proof: 6 + 9 = 15 illustrates the theorem without proving it.

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?

A conditional statement "if P then Q" is false in only one case: P true and Q false. The contrapositive, "if not Q then not P", fails in exactly that case, so it is true whenever the original is. The converse, "if Q then P", fails when Q is true and P is false, a different case, so it can be false while the original is true. Take "if a number ends in 0, it is divisible by 5". Its contrapositive, "if a number is not divisible by 5, it does not end in 0", is true. Its converse, "if a number is divisible by 5, it ends in 0", is false: 15 = 3 × 5 ends in 5. When both directions hold, the statement is an "if and only if", and each direction needs its own proof. For the original, the breaking case never occurs: a number ending in 0 is a multiple of 10, and 10 = 2 × 5.

It is written $P\Rightarrow Q$P ⇒ Q, with P the hypothesis and Q the conclusion. When P is false the conditional promises nothing, so it cannot be broken.

In symbols the converse is $Q\Rightarrow P$Q ⇒ P, and the contrapositive is not $Q\Rightarrow$Q ⇒ not P. With "if n is a multiple of 4 then n is even", the converse fails at n = 6, while the 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 covers. "For all", written $\forall$∀, claims something of every object in a set; "there exists", written $\exists$∃, claims that at least one object has the property. They are proved and disproved in opposite ways. A for-all claim needs an argument covering every case, and one counterexample disproves it. A there-exists claim needs one example, and disproving it means ruling out every case. So "every prime is odd" falls to the prime 2, while "some square ends in 6" is proved by 4 × 4 = 16. The reason is negation: the negation of a for-all claim is a there-exists claim. The order of quantifiers changes the meaning. "For every x there is a larger y" is true for whole numbers, since y = x + 1 works, but "there is a y larger than every x" claims a largest number and is false. To negate a quantified claim, swap the quantifier and negate what follows it.

"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.

The negation of "every swan is white" is "some swan is not white", not "no swan is white", which claims far more.

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: direct proof, proof by the contrapositive, proof by exhaustion, disproof by counterexample, a uniqueness proof, and proof by induction. A direct proof assumes the hypothesis and takes forced steps to the conclusion. To prove that the product of two odd numbers is odd, write them as 2a + 1 and 2b + 1; their product is 4ab + 2a + 2b + 1, which is 2(2ab + a + b) + 1, so it is odd. For instance, 7 × 9 = 63 = 2 × 31 + 1. The shape of the claim chooses the method. When the hypothesis gives little to work with, as in "if $n^2$n² is odd then n is odd", prove the contrapositive. A few cases call for exhaustion, a false claim for one counterexample, and a claim about every whole number for induction. A proof is complete only when each step follows from earlier ones, so name what justifies every line.

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 inequalities are worth knowing by name: the triangle inequality, the AM-GM inequality, the Cauchy-Schwarz inequality, and the growth ordering of exponentials, polynomials and logarithms. Each bounds a quantity when an exact value is hard to find or not needed. The AM-GM inequality is the most used: for nonnegative a and b, the arithmetic mean $\frac{\left(a+b\right)}{2}$(a + b)/2 is at least the geometric mean $\sqrt{ab}$√(ab). With a = 9 and b = 1, (9 + 1) ÷ 2 = 5 and $\sqrt{9}=3$√9 = 3, and $5\ge 3$5 ≥ 3. It holds because a square is never negative: the square of $\sqrt{a}-\sqrt{b}$√a − √b is at least 0, which rearranges into the inequality. Equality needs a = b, and that is how the inequality finds a minimum. For x > 0, $x+\frac{1}{x}\ge 2$x + 1/x ≥ 2, with the minimum at x = 1, because the geometric mean of x and $\frac{1}{x}$1/x is 1. Try a value: x = 4 gives $4+\frac{1}{4}$4 + 1/4, which is above 2.

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.

In symbols the inequality is $\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. 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?

When you are stuck, use a heuristic: a method for finding a proof rather than writing one. Three do most of the work: working backward from the goal, solving a simpler version first, and moving from special cases to the general one. Suppose you want the number of diagonals of an n-sided polygon. Count small cases: a square has 2, a pentagon 5, and a hexagon 9. Each vertex joins n − 3 others by a diagonal, and each diagonal has two ends, which suggests $\frac{n\left(n-3\right)}{2}$n(n − 3)/2. Small cases help because they can be checked by hand and they expose the pattern a general argument must explain. A pattern is not a proof, though: the counting argument proves the formula, not the table. Working backward changes the order of writing: you find the steps from the goal, then write the proof forward from the hypothesis. Test the formula on a counted case: for a hexagon, 6 × 3 ÷ 2 = 9.

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.

Solving a simpler problem first shrinks the problem until it can be done by hand, and the small cases show the rule.

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.