1.3 Proof and Reasoning

Tags

Proof

Induction

Deduction

Contradiction

Counterexample

•

Simple deductive proof, numerical and algebraic; how to lay out a left-hand side to right-hand side (LHS to RHS) proof. (1.6)

•

The symbols and notation for equality and identity.

•

Proof by mathematical induction (AHL 1.15)

•

Proof by contradiction

•

Use of a counterexample to show that a statement is not always true.

Notation	Definition
$N$	The set of natural numbers
$Z$	The set of integers
$Q$	The set of rational numbers (quotients)
$R$	The set of real numbers

Terminology	Definition
Proposition	A True of False statement
Not $\neg$	Simply, a negation. For instance, $\neg p$ will be false if $p$ is true.
And $\land$	Both propositions $p$ and $q$ must be true for “ $p$ and $q$ ” statement to be true.
Or $\lor$	Either one of $p$ or $q$ can be true for “ $p$ or $q$ ” statement to be true.
Implication	$p⇒ q$ denotes “If $p$ , then $q$ ”.
Antecedent	The sufficient condition in the implication, i.e. $p$ in $p⇒ q$
Consequent	The necessary condition in the implication, i.e. $p⇒ q$
Logical Equivalence	$p \Leftrightarrow q$ . This is also written as “if and only if”, or “iff”.
Converse	A converse of logical statement; the converse of $p⇒q$ is $q⇒p$ The converse is not necessarily true even if $p⇒q$ is true; i.e. $p⇒ q ⇏ q⇒ p$
Contrapositive	A negated converse of logical statements. The contrapositive of $p⇒q$ is $\neg{q}⇒\neg{p}$ . This has the same truth value as the statement $p⇒q$ .

Methods	Steps
Direct proof	Given $p⇒q$ , start from $p$ to arrive at $q$ . When you are proving $p⇒q$ , never assume $q$ when beginning your proof. You cannot start from the consequent and derive the antecedent. If it seems easy to prove the converse $q⇒p$ , use backward reasoning if possible. Note that you have to prove both implications $p⇒q$ and $q⇒p$ when proving $p\Leftrightarrow q$ . Direct proof questions typically involve demonstrating that a statement holds true for all integers, consecutive integers, or specific subsets such as even or odd numbers. You can start from letting an integer equal to or either $2n$ (even integer) or $2n+1$ (odd integer) for conventions.
Proof by contradiction	1. Given $p$ , assume $\neg p$ is true. • $n$ is rational ⇒ Assume $n$ is irrational. • If $n^2$ is odd then $n$ is odd ⇒ Assume $n^2$ is odd and $n$ is even. 2. Find a contradiction in this logical statement. 3. Therefore, conclude that p is indeed true. Common questions include: • Irrational numbers • Prime numbers • Odds and evens • Maximum and minimum values
Proof of the contrapositive	Given $p⇒q$ , prove $\neg{q}⇒\neg{p}$ instead, and use the property of the contrapositive.
Proof by induction	Give the proposition $P_n$ , defined for $n ≥ a$ for $a∈Z$ : 1. Prove the base case; i.e. $n=a$ 2. Suppose/ assume that $P_k$ is true, and prove $P_k \Rightarrow P_{k+1}$ •Suppose $n=k$ is true for $k≥ a$ for a ℤ •Let $n=k+1$ 3.As $P_a$ is true and $P_{k+1}$ is true whenever $P_k$ is true, $P_n$ must be true for all $n ≥ a$ . Common questions include: •Sums of sequences $\sum_{r=1}^nf(r)=g(n)$ , then use $\sum_{r=1}^{k+1} f(r) = f(k+1) + \sum_{r=1}^{k} f(r)$ for induction •Divisibility of an expression $f(n)=m\cdot q_n$ where $m$ and $q_n$ are integers, then use $a^{k+1}=a \cdot a^k$ for induction •Complex numbers de Moivre’s theorem •Derivatives $f^{(n)}(x)=g(x)$ , then use $f^{(k+1)}(x)=\frac {d}{dx}(f^{(k)}(x))$ for induction