Previously, I have talked about logic and some of the most important rules of logic. These are quite important and useful in doing mathematics. However, it is necessary to go further, because logic is not specific enough. Mathematics analyzes patterns that involve concepts like shape, number, repetition, and symmetry. Pure logic does not adequately handle all of these ideas, and so we must expand our thinking to help us understand mathematical ideas.
Because of this expansion, and the complexity that emerges as mathematics develops, there are a variety of styles of proofs in mathematics that are useful. There are in fact some pretty large practical and strategic differences in various approaches that a mathematician might take to solve a given problem, and so before I elaborate specific methods, I’d like to discuss some of the broader categories of ideas and proof styles that mathematics uses.
Direct and Indirect Proofs
The first distinction we can draw is between direct proofs and indirect proofs. As the names might suggest, the direct proof is the natural beginning point. In essence, a direct proof is one that accomplishes its goal in exactly the same format that the goal itself is presented. An example may make what is meant here clearer. Take some time to consider the following mathematical proof of the statement that an odd number times an odd number is always odd.
Proof: Recall that we can say a whole number X is odd if there is some other whole number Y for which X = 2Y+1. Suppose that N and M are both odd numbers. By definition of ‘odd number’, that means that for some whole numbers A and B, the relationships N = 2A+1 and M=2B+1 are both true. We can now multiply N and M using the distributive property:
Next, we make the observation that by taking a common factor of 2 in the first three terms above, we obtain N*M = 2(2AB + A + B) + 1. If we go back to our definition of an odd number, notice that the equation we just created satisfies this definition if we let N*M play the part of X, and 2AB + A + B play the part of Y. Since N*M satisfies the definition of oddness, we now know that N*M is odd.
Let’s pause for a moment and consider what we have done. The claim I made was that if you take two odd numbers and multiply them together, the result will also be odd. The discussion that ensued moved in the same direction as the initial claim I made. I started at the beginning of the sentence (with two odd numbers), and I moved towards the end of the sentence (their product is odd). This is the method of a direct proof – it flows in the same direction as the original statement.
Not all proofs are direct. Sometimes, there are roundabout ways to learn things. This occurs in common experience through the process of elimination. To summarize the process of elimination, suppose that you have some problem you have to solve that has 3 possible options. If you manage to demonstrate that two of those options fail, then the remaining option must work, even if you don’t know why. This is very similar to the idea of an indirect proof. To draw contrast between the direct and indirect proof methods, let’s prove the same statement from earlier, that an odd number times an odd number is always odd, using an indirect proof.
Proof: Suppose that we have two whole numbers N and M, and we are told in advance that N*M is not odd. Since, by definition, every whole number is either odd or even, N*M must be even. This means that there must be some whole number X for which the equation N*M = 2*X is true. Now, 2 is known as a prime number, which is a number whose only factors are 1 and itself (more on prime numbers another time). Because 2 is a prime number, we know that 2 has the special property that in any situation that 2 is a divisor of a number N*M, 2 is a divisor of either N or M (or perhaps both). Because of the definition of odd numbers, 2 cannot be a divisor of any odd number, and so the equation N*M = 2*X implies that one of N and M must not be an odd number. We may conclude that our original claim that an odd times an odd must be odd is true.
A trained mathematician would recognize the following paragraph as a proof by contrapositive, which we can discuss in more detail at a later time. The logic being used here is that the statement “If P, then Q” has the same meaning as the sentence “If opposite-of-Q, then opposite-of-P“. You can convince yourself of this if you’d like, or do some research of your own right now. I’ll provide an explanation of my own later. My main point for the time being is that this logic is correct, but on the surface is not the same sort of thing as the original statement.
To see this, we again take a bird’s eye view. The original statement, an odd number times an odd number is always odd, begins by assuming some information about the two separate numbers, which we gave the names N and M. Yet in the proof just given, we make an assumption about the single number N*M, not the separate numbers N and M. And the conclusion of the original statement is about the number N*M, but the conclusion of the proof I just gave says something about the two numbers N and M. So there is something “flipped” about this. Despite these differences, the proof still works and in the end establishes the same truth as the original proof does. The end-to-beginning feeling of this argument is why we use the title of indirect proof. Instead of attacking the question head-on, it addresses a related question that indirectly answers the question we originally asked.
This now completes an initial discussion of the difference between a direct proof and an indirect proof. We can now move on to another important distinction.
Existence, Uniqueness, and Universal Proofs
This distinction is not so much in the type of proof, but in the type of statement. However, I include this distinction in this post because statements of the three different types have proofs that are usually quite different from one another. So, I find this worth discussing now.
The differences between these three different types of statement, and types of proof, are about quantity. An existence proof is one that proves that it is possible for some particular statement to be true. For example, when we say that the equation 2x = 8 has a solution, and we justify this by noticing that x = 4 is a solution since 2*4 = 8, this is an example of an existence proof.
A uniqueness proof proves that a particular problem cannot have multiple different solutions. To use the same example, we can say that the only possible solution to the equation 2x = 8 is x = 4, which we can prove by ‘dividing both sides of the equation by 2’. Notice that we haven’t actually claimed here that x = 4 is a solution per se, all we have stated is that x = 4 is the only possibility. Checking that x = 4 is a solution is the existence proof from earlier.
Finally, there are what might be called universal proofs. An example of this would be the claim that the equation a*b = b*a is always true. As opposed to the two examples before, we are making the claim that it does not matter which numbers a and b might be, because this equation will be true in every case. Unlike in the previous proofs, it would not be enough to check examples, we would instead have to give a broader argument.
When reading and doing math, it is important to remember which of these ideas we have in mind, because it drastically impacts which we can and cannot do in our proofs.
Constructive and Non-Constructive Proofs
Unlike the previous discussion, this distinction does not apply to all proofs. This distinction only relates to existence proofs. An existence proof can be either constructive or non-constructive. A constructive proof is one that gives a specific example that is a solution to the problem at hand. For instance, the proof that 2x = 8 has the solution x = 4 is a constructive proof, because we now know exactly what that solution is. On the other hand, a non-constructive proof is one that proves that there has to be an example, but does not actually give the example. Non-constructive proofs are very often indirect proofs. I will provide a more detailed example of a non-constructive proof later, but I would encourage the curious reader to consider the following:
Suppose that I have three boxes and four apples, and that I place all my apples into the boxes. Then one of the three boxes must have more than one apple. If you take your time and think it through, I think we can convince ourselves that this is definitely correct. But if I then asked you which box has more than one apple in it, we are speechless, because we do not know without looking into the boxes. Notice that in this example, we know that there is a box with more than one apple, even though we have no idea which box that might be. This is the essence of a non-constructive proof.
While abbreviated and perhaps not quite comprehensive, this should provide a strong enough conceptual overview of some of the different strategies one can use when doing mathematics. In the posts that follow, I hope to use this conceptual framework to lay out some specific ways that mathematicians use these concepts to learn about numbers and the world.