Mathematical Proofs: An Introduction to Logical Reasoning

Introduction to Mathematical Thinking. Proofs In mathematics, a proof is a logically sound argument that establishes thetruth of the statement being proved. The word argument here is, of course, not the more common everyday use to mean a disagreement between two people. Agood proof preemptively counters all counterarguments that a reader might putforward. When professional mathematicians read a proof, they generally do so in amanner reminiscent of a lawyer cross-examining a witness. Constantly probing andlooking for flaws. Learning how to prove things forms an important part ofcollege-level mathematics; it takes years to master this skill. What can be achievedin a short period of time is understanding that proving mathematical statements iscrucial to mathematicians. We make such a big deal about proofs because they areused for two purposes: establishing truth and communication. A proof must explainwhy a given statement is true. Proofs written to convince others must be bothlogically sound and communicatively effective. For complicated groups, therequirement that a mathematician can follow his or her own proof weeks later canalso be significant. Some proofs are so deep and complex that only a few experts inthe field can understand them. For example, for many centuries most mathematicians believed, or at least held astrong suspicion that x to the n + y to the n = z to the n has no positive whole numbersolutions for x, y, and z when n is greater than or equal to 3. That was conducted bythe French mathematician Pierre de Fermat in the 17th century; however, it wasn'tfinally proved until 1994 when British mathematician Andrew Wiles constructed a

long and extremely big proof. Over time it became common knowledge amongmathematicians that this was "Fermat's Last Theorem." Since it was the last ofseveral mathematical statements Fermat announced that remained unproven forhundreds of years. Most mathematicians, myself included, lack the detailed domainknowledge needed to follow proofs ourselves but it did convince experts in thefield—analytic number theory. Since its initial formulation by Pierre de Fermat in1637, Fermat's Last Theorem has been proven true for all cases but compositenumbers with one or more prime factors equal to or greater than 5. Most proofs in mathematics can be read and understood by all professionalmathematicians. Though it can take days, weeks, or even months to understandsome proofs sufficiently to be convinced by them. Proving a mathematical theorem ismuch more than gathering evidence in its favor. The Goldbach Conjecture is afamous example of a mathematical statement that has withstood attempts at solutionfor over 250 years. The conjecture originated when the Swiss mathematicianLeonhard Euler suggested that every even number greater than two can beexpressed as the sum of two primes. This property has been verified for manyspecific even numbers and to date, 2012, it has been verified up to and beyond 1.6quintillion (16 followed by 18 zeros). Most mathematicians believe it to be true, but ithas not yet been proved. All it would take to disprove the conjecture would be to findan even number n for which it could be shown that no two primes sum to n. Thisconjecture has no known applications or even any significant consequences withinmathematics; it is famous solely because it is easy to understand and has resistedall attempts at solution for over 250 years. Proofs have no standard format, but allproofs must be logically sound and establish the truth of some statement. A proof'sclarity is also important because the intended reader must be able to follow yourreasoning. Euclid's proof that there are infinitely many primes is an example of a proof thatrelies on an unusual insight. Let's look at it again. Here's what we did: We showedthat if we list the primes in increasing order, then the list can be continued forever. Sowe imagine we've listed the primes p1 = 2, p2 = 3, p3 = 5, etc., all the way up tosome stage Pn. And we're sure that we can always add another prime to this list. Todo this, we look at this number N which we obtain by multiplying together all theprimes in the list so far and then adding 1. Now this number N consists of theproduct of all those numbers pi through pi + 1. So it certainly must be bigger thaneach of those individual numbers pi through pi + 1. If N is prime, one can prove thatthere is a prime number greater than pN. In this case, the list of prime numbers canbe continued by adding N to the end of it. Otherwise, if N is not prime, then thereexists a prime number q less than N that divides into it. However, none of the primesp1, p2, etc., listed above would divide evenly into N because if one were to divide Nby any of these primes (for example), one would get a remainder of 1. So for each q> pn, we have a prime p dividing N. That is, pn = q × p for some prime q > p. If qdoes not equal one of these first n primes, it must be later on in the list. In this case,

because we showed that there is a prime bigger than pn, we can continue the list byadding this new number to it. The fact that this particular q that divides N is notnecessarily the next prime doesn't matter because showing that there is anotherprime at all is enough to prove the theorem's claim. Either way, either if N is prime orif N is not prime, either way there's another prime to add to the list. It follows thatthere are infinitely many primes and the theorem is proved. The proof included two creative ideas. The first was to list the primes in increasingorder as p1, p2, etc., and to show that the list can be continued forever. The secondidea was to construct a number N that guarantees that we can always find anotherprime number. Many mathematicians would eventually come up with this secondidea; it is not an obvious one. This idea is truly genius—one of the greatest ideas inthe history of mathematics. In order to prove that the square root of two is irrational, let us first state the mostbasic facts about numbers used in this proof. Next, we will begin the actual proof bystating an assumption. We will then proceed with our proof using well-establishedtechniques of mathematical logic and algebra. A proof is a logical argument, and toprove something is true, we must prove that it isn't false. If you've never seen theproof that the square root of 2 is irrational before, this first step might seem prettymysterious. Why do we begin by assuming what we're trying to prove is false? Thereason this is a great example is that in about six or seven lines we can make it clearwhile we`re doing something right in the first step. If the square root of 2 wererational, then there would be natural numbers p and q such that p/q equals thesquare root of 2. A rational number is one that can be expressed as the quotient oftwo integers. In the case of a positive number it would be two natural numbers. Wecan always pick those natural numbers, or those integers, to have no common

factors. In other words, when we write a rational number as a quotient, we canalways cancel out any common factors and express it as a quotient where the twonumbers themselves have no common factors. The reason for canceling out common factors is simple: it allows us to rewrite anexpression as a sum of its parts. As we'll see later on, doing so will help us solveequations. Squaring both sides yields 2 = p squared over q squared. Rearranginggives me 2 q squared = p squared; multiply both sides by q squared and thecommon factors disappear, leaving us with 2 q squared on the left side of myequation and a p squared on the right side. We multiply both sides by q squaredagain and take out another factor of q squared. This leaves me with a 2p^2; hence pis even because the square of an even number is even and the square of an oddnumber is odd. Since p is a multiple of 2, then r must be a factor of p; hence p=2r.Substituting this back into the original equation 2q2=p2 gives 4r2=(2r)2, so 4r2=4r2.Cancelling the middle term gives 2q2=4r2 which is an even number since q2 wasshown to be even earlier on, and since p was also shown to be even earlier on, itfollows that both p and q are even numbers—contradicting our assumption that theyhad no common factors other than 2. It is impossible to reach an incorrect conclusion through sound reasoning, thereforethe only explanation for a false conclusion is that an initial assumption was false. Ifwe reach a false conclusion by sound reasoning then we must have started with afalse assumption. Thus, the assumption that the square root of 2 is rational must be false. This impliesthat the square root of 2 is irrational. It is actually not a bad idea to indicate when a

proof ends. Mathematicians have different ways of doing this, such as writing a littlebox at the end or using symbols indicating it is complete. How you express it, howyou lay it out on the page is not that critical, provided that you make it clear whereeach statement ends and another begins. The idea was just to lay it out in a way thatcan be followed. What makes a proof a proof isn't the fact that you call it a proof orend with QED; it's how logically precise each step is and if you can follow its flow.The theorem is a good example to give because it is short, concise, and each stepfollows from the previous one in a logical sequence. The result of this theorem issignificant and changed the course of Greek mathematics. The Greeks had assumedthat quotients of integers could be used to measure all lengths in geometric figures;however, this is not true for square roots of 2 or any number whose square is greaterthan 1. This discovery led mathematicians to consider arithmetic progression as analternative method for measuring lengths in geometric figures. The Pythagorean proposition is an example of a proof that is both elegant andsimple, relying on only simple arithmetic operations. Its significance lies in its abilityto demonstrate that square roots are not always integers, which had been previouslyassumed by other mathematicians. In addition, it proved that quotients of integerswere insufficient to measure all lengths in geometric figures. This discovery had adramatic effect on Greek mathematics and subsequently on the rest of mathematics.