Lesson Video: Mathematical Logic and Proof Mathematics

Video Transcript

In this video, we will learn how to prove mathematical statements by deductive reasoning or by exhaustion or disprove them using a counterexample.

One of the main concepts we want to consider in this video is what constitutes a mathematical proof. In concrete terms, a mathematical proof is a logical and systematic argument that shows a statement to be true or false. Having said that, it may be unclear exactly what logical and systematic means.

Let us consider an example statement. If 𝑚 and 𝑛 are even numbers, then 𝑚 plus 𝑛 is even. To show that this is true, it may be tempting to just select random even numbers for 𝑚 and 𝑛, to compute their sums, and then to conclude that since they are all even, the statement probably holds. However, the reality is that we would need to check every pair of even numbers possible in order to conclusively prove this statement is true. Since there are infinitely many even numbers to choose from, there is no way we can do this.

To mathematically prove something, we have to prove it for all cases using a logical argument. How would we do this? Well, let us first start by considering the assumption. If possible, it is helpful to be able to write any assumptions in mathematical terms so that we can use algebraic arguments to get to what we are trying to prove.

One helpful property we can use is that if 𝑚 and 𝑛 are even, then they are each divisible by two. So we can write them as 𝑚 equals two 𝑘 and 𝑛 equals two 𝑗, where 𝑘 and 𝑗 are integers. Then if we add 𝑚 and 𝑛, we are adding two 𝑗 and two 𝑘, which we can factor two out of. Thus, we can see that we have a product of two and an integer, which must be an even number. Therefore, 𝑚 plus 𝑛 must be even.

Now let us analyze what we have done. We started from a known property of even numbers based on our assumption. We then applied a sequence of logical steps based on algebraic properties. And finally, we arrived at the conclusion. As it turns out, this is actually an example of a proof by deduction, also known as a direct proof. A proof by deduction starts from a known fact or definition and then follows a series of logical steps to a conclusion. As a diagram, we can write the process like this. Now let us consider an example of analyzing a proof by deduction.

Liam wants to prove the statement that 𝑥 squared plus two 𝑥 plus three is positive for any real value of 𝑥. He does the following calculation. 𝑥 squared plus two 𝑥 plus three is greater than zero. 𝑥 plus one squared minus one plus three is greater than zero. 𝑥 plus one squared plus two is greater than zero. Since 𝑥 plus one squared is greater than or equal to zero for all real values of 𝑥, the statement is true. Identify a potential problem with Liam’s calculation.

For now, let us focus on the argument presented to us. Recall that a proof by deduction requires us to start from a known fact or definition, proceed through a series of logical steps, and reach a conclusion. If we consider each step of the proof, we can see that they are logically sound. We complete the square, subtract one from three, and state that 𝑥 plus one squared is nonnegative.

However, a proof needs to start from something we already know and arrive at what we are trying to prove. The issue with this argument is that the very first line is not a known fact, but rather it is the statement we are trying to prove, which means that the proof is not valid.

If we were to write an actual proof of this, we would need to start from the known fact that 𝑥 plus one squared is greater than or equal to zero, since the square of any number is greater than or equal to zero. Then we could proceed with the steps in effectively the reverse order. First, we add two to the left-hand side to make it strictly greater than zero. Then we expand the parentheses to get 𝑥 squared plus two 𝑥 plus one plus two is greater than zero. And finally, by combining the constant terms, we finish with the line that we are trying to prove.

If we consider the five possible options for this question, we can see that the correct option is (E). That is, the problem with Liam’s calculation is that he starts with the conclusion that he is trying to prove.

Let us consider another method of proof: proof by exhaustion. In a proof by exhaustion, we break a statement down into a series of individual cases and prove each one separately. We call this method a proof by exhaustion since we are exhausting all the possibilities until everything is proved.

For example, suppose we wanted to show that 𝑥 to the four minus six 𝑥 cubed plus seven was negative for integer values of 𝑥 between two and five. There are numerous ways we could show this, but with a proof by exhaustion, we just have to consider the value of the function for each 𝑥 in the given interval. We can do this by making a table, calculating the left-hand side of the inequality for each value. And we can conclude that since they are all negative, the inequality is indeed true for these values.

An important aspect of this method is that it only works when we can divide a statement into a finite number of cases that we can check. If 𝑥 was not restricted to a small number of values, this would not be feasible.

Let us now consider an example where we need to determine the kind of proof that can be used to prove a statement.

Anthony wants to prove that there are no positive integers 𝑎, 𝑏, or 𝑐 all less than five such that 𝑎 cubed plus 𝑏 cubed equals 𝑐 cubed. Is this possible? If so, what kind of proof should he use? Is the answer (A) no, it is not possible? (B) Yes, it is possible using deductive proof. Or (C) yes, it is possible using proof by exhaustion.

The key to this example is understanding what kind of proof is suitable for the given statement. We can recall that a deductive proof is one that starts from a known fact and follows a series of logical steps to a conclusion. On the other hand, a proof by exhaustion breaks a statement down into cases and proves each one separately. Strictly speaking, it is possible to prove that there are no positive integers such that 𝑎 cubed plus 𝑏 cubed equals 𝑐 cubed. However, doing this using a simple deductive proof is almost certainly not possible. Or at least, we would not be able to fit it all on the screen. And in any case, it is not necessary for proving the given statement.

Instead, we should be aware that we only have to prove the statement for a limited number of cases, rather than all positive integers. Therefore, we should consider a proof by exhaustion, where we consider each combination of 𝑎, 𝑏, and 𝑐 that is four or less.

Let us list these values in a table. To make things easier, we only have to include cases where 𝑎 and 𝑏 are less than 𝑐, since otherwise the left-hand side would end up being bigger. This excludes 𝑎 or 𝑏 from being four. And we can also ignore any cases that are just 𝑎 and 𝑏 swapped around. Overall, this gives us 10 cases. Then we can work out the left- and right-hand sides of the equation. And we can see that in no case is 𝑎 cubed plus 𝑏 cubed equal to 𝑐 cubed. Thus, we have proved by exhaustion that there are no positive integers 𝑎, 𝑏, and 𝑐 all less than five such that 𝑎 cubed plus 𝑏 cubed equals 𝑐 cubed. This corresponds to option (C).

Let us now consider another example of proof by exhaustion.

Olivia wants to prove that all the cube numbers between one and 100 inclusive can be written in the form nine 𝑘 minus one, nine 𝑘 or nine 𝑘 plus one, where 𝑘 is an integer. If she wants to prove this by exhaustion by checking each number directly, how many numbers will she need to check? For the second part, Olivia now wants to prove the statement for all possible cube numbers by considering 𝑛 cubed for different cases of 𝑛. Is this possible? If so, which cases of 𝑛 would she need to check?

Let us start off by just considering the first part. Recall that proving a statement by exhaustion means breaking the statement down into cases and proving each one separately. If we consider the statement that we are trying to prove, we can see that we are interested in the cube numbers between one and 100 inclusive. In particular, if we can show that all of the numbers in this interval can be written in one of the three given forms, then we can prove the statement by exhaustion.

Now we know that the cube numbers can be obtained by cubing the positive integers one, two, three, and so on, which are one, eight, 27, 64, 125, and so on. And we can see that the ones between one and 100 are the first four of these cubes. While not required to answer the question, it is indeed possible to show that each of these numbers can be written in one of the given forms. For example, one is equal to nine 𝑘 plus one, where 𝑘 is zero. Eight is equal to nine times one minus one. And similarly, the other two cubes can also be written in these forms. In any case, the answer is that Olivia will need to check four numbers to prove the statement by exhaustion.

Now we need to consider how to prove the statement for all 𝑛 by considering different cases of 𝑛. It may help us to consider the potential options here. We have (A) no, is not possible. (B) Yes, it is possible by checking 𝑛 equals two 𝑘 minus one and 𝑛 equals two 𝑘. (C) Yes, it is possible by checking 𝑛 equals nine 𝑘 minus one, nine 𝑘, and nine 𝑘 plus one. (D) Yes, it is possible by considering every integer value of 𝑛. Or (E) yes, it is possible by checking 𝑛 equals three 𝑘 minus one, three 𝑘, and three 𝑘 plus one.

Leaving aside the possibility for now that there is no way to solve this by considering cases of 𝑛, let us consider the other options. We can also discount option (D), since we will need to divide up the integers into cases in some way. Otherwise, we will not obtain three different forms. If we consider the remaining cases, we can see that, unlike in the first part, we are not considering individual values for 𝑛, but rather different partitions of the integers.

For example, for option (B), by considering 𝑛 equals two 𝑘 minus one or two 𝑘, we can see that we are implicitly considering odd or even numbers. Similarly, in option (E), we are considering multiples of three and numbers that are one less than or one greater than a multiple of three, which together comprises all the integers. However, in option (C), we can see that this division of the integers will not cover all possible cases, so it will not work.

For the two remaining options, let us do as the question suggests and try considering 𝑛 cubed for the different cases to see whether we can get the different forms. For instance, if 𝑛 equals two 𝑘, then 𝑛 cubed is two 𝑘 all cubed, which is eight 𝑘 cubed. But we need nine rather than eight here, so this is probably not useful. If, on the other hand, we consider 𝑛 equals three 𝑘, then 𝑛 cubed is three 𝑘 all cubed, which is 27𝑘 cubed.

Now since three 𝑘 cubed is an integer, we could let three 𝑘 cubed be 𝑗, say, where 𝑗 is an integer. So we can write this as nine 𝑗. And we can see that this is the same form as nine 𝑘 just using a different letter, since 𝑘 and 𝑗 are both integers. So we have obtained one of the desired forms.

Let us now consider the case where 𝑛 equals three 𝑘 minus one. Then 𝑛 cubed is three 𝑘 minus one all cubed, which we can expand to get 27𝑘 cubed minus 27𝑘 squared plus nine 𝑘 minus one. And we can factor nine 𝑘 out of the first three terms. Now using a similar approach to the first case, we note that 𝑘 times the expression inside the parentheses is an integer, which we can denote by 𝑗. So this is just nine 𝑗 minus one for some integer 𝑗, which corresponds exactly to the form nine 𝑘 minus one.

We also note that the case for three 𝑘 plus one is pretty much the same, except we replace all the negative signs with positive signs. Hence, this case corresponds to the final form nine 𝑘 plus one. Thus, we can conclude that the answer is (E). That is, it is possible to prove that all cube numbers can be written in the three given forms by checking 𝑛 equals three 𝑘 minus one, 𝑛 equals three 𝑘, and 𝑛 equals three 𝑘 plus one.

Having now seen how to prove mathematical statements, it remains to be seen how one could prove something is not correct. In order to prove something is not true, we only need to find a single case that contradicts it. This is called a counterexample. Consider, for example, the statement that all prime numbers are odd. A counterexample to this would be that two is a prime number, yet it is even, which disproves the statement.

Sometimes finding a counterexample is easy, but sometimes it requires some more thought. As a slightly more difficult example, take the statement that for any integer 𝑛, there are more positive integers less than 𝑛 with an odd number of prime factors than an even number. For example, eight has three prime factors, since it is two times two times two. But six only has two, since it is two times three. So if we considered 𝑛 equals 10 for instance, we would find it has five numbers less than it with an odd number of prime factors and only four with an even number of prime factors. Thus, the property holds for 𝑛 equals 10.

As it turns out, this property holds for most of the everyday numbers that we might consider. In fact, the first number for which this is not true is 𝑛 equals 906,150,257. Fortunately, we will not usually have to consider numbers this large when finding counterexamples. Let us consider a full example of disproving statements using this method.

Select the counterexample to each of the given statements. “All integers have an even number of distinct factors.” Is it (A) 12, (B) three, (C) six, (D) nine, or (E) 15? “The expression two 𝑛 squared minus five 𝑛 plus one is positive for all values of 𝑛.” Is it (A) negative one, (B) negative two, (C) four, (D) two, or (E) zero?

Recall that a counterexample is a single example that refutes a statement, thus disproving it. Since we have been given five options in each case, we just have to consider each of them in turn to see whether they contradict the corresponding statement or not.

In the first case, it is stated that all integers have an even number of distinct factors. So let us list the factors of each given option. For example, for 12, we see that it is equal to one times 12, or three times four, or six times two. Therefore, we can write its factors as a set of these numbers. Since there are six distinct factors, which is an even number, 12 is not a counterexample.

Continuing this for the remaining options, we see that three has factors one and three; six has one, two, three, and six; nine has one, three, and nine; and 15 has one, three, five, and 15. We see that only nine has an odd number of distinct factors, which happens because it is a perfect square. And the factor three is repeated. Thus, the answer is (D) nine.

Now let us consider the second statement. To find whether the given values are positive for two 𝑛 squared minus five 𝑛 plus one, we must substitute each of them for 𝑛 in the expression. So for 𝑛 equals negative one, we have two times negative one squared minus five times negative one plus one, which is two plus five plus one. And this is eight, which is positive. So it is not a counterexample.

For 𝑛 equals negative two, after some calculations, we get 19, which is also positive. For 𝑛 equals four, we get 13, which is also positive. But for 𝑛 equals two, we get negative one, which is not positive, so two is a counterexample to the statement. For the sake of completeness, we check 𝑛 equals zero to find it is one; therefore, it is not a counterexample. Thus, the counterexample to the expression two 𝑛 squared minus five 𝑛 plus one being positive for all values of 𝑛 is option (D) two.

Let us finish by considering the key points we have learned in this video.

First of all, a mathematical proof is a logical and systematic argument that shows a statement to be true or false. Proof by deduction, or direct proof, starts from a known fact and then proceeds in a series of logical steps to a conclusion. Proof by exhaustion means breaking a statement down into a series of cases and proving each one individually. And disproof by counterexample means showing a statement is false using a single example that contradicts it.