VCE Specialist Mathematics

Statements and conjectures

A statement (or proposition) is a sentence that is either true or false, never both. "$7$ is prime" and "every square number is even" are statements, the first true and the second false. "$x + 2 = 5$" is not a statement on its own, because its truth depends on $x$; it becomes one when $x$ is given a value or quantified.

A conjecture is a statement put forward as possibly true, which has then to be proved or disproved. Mathematicians usually reach one by looking at examples and spotting a pattern. The values $n^2 - n + 41$ are prime for $n = 1, 2, 3, \dots, 40$, which might suggest that the expression is always prime, but $n = 41$ gives $41^2$, which is not. Examples therefore support a conjecture without establishing it, whereas one failure disproves it.

Connectives

Statements are combined with the connectives "and" ($\wedge$), "or" ($\vee$) and "not" ($\neg$). In mathematics "or" is inclusive: $P \vee Q$ is true when $P$ is true, when $Q$ is true, or when both are.

The negation of "$P$ and $Q$" is "not $P$ or not $Q$", and the negation of "$P$ or $Q$" is "not $P$ and not $Q$". For example, the negation of "$x > 2$ and $x < 5$" is "$x \le 2$ or $x \ge 5$".

Implications

The implication $P \Rightarrow Q$ ("if $P$ then $Q$", "$P$ implies $Q$") says that whenever $P$ is true, $Q$ is also true. It is false in exactly one case, when $P$ is true and $Q$ is false.

When $P$ is false the implication makes no claim, so it counts as true (it is vacuously true). The statement "if $x$ is a multiple of $4$ then $x$ is even" is not contradicted by the number $7$, which is neither.

Converse, inverse and contrapositive

From $P \Rightarrow Q$ three related statements can be formed.

The contrapositive is logically equivalent to the original, which is why proving it proves the original. Take "if I have a tiger then I have a cat". Its contrapositive is "if I do not have a cat then I do not have a tiger", which is true for the same reason. The converse, "if I have a cat then I have a tiger", is false.

The converse of a true statement can be true or false: "if $x = 2$ then $x^2 = 4$" is true, but its converse "if $x^2 = 4$ then $x = 2$" is false because $x = -2$ also works.

Equivalence and "if and only if"

If both $P \Rightarrow Q$ and $Q \Rightarrow P$ hold, the statements are equivalent, written $P \Leftrightarrow Q$ and read "$P$ if and only if $Q$". To prove an "if and only if" statement, prove both directions separately, unless every step of one argument is reversible.

An integer is divisible by $6$ if and only if it is divisible by both $2$ and $3$. Each direction needs its own argument: if $6 \mid n$ then $n = 6k = 2(3k) = 3(2k)$, and if $2 \mid n$ and $3 \mid n$ then $n = 2a$ and $3 \mid 2a$, so $3 \mid a$ because $3$ shares no factor with $2$, giving $6 \mid n$.

Necessary and sufficient conditions

When $P \Rightarrow Q$, the condition $P$ is sufficient for $Q$ (knowing $P$ is enough to be sure of $Q$) and $Q$ is necessary for $P$ (if $Q$ fails, $P$ cannot hold). When $P \Leftrightarrow Q$, each is necessary and sufficient for the other.

For real $x$, "$x > 3$" is sufficient for "$x^2 > 9$", since $x > 3$ forces $x^2 > 9$. It is not necessary, because $x = -4$ has $x^2 > 9$ without $x > 3$. Being a square is necessary for a number to be a perfect fourth power, but it is not sufficient, since $9$ is a square and not a fourth power.

Quantifiers

A statement about a variable needs to say how many values of it the claim covers.

• The universal quantifier $\forall$, "for all" or "for every": $\forall x \in \mathbb{R},\ x^2 \ge 0$.
• The existential quantifier $\exists$, "there exists" or "for some": $\exists x \in \mathbb{R},\ x^2 = 2$.

The set the variable comes from matters. "$\exists x,\ x^2 = 2$" is true over $\mathbb{R}$ and false over $\mathbb{Q}$, since $\sqrt{2}$ is irrational. "There exists an $x$ with $x^2 = -1$" is false over $\mathbb{R}$ and true over $\mathbb{C}$.

Negating quantified statements

To negate a statement with a quantifier, swap the quantifier and negate what follows.

The negation of "every prime is odd" is "some prime is even", which is true because of $2$. The negation of "there is a real $x$ with $x^2 + 1 = 0$" is "for every real $x$, $x^2 + 1 \ne 0$", which is true. With two quantifiers, each is swapped in turn: the negation of $\forall x\ \exists y,\ y > x$ is $\exists x\ \forall y,\ y \le x$.

Examples and counter-examples

An example cannot prove a universal statement, because no number of cases covers every case. A single counter-example disproves one, because a statement that holds "for all $x$" fails as soon as it fails for one $x$.

To disprove "for all real $x$, $x^2 > x$", take $x = \tfrac{1}{2}$: then $x^2 = \tfrac{1}{4}$, which is less than $\tfrac{1}{2}$. To disprove "if $f'(a) = 0$ then $f$ has a turning point at $x = a$", take $f(x) = x^3$ and $a = 0$: the derivative $3x^2$ is zero at $0$, but the gradient is non-negative on both sides, so there is a stationary point of inflection and no turning point.

An existence claim ("there exists") is the opposite: one example proves it, and showing that it fails for some values disproves nothing. Disproving "there exists $x$ such that $\dots$" needs an argument covering every $x$.

An implication is disproved by a case where $P$ holds and $Q$ fails. For "if $n$ is prime then $n$ is odd", the counter-example is $n = 2$. A counter-example to "if $f(0) = 0$ then $f$ has a point of inflection at $x = 0$" is $f(x) = x^2$, which has a minimum at the origin.

Stating what has to be proved

Before writing a proof, put the claim into the form $P \Rightarrow Q$ (or $P \Leftrightarrow Q$, or a quantified statement), name the assumptions $P$, and name the goal $Q$. "The sum of two odd integers is even" becomes: for all integers $a$ and $b$, if $a$ and $b$ are odd then $a + b$ is even. The same statement tells you which proof technique suits it: a direct argument from the assumptions, an argument from the contrapositive, or a contradiction.