Notes by Lex Toumbourou

6.101 Introduction to proofs

• Proof
  • A proof is a valid argument, that is used to prove the truth of a statement.
  • To build a proof, we need to use things previously introduced:
    • variables and predicates.
    • quantifiers.
    • laws of logic.
    • rules of inference.
  • Some terminology used:
    • Theorem
      • formal statement that can be shown to be true.
    • Axiom
      • a statement we assume to be true to serve as a premise for further arguments.
    • Lemma
      • a proven statement used as a step to a larger result rather than as a statement of interest by itself.
• Formalising a theorem
  • Consider statement S: "There exists a real number between any two not equal real numbers"
  • S can be formalised as: $\forall x, y \in \mathbb{R}$ if $x < y$ then $\exists z \in \mathbb{R}$ where $x < z < y$.
  • S is an example of a theorem.
• Direct proof
  • A direct proof is based on showing that a conditional statement: $p \rightarrow q$ is true.
  • We start by assuming that p is true and then use: Axioms, definitions and Theorems, together with rules of inference to show that q must also be true.
  • Example
    • "There exists a real number between any two not equal real numbers"
    • Proof:
      • Let $x, y$ be arbitrary elements in $\mathbb{R}$
      • Let's suppose $x < y$
      • Let $z = (x + y) / 2$
      • $z \in \mathbb{R}$, satisfying $x < z < y$
    • Therefore, using the universal generalised rule, we can conclude that: $\forall x, y \in \mathbb{R}$ if $x < y$ then $\exists z \in \mathbb{R}$ where $x < z < y$.
• Proof by Contrapositive
  • A proof by contrapositive is based on the fact that proving the conditional statement $p \rightarrow q$ is equivalent to providing its contrapositive $\neg q \rightarrow \neg p$
    • We start by assuming that $\neg q$ is true and then use axioms, definitions and theorems, together with rules of inference, to show that $\neg p$ must be true.
  • Example
    • Proof of the theorem:
      • If $n^2$ is even then n is even
      • Direct proof:
        • Let $n \in Z$. If $n^2$ is even then $\exists k \in Z$, $n^2 = 2k$
        • Then $\exists k \in Z$, $n = \pm \sqrt{2k}$
          • From this equation it doesn't seem intuitive to prove that n is even.
      • Proof by contraposition:
        • Let's supposed n is odd.
        • Then $\exists k \in Z$, $n = 2k + 1$
        • Then $\exists k \in Z$, $n^2 = (2k + 1)^2 = 2(2k^2 + 2k) + 1$
        • Then $n^2$ is also odd.
        • We have succeeded in providing the contrapositive: if n is odd then $n^2$ is odd.
• Proof by contradiction
  • A proof by contradiction is based on assuming that the statement we want to prove is false, and then showing that this assumption leads to a false proposition.
  • We start by assuming that $\neg p$ is true and then use: Axioms, definitions and Theorems, together with rules of inference to show that $\neg p$ is also false. We can conclude that it was wrong to assume that p is false, so it must be true.
  • Example
    • Let's give a direct proof of the theorem: "There are infinitely many prime numbers"
    • Proof
      • Let's suppose that there are only finitely many prime numbers
      • Let's list them as $p_1, p_2, p_3, ..., p_n$ where $p_1 = 2, p_2 = 3, p_3 = 5$ and so on.
      • Let's consider the number c = $p_1 \ p_2 \ p_3 ... p_n + 1$, the product of all prime numbers, plus 1.
      • Then, as c is a natural number, it has at least one prime divisor.
      • Then $\exists k \in \{1 ... n\}$ where $p_k | c$ (where $p_k$ divides $c$).
      • Then $\exists k \in \{1 ... n\}, \exists d \in N$ where $dp_k = c = p_1 \ p_2 \ p_3 ... p_n + 1$
      • Then $\exists k \in \{1 ... n\}$, $\exists d \in N$ where $d = p_1 p_2 ... p_{k + 1} ... p_n + \frac{1}{p_k}$
      • Then, $\frac{1}{p_k}$, in the expression above, is an integer, which is a contradiction.

6.103 The principle of mathematical induction

• Mathematical Induction
  • Can be used to prove that a propositional function $P(n)$ is true for all positive integers.
  • The rule of inference: $P(1) \text{ is true}$ $\forall k (P(k) \rightarrow P(k + 1))$ $\therefore \forall n P(n)$
    • Intuition:
      • P is true for 1.
      • Since P is true for 1, it's true for 2.
      • Since P is true for 2, it's true for 3.
      • And so on...
      • Since P is true for n-1, it's true for n ...
    • In other words:
      • The base case shows that the property initially holds true.
      • The induction step shows how each iteration influences the next one.
  • Structure of induction
    • In order to prove that a propositional function P(n) is true for all, we need to verify 2 steps:
      • 1. BASIS STEP: where we show that P(1) is true.
      • 1. INDUCTION STEP: where we show that for $\forall k \in \mathbb{N}$: if $P(k)$ is true called inductive hypothesis, then $P(k + 1)$ is true.
  • Some uses of induction
    • Mathematical induction can be used to prove P(n) is true for all integers greater than a particular integer, where P(n) is a propositional function. Might cover multiple cases like:
      • Proving formulas
      • Proving inequalities
      • Proving divisibility
      • Providing properties of subsets and their cardinality.

6.106 Proof by induction

• Proof By Induction
  • Proving formulas
    • Proving a simple formula formalised as the propositional function, $P(n): 1 + 2 + 3 + ... + n = n (n + 1) / 2$
    • The sum of 1 to n is equal to n multipled by n plus 1 divided by 2, for all n in N.
  • In order to prove that a propositional function $P(n)$ is true for all N, we need to verify 2 step:
    • 1. BASIS STEP: where we show that P(1) is true.
    • 1. INDUCTIVE STEP: where we show that for $\forall k \in \mathbb{N}$: if $P(k)$ is true, called inductive hypothesis, then P(k + 1) is true.
  • 1. BASIS STEP: The basis step, P(1) reduces to 1 = $P(1) = 1 (2) / 2 = 1$
  • 1. INDUCTIVE STEP:
    2. Let $\forall k \in \mathbb{N}$
    3. If the inductive hypothesis P(k) is true:
       • we have $1+2+3+...+k = k(k+1)/2$
       • then, $1+2+3+...+k+(k+1)$
       • $= k(k+1) / 2+(k+1)$
       • $= (k (k + 1) + 2(k + 1)) / 2$
       • $= (k + 1) ((k + 1) + 1) / 2$
       • which verifies, $P(k+1)$
• Proving inequalities
  • We may also use math induction to prove an inequality that holds for all positive integers greater than a particular positive integer.
  • Consider proving the propositional function $P(n): 3^n < n!$ if n is an integer greater than or equal to 7.
    • 1. BASIS STEP: The basis step, $P(7)$ reduces to $3^7 < 7!$ because 2187 < 5040.
    • 1. INDUCTIVE STEP:
      2. Let $k \in \mathbb{N}$ and $k \ge 7$
      3. If inductive hypothesis $P(k)$ is true:
         • then $3^{k+1} = 3 * 3^{k} < (k + 1) * k! = (k + 1)!$ which verifies $P(k + 1)$ is true.
• Proving divisibility
  • We can use math induction to prove divisibility that holds for all positive integers greater than positive integer.
  • Consider proving the prop function $P(n): \forall n \in \mathbb{N} \ 6^{n} + 4$ is divisible by 5.
  • Example
    • 1. BASIS STEP: The basis step, P(0), reduces to $6^{0} + 4$ is divisible by 5, because $6^{0} + 4 = 5$
    • 1. INDUCTION STEP:
      2. Let $k \in \mathbb{N}$
      3. If inductive hypothesis P(k) is true:
         • then, $6^{k} + 4 = 5p$ where $p \in \mathbb{N}$
         • then, $6{k+1} + 4 = 6 * (5p - 4) + 4 = 30p - 20$
         • $= 5(6p - 4)$ which is divisible by 5 and verifies $P(k + 1)$ is true.
• Incorrect Induction
  • Consider the statement of the following incorrect induction: $P(n): \forall n \in \mathbb{N} \sum^{n-1}_{i=0} 2^{i} = 2^{n}$
  • Proof:
    • Let $k \in \mathbb{N}$. Let's suppose the inductive hypothesis $P(k)$ is true, which means: $\sum^{k-1}_{i=0} 2^{i} = 2^{k}$
    • Let's examine $P(k + 1)$
    • $\sum^{k}_{i=0} 2^{i} = \sum^{k-1}_{i=0} 2^{i} + 2^{k} = 2^{k} + 2^{k} = 2^{k + 1}$
    • This means that $P(k + 1)$ is also true and verifies the induction step.
  • Even though we have been able to prove induction step, let's prove statement: $\forall n \in \mathbb{N}$ $\sum^{n-1}_{i=0} 2^{i} = 2^{n}$ is FALSE.
    • For example, $2^{0} + 2^{1} = 3$ which is different from $2^2$
  • Our reasoning seemed correct but we didn't verify the base case and have made false assumptions.
  • In other words, as we saw in propositional logic, false assumptions imply false conclusions.
  • To avoid this situation, we need to make sure both the base case and induction step are verified.

6.108 Strong induction

• Strong Induction
  • Can be formalised with rule of inference:
    • $P(1)$ is true.
    • $\forall k \in \mathbb{N} \ P(1), P(2) ... P(k) \rightarrow P(k+1)$
    • $\therefore \forall n \in \mathbb{N}, P(n)$
  • Sometimes easier to prove statements using strong induction than other methods.
  • Strong induction is sometimes called: "the 2nd principal of mathematical induction" or "complete induction".
  • Example:
    • Prove propositional function, P(n): $\forall n \in \mathbb{N}$ and $n \ge 2, n$ is divisible by prime number.
    • To prove need to verify 2 steps:
      • 1. BASIS STEP: $P(2)$ reduces to 2, which is divisible by prime number because 2 is a prime number and divides itself.
      • 1. INDUCTIVE STEP:
        2. Let $k \in \mathbb{N}$ greater than 2.
        3. If inductive hypothesis, $P(k)$ is true:
           • Let's also assume $P(2) ... P(k+1)$ is true. Then, $\forall m \in \mathbb{N}$ and $2 \le m \le k+1 : \exists p$
           • Then, $\forall m \in \mathbb{N}$ and $2 \le m \le k + 1$: $\exists p$ is a prime number dividing m.
           • We have two cases:
             • k + 2 is a prime number, in which case it is trivially divisible by itself.
             • k + 2 is not a prime number, in which case $\exists m$ dividing $k + 2$
             • as $2 \le m \le k + 1$, $\exists p$ is a prime number dividing m. p also divides k+2
             • Which verifies P(k + 2) is true and proves the strong induction.
• Well-Ordering Property
  • The well-ordering property is an axiom about $\mathbb{N}$ that we assume to be true. The axioms about $\mathbb{N}$ are the following:
    • 1. The number 1 is a positive integer.
    • 1. If $n \in \mathbb{N}$ then $n + 1$, the successor of n, is also a positive integer.
    • 1. Every positive integer other than 1 is the successor of a positive integer.
    • 1. The well-ordering property: every nonempty subset of positive integers has at least one element.
  • The well-ordering property can be used as a tool in building proofs.
  • Example
    • Let's reconsider the earlier statement P(n): $\forall n \in \mathbb{N}$ and $n \ge 2$, n is divisible by a prime number.
    • Proof
      • Let $S$ be the set of positive integers greater than 1 with no prime divisor.
      • Suppose $S$ is nonempty. Let n be its smallest element.
      • n cannot be a prime, since n divides itself and if n were prime, it would be its own prime divisor.
      • So n is composite: it must have a divisor d with 1 < d < n. Then, d must have a prime divisor d with 1 < d < n. Then, d must have a prime divisor (by the minimality of n), let's call it p.
      • Then p / d and d / n, so p/n, which is a contradiction.
      • Therefore S is empty, which verifies P(n).
• Equivalence of the three concepts
  • We can prove the following statements:
    • mathematical induction -> the well-ordering property.
    • the well-ordering property -> strong induction.
    • strong induction -> mathematical induction.
  • That is, the principles of mathematical induction, strong induction and well-ordering are all equivalent.
    • The validaity of each of the 3 proof techniques implies the validity of the other 2 technicques.