Methods of Proof

Rachel published in Discrete Mathematics (MTH1114)

2022-04-10 921 words 5 minutes

Contents

In this segment, we will explore the main mathematical proof techniques.

1 Proving conditional statements

Direct proof of $p→q$

Assume $p$ to be true.
Conclude that the intermediary propositions must be true.
Conclude that $q$ must be true.

Example

Proposition: The sum of any even number and any odd number is odd.

Direct Proof

Suppose that $x$ is an even number and $y$ is an odd number.
Then $x$ can be expressed as $2m$ and $y$ can be expressed a $2n+1$ where $m,n$ are integers by definition of even and odd numbers.
$x+y = 2m + 2n + 1 = 2(m + n) + 1$
Let $k$ = $(m + n)$, where $(m + n)$ is an integer by closure of integers under addition
This implies that $x+y$ can be expressed as $2k+1$, which is by definition an odd number.
Therefore, we have proven that the sum of any even number and any odd number is odd.

2 Proving biconditional statements

Direct proof of $p↔q$

Assume p to be true.
Conclude that $p→q$ must be true.
Conclude that $p←q$ must be true.
Conclude that $p↔q$ must be true.

Example

Proposition: $2x-4 > 0$ if and only if $x > 2$

Direct Proof

Suppose that $2x-4 > 0$ is true.
Then $2(x-2) >0$.
By solving the equation, we get $x>2$.
We have shown that if $2x-4 > 0$, then $x>2$. Now, we have to show that if $x>2$, then $2x-4 > 0$.
Suppose $x>2$.
Then $2x-4 > 2(2) - 4 = 0$ by substitution.
Hence $2x-4 >0$.

Now that we have a basic understanding of direct proof, it’s time to explore more sophisticated proof methods.

3 Proof by contradiction

Proof by contradiction of the statement $p$

Assume that $p$ is false or that its negation is true.
Follow the method of Direct Proof to conclude that $q$ must be true.
Conclude that it contradicts the assumption that $p$ is false.
Conclude that $p$ is therefore true.

Example

Prove that $√2$ is irrational.

Proof by contradiction

Suppose $√2$ is rational.
This implies that $√2$ can be expressed as $\frac{a}{b}$, where $a$,$b$ are integers by defition of rational numbers. In other words, $√2$ = $\frac{a}{b}$.
Squaring both sides, we get $2 = \frac{a^2}{b^2}$, which implies that $a^2$ is even since it is a multiple of 2.
It follows that $a$ is even.
Since $a$ is even, then there exists an integer $k$ such that $a = 2k$
By substitution, we get $2b^2 = a^2 = (2k^2)^2 = 4k^2$.
Dividing both sides, we get $b^2 = 2k^2$, which tells us that $b^2$ is even. So, $b$ is also even.
Since $a$ and b are both even, they are both divisible by 2. But by assumption, $a$ and $b$ have no common factors, so this is impossible.
Therefore, it cannot be the case that the proposition is false, so it must be true.
Thus $√2$ is irrational.

4 Proof by contrapositive

Proof by contraposition of $p→q$

Assume the contrapositive of $p→q$ to be true, that is, for $¬q→¬p$ to be true.
Conclude that the contrapositive is true.
Since a proposition is logically equivalent to its contrapositive, therfore it must also be true.

Example

For any integer $a$,if $3a + 1$ is even, then $a$ is odd.

Proof by contrapositive

By contraposition, it is equivalent to prove “if $a$ is even, then $3a+1$ is odd”.
Assume that $a$ is even.
By definition of even numbers, $a = 2k$ for some integer $k$.
Then, $3a+1=3(2k)+1=2(3k)+1=2m+1$, for some integer $m$ such that $m = 3k$.
$2m+1$ is odd by definition of odd numbers.
Therefore, we have shown that for any integer $a$,if $3a + 1$ is even, then $a$ is odd.

5 Proof by cases (proof by exhaustion)

Proof by cases for statement $p$

Let $p$ be a conjunction of cases, i.e $p ≡ r_{1} ∧ r_{2} ∧ r_{3} ∧ … $, where $r$ represents cases.
Proof that $p(r_{i})$ is true for all $r_{i}$, where $i=${$1, 2, 3,…$}
Conclude that $p$ must be true.

Example

Let $x$ be a real number. Prove that $-|x| ≤ x ≤|x|$.

Proof by cases

Case 1: Suppose $x ≥ 0$. Then $|x| = x$.
Since $x ≥ 0$, $-x ≤ x ≤x$ if and only if $-|x| ≤ x ≤|x|$ in this case.
Case 2: Suppose $x < 0$. Then $|x| = -x$.
Since $x < 0$, $x ≤ x ≤-x$ if and only if $-|x| ≤ x ≤|x|$ in this case.
Thus, for any real number, $-|x| ≤ x ≤|x|$.

6 Disproof by counterexample

Now that we have learnt how to prove statements, it is also important that we know how to disprove them.

Recall that for $∀ p(x)$ is false if there exists some element $x$ in the universe where $p(x)$ is false. The same concept is to be applied here. As long as we can find a counterexample for the argument, we have shown that it is false.

Example

Disproof the following proposition: For all real numbers $x$, $x^2>0$.

Disproof by counterexample

Let $x=0$.
Then $x$ is a real number.
But $x^2=0$, which is not greater than 0.
Therefore the proposition is false.

To disproof a universal statement $∀x$ $p(x)$, show that there exists an element $x$ in the universe such that $p(x)$ is false.

To disproof an existential statement $∃x$ $p(x)$, show that for all elements $x$ in the universe, $p(x)$ is false.

Important definitions and theorems

Here are some commonly used definitions for mathematical proofs. As previously highlighted, clear and concise definitions are crucial to a good proof.