**What is a proof?**

Proofing as a social process, a communication art.

Theoretically, a proof of a mathematical statement is no

different than a logically valid argument starting with

some premises and ending with the statement. However,

in the real world such logically valid arguments can get so

long and involved that they lose their "punch" and require

too much time to verify.

In mathematics, the purpose of a proof is to convince

the reader of the proof that there is a logically valid

argument in the background. Both the writer and the

reader must be convinced that such an argument can be

produced – if needed.

Writing mathematical proofs is therefore an art form (the

art of convincing) and a social process since it is directed

at people (the readers).

A mathematical proof of a statement strongly depends

on who the proof is written for. Proofs for a research

audience are quite different from those found in

textbooks. And even textbook proofs look different

depending on the level of the audience (high school vs.

college vs. graduate school).

To simplify our task in this course, you will write all of

your proofs with a specific audience in mind:

**ME!**

That is, you are writing to convince me that you could

drop down to the logic level and provide all the details, if I

asked you to do so.

Rigor in proofs.

The above remarks should not be construed to mean that

you can get sloppy with your proofs – your audience

requires clarity, precision and, above all, correctness.

Phrases such as "clearly" or "it is easy to see that" are

neither clear nor easy for this audience.

When you say something follows from a definition, I

want to know "the definition of what?"

**General Hints**

The importance of definitions.

It can not be overemphasized how important definitions

are. Without a clear and crisp understanding of a

definition, you will not be able to use it in a proof. You

have to be able to recall a definition precisely when it is

needed – vague familiarity will not work for you.

Working backwards.

There is a big difference between discovering a proof

and presenting a proof. In presenting a proof you must be

convincing, and things need to follow in a logical order .

To discover a proof, you are under no such restrictions

and often the best procedure is to work the problem

backwards.

** Methods of Proof **

We will survey the basic proof methods. In doing so, our

examples to illustrate the techniques should not be very

complicated ... so we will restrict them to fairly simple

statements which do not need a great deal of background

to understand.

The Theory of Numbers provides an excellent source

for such examples ... so most of our examples will deal

with numbers in this section. Remember that our aim is

not to learn more about the theory of numbers, most of

the examples will be statements that you know are true,

rather we are interested in the way that the proofs are

constructed... so, concentrate on the techniques.

**Direct Proof**

**In a direct proof one starts with the premise
(hypothesis) and**
proceed directly to the conclusion with a chain of implications.
Most simple proofs are of this kind. |

Definitions:

An integer n is **odd** iff there exists an integer k so that n = 2k+1.

An integer n is **even** iff there exists an integer k so that n = 2k.

Example of a direct proof:

If n is an odd integer then n^{2} is odd.

Pf: Let n be an odd integer.

There exists an integer k so that n = 2k+1.

Since 2k^{2} + 2k is an integer, n^{2 } is odd.

**Contrapositive Proof**

When proving a conditional, one can prove the
contrapositive
statement instead of the original – this is called a **contrapositive**
proof. |

Example:

If n^{2} is an odd integer, then n is odd.

Pf: Suppose n is an even integer.

There exists an integer k so that n = 2k.

Since 2k^{2} is an integer, n^{2} is even.

**Contradiction Proofs**

This proof method is based on the Law of the Excluded Middle.

Essentially, if you can show that a statement can not be false, then

it must be true. In practice, you assume that the statement you are

trying to prove is false and then show that this leads to a

contradiction (any contradiction).

This method can be applied to any type of statement, not just

conditional statements.

There is no way to predict what the contradiction will be.

The method is wide-spread and is often found in short segments

of larger proofs. For example, ...

**Another Contrapositive Proof**

**Definition:** An integer n **divides** an integer m, written n|m, iff there exists an

integer k so that m = nk.

Example:

If A and B are integers and B ≠ 0. Show that if A

divides B then |A| ≤ |B|.

Pf: Suppose that |A| > |B|. (**Note that A ≠ 0**.)

Then 1 > |B|/|A| > 0.

If A | B then there is an integer k so that B = Ak.

k = B/A and the integer |k| = |B|/|A|.

But, there is no integer 1 > |k| > 0.

So A does not divide B.

**Contradiction Proof**

**Definition:** A real number r is **rational **iff it can be
written as r = a/b with a

and b integers and b ≠ 0. A real number is **irrational **if it is not rational.

Example:

The is irrational.

Pf: BWOC assume that is rational .

There exist integers p and q so that = p/q.

We may assume that the fraction is reduced ,

i.e. no integer divides both p and q.

, so p^{2} is even.

Thus, p is even.

** is irrational**

There exists an integer k so that p = 2k.

So, q^{2} is even and therefore q is even.

Since 2 divides both p and q we have a contradiction

So, is not rational.

**This proof is due to Euclid, but the theorem dates back to**

Pythagoras and the Pythagoreans.

**Proofs of Biconditionals**

**proof of a statement usually uses the
tautology**
That is, we prove an iff statement by seperately proving the "if" part
and the "only if" part. |

Example:

Integer a is odd if and only if a+1 is even.

Pf: (Sufficiency, if a is odd then a+1 is even)

Suppose a is an odd integer.

There exists an integer k so that a = 2k + 1.

a+1 = (2k+1) + 1 = 2k+2 = 2(k+1)

Since k+1 is an integer, a+1 is even.

Example:

Integer a is odd if and only if a+1 is even.

Pf: (Necessity, if a+1 is even then a is odd)

Suppose a+1 is an even integer.

There exists an integer k so that a+1 = 2k.

a = a + 1 – 1 = (2k) - 1 = (2(k-1) + 2) – 1 = 2(k-1) + 1

Since k-1 is an integer, a is odd.

**Uniqueness Proofs**

Proofs of existentially quantified statements () can be

constructive – in which case you produce an x which makes P(x)

true, or non-constructive – when you use contradiction to show

that ~() is false.

**Definition:** To say that there is one and only one x which makes

the predicate P(x) true, we write () **(there exists a unique**

x such that P(x)).

To prove a ()
statement, we first prove () and then
show that if P(x) and P(y) are both true, we must have x = y. |

**Definition:** Let a and b be two positive integers. If n is
a positive integer and a|n

and b|n, then we call n a ** common multiple ** of a and b. If n is a common multiple

of a and b, and if for every other common multiple , m, of a and b we have that

n|m, we say that n is a ** least common multiple** of a and b. In this case, we write

n = LCM(a,b).

Example:

For all positive integers a and b, LCM(a,b) is unique.

Pf: (We shall omit the proof of the existence of the LCM
and just show it's

uniqueness, assuming that it exists.)

Let a and b be positive integers.

Suppose m_{1} and m_{2} are two LCM's for a and b.

Since m_{1} is an LCM and m_{2} is a common multiple, m_{1}|m_{2}, so m_{1} ≤ m_{2}.

Since m_{2} is an LCM and m_{1} is a common multiple, m_{2}|m_{1}, so m_{2}≤ m_{1}.

Therefore, m_{1} = m_{2}.