Proof, Logic, and Mathematical Reasoning

Mathematics asks not only whether a claim seems true, but why it must be true. A proof is a clear chain of statements that begins with accepted facts and definitions and ends at the claim. This lesson develops the language and main proof methods used from algebra through technical study. Familiarity with algebraic manipulation is helpful; for an extended induction proof involving expansions, see the binomial article.

Statements, Truth, and Quantifiers

A statement (or proposition) is a sentence that is either true or false. “7 is prime” is a true statement; “x + 2 = 9” is not a statement until a value or condition on x is supplied. Definitions matter: an integer is even precisely when it can be written as 2k for some integer k.

Quantifiers tell us how broadly a statement applies.

Symbol and reading	Meaning	Example
∀: “for every”	The claim holds for all objects in the stated set.	∀ integers n, n² ≥ 0.
∃: “there exists”	At least one object in the stated set has the property.	∃ an integer n such that n² = 49.

Order is important. “For every student, there exists a favourite book” allows different books for different students. “There exists a book that every student favours” requires one book for all students.

Worked example: negating quantified claims

Negate: “Every real number has a real square root.”

Original: for every real x, there exists a real y with y² = x.

Negation: there exists a real x for which no real y has y² = x.

Choose x = −1. Since y² ≥ 0 for every real y,
no real y satisfies y² = −1.
Therefore the original statement is false.

In general, negating “for every” changes it to “there exists,” and negating “there exists” changes it to “for every,” while also negating the property.

Conditionals, Converses, and Contrapositives

A conditional statement has the form “if p, then q,” written p ⇒ q. Here p is the hypothesis and q is the conclusion. It makes no promise when p is false. The conditional is false only when p is true and q is false.

Form	For “if n is divisible by 4, then n is even”	Status
Conditional	If 4 divides n, then 2 divides n.	True
Converse: q ⇒ p	If n is even, then 4 divides n.	False: n = 6
Inverse: not p ⇒ not q	If 4 does not divide n, then n is not even.	False: n = 6
Contrapositive: not q ⇒ not p	If n is not even, then 4 does not divide n.	True

A conditional and its contrapositive are logically equivalent: proving either proves the other. A converse is a new claim and needs its own proof or a counterexample.

Worked example: a contrapositive proof

Prove: if n² is even, then n is even, where n is an integer.

Prove the contrapositive: if n is odd, then n² is odd.

If n is odd, n = 2k + 1 for some integer k.
n² = (2k + 1)²
   = 4k² + 4k + 1
   = 2(2k² + 2k) + 1.

The number in parentheses is an integer, so n² is odd.
The contrapositive is true; therefore the original statement is true.

Counterexamples and the Structure of a Proof

One example can support a conjecture, but cannot establish a universal statement. One counterexample disproves a universal statement: it is a permitted input for which the conclusion fails. To disprove “all primes are odd,” 2 is enough.

Write proofs so a reader can check each step. State the domain, introduce variables with the needed property, use definitions or previously proved facts, and explain why each conclusion follows. Testing several values is useful exploration, not a proof of an infinite claim.

Worked example: finding a counterexample

Consider the claim: “If ab is even, then a and b are even.” It is false.

Take a = 2 and b = 3.
Then ab = 6, which is even.
But b = 3 is not even.

Thus the hypothesis holds and the conclusion fails, so this is a counterexample.

The correct related statement is: if ab is odd for integers a, b, then both a and b are odd.

Direct Proof

In a direct proof, assume the hypothesis and use definitions and valid algebra until the conclusion appears. The definition of even and odd numbers often supplies the first line.

Worked example: sum of two odd integers

Prove that the sum of two odd integers is even.

Let a and b be odd integers.
Then a = 2m + 1 and b = 2n + 1 for some integers m and n.

a + b = (2m + 1) + (2n + 1)
      = 2m + 2n + 2
      = 2(m + n + 1).

Because m + n + 1 is an integer, a + b is even.

The proof did not assume particular odd numbers; it used arbitrary ones. That is why it proves the general claim.

Proof by Contradiction

To prove a statement by contradiction, assume its negation and derive an impossibility, such as a number being both even and odd or an inequality contradicting itself. Then the negation cannot be true.

Worked example: √2 is irrational

A rational number can be written as a fraction of integers. Prove that √2 is irrational.

Assume, for contradiction, that √2 = a/b in lowest terms,
where a and b are integers and b ≠ 0.

2 = a²/b², so a² = 2b². Thus a² is even.
By the contrapositive result above, a is even; write a = 2k.

(2k)² = 2b²
4k² = 2b²
b² = 2k².

So b², and hence b, is even. Both a and b are even,
contradicting that a/b was in lowest terms.
Therefore √2 is irrational.

Proof by Cases

When every allowed possibility falls into a small number of exhaustive cases, prove the claim separately in each case. The cases must cover all possibilities and should not silently omit boundary values.

Worked example: absolute value

Prove that |x|² = x² for every real x.

Case 1: x ≥ 0. Then |x| = x, so |x|² = x².

Case 2: x < 0. Then |x| = −x, so |x|² = (−x)² = x².

The two cases cover every real number. Therefore |x|² = x².

Mathematical Induction

Induction proves a statement P(n) for every integer n at or above a starting value. It has two essential parts: a base case and an inductive step. In the step, temporarily assume P(k) for an arbitrary integer k in the range; this is the inductive hypothesis. Use it to prove P(k + 1).

Worked example: sum of the first n positive integers

Prove that 1 + 2 + … + n = n(n + 1)/2 for every integer n ≥ 1.

Base case n = 1:
left side = 1, and 1(1 + 1)/2 = 1. True.

Inductive hypothesis:
Assume 1 + 2 + ... + k = k(k + 1)/2 for some k ≥ 1.

Step from k to k + 1:
1 + 2 + ... + k + (k + 1)
= k(k + 1)/2 + (k + 1)
= (k + 1)(k/2 + 1)
= (k + 1)(k + 2)/2.

This is the formula with n = k + 1. Therefore it holds
for every integer n ≥ 1 by induction.

Do not merely verify many starting values: the step is what connects every case to the next. For a different, more algebra-heavy induction application, consult the binomial article.

Common Mistakes to Avoid

Affirming the converse: from “if p, then q” and q, one cannot conclude p.
Using examples as a universal proof: checking n = 1, 2, 3 does not prove a formula for every n.
Dividing by an expression that could be zero: first justify that it is nonzero, or handle the zero case separately.
Assuming the target: a proof must start from the hypothesis or known facts, not from what it is meant to establish.
Incomplete induction: both a verified base case and a general k to k + 1 step are required.

Practice Set

Is “x² − 1 = 0” a statement as written? Explain.
Write the negation of: “Every integer is either even or odd.”
For “if a quadrilateral is a square, then it has four right angles,” state the converse and say whether it is true.
Give a counterexample to “For every real x, x² > x.”
Prove directly that the product of two even integers is even.
Prove using a contrapositive: if 3 does not divide an integer n, then 3 does not divide n².
Prove by cases that max(x, 0) + max(−x, 0) = |x| for every real x.
Explain the flaw: “All numbers in the list 1, 2, 3, 4, 5 are less than 10; therefore every positive integer is less than 10.”
Use induction to prove 2 + 4 + 6 + … + 2n = n(n + 1) for integers n ≥ 1.
Use contradiction to prove that there is no greatest integer.

Answers

No. Its truth depends on x. It becomes a statement after specifying a value or adding a quantifier, such as “there exists a real x such that ...”.
“There exists an integer that is neither even nor odd.” This negation is false, so the original statement is true.
Converse: if a quadrilateral has four right angles, then it is a square. It is false; a non-square rectangle is a counterexample.
x = 0 works because 0² > 0 is false. Also, x = 1 gives equality, not a strict inequality.
Let a = 2m and b = 2n for integers m, n. Then ab = 4mn = 2(2mn), so the product is even.
Prove the contrapositive: if 3 divides n², then 3 divides n. Any integer has remainder 0, 1, or 2 on division by 3. The squares of these remainders are 0, 1, and 4 ≡ 1 (mod 3). Thus only remainder 0 can give a square divisible by 3. The contrapositive, and hence the original claim, follows.
If x ≥ 0, the left side is x + 0 = x = |x|. If x < 0, it is 0 + (−x) = −x = |x|. These cases cover all real x.
The listed examples are only five positive integers; they do not cover all positive integers. For instance, 10 itself is not less than 10.
Base: for n = 1, 2 = 1(2). Assume 2 + 4 + … + 2k = k(k + 1). Then adding 2(k + 1) gives k(k + 1) + 2(k + 1) = (k + 1)(k + 2), the required formula for k + 1.
Assume a greatest integer G exists. Then G + 1 is an integer and G + 1 > G, contradicting that G was greatest. Therefore no greatest integer exists.