Mathematical proofs are essential to establishing the truthfulness of situations that we take for granted. Advanced topics such as probability, Calculus, linear algebra, and machine learning, all rely on well-defined axioms and established theorems.
A true mathematical statement whose truth can be accepted without proof is known as an axiom.
Probability theory is based on three axioms.
These axioms define probability theory. Their veracity is never challenged. They are assumed to be true.
A true mathematical statement whose truth can be verified is often referred as a theorem. Mathematical proofs rely on axioms and previously proven theorems to develop new theorems. When the truth of a mathematical statement is verified, it becomes a theorem.
A lesser verified statement that helps in developing more complex theorems is known as a lemma.
A statement that can be deduced from a theorem or a lemma or other earlier result is known as a corollary.
Many mathematicians reserve the term theorem for results that are particularly significant and the term lemma or corollary for results that help or result from the important theorem.
So, remember this: A lemma helps prove a theorem and a corollary results from the grand theorem.
In mathematics, when we do not know the truth of a statement, but have reasons to believe that it might be true, then it is known as a conjecture. If a conjecture gets proven, it ceases to be one and becomes an important theorem.
When posed with an open problem, it may not be clear how to proceed. Planning to arrive at a proof by considering various alternatives is known as proof strategy.
A proof strategy occurs in the design phase of proving a result, before you arrive at the result.
When you arrive at a proof or are presented a proof leading to a result, it is usually useful to reflect on the proof to understand it better. Such a discussion is known as proof analysis.
Most theorems are usually stated as implications of the form "if \( P(x) \) then \( Q(x) \) for \( x \in S \)", or, using the logical notation, \( P(x) \Rightarrow Q(x), \forall x \in S \).
In some implications, it turns out that \( Q(x), \forall x \in S \) can be shown to be always true, irrespective of the value of \( P(x) \). Such proofs are known as trivial proofs.
Consider the statement "For \(n \in \natural\), if \( n^3 > 0\), then, 3 is odd".
As an implication, this statement is the implication \( P(n) \Rightarrow Q(n), \text{ for } n \in \natural \), where
$$ P(n): n^3 > 0 $$ $$ Q(n): 3 \text{ is odd.} $$
In this case, the conclusion of the implication, \( Q(n) \), "3 is odd", is always true. It does not matter if the hypothesis \( P(n) \) is true or false. Hence the proof is trivial.
Most theorems are usually stated as implications of the form "if \( P(x) \) then \( Q(x) \) for \( x \in S \)", or, using the logical notation, \( P(x) \Rightarrow Q(x), x \in S \).
In some implications, it turns out that \( P(x) \) is false for all \( x \in S \), regardless of the truth value of \( Q(x) \). Such a proof is known as a vacuous proof.
Consider the statement "For \(n \in \natural\), if 3 is even, then \( n^3 > 0\)".
As an implication, this statement is the implication \( P(n) \Rightarrow Q(n), \text{ for } n \in \natural \), where $$ P(n): 3 \text{ is even.} $$ $$ Q(n): n^3 > 0 $$
In this case the hypothesis, \( P(n) \), "3 is even", is always false, and the conclusion \( n^3 > 0 \) does not need to be proven. Hence, this is a vacuous proof.
Let \( P(x) \) and \( Q(x) \) be open sentences over a domain \( S \). Suppose we wish to prove the quantified statement \( \forall x \in S, P(x) \Rightarrow Q(x) \). The implication \( P(x) \Rightarrow Q(x) \) is true whenever the hypothesis \( P(x) \) is false for some \( x \in S \). So, we do not need to concern about the case when \( P(x) \) is false. We only need to show that if \( P(x) \) is true for some arbitrary \( x \in S \), then \( Q(x) \) is also true for the same \( x \).
A proof strategy that follows along this direction is known as a direct proof.
Prove: If \(n\) is an odd integer, then \(5n + 3\) is an even integer.
Proof: Assume that \( n \) is some odd integer. Since \( n \) is an odd integer, it can be written as \( 2k + 1 \), where \( k \) is some integer. Thus,
\begin{align} 5n + 3 = &~ 5(2k+1) + 3 \\\\ = &~ 10k + 5 + 3 \\\\ = &~ 10k + 8 \\\\ = &~ 2(5k + 4) \end{align}
So, when \( n \) is odd, \( 5n + 3 \) can be written as two times some integer. Hence, \( 5n + 3 \) is even.
Proof Analysis: In this case, \( P(n) \) is "\( n \) is odd" and \( Q(n) \) is "\(5n + 3\) is even" and we have to prove \( P(n) \Rightarrow Q(n) \). We assumed some \( n \) for which \( P(n) \) was true and showed that \( Q(n) \) is also true in that case. Hence, this is a direct proof.
For statements \( P \) and \( Q \), the contrapositive of the implication \( P \Rightarrow Q \) is the implication \( (\neg Q) \Rightarrow (\neg P) \). It is important to note that an implication is logically equivalent to its contrapositive, as this truth table suggests.
| \( P \) | \( Q \) | \( P \Rightarrow Q \) | \( \neg P \) | \( \neg Q \) | \( \neg Q \Rightarrow \neg P \) |
|---|---|---|---|---|---|
| T | T | T | F | F | T |
| T | F | F | F | T | F |
| F | T | T | T | F | T |
| F | F | T | T | T | T |
Since an implication and its contrapositive are logically equivalent, sometimes it might be easier to prove an implication by directly proving its contrapositive. Such a direct proof of the contrapositive of an implication is known as proof by contrapositive.
Prove: If \( 5n + 3 \) is even, then \( n \) is odd.
Contrapositive implication: If \( n \) is not odd, then \( 5n + 3 \) is not even.
Starting with the contrapositive, we assume an arbitrary \( n \) that is not odd. Being an even integer \( n \) can be written as \( 2k \), for some integer \( k \). So,
\begin{align} 5n + 3 = &~ 5(2k) + 3 \\\\ = &~ 10k + 3 \\\\ = &~ 2(5k + 2) + 1 \end{align}
So, if \( n \) is not odd, then \( 5n + 3 \) can be written as \( 2m + 1 \) for some integer \( m \). Thus, \(5n + 3\) is not even when \( n \) is not odd. Hence proved.
Proof analysis: In this case, choosing to use a contrapositive proof strategy was a straightforward choice. As opposed to a direct proof, we were able to work with \( n \) that was even instead of \( 5n + 3 \) as an even, which is more cumbersome to work with.
In developing proofs for mathematical statements concerning elements in a domain, it is sometimes useful to partition the domain into subsets such that a separate proof for each of the subsets is easier to develop. Such subsets are known as cases and the proof strategy is known as proof by cases. For example proofs involving integers may be split over even integers and odd integers, while proofs over real number maybe split over positive and negative values, if that makes the proofs easier.
Prove: If \( n \) in \( \natural \), then \( n^2 + 1 \) and \( n \) have opposite parity. This means, when \( n \) is even then \( n^2 + 1 \) is odd and when \( n \) is odd, then \( n^2 + 1 \) is even.
Proof: We use proof by cases by splitting into two cases, when \( n \) is even and when it is odd.
Case 1: \( n \) is even. Then \( n = 2k \) for some \( k \in \natural \). So,
\begin{align} n^2 + 1 = &~ (2k)^2 + 1 \\\\ = &~ 4k^2 + 1 \\\\ = &~ 2(2k^2) + 1 \end{align}
Thus, when \( n \) is even, \( n^2 + 1 \) is odd.
Case 2: \( n \) is odd. Then \( n = 2k + 1 \) for some \( k \in \natural \). So,
\begin{align} n^2 + 1 = &~ (2k + 1)^2 + 1 \\\\ = &~ 4k^2 + 4k + 1 + 1 \\\\ = &~ 4k^2 + 4k + 2 \\\\ = &~ 2(k^2 + 2k + 1) \end{align}
Thus, when \( n \) is odd, \( n^2 + 1 \) is even.
Sometimes, statements can be disproved just by showing an example for which the implication is false. Such an example is known as a counterexample.
Prove: Show that the following statement is false. For every real number \( x \), \( (x^2 - 1)^2 > 0 \)
Proof: Suppose \( x = 1 \). Then \( (x^2 - 1)^2 = 0 \). Thus, the statement does not hold for at least one \( x \) and hence must be false.
In this example, we chose an easy counterexample that could immediately show that the statement is false for at least that counterexample.
Sometimes it is easier to show that the statement to be proven is not false and hence must be true. For example, if we wish to prove an implication \( R \) is true, then we can instead try proving that the implication cannot be false. Such proofs are known as proof by contradiction. These proof strategies usually begin with statements such as "Suppose that \( R \) is false" or "Assume, to the contrary, that \( R \) is false".
Prove: There is no smallest positive real number
Proof: Suppose there is a smallest positive real number, say \( x \). Since, \( 0 < \frac{x}{2} < x \), we know that \( x \) cannot be the smallest, since \( \frac{x}{2} \) is smaller than \( x \). This is a contradiction. So, there is no smallest positive real number.
Theorems of the form "There exists an \( x \in S \) such that \( R(x) \)" are known as existence theorems and a proof of such a theorem is known as an existence proof. An existence proof is not required to provide a recipe for finding the element that satisfies the theorem, instead, it only guarantees that such an element exists.
For example, there exists a person with least amount of hair in a class, but we may not know which one it is. This is a famous quote by the great mathematician David Hilbert when he presented existence proofs to his students.
Prove: There exist real numbers \( a \) and \( b \) such that \( (a+b)^2 = a^2 + b^2 \).
Proof: It is easy to verify that the equation holds for \( a = 1 \) and \( b = 0 \).
A number \( m \in A \) is known as the least element, minimum, or smallest element of \( A \) if \( x \ge m \) for every \( x \in A \). For example, the set of natural numbers has a least element, but the set of integers does not.
A set \( S \) is said to be well-ordered if every non-empty subset of \( S \) has a least element. For example, the set \( \natural \) of positive integers is well-ordered.
This statement is also known as the well-ordering principle and is an important building block for the principle of mathematical induction.
Here's the statement of the principle of mathematical induction:
For each positive integer \( n \) let \( P(n) \) be a statement. If
then, \( \forall n \in \natural, P(n) \) is true.
A proof using this principle is known as an induction proof or a proof by induction.
The first step, the verification of the truth of \( P(1) \) is known as the base step, basis step or the anchor of the induction. The implication \( P(k) \Rightarrow P(k+1) \) for arbitrary positive integer \( k \) is known as the inductive (or induction) hypothesis. Establishing the truth of this implication is called the inductive step of the induction proof.
Note that more generally, the principle of mathematical induction is also applied to proofs of the form "For every integer \( n \ge m, P(n) \)" by starting with the base step verifying the truth of \( P(m) \).
Prove: \( \forall n \in \natural, \sum_{i=1}^{n} i = \frac{n(n+1)}{2} \)
Proof:
Let \( f(n) = \sum_{i=1}^n \) and \( g(n) = \frac{n(n+1)}{2} \).
We need to show that \( f(n) = g(n), \forall n \in \natural \).
As the base step, observe that
$$ f(1) = \frac{1(1+1)}{2} = 1 $$
The induction hypothesis is then suppose \( f(k) = \frac{k(k+1)}{2} \). Thus,
\begin{align} f(k+1) = &~ f(k) + (k+1) \\\\ = &~ \frac{k(k+1)}{2} + (k+1) \\\\ = &~ \frac{k^2 + k + 2k + 2}{2} \\\\ = &~ \frac{(k+1)(k+2)}{2} \end{align}
Thus, we have shown that if \( f(k) = \frac{k(k+1)}{2} \) for some \( k \in \natural \), then \( f(k+1) = \frac{(k+1)(k+2)}{2} \), thereby completing the induction step. Hence, \( \forall n \in \natural, f(n) = \frac{n(n+1)}{2} \).
Here's the statement of the strong principle of mathematical induction:
For each positive integer \( n \) let \( P(n) \) be a statement. If
then, \( \forall n \in \natural, P(n) \) is true.
The principle of mathematical induction and the strong principle of mathematical induction differ in the induction step. Remember that in the former, the induction step is \( P(k) \Rightarrow P(k+1) \).
Nevertheless, any result that can be proved by the principle of mathematical induction can also be proved by its stronger version. The strong principle is used when \( P(k) \) is insufficient to verify the truth of \( P(k+1) \) and all the statements \( P(1), P(2), \ldots P(k+1) \) must be true to ensure \( P(k+1) \) is true.
Remember that the proof by contradiction is used when it is easier to show that the statement to be proven is not false, and hence must be true.
If such a proof by contradiction can be given using the fact that a number \( m \) is the least number such that \( P(m) \) is false, then such a proof is known as a proof by minimum counterexample and the example \( m \) is known as the minimum counterexample.
Prove: \( \sum_{i=1}^{n} i = \frac{n(n+1)}{2} \)
Proof: Let \( f(n) = \sum_{i=1}^n \) and \( g(n) = \frac{n(n+1)}{2} \). We need to show that \( f(n) = g(n), \forall n \in \natural \).
We approach this using the strategy of proof by minimum counterexample. Suppose there is a smallest \( m \in \natural \) such that \( f(m) \ne g(m) \) and for every natural number \( n < m, f(n) = g(n) \).
Since \( f(1) = g(1) \), it follows that \( m \ge 2 \).
Observe that \( f(m) = f(k) + k + 1 \), where \( k = m - 1 \) is the largest natural number for which \( f(k) = g(k) \), as mentioned earlier. Thus,
$$ f(m) = f(k) + (k+1) = \frac{k(k+1)}{2} + (k+1) = \frac{k^2 + k + 2k + 2}{2} = \frac{(k+1)(k+2)}{2} = \frac{m(m+1)}{2}$$
Thus, \( f(m) = g(m) \). This is a contradiction. There is no smallest positive integer such that \( f(m) \ne g(m) \).
Hence, \( f(n) = g(n), \forall n \in \natural \).
With a sound understanding of developing mathematical proofs, it is time to strengthen your foundations by following relevant topics from our mathematics curriculum.
Help us create more engaging and effective content and keep it free of paywalls and advertisements!
Please share your comments, questions, encouragement, and feedback.