Skip to content
Axioma

Mathematics · Advanced · 30 min · Chapter 12 of 28

The language of proof

Definitions, quantifiers, and the handful of proof shapes — direct, contrapositive, contradiction, counterexample — that every later course assumes.

Read first: Discrete mathematics, Algebra

The idea

From here on, mathematics is less about getting a number and more about showing that a statement holds for every object of a certain kind. A statement is a sentence that is true or false. An open sentence has a variable; a quantifier closes it. “For every real x, x² ≥ 0” is a statement. “x² ≥ 0” is not, until you say for which x. The negation of “for all x, P(x)” is “there exists an x such that not P(x).” The negation of “there exists” is “for all, not.” Getting this wrong invalidates the proof before it starts.

A direct proof assumes the hypothesis and walks, by definitions and previously proved facts, to the conclusion. A proof by contrapositive proves “if not Q, then not P” instead of “if P, then Q”; the two implications are equivalent. A proof by contradiction assumes the hypothesis and the negation of the conclusion, then reaches a statement that is false, such as 1 = 0. A counterexample is the honest way to kill a universal claim: you do not argue that it feels unlikely, you exhibit one object that fails it.

Two habits matter more than vocabulary. First, when you say “let x be arbitrary,” you must not smuggle in extra properties. Second, an example can suggest a theorem and can never replace one, unless the claim was existential — in which case the example is the proof. The phrase “it is obvious” is allowed only when you could, if asked, fill in the step. Readers of analysis and algebra will ask.

Hold onto this

  1. A definition is a biconditional you are allowed to use in both directions.
  2. “For all” and “there exists” do not commute. Their order is the meaning.
  3. To disprove a universal claim, one counterexample is enough.
  4. Contradiction assumes the negation and derives an impossibility.

Formulas

Contrapositive

An implication and its contrapositive are the same statement. The converse is a different statement.

⇒
Implies
¬
Not

Negating quantifiers

The negation of a universal claim is an existence claim about a failure.

∀
For all
∃
There exists

De Morgan

The negation of an and is the or of the negations. There is a twin with and and or swapped.

∧, ∨
And, or

Worked examples

1. A direct proof

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

  1. Assume n is even. By definition, n = 2k for some integer k.
  2. Then n² = 4k² = 2(2k²), which is 2 times an integer.
  3. So n² is even.

Evenness of n forces evenness of n², by the definition of even.

2. A counterexample

Disprove the claim that |x + y| = |x| + |y| for all real x and y.

  1. The claim is universal. One pair that fails is enough.
  2. Take x = 1 and y = −1.
  3. |1 + (−1)| = 0, while |1| + |−1| = 2.

The equality is false in general. It holds when x and y have the same sign, which is a different theorem.

Try these

Write the negation of: for every ε > 0 there exists N such that for every n > N, |aₙ| < ε.

Prove by contrapositive: if n² is even, then n is even.

Common mistakes

  • The converse of a true implication can be false. “If it is raining, the ground is wet” does not mean a wet ground implies rain.
  • Proving a statement for n = 1, 2, and 3 is not a proof for all n.
  • “For all x there exists y” lets y depend on x. “There exists y for all x” demands one y that works for every x.