Overview
In this page, we will provide more examples of proofs written using the proof system that we introduced in Unit 1. The goal of this page is to help you to get familiarised with:
- How the different proof strategies (i.e., direct proof, proof by cases, proof by contradiction, proof by contrapositive) work
- How to justify each step of a proof
Nota Bene: As we go along, we will introduce relevant definitions, lemmas and theorems that will be used in the upcoming proofs.
Proof Strategy #1: Direct Proof
Proving directly is arguably one of the simplest ways of showing that a statement is true. The overarching concept is to start with a certain set of facts and work your way towards the end result: no fancy propositional logic involved, just a sequence of simple step-by-step deductions.
Example 1.1
We will refer to the standard definitions of and :
Example 1.1
Prove that .
How do I know where to start?
Observe that we have an existential statement, i.e., we need to show that such a value of exists that fulfils . Working backwards, we have , so perhaps we could start there.
Proof 1.1
Proof:
- [Basic algebra]
- [Basic algebra]
- [Existential generalisation on lines 1, 2]
- [Unpacking definition of ]
Try It Out!
Prove that .
Solution
Proof:
- . [Basic algebra]
- [Basic algebra]
- [Existential generalisation on lines 1, 2]
- [Unpacking definition of ]
Example 1.2
We will refer to the following definition for rational numbers:
Example 1.2
Prove that .
How do I know where to start?
Now, we have a universal statement, so we need to prove the statement for every possible integer . Doing so manually is clearly impossible, but we can instantiate an arbitrary value and show that the statement is true for this particular . Finally, we generalise it back into a universal statement.
Regarding the statement itself, it is not hard to see why the statement should be true: for every integer , we have , and is clearly a rational number!
Proof 1.2
Proof:
- Let be arbitrarily chosen.
- [Basic algebra]
- . [Basic algebra]
- [Basic algebra]
- [Conjunction on lines 3, 4]
- [Existential generalisation on line 5]
- [Definition of ]
- [Universal generalisation on lines 1, 7]
Rules of deduction/inference used:
On line 5, we performed a conjunction because the definition of required the proposition "" to appear. To make this explicit, we rewrite lines 3 and 4 into a form that looks exactly like it.
On line 6, we used existential generalisation to rewrite line 5 into a form that we recognise as the definition of .
On line 7, we “reverse engineered” the definition of .
On line 8, we used universal generalisation to restore the statement to its original, universal form.
Why do I need to mention that is in ?
This is because the definition of the rational numbers requires that the numerator and the denominator in our fraction have to be integers themselves (""). Therefore, to fit the definition explicitly, we should state that and are also integers.
Try It Out!
Prove that .
Solution
Proof:
- Let be arbitrarily chosen.
- [Definition of ]
- Let be such that . [Universal instantiation on lines 1, 2]
- [Specialisation on line 3]
- Since , . [Basic algebra]
- [Basic algebra]
- [Specialisation on line 3]
- [Conjunction on lines 6, 7]
- [Existential generalisation on line 8]
- [Definition of ]
- [Universal generalisation on lines 1, 10]
Example 1.3
For this example, we introduce the concept of congruence. If , we say that ” is congruent to modulo “.
Example 1.3
Prove that .
How do I know where to start?
Once again, there are three universal quantifiers involved, so we might instantiate each one of them. Now, our goal is to show that if is congruent to modulo , then is also congruent to modulo .
Let’s try out some examples to get a feel of why this statement would be true. Suppose we pick , and . Then, since , and is a multiple of . What about ? Well, that’s also true, because , and is also a multiple of .
At this point, you might observe that the quantities and are really just the same thing, except that one is positive and the other is negative. In that case, the sign does not affect whether they are multiples of , i.e., if is a multiple of , then must necessarily be a multiple of as well! And therein lies the insight of the proof.
As for constructing the proof itself, we notice that there is an implication in the statement. In such situations, we assume the antecedent and try to prove the consequent. In other words, if we want to show that , then we assume and try to prove by the end.
Proof 1.3
Proof:
- Let , and be arbitrarily chosen.
- Assume .
- [Definition of ]
- Let be such that . [Existential instantiation on line 2.1]
- [Basic algebra]
- Since , . [Basic algebra]
- [Existential generalisation on lines 2.3, 2.4]
- [Definition of ]
- [Implication introduction on lines 2, 2.6]
- [Universal generalisation on lines 1, 3]
Rules of deduction/inference used:
- On line 2.1, we wanted to move from the predicate to an explicit quantified statement so that we can perform instantiation. This was done using definition unpacking.
- On line 2.2, we used existential instantiation in order to refer to as a particular integer instead of working with the variable .
- On line 2.5, once we have found suitable values, we used existential generalisation to rewrite lines 2.3 and 2.4 into a form that we recognise as the predicate .
- On line 2.6, we “reverse engineered” the definition unpacking to obtain again.
- On line 3, we used implication introduction so that we can explicitly obtain the statement "" from the original statement to be proved.
- On line 4, we used universal generalisation to restore the statement to its original, universal form.
Try It Out!
Prove that .
Solution
Proof:
- Let be arbitrarily chosen.
- Assume that .
- [Definition of ]
- Let be such that . [Existential instantiation on line 2.1]
- [Basic algebra]
- Since , . [Basic algebra]
- [Existential generalisation on lines 2.3, 2.4]
- [Definition of ]
- [Implication introduction on lines 2, 2.6]
- [Universal generalisation on lines 1, 3]
Proof Strategy #2: Proof by Cases
Sometimes, a direct proof might not work because different instances might have different properties, so choosing arbitrarily might not be a good idea. In such situations, we can break down the statement into several cases, and prove each case separately.
There are two important properties to take note when proving by cases:
- You must consider all possible cases.
- In every single case, the statement must hold true.
Keep these two properties in mind as you go through the following proofs!
Example 2.1
For this example, we introduce the definition of absolute values (also known as modulus) for any real number :
We will also define the following for real numbers and :
Example 2.1
Prove that .
How do I know where to start?
Given the definition of , it is not difficult to see how the proof by cases would work: consider each of the three cases, and show that . The first two cases are trivial, and the last case is easy to show given some basic knowledge of how inequalities work.
Proof 2.1
Proof:
- Let be arbitrarily chosen.
- Since , . [Basic algebra]
- Case 1: .
- [Definition of absolute value]
- [Basic algebra, from line 2.1]
- [Generalisation on lines 2.1.1, 2.1.2]
- [Definition of ]
- Case 2: .
- [Definition of absolute value]
- [Generalisation on line 2.2.1]
- [Definition of ]
- Case 3: .
- [Definition of absolute value]
- [Basic algebra, from line 2.3]
- [Basic algebra, from lines 2.3.1, 2.3.2]
- [Generalisation on line 2.3.3]
- [Definition of ]
- [Proof by cases on lines 2, 2.1.4, 2.2.3, 2.3.5]
- [Universal generalisation on lines 1, 3]
Rules of deduction/inference used:
- On lines 2.1, 2.2 and 2.3, we considered each of the propositions laid out in line 2. Then, in each of those cases, we used generalisation to arrive at the statement .
- On line 3, we “summarised” the cases using the proof by cases rule.
- On line 4, we used universal generalisation to restore the statement to its original, universal form.
Try It Out!
Prove that .
Solution
Proof:
- Let be arbitrarily chosen.
- Since , . [Basic algebra]
- Case 1: .
- [Definition of absolute value]
- [Basic algebra]
- Case 2: .
- [Definition of absolute value]
- [Basic algebra]
- Case 3: .
- [Definition of absolute value]
- [Basic algebra]
- [Proof by cases on lines 2, 2.1, 2.2, 2.3]
- [Universal generalisation on lines 1, 3]
Example 2.2
For this example, we refer to the lemma presented in Q4 of Assignment 1:
Lemma 1
.
Example 2.2
Prove that .
How do I know where to start?
Clearly, our proof must involve finding the value of , then showing that it fits the definition of . Direct proof probably will not be useful, since instantiating just gives us , and we are back to square one. What if we try proving by cases? Which cases do we consider?
For a start, since we need to prove that something is even, we might just begin by trying even values of and seeing where that brings us. Suppose . Then, Well, that wasn’t too surprising, was it? Each term of the sum is clearly even, so their sum must be even as well! Ok, what about odd numbers then? Let’s try : Interesting! Somehow, even though the first two terms were not even, their sum ended up being even; one might say that their odd-ness “cancelled out”. The question becomes: “Will this ‘cancelling out’ occur for all odd numbers?”
As it turns out, the answer is yes, and we can show this algebraically.
Proof 2.2
Proof:
- Let be arbitrarily chosen.
- . [Universal instantiation of Lemma 1]
- Case 1: .
- [Definition of ]
- Let be such that . [Existential instantiation on line 2.1.1]
- [Basic algebra]
- Since , . [Basic algebra]
- [Existential generalisation on lines 2.1.3, 2.1.4]
- [Definition of ]
- Case 2: .
- [Definition of ]
- Let be such that . [Existential instantiation on line 2.2.1]
- [Basic algebra]
- Since , . [Basic algebra]
- [Existential generalisation on lines 2.2.3, 2.2.4]
- [Definition of ]
- [Proof by cases on lines 2, 2.1.6, 2.2.6]
- [Universal generalisation on lines 1, 3]
Try It Out!
Prove that .
Solution
Proof:
- Let be arbitrarily chosen.
- . [Universal instantiation of Lemma 1]
- Case 1: .
- [Definition of ]
- Let be such that . [Existential instantiation on line 2.1.1]
- [Basic algebra]
- Since , . [Basic algebra]
- [Existential generalisation on lines 2.1.3, 2.1.4]
- [Definition of ]
- Case 2: .
- [Definition of ]
- Let be such that . [Existential instantiation on line 2.2.1]
- [Basic algebra]
- Since , . [Basic algebra]
- [Existential generalisation on lines 2.2.3, 2.2.4]
- [Definition of ]
- [Proof by cases on lines 2, 2.1.6, 2.2.6]
- [Universal generalisation on lines 1, 3]
Example 2.3
For this example, we will refer to the following definition of divisibility: To aid our proof, we will also introduce the following lemma:
Lemma 2
.
Example 2.3
Prove that .
How do I know where to start?
As always, when it doesn’t seem obvious how a statement could be true, it is good practice to try out some values to get a sense of how the proof might work.
Suppose we pick . Then, , which is divisible by . How about ? Then, , which is also divisible by . One last one: . Then, , and that is also divisible by . Ok, it seems plausible that the statement is true! Now, let’s dig deeper and try to understand why.
- When , one might observe that the result was divisible by thanks to the last number: , which was the "" factor of our product.
- When , the product is obviously divisible by thanks to the "" factor of our product.
- When , the product was divisible by because of the number , which was due to the "" factor of our product.
Hmm, it seems like no matter which number we pick, there will always be a factor (either , , or ) that is divisible by . How strange!
Proof 2.3
- Let be arbitrarily chosen.
- . [Universal instantiation of Lemma 2]
- Case 1: .
- [Definition of ]
- Let be such that . [Existential instantiation on line 2.1.1]
- [Basic algebra]
- Since , . [Basic algebra]
- [Existential generalisation on lines 2.1.3, 2.1.4]
- [Definition of ]
- Case 2: .
- [Definition of ]
- Let be such that . [Existential instantiation on line 2.2.1]
- [Basic algebra]
- Since , . [Basic algebra]
- [Existential generalisation on lines 2.2.3, 2.2.4]
- [Definition of ]
- Case 3: .
- [Definition of ]
- Let be such that . [Existential instantiation on line 2.3.1]
- [Basic algebra]
- Since , . [Basic algebra]
- [Existential generalisation on lines 2.3.3, 2.3.4]
- [Definition of ]
- [Proof by cases on lines 2, 2.1.6, 2.2.6, 2.3.6]
- [Universal generalisation on lines 1, 3]
Try It Out!
Prove that .
Hint: There are two cases to consider.
Solution
Proof:
- Let be arbitrarily chosen.
- [Universal instantiation of Lemma 1]
- Case 1: .
- [Definition of ]
- Let be such that . [Existential instantiation on line 2.1.1]
- [Basic algebra]
- Since , . [Basic algebra]
- [Existential generalisation on lines 2.1.3, 2.1.4]
- [Definition of ]
- [Generalisation on line 2.1.6]
- Case 2: .
- [Definition of ]
- Let be such that . [Existential instantiation on line 2.2.1]
- [Basic algebra]
- Since , . [Basic algebra]
- [Existential generalisation on lines 2.2.3, 2.2.4]
- [Definition of ]
- [Generalisation on line 2.2.6]
- [Proof by cases on lines 2, 2.1.7, 2.2.7]
- [Universal generalisation on lines 1, 3]
Proof Strategy #3: Proof by Contradiction
Often, proving directly (be it using direct proof or proving by cases) is infeasible or downright impossible. In such cases, we have two options: proving by contradiction, or proving by contrapositive. However, when there isn’t an implication in the statement, it might be difficult to prove by contrapositive; here’s where proofs by contradiction can be useful!
Throughout the examples in this section, pay attention to the following:
- The “conjunction-contradiction-proof by contradiction” trio at the end of each proof
- How the contradictions were derived without circular reasoning
Example 3.1
Example 3.1
Prove that .
How do I know where to start?
Clearly, the statement is true, since must be a multiple of , which is evidently not. If we proceeded to prove the statement directly as per usual, we quickly run into a problem:
Attempt:
- Let be arbitrarily chosen.
There is no property about an arbitrary integer that tells us cannot be , as painfully obvious as it might seem! In times like these, we can try a proof by contradiction instead.
The contradiction arises when we suppose that there is indeed a number where , namely that is not possible since we already assumed that is an integer.
Proof 3.1
Proof:
- Let be arbitrarily chosen.
- Assume, for the sake of contradiction, that .
- [Logically equivalent to line 2]
- [Basic algebra]
- [Basic algebra]
- Since and , . [Basic algebra, from line 1, 2.2]
- [Conjunction on lines 2.3, 2.4]
- . [Contradiction rule on line 2.5]
- [Proof by contradiction rule on lines 2, 2.6]
- [Universal generalisation on lines 1, 3]
Try It Out!
Prove that .
Solution
Proof:
- Let and be arbitrarily chosen.
- Assume, for the sake of contradiction, that .
- . [Logically equivalent to line 2]
- [Basic algebra]
- [Basic algebra]
- Since , , so . [Basic algebra, from lines 1, 2.2]
- [Conjunction on lines 2.3, 2.4]
- . [Contradiction rule on line 2.5]
- [Proof by contradiction rule on lines 2, 2.6]
- [Universal generalisation on lines 1, 3]
Example 3.2
For this example, we denote the set of positive rational numbers as . That is:
Example 3.2
Prove that there is no smallest positive rational number, i.e., prove that:
How do I know where to start?
First, we might try to figure out if the statement is even true. What about ? Then we can just let , for example, and we see that since . What about ? Well, we can let and again find that !
Let’s think about this more abstractly. What does a “smallest positive rational number” that breaks this rule look like? If were indeed the smallest positive rational number, that means that every other positive rational number is somehow equal to or greater than it. However, as we’ve seen, that is clearly impossible since we can just halve to get a smaller rational number!
Therefore, we assume that the original statement is false (i.e., there is indeed a smallest positive rational number), and then somehow conjure the aforementioned contradiction.
Proof 3.2
Proof:
- Let be arbitrarily chosen.
- Assume, for the sake of contradiction, that .
- [Logically equivalent to line 2]
- Consider .
- Since , . [Basic algebra]
- Since , then . [Basic algebra]
- . [Basic algebra, from line 2.2.2]
- [Basic algebra, from line 2.2.3]
- [Existential generalisation on lines 2.2.1, 2.2.4]
- [Logically equivalent to line 2.2.5]
- [Conjunction on lines 2.1, 2.2.6]
- . [Contradiction rule on line 2.3]
- [Proof by contradiction rule on lines 2, 2.4]
- [Universal generalisation on lines 1, 3]
Rules of deduction/inference used:
- On line 2, we assume the negation of our original statement. From here on, there is no new information used, only a sequence of logically deductions to derive the contradiction on line 2.2.4.
- On line 2.1, we produce the first half of our contradiction.
- On line 2.2, we construct a concrete number (in this case, ) so that by line 2.2.6 we are able to produce the second half of our contradiction.
- On line 2.3, we used conjunction to link the two halves (lines 2.1 and 2.2.6).
- On line 2.4, we used the contradiction rule to create the "" statement.
- On line 3, we used the proof by contradiction rule to conclude that our initial assumption (line 2) was faulty, thereby proving our original statement.
Can I do the following?
(Bad, Informal) Proof:
- Assume, for the sake of contradiction, that there exists a smallest positive rational number.
- Let be the smallest positive number. [Existential instantiation on line 1]
- However, since there is no smallest positive rational number, cannot exist.
- . [Contradiction rule on line 3]
- Hence, there is no smallest positive rational number. [Proof by contradiction rule on line 4]
No, you cannot!
This is a classic example of circular reasoning: using the original statement as a justification for a proof of that same statement is not allowed. In essence, the proof does the following: 6. We are trying to prove that a smallest positive rational number, , does not exist. 7. If we claim that exists, then we are wrong, because doesn’t exist.
So how should it be done?
Instead, one should try to refute the statement that results from our (incorrect) assumption, without referring to the original statement, and relying on other facts instead, e.g., basic algebraic facts/axioms, or other intermediate conclusions that resulted due to our initial assumption.
Try It Out!
Prove that there is no largest integer, i.e., prove that:
Solution
- Let be arbitrarily chosen.
- Assume, for the sake of contradiction, that .
- [Logically equivalent to line 2]
- Consider .
- Since , . [Basic algebra]
- [Basic algebra]
- [Existential generalisation on lines 2.2.1, 2.2.2]
- [Logically equivalent to line 2.2.3]
- [Conjunction on lines 2.1, 2.2.4]
- . [Contradiction rule on line 2.3]
- [Proof by contradiction rule on lines 2, 2.4]
- [Universal generalisation on lines 1, 3]
Example 3.3
Definition of irrational numbers
A real number is said to be irrational if and only if .
Example 3.3
Prove that the sum of any irrational number and any rational number is itself irrational, i.e., prove that
Here, the set refers to the set of real irrational numbers.
How do I know where to start?
Since irrational numbers do not have an explicit form of construction (unlike the rational numbers, which can be expressed as for some integers and , with being non-zero), it is difficult to prove this directly. We can no longer instantiate an irrational number based on a quantified statement. Hence, it might be a good idea to try a proof by contradiction instead.
Suppose instead that the sum of some irrational and rational does turn out to be rational; we want to show that leads us to a contradiction. An obvious contradiction we can attempt to show is that ends up being rational, i.e., we want to express in a way such that is some fraction of integers. Clearly, , and the right-hand side is rational thanks to and — hmm, looks promising!
Proof 3.3
Proof:
- Let and be arbitrarily chosen.
- Since , [Definition of ]
- Let and be such that . [Existential instantiation on line 2]
- Assume, for the sake of contradiction, that .
- Since , [Definition of ]
- Let and be such that . [Existential instantiation on line 4.1]
- [Basic algebra]
- [Specialisation on line 3]
- [Specialisation on line 4.2]
- Since and , . [Basic algebra, from lines 4.4, 4.5]
- Since , . [Basic algebra, from lines 3, 4.2]
- [Existential generalisation on lines 4.3, 4.6, 4.7]
- [Definition of ]
- [From line 1]
- [Definition of set difference]
- [Specialisation on line 4.11]
- [Conjunction on lines 4.9, 4.12]
- . [Contradiction rule on line 4.13]
- . [Proof by contradiction rule on lines 4, 4.14]
- [Universal generalisation on lines 1, 5]
Proof Strategy #4: Proof by Contrapositive
Finally, we have proofs by contrapositive. This strategy is useful when there is an implication in the statement we are trying to prove, and proving from directly is difficult. Instead, we suppose and try to show . This gives us , which is logically equivalent to .
Example 4.1
Example 4.1
Prove that .
How do I know where to start?
If we begin by assuming that , we might have to break it up into two cases: or . In the first case, we would need to say that is always non-negative and somehow mention that no real number falls under that case. This is getting messy.
Instead, if we look at the contrapositive, all we need to do is show that if , then , which is simple algebra!
Proof 4.1
Proof:
- Let be arbitrarily chosen.
- Assume that .
- [Basic algebra]
- Case 1: .
- [Basic algebra]
- Case 2: .
- [Basic algebra]
- [Proof by cases on lines 2.1, 2.2.1, 2.2.2]
- [Implication introduction on lines 2, 2.4]
- [Logically equivalent to line 3]
- [Universal generalisation on lines 1, 4]
Rules of deduction/inference used:
- On line 2, we assumed the negation of the consequent (i.e., our ).
- Through a series of algebraic deductions, line 2.4 concludes the negation of the antecedent (i.e., our ).
- On line 3, we used implication introduction to connect our with our , giving us .
- On line 4, we used the equivalence of contrapositive statements to recover our original statement .
Try It Out!
Prove that .
Solution
Proof:
- Let be arbitrarily chosen.
- Assume that .
- [Basic algebra]
- [Definition of ]
- Let be such that . [Existential instantiation on line 2.2]
- [Basic algebra]
- Since , . [Basic algebra]
- [Existential instantiation on lines 2.4, 2.5]
- [Definition of ]
- [Implication introduction on lines 2, 2.7]
- [Logically equivalent to line 3]
- [Universal generalisation on lines 1, 4]
Example 4.2
Example 4.2
Prove that .
How do I know where to start?
Let’s try the direct proof: Suppose that for some integer , and we need to somehow show that either is even or is even. Hmm… looks like we’re stuck, because we have no way of “splitting” the product into anything meaningful!
Let’s try the contrapositive instead: Ok, this looks much more promising! Now, we have both and to work with, and all we need to do is to show that for some integer . This is much simpler to show!
Proof 4.2
Proof:
- Let and be arbitrarily chosen.
- Assume that .
- [Logically equivalent to line 2, using basic algebra]
- [Specialisation on line 2.1]
- [Definition of ]
- Let be such that . [Existential instantiation on line 2.3]
- [Specialisation on line 2.1]
- [Definition of ]
- Let be such that . [Existential instantiation on line 2.6]
- [Basic algebra]
- Since , . [Basic algebra]
- [Existential generalisation on lines 2.8, 2.9]
- [Definition of ]
- [Basic algebra]
- [Implication introduction on lines 2, 2.12]
- [Logically equivalent to line 3, and by basic algebra]
- [Universal generalisation on lines 1, 4]
Why the "basic algebra" on lines 2.1 and 2.12?
For the sake of illustrating the concept of proving by contrapositive, the nitty-gritty of and has been left as an exercise for the reader. However, you should still provide the full proof if these lemmas have not yet been established!
Try It Out!
Prove that .
Solution
Proof:
- Let and be arbitrarily chosen.
- Assume that .
- Case 1: .
- [Definition of ]
- Let be such that . [Existential instantiation on line 2.1.1]
- [Basic algebra]
- Since and , . [Basic algebra]
- [Existential generalisation on lines 2.1.3, 2.1.4]
- [Definition of ]
- Case 2: .
- [Definition of ]
- Let be such that . [Existential instantiation on line 2.2.1]
- [Basic algebra]
- Since and , . [Basic algebra]
- [Existential generalisation on lines 2.2.3, 2.2.4]
- [Definition of ]
- [Proof by cases on lines 2, 2.1.6, 2.2.6]
- [Implication introduction on lines 2, 2.3]
- [Logically equivalent to line 3]
- [Universal generalisation on lines 1, 4]