Week 2 Summary

COMP109 Lectures 2020-10-26

More Examples of Direct Proof

1. $\forall\ n$ if $n$ is an integer then $n$ is rational.
   • Proof: Suppose that $n$ is a particular but arbitrarily chosen integer.
     • $n=\frac{n}{1}$
       • By definition of a rational number $\frac{n}{1}$ is rational.
2. $\forall\ r$ and $s$, if $r,s$ are rational then $r+s$ is rational.
   • Proof: Suppose that $r$ and $s$ are particular but arbitrarily chosen rational numbers.
     • As $r$ is rational $r=\frac{l}{m}$ where $l,m$ are integers, $m\neq 0$.
     • As $s$ is rational $s=\frac{i}{k}$ where $i,k$ are integers, $k\neq 0$.
       • Then $r+s = \frac{l}{m} + \frac{i}{k} = \frac{lk+mi}{mk}$
         • As $m\neq 0, k\neq 0$ we derive that $mk\neq 0$
         • As $lk+mi,mk$ are integers, $mk\neq 0$ we conclude that $r+s$ is a rational number.

Proof by Cases

For proofs that have multiple cases then you can prove that the statement holds for each case to give a universal proof.

Example 1

For all integers $n,\ n^2 + n$ is even.

Proof

Case 1: $n$ is even

• Then $n=2k$, for some integer $k$
• $(2k)^2+2k=4k^2+2k=2(2k^2+k)$
  • By definition of even, $n^2 + n$ is even.

Case 2: $n$ is odd

• Then $n=2k+1$, for some integer $k$.
• $(2k+1)^2+(2k+1)=4k^2+6k+2=$ $2(2k^2+3k+1)$
  • By definition of even, $n^2 + n$ is even.

As both cases (which are all cases) conclude the same thing then the statement is considered proved.

Example 2

Prove that the product of any two consecutive integers is even.

Rewording

$\forall\ n$ if $n$ is an integer then $n(n+1)$ is even.

Proof

Consider that $n$ is a particular but arbitrarily chosen integer. We proof the statement by a consideration of cases.

Case 1: $n$ is even.

• Then $n=2k$.
  • So $n(n+1)=2k(2k+1)$.

Case 2: $n$ is odd.

• Then $n=2k+1$, for some integer $k$.
  • So $n(n+1)$ $=(2k+1)((2k+1)+1)$ $= (2k+1)(2k+2)$ $= 2(2k+1)(k+1)$.

Indirect proofs

In a direct proof you start with the hypothesis and make deductions until you reach the conclusion.

For an indirect proof you can make use of contradictions to prove statements logically. An example may be in a Sudoku puzzle where you prove which number goes in a square based on the fact that it can’t be any other number.

Proof by Contradiction

If it is not the case that it is not true. It must be the case that it is true.

graph LR
D[Definitions] --> C[Contradiction]
K[Known Facts] --> C
N[Negated Conjecture] --> C

Examples

1. Show that there is not greatest integer.

   Proof: Suppose for a proof by contradiction that the conjecture is not true.
   Then there is an integer larger than any other integer.
   Let $N$ be such an integer. So $N>N+1$ and therefore 0>1, which is a contradiction.
   Therefore, our assumption that the conjecture is not true is false. So there is no greatest integer.

2. No integer can be both even and odd.

   Proof: Suppose for a proof by contradiction that this conjecture is not true.
   Then there exists an integer $N$ which is both even and odd.
   By definition of even, $n=2l$, for some integer $l$. By definition of odd, $n=2k+1$, for some integer $k$.
   $2l=n=2k+1$. So $2l=2k+1$. Then $2l-2k=1$. Then $2(k-l) = 1$.
   Then 1 must be even, which is a contradiction.
   Therefore, we can conclude that no integer can be both even and odd.

Proof by Contraposition

To prove \(\forall \text{ if } P(x) \text{ then } Q(x)\) it suffices to prove
\(\forall \text{ if not } P(x) \text{ then not } Q(x)\)

Example

1. For all integers $m$ if $m^2$ is even then $m$ is even.
   • For all integers $m$ if $m$ is not even then $m^2$ is not even.

   This can be re-written as:

   • For all integers $m$ if $m$ is odd then $m^2$ is odd.

This can then be taken into a direct proof however it may make more sense to prove by contradiction instead of contraposition and it is the preferred method at this time.