The Language of Proof
Statements, implications, converses, negations and contrapositives; the symbols ⇒, ⇔ and =; the quantifiers for all and there exists; and using examples and counter-examples.
45 min · Proof
The full teaching. Start here.
The short version
- A statement is a sentence that is either true or false.
- For the implication ("if then "):
- converse: (swap);
- contrapositive: (swap and negate), which is always equivalent to the original;
- negation: and not .
- means the implication holds both ways ("if and only if").
- joins expressions with equal values; and join statements.
- is ; is .
- One counter-example disproves a "for all" claim. Examples never prove one, but one example proves a "there exists" claim.
Statements and implications
- Statement
A sentence that is either true or false, but not both. " is prime" is a statement. "" is not, until is given a value or a quantifier ("for all ", "there exists ").
Most theorems have the form if , then , written . Here is the hypothesis and the conclusion. We also say " implies ", " is sufficient for ", and " is necessary for ".
An implication is false in exactly one situation: when is true and is false. If is false, the implication makes no claim, and counts as true.
| T | T | T | T | T |
| T | F | F | F | T |
| F | T | T | T | F |
| F | F | T | T | T |
The table shows the key fact: the contrapositive has exactly the same truth values as the original, while the converse can differ.
- Converse, contrapositive and negation
For : the converse is ; the contrapositive is ; the negation is " and not ", the one case that makes the implication false.
Worked example4 marks
Converse, contrapositive and negation
For integers , consider "if is divisible by , then is even." Write its converse, contrapositive and negation, and decide whether each is true.
Identify P and Q
Everything follows mechanically from these.
: is divisible by . : is even. The original is true, since .
Converse
Swap.
"If is even, then is divisible by ." False: .
Contrapositive
Swap and negate.
"If is odd, then is not divisible by ." True, because it is equivalent to the original.
Negation
P and not Q.
"There is an integer divisible by that is odd." False, because the original is true.
Answer
Converse false (); contrapositive true; negation false.
Is that answer sensible?
Exactly one of a statement and its negation is true: the original is true and the negation is false. Consistent.
CheckpointAnswer before reading on.
Which of these is a statement in the logical sense?
Hint 1A statement is true or false.
Hint 2Questions and commands are neither.
Hint 3Expressions with a free variable are neither until the variable is fixed.
CheckpointAnswer before reading on.
What is the converse of "If n is divisible by 4, then n is even"?
Hint 1Swap the two parts.
Hint 2Converse of is .
Hint 3Do not negate.
CheckpointAnswer before reading on.
What is the contrapositive of "If , then "?
Hint 1Contrapositive of is .
Hint 2Swap and negate.
Hint 3The negation of is .
CheckpointAnswer before reading on.
What is the negation of "" for a real number ?
Hint 1Exactly one of the statement and its negation is true.
Hint 2The opposite of is not .
Hint 3Include equality.
CheckpointAnswer before reading on.
What is the negation of "n is even and n > 10"?
Hint 1Negating "and" gives "or".
Hint 2Negate each part.
Hint 3De Morgan's law.
CheckpointAnswer before reading on.
Which implication is true but has a false converse? (All variables are real.)
Hint 1Test the converse with a counter-example.
Hint 2Squaring loses the sign.
Hint 3.
CheckpointAnswer before reading on.
For real , "" is ______ for "".
Hint 1P sufficient for Q means P ⇒ Q.
Hint 2Does x > 5 force x > 3?
Hint 3Does x > 3 force x > 5?
Exam question
Standard · about 4 min
2 marks
Explain why and its contrapositive always have the same truth value, but and its converse need not.
Hint 1When is P ⇒ Q false?
Hint 2When is ¬Q ⇒ ¬P false?
Hint 3Compare with Q ⇒ P.
Where students lose marks on this one
Assuming the converse always holds.
Why it happens: Treating ⇒ as ⇔.
Give a counter-example to show the converse can fail.
Written for this site.
Exam question
Standard · about 3 min
2 marks
State the converse of "if then " (for real ), and decide whether it is true.
Hint 1Swap the parts.
Hint 2Try negative x.
Hint 3.
Where students lose marks on this one
Saying it is true because the original is.
Why it happens: Assuming converses inherit truth.
Test it separately.
Written for this site.
Exam question
Standard · about 4 min
3 marks
By proving the contrapositive, show that if is even then is even, for integers .
Hint 1Contrapositive: n odd ⇒ n² odd.
Hint 2Let .
Hint 3.
Where students lose marks on this one
Proving the converse instead.
Why it happens: Swapping without negating.
n even ⇒ n² even is the converse, not the contrapositive.
Written for this site.
Common mistake
The negation of 'if it rains, the ground is wet' is 'if it rains, the ground is not wet'.
Why it happens: The negation of an implication is not another implication.
"If then " is false only when happens and does not. So its negation is " and not ": "it rains and the ground is not wet".
Implication, equivalence and equality
These three symbols do different jobs:
- says two expressions have the same value: .
- says that if statement is true, statement is true: .
- says each implies the other (" if and only if ", often "iff"): .
When solving equations, each line is a statement, so the lines should be joined by or , never by . Use only when every step can be reversed. Squaring both sides, for example, is only , which is why it can introduce false solutions.
CheckpointAnswer before reading on.
Which statement is true when written with ? ( real.)
Hint 1Both directions must hold.
Hint 2Check the reverse.
Hint 3Look for a hidden sign.
CheckpointAnswer before reading on.
A student writes . What is wrong?
Hint 1What does = join?
Hint 2Numbers or statements?
Hint 3Use ⇒ or ⇔ between statements.
Exam question
Standard · about 3 min
2 marks
Write "an integer is odd if and only if is odd" as two implications, and name each direction.
Hint 1iff means both ways.
Hint 2Which part is P?
Hint 3 and .
Where students lose marks on this one
Writing only one implication.
Why it happens: Treating iff as if.
An iff statement needs both directions.
Written for this site.
Quantifiers
- means for all: .
- means there exists: .
To negate, flip the quantifier and negate what follows:
The order of quantifiers matters. (every number has a bigger one) is true, because can depend on . (one number is bigger than all numbers) is false.
CheckpointAnswer before reading on.
What does say?
Hint 1 means for all.
Hint 2 means real.
Hint 3Read it aloud.
CheckpointAnswer before reading on.
Which statement is false?
Hint 1Test each claim.
Hint 2 is not an integer.
Hint 3One example proves an ∃ claim.
CheckpointAnswer before reading on.
What is the negation of "for all real x, x² > 0"?
Hint 1¬∀ becomes ∃¬.
Hint 2Negate the inside.
Hint 3The negation of is .
CheckpointAnswer before reading on.
What is the negation of "there exists an integer n with n² = 2n + 1"?
Hint 1¬∃ becomes ∀¬.
Hint 2Negate the equation.
Hint 3For every n, …
CheckpointAnswer before reading on.
Which statement is true for real numbers?
Hint 1Order of quantifiers matters.
Hint 2Can y depend on x?
Hint 3Is there one y bigger than every x?
Examples and counter-examples
- To prove "for all , ", you need a general argument. Checking examples, however many, is not enough.
- To disprove it, one counter-example is enough: a single for which is false.
- To prove "there exists with ", one example is enough.
Worked example3 marks
Disproving with a counter-example
Disprove: "for all real numbers and , ." State the negation you have proved.
Choose simple values
One failure is enough.
Take , : but .
Negation
¬∀ is ∃¬.
We have shown "".
Answer
, gives , so the statement is false.
Is that answer sensible?
The statement holds when and , which shows why a few "nice" examples can mislead. One counter-example still settles it.
CheckpointAnswer before reading on.
Which values give a counter-example to "if then "?
Hint 1Try negative numbers.
Hint 2Need a > b but a² ≤ b².
Hint 3.
CheckpointAnswer before reading on.
A student checks that a formula works for n = 1, 2, …, 100 and concludes it holds for all positive integers. What is the correct comment?
Hint 1Examples versus proof.
Hint 2Could n = 101 fail?
Hint 3What would prove it?
Exam question
Standard · about 3 min
2 marks
Disprove: " is prime for every positive integer ."
Hint 1One counter-example is enough.
Hint 2Try n = 40.
Hint 3.
Where students lose marks on this one
Checking n = 1 to 10 and concluding it is true.
Why it happens: Treating examples as proof.
Examples cannot prove a "for all" claim.
Written for this site.
Exam question
Standard · about 3 min
2 marks
Disprove: "." Then write the negation of the statement.
Hint 1Try small n.
Hint 2: vs .
Hint 3¬∀ is ∃¬.
Where students lose marks on this one
Using n = 1 as a counter-example.
Why it happens: Not checking the arithmetic.
2¹ = 2 > 1 = 1², so n = 1 satisfies it.
Written for this site.
Exam question
Harder · about 6 min
4 marks
Let P be the statement "If a quadrilateral is a square, then its diagonals are equal in length." (a) Write the contrapositive and state whether it is true. (b) Write the converse and decide whether it is true. (c) Write the negation of P.
Hint 1Contrapositive has the same truth value.
Hint 2Rectangle.
Hint 3 is .
Where students lose marks on this one
Writing the negation as "if it is a square then its diagonals are not equal".
Why it happens: Negating only the conclusion.
The negation of an implication is "P and not Q".
Written for this site.
What lifts this to a Band 6
When asked for a converse, contrapositive or negation, first write ": …" and ": …" on separate lines, then build the answer from them. Most lost marks come from negating a compound part carelessly: the negation of "" is "", the negation of "and" is "or", and the negation of "for all" is "there exists".
Proof by contrapositive versus contradiction
To prove you can prove instead. This is often easier when gives you something concrete to work with. For example, "if is even then is even" is awkward directly, but its contrapositive, "if is odd then is odd", is one line of algebra.
Proof by contradiction is related but more general: assume and together, and derive something impossible. The next lesson uses it to prove that numbers such as and are irrational.