Proofs

A proof is a logically sound argument that establishes the truth a given statement. Even if there is an intuition that some mathematical statement is true, we cannot be sure until we have proven it or read a proof that establishes the truth of that statement.

A good proof is one that:

1. Has a logical structure that a reader could follow.
2. Have thorough explanations that readers can understand.
3. Be able to counter, explicitly or implicitly, all the counterarguments that readers may put forward.

Proof by Contradiction

Proofs can be abstract but there are methods that have been commonly used to prove statements. One such method is proof by condradiction often used to prove something that doesn't exist where we show that the negation of the original statement is false and a true statement cannot lead to a false conclusion allowing us to disprove the negation. If the negation is false, then the original statement is true.

Theorem: $\sqrt 2$ is irrational.

Proof: Assume on the contray, that $\sqrt 2$ were rational.

Then there are natural numbers $p$, $q$, with no common factors, such that

$\sqrt 2 = p / q$

Squaring: $2 = p^2 / q^2$

Rearranging: $2q^2 = p^2$

So $p^2$ is even. Hence $p$ is even. So, $p = 2r$, for some $r$.

Substituting for $p$: $2q^2 = (2r)^2 = 4r^2$.

Cancelling the $2$: $q^2 = 2r^2$.

So $q^2$ is even. So $q$ is even. So $p$, $q$ are both even but this is impossible, since $p$, $q$ has no common factors.

Hence the original assumption that $\sqrt 2$ were rational must be false. Hence $\sqrt 2$ must be irrational. Q.E.D.

note

In the proof above, the statement is a theorem because it has been proven and is significant.

Common statements we will encounter include...

1. Theorems which are statements that have been proven or can be proven.
2. Lemmas which are theorems that is not as significant.
3. Conjectures are statements that has not been proven.

The general structure for a proof by contradiction is:

1. You want to prove statement $\phi$.
2. You start by assuming $\neg\phi$.
3. You reason until you reach a conclusion that is false. This is often done by deducing both $\psi$ and $\neg\psi$ for some $\psi$. For example, "$p$, $q$ have no common factors" and "$p$, $q$ are both even".
4. A true assumption cannot lead to false conclusion.
5. Hence the assumption $\neg\phi$ must be false.
6. In other words, $\phi$ must be true.

Proving Conditionals

When we are proving a conditional in the format $\phi \Rightarrow \psi$, we know that the statement is true if $\phi$ is false. So, we can assume $\phi$ is true. To prove the statement, we assume $\phi$ and deduce $\psi$. For example...

Claim: [ $x$, $y$ are rational ] $\Rightarrow$ [ $x + y$ is rational ]

Proof: Assume $x$, $y$ are rational.

Then there are integers $p$, $q$, $m$, $n$ such that $x = p/m$, and $y = q/n$.

Then $x + y = \frac{p}{m} + \frac{q}{n} = \frac{pn + qm}{mn}$.

Hence $x + y$ is rational.

Quantifiers

Sometimes when we are proving conditionals that involve quantifiers, it is best handled by proving the contrapositive. The contrapositive of $\phi \Rightarrow \psi$ is $\neg\psi \Rightarrow \neg\phi$ and these two statements are equivalent. An example of this kind of proof is...

Claim: $(sin \theta \neq 0) \Rightarrow (\forall n \in \mathbb{N}) (\theta \neq n \pi)$

Proof: The statement is equivalent to $\neg (\forall n \in \mathbb{N})(\theta \neq n \pi) \Rightarrow \neg (\sin \theta \neq 0)$.

In positive form: $(\exists n \in \mathbb{N})(\theta = n \pi) \Rightarrow (\sin \theta = 0)$.

We know this is this! This proves the desired result.

Biconditionals

In order to prove biconditionals in the format $\phi \Leftrightarrow \psi$, we construct two proofs, one of $\phi \Rightarrow \psi$ and the other of $\psi \Rightarrow \phi$. We have already looked at how to prove conditionals so we can apply the same principles to these proofs and the biconditional will be true if both proofs result in true statements. Finally, one thing to note is that occassionally it is easier to prove the two conditionals $\phi \Rightarrow \psi$ and $\neg\phi \Rightarrow \neg\psi$. This works because $\psi \Rightarrow \phi$ is equivalent to $\neg\phi \Rightarrow \neg\psi$.

Proof by Cases

Proof by cases is a brute force method we use for statements that we can split into a finite number of cases and we test every case. An example of a proof using this method is...

Theorem: There are irrationals $r$, $s$ such that $r^s$ is rational.

Proof: We consider two cases,

Case 1: If $\sqrt{2}^{\sqrt{2}}$ is rational, $r = s = \sqrt{2}$.

Case 2: If $\sqrt{2}^{\sqrt{2}}$ is irrational, $r = \sqrt{2}^{\sqrt{2}}$ and $s = \sqrt{2}$.

Then $r^s = (\sqrt{2}^{\sqrt{2}})^{\sqrt{2}} = (\sqrt{2})^{\sqrt{2} \times \sqrt{2}} = (\sqrt{2})^2 = 2$.

Proof by Induction

We often use a powerful method called proof by induction to prove statements of the form $\forall n A(n)$ where n ranges over the natural numbers.

The principle of mathematical induction is that to prove $\forall n A(n)$, we need to establish the following two statements:

1. $A(1)$ which is th initial case / initial step.
2. $\forall n [A(n) \Rightarrow A(n + 1)]$ which is the induction step.

Intuitively, this gives $\forall n A(n)$ as follows: By step 1, $A(1)$. By step 2, $A(1) \Rightarrow A(2)$. So from $A(1)$ we can conclude $A(2)$. By $A(2)$ and the induction step, we can conclude $A(3)$ and etc. Let's look at an example...

Theorem: For any $n$, $1 + 2 + 3 + ... + n = \frac{1}{2} n (n + 1)$.

Proof: By mathematical induction.

For $n = 1$, the identity reduces to $1 = \frac{1}{2} (1)(1 + 1) = \frac{1}{2} (1) (2)$, which is true, since both sides equal $1$.

Assume the identity holds for $n$, i.e. $1 + 2 + ... + n = \frac{1}{2} n (n + 1)$. We want to deduce: $1 + 2 + ... + (n + 1) = \frac{1}{2}(n + 1)((n + 1) + 1)$.

Add $(n + 1)$ to both sides of our identity. We get $1 + 2 + ... + n + n + 1 = \frac{1}{2} n (n + 1) + (n + 1)$

$\frac{1}{2}[n(n+1)+2(n+1)] = \frac{1}{2}[n^2 + n + 2n + 2] = \frac{1}{2}[n^2 + 3n + 2] = \frac{1}{2}[(n + 1)(n + 2)] = \frac{1}{2}(n + 1)[(n + 1) + 1]$.

Which is the identity with $n + 1$ in place of $n$. Hence by the principle of mathematical induction, the identity holds for all $n$.

Mathematical induction is a powerful tool when it comes to proving universal statements. Usually, existence statements are easier to prove as you need to only find one case where the statement holds true. Universal statements on the other hand require us to prove all possible cases and so having tools like mathematical induction is very useful.