NSW HSC Mathematics Extension 2

Statements

A statement, also called a proposition, is a sentence with a definite truth value: it is true or it is false, and never both. "$7$ is prime" is a statement (true), "$2 + 2 = 5$" is a statement (false), and "$x > 3$" is not a statement on its own, because its truth depends on the value of $x$. It becomes a statement once $x$ is given a value or is quantified, as in "for all real $x$, $x^2 \ge 0$".

Statements are usually named with capital letters such as $P$ and $Q$, and new statements are built from them with connectives.

Connectives

The conjunction $P \land Q$ is read "$P$ and $Q$" and is true only when both $P$ and $Q$ are true. The disjunction $P \lor Q$ is read "$P$ or $Q$" and is true when at least one of them is true, so it includes the case where both are true.

The negation of $P$ is "not $P$", written $\neg P$ or $\sim P$. It is true exactly when $P$ is false, and negating twice returns the original statement:

The implication "if $P$ then $Q$" is written $P \Rightarrow Q$ or $P \to Q$ and read "$P$ implies $Q$". The statement $P$ is the hypothesis and $Q$ the conclusion. An implication is false in exactly one situation: $P$ true and $Q$ false. When $P$ is false the implication is true whatever $Q$ is, because nothing has been promised. For example, the statement "if $x = 3$ then $x^2 = 10$" is true when it is applied to $x = 5$, because its hypothesis is false there and nothing is claimed. It is false when applied to $x = 3$, because the hypothesis holds and the conclusion does not.

The truth values can be set out in a table.

Quantifiers

Two quantifiers turn a sentence about a variable into a statement.

• $\forall$ means "for all" or "for every". The statement $\forall x \in \mathbb{R},\ x^2 \ge 0$ says every real number has a non-negative square.
• $\exists$ means "there exists" or "there is at least one". The statement $\exists x \in \mathbb{Z},\ x^2 = 49$ says some integer has square $49$.

The set the variable is drawn from matters. "$\exists x,\ x^2 = 2$" is true over $\mathbb{R}$ and false over $\mathbb{Q}$, and "$\exists x,\ x^2 = -1$" is false over $\mathbb{R}$ and true over $\mathbb{C}$.

A statement with $\forall$ is shown false by a single example that fails, which is a counterexample. A statement with $\exists$ is shown true by a single example that works, but showing it false needs an argument covering every possible value.

Negating statements

Negation has to be done carefully, because the natural-sounding opposite is often wrong. The negation of "all the students passed" is "at least one student did not pass", and not "no student passed".

The rules are:

The second and third rows say that negating a conjunction or a disjunction swaps the connective and negates each part. They are often called De Morgan's laws. The fourth row says that an implication fails only when its hypothesis holds and its conclusion does not.

The negation of an inequality uses the complementary one: $\neg(a > b)$ is $a \le b$, and $\neg(a = b)$ is $a \ne b$.

Examples

Negate "$\forall x \in \mathbb{Z},\ x^2 \text{ is odd}$". The negation swaps the quantifier and negates the property: $\exists x \in \mathbb{Z}$ such that $x^2$ is even. The original is false and its negation is true, since $x = 2$ gives $4$.

Negate "$\exists n \in \mathbb{N},\ n > 5 \land n \text{ is even}$". It becomes $\forall n \in \mathbb{N},\ n \le 5 \lor n \text{ is odd}$.

Negate "if $x > 2$ then $x^2 > 4$". Using $\neg(P \Rightarrow Q) = P \land \neg Q$ it becomes "$x > 2$ and $x^2 \le 4$", which is impossible for real $x$, which agrees with the fact that the original implication is true.

Negate "for every real $\varepsilon > 0$ there is an integer $N$ with $1/N < \varepsilon$". Working from the left, $\forall$ becomes $\exists$ and then $\exists$ becomes $\forall$, and the last inequality is reversed: there is a real $\varepsilon > 0$ such that for every integer $N$, $1/N \ge \varepsilon$. A statement with several quantifiers is negated one quantifier at a time, from the outside in, and the order of the quantifiers is kept.

Order of quantifiers

The order of different quantifiers changes the meaning. Over the real numbers, $\forall x\ \exists y,\ y > x$ is true, since for any $x$ we may take $y = x + 1$. But $\exists y\ \forall x,\ y > x$ says one number exceeds every real number, which is false.

Using statements in mathematics

A result in mathematics is usually a true implication, "if $P$ then $Q$", often with a quantifier hidden in it. "If $n$ is even then $n^2$ is even" means $\forall n \in \mathbb{Z}$, ($n$ even $\Rightarrow$ $n^2$ even). To show it false one exhibits a single integer $n$ that is even while $n^2$ is odd, and no such integer exists, so the statement is true. Reading a worded result as a precisely quantified statement is the first step in both proving and disproving it.