Use the language of proof, prove results by contradiction and contrapositive, and disprove statements by counterexample

What this dot point is asking

NESA wants you to write and read mathematical arguments with precision. You must use logical language correctly (implication, converse, contrapositive, equivalence, "for all", "there exists"), construct direct proofs, prove statements by contradiction and by the contrapositive, disprove false statements with a single counterexample, and recognise the standard logical fallacies that turn a plausible-looking argument into an invalid one. This dot point is the grammar of the whole Proof module: every later technique, including induction and inequality proofs, is written in the language set up here.

The language of proof

A statement (or proposition) is a sentence that is definitely either true or false. An implication $P \implies Q$ ("if $P$ then $Q$") asserts that whenever $P$ holds, $Q$ holds. Here $P$ is the hypothesis (the assumption) and $Q$ the conclusion. The implication says nothing about what happens when $P$ is false; in that case it is automatically counted as true (it is "vacuously true"), which is why a single example with $P$ false can never test an implication.

Three related statements are built from $P \implies Q$, and keeping them apart is the most common source of error in the whole module:

• Converse: $Q \implies P$. The converse is a genuinely different claim and is not logically equivalent to the original. "If it is raining then the ground is wet" is true; its converse "if the ground is wet then it is raining" is false (someone may have used a hose).
• Contrapositive: $\lnot Q \implies \lnot P$. The contrapositive is logically equivalent to $P \implies Q$: the two are true in exactly the same situations, so proving one proves the other.
• Negation: $\lnot(P \implies Q)$ is true exactly when $P$ is true and $Q$ is false. This is the statement you assume at the start of a proof by contradiction.

The quantifiers "for all" ($\forall$) and "there exists" ($\exists$) bind variables and tell you the scope of a claim. Negation swaps them: the negation of $\forall x\, P(x)$ is $\exists x\, \lnot P(x)$, and the negation of $\exists x\, P(x)$ is $\forall x\, \lnot P(x)$. Knowing how to negate a quantified statement is essential, because it is precisely the negation you must establish to disprove the original or to run a contradiction argument.

If and only if (equivalence)

If both $P \implies Q$ and $Q \implies P$ hold, we write $P \iff Q$ ("$P$ if and only if $Q$", often abbreviated "iff"), and say $P$ and $Q$ are equivalent. An "if and only if" statement is really two statements bundled together, and a complete proof must establish both directions separately. A common shorthand to keep them straight: $P \implies Q$ is the "only if" direction ($P$ holds only if $Q$ does) and $Q \implies P$ is the "if" direction.

The danger is doing half the work. Proving "$x^2 = 4 \iff x = 2$" by only checking that $x = 2$ gives $x^2 = 4$ proves just one direction; the other direction is in fact false, because $x = -2$ also satisfies $x^2 = 4$. Always prove forwards and backwards, and watch for the direction that quietly fails.

Direct proof

A direct proof of $P \implies Q$ assumes $P$ and deduces $Q$ through valid algebraic or logical steps. For example, to prove that the sum of two even integers is even: let $a = 2m$ and $b = 2n$ for integers $m, n$. Then $a + b = 2m + 2n = 2(m + n)$, which is a multiple of $2$, hence even. The skill is to translate the words into algebra you can manipulate ("even" becomes "$2 \times$ integer"), do the algebra, then translate back.

Proof by contradiction

To prove a statement $S$ by contradiction, assume $\lnot S$ and derive a logical impossibility, a contradiction such as $1 = 0$, or a number that is simultaneously even and odd, or a fraction in lowest terms whose numerator and denominator share a factor. Since the assumption forces an impossibility, $\lnot S$ cannot hold, so $S$ is true.

The classic example is the irrationality of $\sqrt{2}$. Suppose, for contradiction, that $\sqrt{2}$ is rational. Then $\sqrt{2} = \dfrac{p}{q}$ where $p, q$ are integers with no common factor (the fraction is in lowest terms) and $q \neq 0$. Squaring gives

So $p^2$ is even, which forces $p$ to be even (if $p$ were odd, $p^2$ would be odd). Write $p = 2k$. Then $p^2 = 4k^2 = 2q^2$, so $q^2 = 2k^2$, meaning $q^2$ is even and hence $q$ is even. But then $p$ and $q$ share the factor $2$, contradicting the assumption that $\dfrac{p}{q}$ is in lowest terms. The assumption is impossible, so $\sqrt{2}$ is irrational.

Notice the two features that make a contradiction proof work: you must assume the exact negation of what you want, and you must reach a genuine impossibility, not merely a surprising fact.

Proof by contrapositive

Because $P \implies Q$ is equivalent to $\lnot Q \implies \lnot P$, you may prove the contrapositive instead. This is the right move whenever assuming $\lnot Q$ gives you something concrete to compute with while assuming $P$ gives you very little.

For example, prove: if $n^2$ is odd then $n$ is odd. Arguing directly from "$n^2$ is odd" is awkward, but the contrapositive, "if $n$ is even then $n^2$ is even", is immediate. Let $n = 2m$. Then $n^2 = 4m^2 = 2(2m^2)$, which is even. The contrapositive holds, so the original statement holds. The general signpost: if the hypothesis is a statement of the form "something is not nice" or "something is prime", the contrapositive often turns it into a friendlier "something is nice" or "something is composite".

Contradiction versus contrapositive

The two are close cousins and students often blur them. A contrapositive proof of $P \implies Q$ assumes $\lnot Q$ and derives $\lnot P$ by a direct chain, ending cleanly with no contradiction. A contradiction proof of the same implication assumes $P$ and $\lnot Q$ together and derives any impossibility at all. The contrapositive is usually tidier when it applies; reach for full contradiction when the statement is not an implication (for example "$\sqrt 2$ is irrational" is not naturally "if ... then ...") or when assuming both halves gives you more to work with.

Disproof by counterexample

A statement of the form "for all $x$, $P(x)$" is false if even one value violates it. To disprove it you supply a single explicit counterexample; you do not need, and should not attempt, a general argument. For an implication "for all $x$, if $P(x)$ then $Q(x)$", the counterexample must be a value that satisfies the hypothesis $P(x)$ and fails the conclusion $Q(x)$. An example that fails $P(x)$ proves nothing, because the implication is vacuously true there.

For example, the claim "every odd number is prime" fails because $9$ is odd but $9 = 3 \times 3$ is composite. A single value settles it. By contrast, to disprove "for all primes $p$, $2^p - 1$ is prime" you cannot use $p = 4$ (not prime, so it does not test the claim); you need $p = 11$, where $2^{11} - 1 = 2047 = 23 \times 89$ is composite.

Common logical fallacies

Markers are trained to spot a handful of recurring invalid moves. Knowing them by name helps you avoid them under pressure:

• Affirming the consequent. From $P \implies Q$ and $Q$, concluding $P$. This is just using the converse; it is invalid.
• Denying the antecedent. From $P \implies Q$ and $\lnot P$, concluding $\lnot Q$. Also invalid; only the contrapositive (from $\lnot Q$ conclude $\lnot P$) is valid.
• Circular reasoning (begging the question). Using the statement you are trying to prove as one of your steps. Common when an "iff" is half-assumed.
• Proving the converse by mistake. Setting out to prove $P \implies Q$ but actually arguing $Q \implies P$.
• Generalising from examples. Checking the claim for $n = 1, 2, 3$ and declaring it true for all $n$. Examples can disprove a universal claim but never prove one; that is what induction or a general argument is for.
• Dividing by a quantity that might be zero, or taking a square root that introduces a spurious sign. Both can manufacture a "proof" of a false statement.

How exam questions ask about the nature of proof

• "Prove that ... is irrational" or "Prove that there are infinitely many ...": classic proof by contradiction. Assume the negation (it is rational; there are finitely many) and reach an impossibility.
• "Prove that if $P$ then $Q$" where assuming $P$ is awkward: try the contrapositive, especially when $P$ involves "prime", "not", or "odd/even".
• "Show that there is no integer / no real number such that ...": a non-existence claim; assume one exists and derive a contradiction, often via a parity or divisibility argument.
• "Disprove the statement ..." or "Is it true that ...? Justify.": hunt for a counterexample first; only switch to a proof if no counterexample exists. State clearly that one counterexample suffices.
• "Prove that ... if and only if ...": two separate proofs, one for each direction. Label them.
• "Explain why the following argument is invalid": name the fallacy (usually affirming the consequent or generalising from examples) and give the step where it breaks.

Edge cases and what-ifs

• Vacuous truth. "If $P$ then $Q$" is automatically true whenever $P$ is false. So an example with $P$ false can neither prove nor disprove an implication; to disprove, you must satisfy $P$.
• Negating compound statements. The negation of "$P$ and $Q$" is "$\lnot P$ or $\lnot Q$"; the negation of "$P$ or $Q$" is "$\lnot P$ and $\lnot Q$". Getting these right matters when you set up a contradiction.
• A "surprising" result is not a contradiction. A contradiction proof must reach a genuine impossibility (such as $1 = 0$), not merely an unexpected or ugly statement.
• One direction of an iff can be false. When a question asks you to prove or test an "if and only if", check each direction independently; it is common for one to hold and the other to fail.
• Existence versus universal. To prove "there exists" you exhibit one example; to disprove "for all" you exhibit one counterexample. To prove "for all" you need a general argument, and to disprove "there exists" you need a general argument that no example works.