# Introduction to Proofs

Proofs are the heart of mathematics. If you are a math major, then you must come to terms with proofs--you must be able to read, understand and write them. What is the secret? What magic do you need to know? The short answer is: there is no secret, no mystery, no magic. All that is needed is some common sense and a basic understanding of a few trusted and easy to understand techniques.

## The Structure of a Proof

The basic structure of a proof is easy: it is just a series of statements, each one being either
• An assumption or
• A conclusion, clearly following from an assumption or previously proved result.
And that is all. Occasionally there will be the clarifying remark, but this is just for the reader and has no logical bearing on the structure of the proof.

A well written proof will flow. That is, the reader should feel as though they are being taken on a ride that takes them directly and inevitably to the desired conclusion without any distractions about irrelevant details. Each step should be clear or at least clearly justified. A good proof is easy to follow.

When you are finished with a proof, apply the above simple test to every sentence: is it clearly (a) an assumption or (b) a justified conclusion? If the sentence fails the test, maybe it doesn't belong in the proof.

## An Example: The Irrationality of the Square Root of 2

In order to write proofs, you must be able to read proofs. See if you can follow the proof below. Don't worry about how you would have (or would not have) come up with the idea for the proof. Read the proof with an eye towards the criteria listed above. Is each sentence clearly an assumption or a conclusion? Does the proof flow? Was the theorem in fact proved?

Before we begin the proof, let's recall a few definitions. A real number is called rational if it can be expressed as the ratio of two integers: p/q. The ancient Greeks thought that all numbers were rational. A number that is not rational would be called irrational. You probably believe that p is irrational. (It might surprise you that this is not easy to prove.) When the Greeks proved that the square root of 2 is not a rational number, the very foundations of arithmetic were called into question. This is one of the reasons that Greek geometry subsequently flourished--all numbers could be treated geometrically without reference to rationality.

Another fact that we will need is the Fundamental Theorem of Arithmetic. This exciting sounding theorem is nothing more than the fact that every positive integer has a unique representation as a product of prime numbers. The technique of proof we will use is proof by contradiction . You do not need any specialized knowledge to understand what this means. It is very simple. We will assume that the square root of 2 is a rational number and then arrive at a contradiction. Make sure you understand every line of the proof.

Theorem. The square root of 2 is an irrational number.

Proof. Let's represent the square root of 2 by s. Then, by definition, s satisfies the equation

s2 = 2.

If s were a rational number, then we could write

s = p/q

where p and q are a pair of integers. Infact, by dividing out the common multiple if neccessary, we may even assume p and q have no common multiple (other than 1). If we now substitute this into the first equation we obtain, after a little algebra, the equation

p2 = 2 q2 .

But now, by the Fundamental Theorem of Arithmetic, 2 must appear in the prime factorization of the number p2 (since it appears in the same number 2 q2). Since 2 itself is a prime number, 2 must then appear in the prime factorization of the number p. But then, 22 would appear in the prime factoriztion of p2, and hence in 2 q2. By dividing out a 2, it then appears that 2 is in the prime factorization of q2. Like before (with p2) we can now conclude 2 is a prime factor of q. But now we have p and q sharing a prime factor, namely 2. This violates our assumption above (see if you can find it) that p and q have no common multiple other than 1.

q

Next==>Direct Proofs