HSC Study

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.

TTTTT
TFFFT
FTTTF
FFTTT

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?

Select one answer

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

Select one answer

Hint 1Swap the two parts.

Hint 2Converse of is .

Hint 3Do not negate.

CheckpointAnswer before reading on.

What is the contrapositive of "If , then "?

Select one answer

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 ?

Select one answer

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

Select one answer

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

Select one answer

Hint 1Test the converse with a counter-example.

Hint 2Squaring loses the sign.

Hint 3.

CheckpointAnswer before reading on.

For real , "" is ______ for "".

Select one answer

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

Select one answer

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?

Select one answer

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?

Select one answer

Hint 1 means for all.

Hint 2 means real.

Hint 3Read it aloud.

CheckpointAnswer before reading on.

Which statement is false?

Select one answer

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

Select one answer

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

Select one answer

Hint 1¬∃ becomes ∀¬.

Hint 2Negate the equation.

Hint 3For every n, …

CheckpointAnswer before reading on.

Which statement is true for real numbers?

Select one answer

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

Select one answer

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?

Select one answer

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.