Mathematics/Discrete Math/Proofs
Proofs are a formal means to mathematically show that something is true or false. It can be done in three main ways.
Direct Proof
This is a proof in which we directly declare that p → q. We assume that p is true and go on to show that means q is automatically true. Often times, this is a fairly straightforward means of creating proofs.
Direct Proof Example
Let's prove the theorem "If n is an odd integer, then n^2 is odd."
First, we can define an odd number as "any value 2k + 1 where k is an integer".
Thus, we have the first part of our proof, n = 2k + 1 to define any odd integer.
Next, we want to prove that any n^2 is odd, so we have:
n^2 = (2k+1)^2 is odd.
= 4k^2 + 4k + 1
= 2(2k^2 + 2k) + 1
If you think about it, we can simplify this down to:
2m + 1, for m = (2k^2 + 2k).
This 2m + 1 is comparable to our orginal 2k + 1 definition of an odd number.
So by definition of an odd number, we have proven that our n^2 is also odd.
Proof by Contraposition
Sometimes, a direct proof isn't easy to create. An alternative means is to prove the opposite is true, that is by proving ¬p → ¬q.
Proof by Contraposition Example
Let's prove that "If n is an integer and 3n + 2 is odd, then n is odd."
We start by attempting a direct proof first. So by once again defining an odd number as "any value 2k + 1 where k is an integer", we have:
3n + 2 = 2k + 1 3n + 1 = 2k
At this point, we have two variables and not much we can do with them. So we move on to attempt a proof by contraposition. That is, we start by assuming the original statement is false, which gives us the alternative: "If n is an integer and 3n + 2 is odd, then n is even."
We can define an even number as n=2k for any integer k. So we can substitute to get:
3n + 2 3(2k) + 2 6k + 2 2(3k + 1)
As we can see, no matter what value we enter for k, the end result will be a multiple of 2. This means that, if we assume n is even, then 3n + 2 is actually also even, thus proving our contraposition false.
By extension, this means that the opposite of our assumption must have been true after all, which means we have indirectly proven that "If n is an integer and 3n + 2 is odd, then n is odd."
Note About Example
Note that there may be multiple ways to solve a given proof. In our example, we could have solved it directly if we used substitution instead. We would have:
"If n is an integer and 3n + 2 is odd, then n is odd."
We define an odd number as "any value 2k + 1 where k is an integer."
3n + 2 3(2k + 1) + 2 6k + 3 + 2 6k + 4 + 1 2(3k + 2) + 1
No matter what value we enter for k, we will result in a multiple of 2, plus 1. This leads us back to our original definition of an odd number, thus proving our original assumption.
Proof by Contradiction
A proof by Contradiction is similar to a proof by contraposition, in that it is an indirect proof that may start off similarly. However, proof by contradiction attempts to prove a given p in three steps:
- First, assuming ¬p. Aka, assume that p is false.
- Next, prove that ¬p implies both q and ¬q. That is,
¬p → (q ∧ ¬q). - Since q and ¬q cannot both be true, then ¬p must be false, meaning that p is true.
Proof by Contradiction Example
Let's try to prove that √2 is irrational.
Using proof by contradiction, we first assume the opposite, aka that √2 must be rational.
Thus, by definition of a rational number, then there must be two numbers a, b, such that √2 = a/b. Note that b ≠ 0, and a and b have no factors.
We can then go on to solve:
√2 = a/b 2 = a^2/b^2 2b^2 = a^2
At this point, we can use the definition of an even integer to declare that a^2 must be even. If a is even, then a=2c for some arbitrary integer c. Which gives us:
2b^2 = 4c^2 b^2 = 2c^2
We can now declare that b^2 is even. But wait. We already determined that a/b must be in lowest terms, resulting in a and b having no factors. By definition, if they're both even, then they can be factored, therefore they cannot both be even at once.
Logically, this means our assumption is false, and the original statement (√2 is irrational) must be true.
Induction Proof
Induction Proofs are a form of direct proofs. However, they're common enough and unique enough that they're worth their own section.
Induction proofs can be thought of as a ladder of sorts. To climb the ladder, you start with the bottom rung. Then you go to the second rung, third rung, etc, as you climb upward. Similarly, induction proofs have:
- A Base Case - Find and prove a "base" truth that the proof will use as a starting point. This can be thought of the "bottom rung" of a ladder.
- Induction Step - Once we have the bottom rung, we can move to the next rung. And then the next one after that. Each one is a step forward in logic that builds upon the previous step.
To put it in more mathematical terms, the base case proves P(k) for some starting k value. We then use an induction step to prove the next value P(k + 1) is also valid.
At this point, if we have sound logic and have proven both the basis and first step to be valid, then we know that we can reach any further rungs on the ladder, step by step.
Induction Proof Example
Let's prove P(n) for any n ∈ N when P is the statement 0 + 1 + 2 + ... + n = n(n + 1)/2.
Base Case: First, we can prove the statement holds for the very first value of N at n = 0.
0 = n(n + 1)/2 0 = 0(0 + 1)/2 0 = 0/2 0 = 0 True
Induction Step: Now we need to show that P(k) holds for any P(k + 1).
While technically not necessary (as we want to generalize at this point), we can prove it will work with the next value of n=1:
0 + 1 = n(n + 1)/2 1 = 1(1 + 1)/2 1 = 1(2)/2 1 = 2/2 1 = 1 True
To put it in a more general sense, our basis can be rewritten as:
0 + 1 + 2 + ... + k = k(k + 1)/2
Thus, we can add a k+1 and prove that it still holds by showing:
(0 + 1 + 2 + ... + k) + (k + 1) = (k + 1)((k + 1) + 1)/2
((k(k + 1))/2) + (k + 1) = (k + 1)(k + 2)/2
((k(k + 1))/2) + 2(k + 1)/2 = (k + 1)(k + 2)/2
((k(k + 1)) + 2(k + 1))/2 = (k + 1)(k + 2)/2
(k + 1)(k + 2)/2 = (k + 1)(k + 2)/2
True
By extension, we have proven that this will work for any value k ∈ N.