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, and disprove false statements with a single counterexample.

The language of proof

A statement is a sentence that is 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 and $Q$ the conclusion.

Three related statements matter:

• Converse: $Q \implies P$. The converse is not logically equivalent to the original.
• Contrapositive: $\lnot Q \implies \lnot P$. The contrapositive is logically equivalent to $P \implies Q$.
• Negation: $\lnot(P \implies Q)$, which is true exactly when $P$ is true and $Q$ is false.

If both $P \implies Q$ and $Q \implies P$ hold, we write $P \iff Q$ ("$P$ if and only if $Q$"), and $P$ and $Q$ are equivalent. The quantifiers "for all" ($\forall$) and "there exists" ($\exists$) bind variables; negating $\forall x\, P(x)$ gives $\exists x\, \lnot P(x)$.

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.

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 both even and odd). Since the assumption forces an impossibility, $\lnot S$ is false, 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.

Proof by contrapositive

Because $P \implies Q$ is equivalent to $\lnot Q \implies \lnot P$, you may prove the contrapositive instead. This is useful when assuming $\lnot Q$ gives more concrete information than assuming $P$.

For example, prove: if $n^2$ is odd then $n$ is odd. The contrapositive is: if $n$ is even then $n^2$ is even. Let $n = 2m$. Then $n^2 = 4m^2 = 2(2m^2)$, which is even. The contrapositive holds, so the original statement holds.

Disproof by counterexample

A statement of the form "for all $x$, $P(x)$" is false if even one value violates it. To disprove it, supply a single explicit counterexample; you do not need a general argument.

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.